Last week I went to Budapest to present the paper “An Ant-Based Rule for UMDA’s Update Strategy” in the 10th European Conference on Artificial Life (ECAL 2009). ECAL is one of the leading congresses in the area and some of the most relevant work in the Artificial Life research field is presented there in first hand. It is held every two years and this time the capital of Hungary was chosen to host the event. The Academy of Sciences, in Roosevelt tér (square), on the banks of the Danube and with a perfect view on the Castle and the hills of Buda was ECAL’s headquarters for 4 days.
Only 30% of the accepted papers were selected for oral presentation. The remaining was scheduled for poster sessions (although all the accepted papers were published in full-length in two LNCS volumes) that lasted…the whole day! I cannot understand why not all the congresses follow a line similar to PPSN (a poster-only congress, with 90 minutes sessions) when it comes to poster sessions, but ECAL’s strategy is, my opinion, particularly ineffective and exhausting.
ECAL 2009, Budapest, Academy of Sciences
As for our paper, it presents a study on an alternative update strategy for the Univariate Marginal Distribution Algorithm based on the ACO computational paradigm and first presented here. The aim is to control the balance between exploration and exploitation in order to avoid diversity loss, reduce the optimal population size and improve the scalability of the algorithm on hard problems. The results confirmed the hypothesis. This is the abstract:
This paper investigates an update strategy for the Univariate Marginal Distribution Algorithm (UMDA) probabilistic model inspired by the equations of the Ant Colony Optimization (ACO) computational paradigm. By adapting ACO’s transition probability equations to the univariate probabilistic model, it is possible to control the balance between exploration and exploitation by tuning a single parameter. It is expected that a proper balance can improve the scalability of the algorithm on hard problems with bounded difficulties and experiments conducted on such problems with increasing difficulty and size confirmed these assumptions. These are important results because the performance is improved without increasing the complexity of the model, which is known to have a considerable computational effort.
El pasado viernes asistí a tres charlas que impartó el profesor Francisco Herrera del departamento de CCIA de la Universidad de Granada. En la primera de ellas, “Data Mining: From the Top 10 Algorithms to the New Challenges”, el profesor Herrera habló de los 10 mejores algorimos que se aplican a la minería de datos según (ICDM ‘06), así como de los 10 mayores retos de la minería de datos actual. La siguente charla, titulada “Data Complexity” estaba dedicada a los intentos de dar fundamento teórico a la minería de datos. Se habló de los modos de caracterizar los conjuntos de datos con el fin de recomendar que algoritmo funciona mejor con un determinado conjunto de datos. La última de las tres conferencias “How must I do my Experimental Study?” trataba los test estadísticos que deben aplicarse a los experimentos en un trabajo de investigación con el fin de justificar, por ejemplo, la calidad de un nuevo algoritmo. Se trató el uso de métodos estadísticos no-paramétricos que funcionan bien en conjuntos de datos que no siguen una distribución normal, cosa que sucede en la mayoría de los problemas reales. Este tipo de test, en palabras del profesor Herrera, empiezan a ser indispensables cuando se quiere publicar en revistas científicas de primer nivel. A continuación aportaré alguna información adicional sobre estas conferencias.
“Data Mining: From the Top 10 Algorithms to the New Challenges”
Lo candidatos al Top 10 debían cumplir algunos requisitos, como por ejemplo que tuviesen como mínimo 50 citas recientes. De los inicialmente propuestos quedaron sólo 18 algoritmos finalistas. Los resultados del estudio fueron publicados en el artículo “Top 10 algorithm in data mining” y posteriormente en un libro con el mismo título. La siguiente tabla muestra a los finalistas clasificados en categorías.
En la segunda parte de esta primera charla, se presentaron los 10 grandes retos en minería de datos según (ICDM 2005). No he conseguido más información sobre la fuente del estudio. Ampliaré esta información cuando consiga las transparencias utilizadas en la charla. Los principales desafíos se engloban en las siguientes áreas:
Teoría. Definición de una teoría unificada ¿por qué funcionan los algoritmos? ¿cuales son los fundamentos del Data Mining?
Escalabilidad. Algoritmos que manejen gran cantidad de datos a gran velocidad.
Secuencialidad y series temporales. Técnicas para predecir acontecimientos a partir de datos históricos.
Datos complejos. Obtención conocimiento complejo a partir de datos complejos.
Minería de datos en redes sociales.
Minería de datos en bases de datos distribuidas.
Minería de datos para problemas biológicos y ambientales
Procesos de la minería de datos. Automatización, caracterización de los problemas, etc.
Seguridad, privacidad e integridad.
Minería de datos sobre datos no estáticos y datos cuya observación sea costosa.
Buscando más información sobre estos desafíos futuros he encontrado un artículo reciente sobre este tema titulado “Future tends in data mining“.
“Data Complexity”
Pretende dar respuesta a la pregunta “dado un problema de clasificación, ¿qué clasificador es mejor para el?”. El libro de referencia es Data Complexity in Pattern Recognition. Para poder responder a esa pregunta se necesitan medidas de complejidad de los conjuntos de datos. Podemos encontrar diferentes medida de la complejidad de los datos en el trabajo de Tin Kam Ho, titulado “Measures of Geometrical Complexity in Classification Problems“. Os dejo un enlace a las transparencias de la charla.
“How must I do my Experimental Study?”
Cuando nuestro trabajo de investigación consiste en el desarrollo de un nuevo algoritmo, es muy importante compararlo con con algoritmos de calidad. Muchos artículos son rechazados en revistas de prestigio, cuando se compara un nuevo algoritmo con versiones antiguas de nuestros competidores y no se incluyen comparativas con las últimas versiones más eficientes y precisas. Justificar convenientemente la bondad del nuevo algoritmo utilizando conjuntos de datos conocidos y métodos estadísticos es igualmente importante. En la dirección del grupo de investigación “Soft Computing and Intelligent Information Systems” que dirige el profesor Herrera, podemos encontrar información sobre estos métodos estadísticos y un software desarrollado por el profesor Salvador García, que genera los gráficos para incluir en documentos Latex utilizando a la entrada un fichero en formato CVS.
Data Mining: From the Top 10 Algorithms to the New Challenges
Last Friday we discussed the paper “The generic genetic algorithm incorporates with rough-set theory – An application of the web services composition” of Liang and Huang. This is the standard mixture paper: a kind of algorithm + another soft computing technique + an application of the real world = a complete paper. I am not kidding, I think that combining several techniques, and more important, using them in real applications, should be a basis of research.
Rought set theory provides a way to create a set of decission rules that can be selected in every problem with functional requirements. For example in the extensive area of web services composition. We can provide this information to a genetic algorithm to compose services avoiding constrained solutions and initial population using that decission rules. The authors also use non-functional requirements, such QoS, cost or avilability in the fitness function. They conclude that the usage of rough set in a GA could increase the convergence (but it is necessary to keep some unfeasible solutions during the process, just in case).
It is a easy-to-read paper, so probably you would like to read it instead my summary ;) Moreover, they present some ideas in the web service composition area.
In this paper we analyse the robustness of a Peer-to-Peer (P2P) Evolutionary Algorithm (EA) subject to the following dynamics: peers leave the system independently from each other causing a collective effect known as churn. The algorithm has been designed to tackle large instances of computationally expensive problems and, in this paper, we will assess its behavior under churn. To that end, we have performed a scalability analysis in five different scenarios using the Massively Multimodal Deceptive Problem as a
benchmark. In all cases, the P2P EA reaches the success criterion without a penalty on the response time. The key to the algorithm robustness is to ensure enough peers at the beginning of the experiment. Some of them leave but those that remain are enough to guarantee a reliable convergence.
I returned from Brussels a couple of days ago, where I went to present KANTS: Artificial Ant System for Classification (the model was already described here) at the 6th International Conference on Ant Colony Optimization and Swarm Intelligence. ANTS 2008 is similar to PPSN, with most of the papers being presented at poster sessions (only a few are chosen for oral presentation). This procedure works well when the poster sessions are not just a minor event of the congress, thrown to a distant room in the hotel/university where nobody even bothers to go, or scheduled to the end of a long day. ANTS sessions were well organized and every poster had an assigned space. My presentation was scheduled to the last day of the congress, when most of people had already packed for their trip back home, but nonetheless the session went well, with lots of people wandering around the room, clearly interested in the works. KANTS got the attention of some audience, and I think they were quite impressed by the simplicity (and efficiency) of the idea. The inevitable question arouse (are you planning to test KANTS on a real-world problem?) and this time we can answer yes, we are not only planning to do it, but we are already working on it (later we will report on those experiments). In the same section, another swarm-clustering was presented. I saw the poster, and the results on clustering appear to be quite good (but the system does not perform classification). I haven’t read the paper (as a matter of fact, it is published as an extended abstract), but I was able to realize that the algorithm is little bit complex, simulating the behavior of three different species: ants, birds and spiders.
A week before I was in Barcelona, at the 8th International Conference on Hybrid Intelligent Systems (HIS 2008), presenting the paper Tracking Extrema in Dynamic Fitness Functions with Dissortative Mating Genetic Algorithms. It is quite a different work, and more related to my thesis’ subject, bio-inspired computation on dynamic environments. It describes the experiments performed with an adaptive dissortative mating GA (ADMGA) on Dynamic Optimization Problems. Dissortative mating appears frequently in nature and refers to the occurrence of mating between dissimilar individuals more often than expected by chance. It maintains genetic diversity at a higher level, thus increasing the exploration stage of the algorithm. Dynamic fitness functions are more sensible to genetic diversity than static ones, and so dissortative mating is a good candidate to deal with that kind of problems. The paper describes mainly the experiments performed with trap functions and show that ADMGA may improve GAs on some dynamic optimization scenarios. Robustness is also addressed and results show that ADMGA maintains a more stable performance over the wide range of dynamic scenarios. The congress HIS is mainly dedicated to hybrid models and real-world applications, so ADMGA was somewhat “lost” among other works. But good news came after the congress, and this line of research will probably make its way through other media.
P.S. In Brussels, avoid Hotel Continental, near Midi Station, unless you need inspiration for another insects’ heuristics.
Next week, Carlos Fernandes will present in the ANTS 2008 conference our paper KANTS: Artificial Ant System for Classification (hope the typo is not in the proceedings, but I’m afraid it will be). The algorithm was already presented by Antonio in ALIFE XI, with the paper KohonAnts: a self-organizing ant algorithm for clustering and pattern classification (which is also available from arxiv). Antonio was questioned about what was good about this algorithm, and I guess this is as good a place as any other to tell about it.
The basic idea of Kohonants is to use stigmergy for clustering and classification. Usual ant clustering algorithm place data as objects in the grid ants move around, and then, via some natural inspiration and a great deal of heuristics, they manage to cluster them according to proximity.
Kohonants, on the other hand, makes each data item an ant (or several, if needed). Pheromones are also vectorial in nature, in the same dimension as data, and what ants do when they move about is first take into account what’s the pheromone levels they have around in their neighborhood, and second modify it making them closer to the vector they represent.
That is why they are called Kohonen’s Ants: Kohonen’s algorithm behaves in the same way. Takes a training data vector, compares it to all the vectors in a two-dimensional array, and whoever wins is made closer to the data vector. Ants in Kohonants take the place of data vector in Kohonen’s algorithm, and the two-dimensional vector array that is trained is substituted by the two-dimensional (vectorial) pheromone field in Kohonants.
Results so far have been quite good, but we’ll continue with it to see what are their limits, and how well it fares against other ant and non-ant clustering algorithms. Meanwhile, as we mentioned in our previous post, you can download full code from the GeNeura code repository
Algorithms for decision support in the battlefield have to take into account separately all factors with an impact of success: speed, visibility, and consumption of material and human resources. It is usual to combine several objectives, since military commanders give more importance to some factors than others, but it is interesting to also explore and optimize all objectives at the same time, to have a wider range of possible solutions to choose from, and explore more efficiently the space of all possible paths. In this paper we introduce hCHAC-4, the four-objective version of the hCHAC bi-objective ant colony optimization algorithm, and compare results obtained with them and also with some other approaches (extreme and mono-objective ones). It is concluded that this new version of the algorithm is more robust, and covers more efficiently the Pareto front of all possible solutions, so it can be consider as a better tool for military decision support.
