Large Scale Data Mining using Genetics-Based Machine Learning

Below you may find the slides of the GECCO 2009 tutorial that Jaume Bacardit and I put together. Hope you enjoy it.
Slides
Abstract
We are living in the peta-byte era.We have larger and larger data to analyze, process and transform into useful answers for the domain experts. Robust data mining tools, able to cope with petascale volumes […]

Related posts:

  1. Observer-Invariant Histopathology using Genetics-Based Machine Learning
  2. Deadline extended for special issue on Metaheuristics for Large Scale Data Mining
  3. [BDCSG2008] Algorithmic Perspectives on Large-Scale Social Network Data (Jon Kleinberg)

Below you may find the slides of the GECCO 2009 tutorial that Jaume Bacardit and I put together. Hope you enjoy it.

Slides

Abstract

We are living in the peta-byte era.We have larger and larger data to analyze, process and transform into useful answers for the domain experts. Robust data mining tools, able to cope with petascale volumes and/or high dimensionality producing human-understandable solutions are key on several domain areas. Genetics-based machine learning (GBML) techniques are perfect candidates for this task, among others, due to the recent advances in representations, learning paradigms, and theoretical modeling. If evolutionary learning techniques aspire to be a relevant player in this context, they need to have the capacity of processing these vast amounts of data and they need to process this data within reasonable time. Moreover, massive computation cycles are getting cheaper and cheaper every day, allowing researchers to have access to unprecedented parallelization degrees. Several topics are interlaced in these two requirements: (1) having the proper learning paradigms and knowledge representations, (2) understanding them and knowing when are they suitable for the problem at hand, (3) using efficiency enhancement techniques, and (4) transforming and visualizing the produced solutions to give back as much insight as possible to the domain experts are few of them.

This tutorial will try to answer this question, following a roadmap that starts with the questions of what large means, and why large is a challenge for GBML methods. Afterwards, we will discuss different facets in which we can overcome this challenge: Efficiency enhancement techniques, representations able to cope with large dimensionality spaces, scalability of learning paradigms. We will also review a topic interlaced with all of them: how can we model the scalability of the components of our GBML systems to better engineer them to get the best performance out of them for large datasets. The roadmap continues with examples of real applications of GBML systems and finishes with an analysis of further directions.

Related posts:

  1. Observer-Invariant Histopathology using Genetics-Based Machine Learning
  2. Deadline extended for special issue on Metaheuristics for Large Scale Data Mining
  3. [BDCSG2008] Algorithmic Perspectives on Large-Scale Social Network Data (Jon Kleinberg)

Data-Intensive Computing for Competent Genetic Algorithms: A Pilot Study using Meandre

Below you may find the slides I used during GECCO 2009 to present the paper titled “Data-Intensive Computing for Competent Genetic Algorithms: A Pilot Study using Meandre”. An early preprint in form of technical report can be found as an IlliGAL TR No. 2009001 or the full paper at the ACM digital library

Related […]

Related posts:

  1. Data-Intensive Computing for Competent Genetic Algorithms: A Pilot Study using Meandre
  2. Meandre: Semantic-Driven Data-Intensive Flows in the Clouds
  3. Scaling Genetic Algorithms using MapReduce

Below you may find the slides I used during GECCO 2009 to present the paper titled “Data-Intensive Computing for Competent Genetic Algorithms: A Pilot Study using Meandre”. An early preprint in form of technical report can be found as an IlliGAL TR No. 2009001 or the full paper at the ACM digital library

Related posts:

  1. Data-Intensive Computing for Competent Genetic Algorithms: A Pilot Study using Meandre
  2. Meandre: Semantic-Driven Data-Intensive Flows in the Clouds
  3. Scaling Genetic Algorithms using MapReduce

Efficient serialization for Java (and beyond)


I am currently working on the distributed execution of flows as part of the Meandre infrastructure—as a part of the SEASR project. One of the pieces to explore is how to push data between machines. No, I am not going to talk about network protocols and the like here, but how you can pass the […]

I am currently working on the distributed execution of flows as part of the Meandre infrastructure—as a part of the SEASR project. One of the pieces to explore is how to push data between machines. No, I am not going to talk about network protocols and the like here, but how you can pass the data around. If you have ever programmed MPI using C/C++ you remember the tedious efforts that requires passing complex data structures around between processes. Serialization is a way to take those complex structures into a form that can be easily stored/transmitted, and then retrieved/received and regenerate the original complex data structure. Some languages/platforms support this functionality (e.g. Java, Python), allowing to easily use the serialized representation for persistency or transmission purposes.

