Séparation et évaluation | EPFL Graph Search

Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960. L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum. Parfois, il est possible d'éviter d'énumérer des solutions dont on sait, par l'analyse des propriétés du problème, que ce sont de mauvaises solutions, c'est-à-dire des solutions qui ne peuvent pas être le minimum. La méthode séparation et évaluation est une méthode générale pour cela. Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement. Le branch and bound est parfois comparé

Learning to Reduce Annotation Load

Ksenia Konyushkova

Modern machine learning methods and their applications in computer vision are known to crave for large amounts of training data to reach their full potential. Because training data is mostly obtained through humans who manually label samples, it induces a significant cost. Therefore, the problem of reducing the annotation load is of great importance for the success of machine learning methods. We study the problem of reducing the annotation load from two viewpoints, by answering the questions âWhat to annotate?â and âHow to annotate?â. The question âWhat?â addresses the selection of a small portion of the data that would be sufficient to train an accurate model. The question âHow? focuses on minimising the effort of labelling each datapoint. The question âWhat to annotate?â becomes particularly compelling if we can select data to be annotated in an iterative and adaptive way, a setting known as active learning (AL). The key challenge in AL is to identify the datapoints that are the most informative for the model at a given stage. We propose several techniques to address this challenge. Firstly, we consider the problem of segmenting natural images and image volumes. We take advantage of image priors, such as smoothness of objects of interest, and use them in a novel form of geometric uncertainty. Using this, we design an AL technique to efficiently annotate data that is tailored to segmentation applications. Next, we notice that no single manually-designed strategy outperforms others in every application and that often the burden of designing new strategies outweighs the benefits of AL. To overcome this problem we suggest learning an AL strategy from data by formulating the AL problem as a regression task that predicts the reduction in the generalisation error achieved by labelling each datapoint. This enables us to learn AL strategies from simulated data and to transfer them to new datasets. Finally, we turn towards non-myopic data-driven AL strategies. To this end, we formulate the AL problem as a Markov decision process and find the best selection policy using reinforcement learning. We design the decision process such that the policy can be learnt for any ML model and transferred to diverse application domains. Effectively addressing the question âHow to annotate?â is of no less importance as large cost savings can be achieved by labelling each datapoint more efficiently. This can be done with intelligent interfaces that interact with a human annotator. We make two contributions towards answering the question âHow?â. Firstly, we propose an efficient technique to annotate 3D image volumes for image segmentation. Annotating data in 3D is cumbersome and an obvious way to facilitate it is to select a subset of the data lying on a 2D plane. To find the optimal plane (i.e. the one containing the most informative datapoints) we design a branch-and-bound algorithm that quickly eliminates hypotheses about the optimal projection. Secondly, we propose an intelligent data annotation method to train object detectors. Instead of always asking the human annotator to draw bounding boxes in images, we detect automatically in which cases we can rely on the current detector and verify its proposal.

EPFL2019

Tracking elementary particles near their primary vertex: a combinatorial approach

Thomas Liebling

Colliding beams experiments High Energy Physics rely on solid state detectors to track the flight paths of charged elementary particles near their primary point of interaction. Reconstructing tracks in this region requires, per collision, a partitioning of up to 10^3 highly correlated observations into an unknown number of tracks. We report on the succesful implementation of a combinatorial track finding algorithm to solve this pattern recognition problem in the context of the ALEPH experiment ar CERN. Central to the implementation is a 5-dimensional axial assignment are obtained by means of an extended Kalman filter. A preprocessing step, involving the clustering and geometric partitioning of the observations, ensures reasonable bounds on the size of the poblems, which are solved using a branch & bound algorithm with LP relaxation. Convergence is reached within one second of CPU time on a RISC workstation in average.

1996

Timescales of N-H bond dissociation in pyrrole: a nonadiabatic dynamics study

Momir Malis, Antonio Prlj

The excitation wavelength dependent photodynamics of pyrrole are investigated by nonadiabatic trajectory-surface-hopping dynamics simulations based on time dependent density functional theory (TDDFT) and the algebraic diagrammatic construction method to the second order (ADC(2)). The ADC(2) results confirm that the N-H bond dissociation occurring upon excitation at the origin of the first excited state, S-1(pi sigma*), is driven by tunnelling [Roberts et al., Faraday Discuss., 2013, 163, 95] as a barrier of DE = 1780 cm(-1) traps the population in a quasi-bound minimum. Upon excitation to S-1(pi sigma*) in the wavelength range of 236-240 nm, direct dissociation of the N-H bond takes place with a time constant of 28 fs. The computed time constant is in very good agreement with recently reported measurements. Excitation to the lowest B-2 state in the 198-202 nm range returns a time constant for N-H fission of 48 fs at the B3LYP/def2-TZVPD level, in perfect agreement with the experiment [Roberts et al. Faraday Discuss., 2013, 163, 95]. For the same wavelength range the ADC(2)/aug-cc-pVDZ decay constant is more than three times longer than the experimentally reported one. The accuracy of the B3LYP/def2-TZVPD dynamics is checked against reference complete-active-space second-order perturbation theory (CASPT2) calculations and explained in terms of correct topography of the pi pi* surface and the lack of mixing between the pi pi* and the 3p(x) Rydberg states which occurs in the ADC(2) method.

Royal Soc Chemistry2015

Learning to Reduce Annotation Load

Ksenia Konyushkova

EPFL2019