David Ziegler


Determining the Temporal Order of Events in Natural Language Using Learned Commonsense Knowledge

For many natural language understanding systems, e.g. question answering and document summarization, there is a need for extracting the temporal order of events in a text. Most current temporal order classifiers use linguistic features, for example the tense of the event or cues like "after" etc.

However, humans use commonsense knowledge additional to the explicitly stated information in a text in order to understand it. Similarly, natural language understanding systems can be expected to benefit from such knowledge. Modi & Titov (2014) developed a neural embedding model to learn the prototypical temporal order of events. This is a compositional model, combining verbs and their arguments (subject, objects etc.) in order to represent events. For my thesis I modified the ClearTK TimeML system by Bethard (2013) to take the outcome of Modi & Titov's classifier as an additional feature to classify relations between events. ClearTK TimeML is a participant in TempEval2013 which is a competition for annotating raw text with time expressions, events, temporal links between events (and events and times), and the relation types of these links.

Supervised by Breanndán Ó Nualláin (University of Amsterdam), Ivan Titov (Institute for Logic, Language and Computation), Ashutosh Modi (Saarland University) I am testing whether using commonsense knowledge as an additional feature in the ClearTK system can improve its performance on the TempEval2013 task.



Bethard, S. (2013). ClearTK-TimeML: A minimalist approach to TempEval 2013 In Second Joint Conference on Lexical and Computational Semantics (* SEM) (Vol. 2., pp. 10-14)

Modi, A., & Titov, I. (2014). Learning Semantic Script Knowledge with Event Embeddings. Submitted to Eighteenth Conference on Computational Natural Language Learning


Thesis as pdf



tedxaucollege

TEDxAUCollege Website

In 2014 we organized the first TEDx event at Amsterdam University College. As part of the PR team I created the website for the event: tedxaucollege.com







Using Eye-Movements for Early Detection of Alzheimer

During this internship at National University of Singapore I implemented several algorithms to detect fixations in eye-movement data. Eye movement is always composed of fixations of a few hundred milliseconds and saccades or movements between fixations. The two most accurate algorithms are one that is based on distance between succeeding points and the other is using a Hidden Markov Model based on the speed of movement. Hidden Markov Models are a machine learning technique to find a sequence of states (fixations/saccades) that is most likely, based on the probability to change from one state to another given the speed of movement at a certain point of time.

After implementing these algorithms I started to develop an environment for an experiment for early detection of alzheimer disease. In the middle of the screen is a stimulus shown. Then another stimulus shows up either to the left or right. The subject is told to look in the opposite direction of this stimulus. Alzheimer patients sometimes have problems with this task. Using the fixation detection algorithms the program analyses in which direction the subject looked after the stimulus was shown.

eyetracking
Figure 1: gazeplot during an experiment (blue x-coordinate, green y-coordinate, fixations marked with black bars)


Sharepad

Whenever I try to understand something, plan a project or explain math to a friend the first thing I do is take my notepad and draw it. With sharepad this can be done in the cloud. So, people at different places can collaborate and access earlier sharepads whenever they want again. The url of every sharepad can be sent to others to join it. Everyone can then simultaneously draw in it and see changes in real time. (project with Tobias Sturm; not finished yet...)

sharepad
Figure 2: Sharepad


Swarm Robots

ants
Figure 3: Ants solving a task
collaboratively.

Inspired by the way that ants can work together without a leader and without direct communication (often only over pheromones) we wanted to explore how robots could work together in a team. I did this project together with my friends Tobias Sturm and Renke Schulte.

We tried to come up with a task that several robots could solve so that it could increase productivity to have several robots working on the same task as opposed to only one. Our idea was the following: A number of plastic bottles is randomly spread and the robots' task is to move them together to one 'pile' (I will use the word 'pile' although bottles are not placed on top of each other).

We bought four Asuro robots by the DLR (German space agency). These are very simple, cheap robots just with two wheels and half a table-tennis ball on which they slide. After assembling them we added two things that were necessary for our task: an infrared-sensor to be able to detect bottles and two metal rods at the front to be able to pick up bottles. The original configuration of the robots includes 6 touch sensors at the front to detect collision and infrared sensors at the wheels to measure distance travelled. We divided the work as follows: Renke was responsible for the hardware, he built the robots (they came as spare parts that had to be soldered to the circuit board). Tobias wrote a simulation which allowed us to do the same experiments as in reality just without some constraints like battery time. My task was to program the robots in C.

asuro-side
Figure 4: Asuro robot
experiment
Figure 5: Set up of the experiment

Strategy to solve the collaboration task

Similar to ants the Asuro robots where also extremely simple individually: there was no way to communicate with each other, no GPS-like location detection etc. Thus our challenge was to let the robots solve the task together despite not being able to communicate. Our inspiration for a solution came again from nature: Some termites build there nests in the following dezentralized way: One termite starts accumulating dirt at some place. Every termite follows the rule that when they encounter an accumulation of dirt they won't put the dirt they collected to a new place but to the place they found. At some point the accumulation becomes bigger and easier to see for everyone which means everyone will start collaborating building this big pile instead of other smaller ones.

Just as this solution, our idea is also dezentralized and works without communication: In the beginning the bottles are spread out over the whole area. The robots drive around randomly to explore. If one robot detects a bottle with its infrared-sensor it takes it up and drives around again, pushing the bottle in front of it. If it detects another bottle it measures its size (it could be a pile as well) and saves this as the largest known pile-size. Every subsequent time the robot encounters a pile/bottle while currently pushing a bottle it only adds it to the pile if it is larger or equal to the largest known pile. Robots cannot save the location of the piles because they don't have any location detection mechanism. Different robots might have different largest known piles which means they first build several smaller piles (figure 5, middle) but eventually they will bump into the other piles too and the larger pile will win ('rich get richer' strategy). This means that even without communicating there should be collaboration emerging simply by the rules that every individual follows.

