Author: annalouise

Anna Latour promoted to doctor

On Tuesday 13 September 2022, Anna Latour successfully defended her dissertation in the Great Auditorium of Leiden’s beautiful (and ancient) Academy Building.

Anna’s dissertation, titled “Optimal decision-making under constraints and uncertainty”, was formally approved by her doctorate committee in February. Now, finally, was her time to defend it to a committee of opponents. She is the first of prof. Hoos’s doctorate students from ADA Leiden to receive her title.

The Great Auditorium of the Academy Building in Leiden.

In true Leiden tradition, the ceremony was solemn, but festive. Anna’s opponents (prof. Plaat, dr. Van Leeuwen, prof. Kersting, prof. Stuckey, prof. Bonsangue, and prof. Kleijn) questioned her on the semantics and pros and cons of different probabilistic languages, deep learning, the interpretation of probabilities in logic, the choking hazards presented by printed copies of dissertations, adversarial settings in stochastic constraint (optimisation) problems, and the use of gradient methods in constraint solving. This resulted in a good discussion, characterised by mutual respect and a sense of humour. In good COVID practice, the ceremony was hybrid, with two opponents and even a paranimph participating virtually from Germany, Australia and Canada, and with all in-person attendees wearing masks. Anna’s promotores, prof. Hoos and prof. Kok, as well as her co-promotor dr. Nijssen were present in person.

Still from the livestream.
Anna with the certificate declaring that she has the rights to the title of “doctor”.

The discussion was ended by a loud “Hora Est!” from the Beadle, after which the committee left the room for deliberation. Upon their return, it was prof. Hoos’s duty to speak the “magic formula” that promoted Anna to doctor in Mathematics and the Natural Sciences. This has to be done in Dutch, and since it was his first time promoting a student to doctor in the Netherlands, he was somewhat nervous. He did well, and Anna received her certificate (with a giant seal!) from professor Kleijn, the doctorate committee’s secretary.

Anna’s co-promotor, dr. Nijssen, then praised her in his laudatio for being a scientist with many talents, stating that she has proved not only her scientific competence by earning her doctorate, but also demonstrated her proficiency at writing, presenting and teaching, by winning awards and scholarships for all of those skills during her time as a PhD candidate.

Following the ceremony, we had a reception in the beautiful atrium of the Academy Building, with a view of the spiral staircase, surrounded by the busts of dead scientists. Afterwards, the freshly minted doctor, her (co-)promotores, her opponents and her paranimph went for an Italian lunch and a chat about the future.

The ancient Romans held a feast in honour of the gods Jupiter, Juno and Minerva (Epulum Jovis) on the 13th of September. We think it is only fitting that, on a day that celebrates the Goddess of Knowledge (who adorns Leiden University’s logo), Leiden University gains another female doctor, from a research group named after the Godmother of Programming. Gaudeamus Igitur!

The next step in Anna’s career is a postdoctoral position as Research Fellow in prof. Meel’s group at the School of Computing of the National University of Singapore. She is working on problems in the field of “Beyond NP”, focusing on (optimisation versions of) Boolean satisfiability, and counting. You can follow her and her career through her website.

You can download dr. Latour’s dissertation from the Leiden University dissertation repository.

Advertisement

Exact stochastic constraint optimisation with applications in network analysis

In business, governance, science as well as in our daily lives, we often have to solve problems that involve optimal decision-making under constraints (limitations on the choices that we can make) and uncertainty (probabilistic knowledge about the future).

There are many stochastic constraint (optimisation) problems (SCPs) that arise from probabilistic networks. These are networks where we associate a probability with the nodes and/or edges of the network.

Going viral

One of those problems is the spread of influence (or viral marketing) problem. We are given a social network with probabilistic influence relationships. Suppose Alexa has a probability of 0.8 to convince Claire to do something. We can model this with a node that symbolises Alexa and a node that symbolises Claire, and an edge pointing from Alexa to Claire, labelled with probability 0.8.

In this network, we assume all influence relationships to be symmetric. Hence, there is an edge with label 0.8 pointing from node a (Alexa) to node c (Claire), and the same arrow pointing back, resulting in one undirected edge connecting these two nodes.

Suppose now that we are a company planning a marketing campaign to promote our product. We want to use a word-of-mouth strategy on the probabilistic social network that we have of our potential customers. The way to start the process is to give free samples of our product to certain people in the network, and hope that they like it and convince their friends to buy the product, who then convince their friends, and so on, until our product goes viral. We have a limited budget for this (the constraint), and want to maximise the expected number of people who will eventually buy our product (the optimisation criterion). Which people in the network should get a free sample of our product?

Alternatively, we can require that the expected number of people who become customers exceeds a certain threshold (the constraint), while we aim to minimise the number of free samples that are distributed (the optimisation criterion). In practice, we can solve a stochastic constraint optimisation problem with a stochastic optimisation criterion and a budget constraint by formulating it as a stochastic constraint satisfaction problem (CSP) with a stochastic constraint and budget constraint. We then start the solving process with a very low threshold for the stochastic constraint (e.g., 0), and increase it each time we find a solution to the CSP. Then, we continue the search for a better solution until no better solution can be found. By then, the last solution we have found is an optimum solution.

Finding an optimum solution is hard

