December 25, 2015

"Rental Harmony: Sperner's Lemma in Fair Division"

I recently stumbled on the paper "Rental Harmony: Sperner's Lemma in Fair Division" by Francis Su. It describes an application of a pure combinatorial lemma by Sperner from 1928 to the problem of dividing rent among a number of housemates in a fair manner. Last year, the New York Times published an article together with a rent calculator that is based on this paper.

I am not a mathematician, but the approach is to me very elegant and intuitive and -- at the same time -- solves a practical problem in a way that you wouldn't expect. I think it is not the contribution of this paper but the inductive proof of Sperner's Lemma itself using a "trap-door" argument is very neat. The application to fair division, and particularly to the rent division problem is just beautiful.

It does not make any sense to repeat the details here. The paper itself together with the rent calculator on Su' homepage or the one at the New York Times website are a great source for understanding the problem and its solution.

November 7, 2015

Aggregations in Henshin

The language concepts of Henshin are based on graph transformations. As such, aggregations have not been in the scope of Henshin so far. Aggregations are well known from relational database systems and are a powerful tool for counting entities, calculating minima / maxima or average values etc.

How do aggregations and graph transformations fit together? Well, in Henshin we know the concept of nested multi-rules. In graph transformation terminology this is often referred to as amalgamation. In essence, a transformation rule is extended with parts that are applied with a for-all semantics. These for-all parts are referred to as the multi-rule, whereas the core part is referred to as the kernel rule. In the graphical editor of Henshin, the multi-rule parts are indicated using *-actions.

Now, the trick for supporting amalgamations in Henshin is to allow to use the values of parameters of multi-rules in the kernel rule. What happens is that for one match of the kernel rule, the multi-rule is matched with for-all semantics, and that its parameter values are exposed to the kernel rule as a collection. This enables the use of aggregations functions in the kernel rule, which combine the values of parameters of the multi-rules.

Consider the two example rules below. Both match one :Family object (kernel rule) and all :Person objects in that family (multi-rule). Now, the set of persons can be used as basis for aggregations. In our two example rules, we use as aggregation functions COUNT and AVG to resp. count the number of family members and calculate the average age of the family members.

Note that the expressions Aggregations.COUNT(x) and Aggregations.AVG(a) are not some special syntax for aggregations. They are just calls to ordinary Java methods. The special thing about these methods is that they take a collection of values as parameters (not single values). The Henshin interpreter just calls the (possibly user-defined) functions to calculate the aggregated values. For the interpreter to know which class to use, it must be defined as part of the Java imports of the rule, as shown in the screenshot below. Additionally, you need to ensure that this class is in the Java classpath when executing the Henshin transformation.

The aggregation support is currently available in the development branch of Henshin. You can find the above rules with accompanying Java code in the examples plugins.

May 1, 2015

Towards Modeling of Distributed Graph Algorithms

The most prominent approach for distributed processing of very large graphs today is probably the Bulk Synchronous Parallel (BSP) model. BSP is a bridging model for implementing graph algorithms in such a way that they can be massively parallelized and distributed. One application can be found in the Henshin graph transformation tool, where graph transformation systems can be modeled, and code generated for the BSP framework Apache Giraph.

Although the BSP model is widely accepted and used today, there is no standard implementation framework for BSP algorithms. Frameworks that do provide BSP include Google's Pregel, Apache Giraph and GraphX in Apache Spark. For application developers it is not easy to find out which platform is the most suited one for her problem. An implementation of a graph algorithm in, say, Apache Giraph cannot be reused in other frameworks, even though the underlying concepts of BSP are the same. This is unfortunate, particularly because the overhead of developing, deploying and testing these algorithms is rather high due to the complexity of the distributed frameworks.

This problem can be solved by introducing a modeling layer for BSP algorithms. Instead of directly implementing graph algorithms in Pregel, Giraph or GraphX, the idea is to use a modeling language that supports the concepts of BSP. One possible approach is to use UML 2 state machines for the modeling. The figure below shows a state machine for a BSP-model of the shortest path algorithm.

Using such a model, one could generate code for different platforms, e.g. Pregel, Giraph or GraphX. The code generators need to be implemented only once and are straight-forward to build since the BSP concepts are more or less directly used. Using different code generators, algorithm engineers can automatically derive implementations for different platforms and benchmark them against each other without implementing a single line of code.

In Henshin, the code generation for Apache Giraph is quite complex because the concepts of graph transformations are rather different than BSP. One opportunity to simplify it would be to use BSP models as intermediate target language. Specifically, model transformations can be employed to translate a Henshin model into a BSP model. From that point on, platform-specific code generators could be used to generate the final implementation.

Using a modeling approach would enable the reuse of the many many graph algorithms already implemented in the existing BSP-frameworks. Maybe UML state machines are not the best approach for the modeling -- for instance, one could also come up with a (textual) DSL for BSP. The important point is that an abstraction from the actual implementation platforms is made.  