Last Thursday I was talking to Abhishek Verma, and he pointed out Google’s Protol Buffer project—Google’s take data interchange formats. Not a new idea—for instance Corba’s IDL has been around for a long time—but what caught my eye was their claims about: (1) efficiency, and (2) multiple language bindings. I was contemplating using XStream for Meandre distributed flow execution needs, but the XML heavy weight made me quite reluctant to walk down that path.  The Java native serialization is not a bad choice in terms of efficiency, but does not provide friendly mechanics for modifying data formats without rendering already serialized objects useless, neither a transparent mechanism to allow bindings for other languages/platforms. So the Google’s Protol Buffer seemed an option worth trying. So there I went, and I prepare a simple comparison between the tree: (1) Java serialization, (2) Google’s Protol Buffer, and (3) XStream. Yes, you may guess the outcome, but I was more interested on getting my hands dirty, see how Google’s Protol Buffer perform, and how much overhead for the developer it required.

The experiment

Before getting into the description, this experiment does not try to be an exhaustive performance evaluation, just an afternoon diversion. Having said so, the experiment measured the serialization/deserialization time and space used for a simple data structure containing just one array of integers and one array of strings. All the integers were initialized to zero, and the strings to “Dummy text”. To allow measuring the time required to serialize this simple object, the number of integers and strings were increased incrementally. The code below illustrates the implementation of the Java native serialization measures.

package org.meandre.tools.serialization.xstream;
 
public class TargetObject {
 
       public String [] sa;
       public int [] ia;
 
       public TargetObject ( int iStringElements, int iIntegerElements ) {
             sa = new String[iStringElements];
             for ( int i=0 ; i<iStringElements ; i++ )
                  sa[i] = "Dummy text";
             ia = new int[iIntegerElements];
       }
}

The experiment consisted on generating objects like the above containing from 100 to 10,000 elements by increments of 100. Each object was serialized 50 times, measuring the average serialization time and the space required (in bytes) per object generated. Below you may have the sample code I used to measure native java serialization/deserialization times.

package org.meandre.tools.serialization.java;
 
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
 
import org.junit.Test;
 
public class JavaSerializationTest {
 
       @Test
       public void testJavaSerialization ()
       throws IOException {
             final int MAX_SIZE = 10000;
             final int REP = 50;
             final int INC = 100;
 
             System.out.println("Java serialization times");
             for ( int i=INC ; i<=MAX_SIZE ; i+=INC ) {
                  TargetObjectSerializable tos = new TargetObjectSerializable(i,i);
                  long lAccTime = 0;
                  long lSize = 0;
                  long lTmp;
                  ByteArrayOutputStream baos;
                  ObjectOutputStream out;
                  for ( int j=0 ; j<REP ; j++ ) {
                      baos = new ByteArrayOutputStream();
                      out = new ObjectOutputStream(baos);
                      lTmp = System.currentTimeMillis();
                      out.writeObject(tos);
                      lTmp -= System.currentTimeMillis();
                      out.close();
                      lAccTime -= lTmp;
                      lSize = baos.size();
                  }
                  System.out.println(""+i+"\t"+(((double)lAccTime)/REP)+"\t"+lSize);
             }
       }
 
 
       @Test
       public void testJavaDeserialization ()
       throws IOException, ClassNotFoundException {
             final int MAX_SIZE = 10000;
             final int REP = 50;
             final int INC = 100;
 
             System.out.println("Java deserialization times");
             for ( int i=INC ; i<=MAX_SIZE ; i+=INC ) {
                  TargetObjectSerializable tos = new TargetObjectSerializable(i,i);
                  ByteArrayOutputStream baos = new ByteArrayOutputStream();
                  ObjectOutputStream out = new ObjectOutputStream(baos);
                  out.writeObject(tos);
                  out.close();
                  ByteArrayInputStream bais;
                  ObjectInputStream ois;
                  long lAccTime = 0;
                  long lTmp;
                  for ( int j=0 ; j<REP ; j++ ) {
                      bais = new ByteArrayInputStream(baos.toByteArray());
                      ois = new ObjectInputStream(bais);
                      lTmp = System.currentTimeMillis();
                      ois.readObject();
                      lTmp -= System.currentTimeMillis();
                      lAccTime -= lTmp;
                  }
                  System.out.println(""+i+"\t"+(((double)lAccTime)/REP));
             }
       }
}

Equivalent versions of the code shown above were used to measure Google’s Protol Buffer and XStream. If you are interested on seeing the full code you can download it as it is—no guarantees provided. Also, for completion of the experiment code, you can find below the proto file use for testing the Java implementation of Google’s Protol Buffer.