It is the stochastic constraint mentioned above that makes it hard to find a solution to SCPs. Given a strategy (a choice for which people receive a free sample), computing the probability that a person will become one of our customers is expensive. It involves summing probabilities over many, often partially overlapping, paths in the network. We then have to do this for all people in the network (to get the expected number of customers), and potentially have to repeat this for all possible strategies, in order to find a strategy that maximises the expected number of customers (by repeatedly finding an expected number of customers that exceeds an ever-increasing threshold of the stochastic constraint).

Joining forces

To find a solution to the problem, we therefore need two things: a way to quickly reason about probabilities, and a way to traverse the search space of strategies intelligently. We can combine the technique of knowledge compilation with the paradigm of constraint programming to create data structures (specifically, decision diagrams) that capture information about probability distributions, such that we can quickly compute probabilities, and to create constraint propagation algorithms on those data structures, which prune the search space.

Dedicated constraint propagation yields faster solving

A constraint propagation algorithm helps to prune the search space by removing values from the domains of variables. In particular, it ensures that variable domains contain no values that would falsify the constraint(s) in which the variables are present. Comparing different approaches that combine knowledge compilation and constraint programming, we find that having a dedicated constraint propagation algorithm for stochastic constraints tends to yield shorter solving times than approaches that decompose stochastic constraints into small, linear constraints (for which propagators already exist). We attribute this to the fact that in the decomposition process, we lose information about the relationship between different variables that participate in the stochastic constraint. Hence, the pruning power of the propagation methods is less, and the solver cannot prune certain parts of the search space that do not contain any solutions.

Paper

You can learn more about different ways of combining knowledge compilation and constraint programming in our paper “Exact stochastic constraint optimisation with applications in network analysis”, which was published in Artificial Intelligence, vol 304, March 2022.
Authors: Anna L.D. Latour, Behrouz Babaki, Daniël Fokkinga, Marie Anastacio, Holger H. Hoos, Siegfried Nijssen.
Link: doi.org/10.1016/j.artint.2021.103650

Double win at ICT.OPEN 2019: Anna Louise and Can take home pitch prize and poster prize

This year, the ADA group was well represented at ICT.OPEN, the conference for ICT professionals in The Netherlands, which took place on Tuesday 19 and Wednesday 20 March.

Cooperation is key

Prof. Holger H. Hoos gave the keynote lecture on Tuesday morning, talking about how machine learning is transforming the way we do science. He argued that, while competition is important, cooperation is what ultimately makes us conquer the problems of our times.

Impression of Prof. Dr. Holger Hoos’s keynote lecture by Flatland.

Bob the builder

That evening Anna Louise Latour won the elevator pitch competition. In the final round, four PhD students competed to explain their research in under three minutes to a jury and the audience, using only a single prop to illustrate their story.

Anna Louise described how make optimal decisions under constraints and uncertainty, using an optimisation version of the Powergrid Reliability Problem as an example. During her pitch, she used a yellow Bob-the-builder helmet to distinguish between the user with the problem, and the Computer Scientist with the solution.

She impressed jury and audience with the clarity and content of her pitch, and with her charisma, ranking highest in the jury report and receiving three times as many audience votes as the runner-up.

Predictive power

The next day, we had another win: Can Wang was awarded second prize in the Commit2Data poster competition. Her poster explained how Automated Machine Learning can be used to predict the energy consumption of a household. “Pitching my poster to the jury was a bit out of my comfort zone, but I’m very happy that I’ve won!”, Can said afterwards.

Missed it?

For those of you who missed ICT.OPEN this year: make sure to join next year! In the mean time, enjoy NWO’s video of this year’s event:

Cooperation is key, revisited

Of course this outcome was also a team effort. ADA group members, as well as other people from LIACS, helped Can and Anna Louise by providing feedback on their posters and presentations, or being there to cheer.  Therefore, we celebrated as a team, with cakes 🙂

ADA research group welcomes a new PhD student

Photo credit: Hélène Verhaeghe

Anna Louise Latour started her PhD research in January 2017 at the Institute of Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM) of Université catholique de Louvain (UC Louvain) in Belgium, under supervision of dr. Siegfried Nijssen (UC Louvain) and prof. dr. Joost Kok (Universiteit Twente). She came to Leiden in February 2018 and joined the ADA research group in November 2018.

Her research is funded by an NWO TOP grant awarded to dr. Nijssen for his PROFIDDS (PRObabilistic Features for Intelligent Declarative Data Science) project. Within this project, she focuses on developing solving methods for problems in which users have to make optimal decisions under constraints and uncertainties.

An example of such a problem is a Power Grid Reliability Problem. Suppose that we want to help a user who runs a maintenance project on an electric grid to make it more robust against natural disasters (like earthquakes or hurricanes). During a disaster, each powerline in the grid has a certain probability of breakage (uncertainty). If too many of them break, important buildings like hospitals may become disconnected from the grid and lose power. By reinforcing powerlines, the user can make them stronger and less likely to break during an earthquake. However, reinforcing lines is an expensive task, and the user only has a limited budget (a constraint). On which powerlines should the user spend their budget, such that they maximise (optimal decision making) the expected number of important buildings that are still connected to a powerplant?

Her aim is to develop solving methods for these kinds of problems such that they are a) generic, and therefore applicable to a wide range of problems, and b) accessible, even to people who are not programmers.

In order to achieve this goal, she combines modelling and solving techniques from both Constraint Programming and Probabilistic Logic Programming.

Together with Marie Anastacio, Anna Louise also supervises Master student Daniël Fokkinga in his Master’s research.