April 16, 2015

Artificial Intelligence by Peer-Reviewing Agents

The dream of artificial general intelligence (AGI) is to build algorithms and machines that are capable of performing intellectual tasks that a human can. Futurists like Ray Kurzweil even postulate the development of machines that will exceed the intelligence of humans by far.

Methods used in AI research range from symbolic manipulation methods developed in the 1950's over neural networks and diverse machine learning algorithms, and many more. In the past few years, detailed simulations of brain components gained a lot of attention. Also deep learning and the idea of distributed artificial intelligence in cyber-physical systems and the Internet of Things are popular these days.

A Small Gedankenexperiment

First, let us assume that one day we in fact build a machine X with artificial general intelligence, i.e., which has the same intellectual power as humans. Second, assume we build a machine X++ that exceeds the human intellectual capabilities by far.

In the classical terminology of machine learning, the development of the machine X can be regarded as a supervised learning problem. We basically implement algorithms that can learn human intelligence by observing labeled training data. For example, we teach a robot how to cross a street by showing it examples of right and wrong ways of crossing a street. Let's assume that we somehow manage to do this.

Now, if we try to apply the same method to build the machine X++, we run into an apparent bootstrapping (or chicken-egg) problem. How can we apply supervised learning for this task? How can we teach a machine that is supposed to become far more intelligent than we are? This is of course a philosophical question, but it it is also of practical relevance as it shows the limits of supervised machine learning methods.

Trying to build X or even X++ by a detailed reverse engineering of the human brain has similar problems. The most apparent one is the need for an embodied agent that connects the brain with the outside world.

The Role of the Society

If we want to build X++, the most crucial question is not what the nature of human intelligence is, but rather how it became how we know and (partially) understand it today. Of course it is necessary to understand how the organ of the human brain works -- it developed over millions of years. However, the key point is that there has been an exponential growth of the general human intelligence during the last ~2000 years. Why is there such an immense growth in this short amount of time?

A major part of the answer are the sociological structures that the modern human forms. Today, children learn in pre-school what was not thinkable in the Mediveal. But how did the important ideas crystalize from the irrelevant ones? How do we evaluate today the future impact of ideas and concepts, such that the general intelligence of humans keeps its fast growth in the future?

In my point of view, the concept of peer-reviewing and rating is the key to accelerate the development of intelligence. When Einstein came up with his idea of relativity, no one knew that this will be of such a huge relevance for the future of physics. His ideas had to be evaluated, discussed, rated and compared to others to gain insight of its potential. If someone has a great idea, but fails in convincing the society that it is a good one, he will probably take it to the grave. The human intelligence could only develop by sharing and evaluating ideas. The media channels for this sharing changed over time, but the principle remains the same.

Peer-Reviewing Agents

If we want to build X++, a machine that shall become more intelligent than we are, we need to apply the same principles to learning algorithms and machines as manifested in the human society. It is not enough to simulate a single brain by a learning algorithm. The learning algorithm must be embedded into a society of (virtual) agents. Single agents must have the capability of learning like the human brain. In addition, they must be pro-active and able to generate and share their ideas with peers. Similarly to scientific peer-reviewing or liking in social networks, agents must be able to rate ideas of others. Based on their ratings, agents can become experts in certain domains, and thereby their reviews get higher impact. Also the idea of agent generations seems important: at some point agents die and make room for new ones which learn the ideas of the previous generation, but maybe in a condensed form and seeing it from a different angle. Therefore, it is also important that agents learn from other agents. This is the key difference to classical supervised leaning: it is not us humans who teach the machines, but they need to crystalize their own ideas and learn from each other.

A virtual society of peer-reviewing agents has the potential to develop a form of intelligence that exceeds that of humans. However, since the agents live in their own world, they have to develop not only their own ideas, but also the very principles of interaction and communication, e.g., their own language. Important milestones for such a system would be to observe communication patterns, the formation of sociological structures and peer-reviewing mechanisms and, last but not least, knowledge and intelligence.

February 6, 2015

Henshin 1.2

We are happy to announce the release of Henshin 1.2! Henshin is a model / graph transformation tool for EMF models. The new release comes with new features for the graphical editor and a better integration with Apache Giraph.

The graphical editor now supports attribute conditions, which are used to restrict the applicability of transformation rules. In addition, the editor now supports live validation which gives you an immediate warning if you are trying to add an object to two containers or you are using an invalid JavaScript expression etc.

For me the most important new feature of the new version is the improved code generation facilities for Giraph. The new wizard will generate a full-fledged Java-project with all needed libraries, set up a Maven build and even automatically install a local Hadoop test environment if you like. This means that you can model a graph transformation in Henshin and fully automatically generate executable Giraph code that you can directly run in Eclipse. The video below shows you a demo of this new code generator.

Henshin 1.2 is available at our release update site.