package test;
 
option java_package = "org.meandre.tools.serialization.proto";
option java_outer_classname = "TargetObjectProtoOuter";
 
message TargetObjectProto {
  repeated int32 ia = 1;
  repeated string sa = 2;
}

In order to run the experiment, besides Google’s Protol Buffer and XStream libraries, you will also need JUnit.

The results

The experiments were run on an first generation MacBook Pro using Apple’s Java 1.5 virtual machine with 2Gb of RAM. The figure below illustrated the different memory requirements for each of the the three serialization methods compared. Figures and data processing was done using R.

Data size of the serialized objectSerialized/original data size ratio

Figures show the already intuited bloated size of XML-based XStream serialization, up to 6 time larger than the original data being serialized. On the other hand, the Java native serialization provides a minimal increase on the serialized equivalent. Google’s Protocol Buffer presents a slightly larger requirement than the native Java serialization, but never doubled the original size. Moreover, it does not exhibit the constant initial payload overhead displayed by both XStream and the Java native serialization. The next question was how costly was the serialization process. Figures below show the amount of time required to serialize an object.

Serialization timeSerialization time ratio

The Java native serialization was, as expected the fastest, however Google’s Protocol Buffer took only, on average, four times the more time than the Java native version. However, that is peanuts when compared to the fifty times slower XStream version. Deserialization times of the encoded object presents the same trends as the serialization, as the figures below show.

Deserialization timeDeserialization time ratio

It is also interesting to note that serialization—as the figures below show—is faster than deserialization (as common sense would have suggested). However, it is interesting to note that Google’s Protocol Buffer is the method where these difference is more pronounced.

Serialization/deserialization ratio

The lessons learned

As I said, this is far from being an exhaustive or even representative example, but just one afternoon exploration. However, the results show interesting trends. Yes, XStream could also be tweaked to make the searialized XML leaner, and even would—with the proper tinkering—make possible deserialize the object on a different platform/language, but at an enormous cost—both in size and time. The Java native serialization is by far the fastest and the most size efficient, but is made from and for Java. Also, changes on the serialized classes—imagine wanting to add or remove a field—may render the serialize objects unreadable. Google Protocol Buffers on the other hand delivers the best of both scenarios: (1) the ability to serialize/deserialize objects in a compact and relatively fast manner, and (2) allows the serialization/deserialization to happen between different languages and platforms. For these reasons, it seems to be a very interesting option to keep exploring, if you need both.

Data-Intensive Computing for Competent Genetic Algorithms: A Pilot Study using Meandre

by Llorà, X.
IlliGAL technical report 2009001. You can download the pdf here. More information is also available at the Meandre website as part of the SEASR project.
Abstract: Data-intensive computing has positioned itself as a valuable programming paradigm to efficiently approach problems requiring processing very large volumes of data. This paper presents a pilot study about how to apply the data-intensive computing […]

by Llorà, X.

IlliGAL technical report 2009001. You can download the pdf here. More information is also available at the Meandre website as part of the SEASR project.

Abstract: Data-intensive computing has positioned itself as a valuable programming paradigm to efficiently approach problems requiring processing very large volumes of data. This paper presents a pilot study about how to apply the data-intensive computing paradigm to evolutionary computation algorithms. Two representative cases—selectorecombinative genetic algorithms and estimation of distribution algorithms—are presented, analyzed, discussed. This study shows that equivalent data-intensive computing evolutionary computation algorithms can be easily developed, providing robust and scalable algorithms for the multicore-computing era. Experimental results show how such algorithms scale with the number of available cores without further modification.

Data-Intensive Computing for Competent Genetic Algorithms: A Pilot Study using Meandre

Abstract: Data-intensive computing has positioned itself as a valuable programming paradigm to efficiently approach problems requiring processing very large volumes of data. This paper presents a pilot study about how to apply the data-intensive computing paradigm to evolutionary computation algorithms. Two representative cases—selectorecombinative genetic algorithms and estimation of distribution algorithms—are presented, analyzed, discussed. This study […]

Abstract: Data-intensive computing has positioned itself as a valuable programming paradigm to efficiently approach problems requiring processing very large volumes of data. This paper presents a pilot study about how to apply the data-intensive computing paradigm to evolutionary computation algorithms. Two representative cases—selectorecombinative genetic algorithms and estimation of distribution algorithms—are presented, analyzed, discussed. This study shows that equivalent data-intensive computing evolutionary computation algorithms can be easily developed, providing robust and scalable algorithms for the multicore-computing era. Experimental results show how such algorithms scale with the number of available cores without further modification.