strategy
Figure 6: Strategy to solve the task
measurments
Figure 7: Measurement of pile-size

I have been talking about the robots measuring the pile size. Let me explain in more detail how this works: Figure 6 depicts a pile of bottles where we want to know radius r assuming that the bottles are arranged more or less in a circle. The robots 'vision' is only a distance at exactly one point (where the infrared sensor points to). This means the robot has to turn from pointing to one end of the pile to the other end. By this procedure it determines $\alpha$ (the degree turned) and d (the minimum distance to the circle). The best we can do is get an estimation of the size of the pile, it won't always be correct. Quantity d is almost the same as the minimum distance from robot to the circle around the pile. Since there is a right angle between t and r we get:

$ sin \frac{\alpha}{2} = \frac {r}{r+d}$

This can be transformed into:     $ r = \frac{d}{(sin \frac{\alpha}{2})^{-1} - 1} $


Experiments

We conducted experiments on a 2x2m area (figure 4) with the following constellations to rule out the start positions of the bottles as a factor deciding the outcome of the experiments:

Each of the experiments lasted 15 min and we repeated it for each of the constellations 4 times which makes 16 experiments.

experiments
Figure 7: Bottle positions at the end of an experiment>

Every experiment was filmed by a webcam positioned exactly above the experimental area (see figure 4). We took the last image of each experiment and marked the positions of the bottles with a small tool that we wrote, yielding images like figure 7. We define that two bottles belong to the same pile if the distance of their center points is less than 15cm because this is approximately the tolerance value from which on a robot recognizes two bottles as a pile and not two single bottles. We define the task as solved well if many bottles stand very close together. To measure this we imagined a circle of 7.5cm around each bottle. The more bottles stand very close together the more are these circles overlapping. Therefore, the total area that is covered by these circles is a measure for effectivity:     $ effectivity \sim \frac{1}{occupied\hspace{3pt} area} $ ).

Results

experiments
Figure 8: Results of the experiments

Averaging all experiments we got slightler better effectivity-values for 3 robots than for 1 both in the pseudo-random bottle arrangement as well as the grid (figure 8 shows results for one robot in blue and three robots in red). However, you would expect three robots to be about three times better than one robot (shown in green) which they did not reach by far. This means in this case the robots did not collaborate very well. Sometimes they did destroy piles that another robot just built. Mostly the results are due to the fact that we reached the borders of what you can do with such simplistic technology: Since the sensors at the wheels measuring how much they turn work with light they were sensitive to the environment. Due to this it could sometimes happen that a measurement was wrong and a robot e.g. assumes a way too bug 'largest-known-pile' which means it does not do anything sensible for the rest of the experiment.

In 2009 and 2010 we took part in the German science competition Jugend forscht. In 2009 we became 2nd on regional level, in 2010 we got the 3rd prize of federal state level. The complete paper written for the competition can be found here (18 pages, German).


Mindshare

In 2007 Tobias Sturm and me made a website to enable students to share knowledge and help each other studying. The idea was that everyone can upload documents (text, images, pdf etc.) that a part of knowledge learned in school or additional to it. These can then be linked to a class within a school, to a subject and to other keywords. We made a tag-cloud to be able to browse through different keywords and discover interesting content. The aim of this system was to be complementing to the traditional school and give students the possibility to fill knowledge gaps, help each other studying and discover interesting topics.

With this project we participated in the German science competition Jugend forscht in 2007. The website is not online anymore. A documentation website with more information can be found here (in German).

experiments
Figure 9: Mindshare startpage showing recently uploaded documents>


Sierpinski Fractals in Polygons

fractals
Figure 10: Sierpinski triangle>

Fractals are self-similar patterns. For example the Sierpinski triangle contains three smaller triangles which each contain three triangles and so on. Tobias Sturm wondered in 2005 why the Sierpinski pattern is only known in triangles and whether the same algorithm applied to other polygons would yield fractals as well. The Sierpinski algorithm works as follows:

  1. choose a random point in the triangle.
  2. choose a random corner and draw an imaginary line from the this point to this corner.
  3. draw a point at the middle of this line and repeat (2) from this point.

Figure 10 shows the result of repeating this process 100,000 times. black and white We wrote a program that applies the same algorithm to any regular polygon, freely drawn polygons, in 3D, in more dimensions (without drawing it) and helps analyzing them by zooming etc.

We wondered what would happen if we didn't draw the points in the middle of the imaginary lines but divide the line by another factor. We called this 'linefactor' and figures 12-15 show the results of playing with the linefactor.

fractals
Figure 11: Pentagon with linefactor 2
fractals
Figure 12: Pentagon with linefactor 2.62
fractals
Figure 13: Pentagon with linefactor 3.5
fractals
Figure 11: Pentagon with linefactor -2.62
fractals
Figure 12: Freely drawn form, linefactor 2.5
fractals
Figure 13: Pyramid (3D), linefactor 2.5

In 2006 we took part in the German science competition Jugend forscht the first time. We got the inspiration from Sven Schimmel, founder of Ippos.net who used his spare time to teach programming to kids. Thanks Sven :)   We won the first prize on federal state level which means we could travel to Freiburg and take part in the highest level of Jugend forscht (Germany-wide). This was so inspiring that we did more projects in every subsequent year (see above).