We consider the problem of learning the parameters of a structured output prediction model, that is, learning to predict elements of a complex interdependent output space that correspond to a given input. Unlike many of the existing approaches, we focus on the weakly supervised setting, where most (or all) of the training samples have only been partially annotated. Given such a weakly supervised dataset, our goal is to estimate accurate parameters of the model by minimizing the regularized empirical risk, where the risk is measured by a user-specified loss function. This task has previously been addressed by the well-known latent support vector machine (latent SVM) framework. We argue that, while latent SVM offers a computational efficient solution to loss-based weakly supervised learning, it suffers from the following three drawbacks: (i) the optimization problem corresponding to latent SVM is a difference-of-convex program, which is non-convex, and hence susceptible to bad local minimum solutions; (ii) the prediction rule of latent SVM only relies on the most likely value of the latent variables, and not the uncertainty in the latent variable values; and (iii) the loss function used to measure the risk is restricted to be independent of true (unknown) value of the latent variables. We address the the aforementioned drawbacks using three novel contributions. First, inspired by human learning, we design an automatic self-paced learning algorithm for latent SVM, which builds on the intuition that the learner should be presented in the training samples in a meaningful order that facilitates learning: starting frome easy samples and gradually moving to harder samples. Our algorithm simultaneously selects the easy samples and updates the parameters at each iteration by solving a biconvex optimization problem. Second, we propose a new family of LVMs called max-margin min-entropy (M3E) models, which includes latent SVM as a special case. Given an input, an M3E model predicts the output with the smallest corresponding Renyi entropy of generalized distribution, which relies not only on the probability of the output but also the uncertainty of the latent variable values. Third, we propose a novel learning framework for learning with general loss functions that may depend on the latent variables. Specifically, our framework simultaneously estimates two distributions: (i) a conditional distribution to model the uncertainty of the latent variables for a given input-output pair; and (ii) a delta distribution to predict the output and the latent variables for a given input. During learning, we encourage agreement between the two distributions by minimizing a loss-based dissimilarity coefficient. We demonstrate the efficacy of our contributions on standard machine learning applications using publicly available datasets.

In recent years, the crucial importance of metrics in machine learningalgorithms has led to an increasing interest in optimizing distanceand similarity functions using knowledge from training data to make them suitable for the problem at hand.This area of research is known as metric learning. Existing methods typically aim at optimizing the parameters of a given metric with respect to some local constraints over the training sample. The learned metrics are generally used in nearest-neighbor and clustering algorithms.When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance, which is parameterized by a positive semi-definite matrix. Recent methods offer good scalability to large datasets.Less work has been devoted to metric learning from structured objects (such as strings or trees), because it often involves complex procedures. Most of the work has focused on optimizing a notion of edit distance, which measures (in terms of number of operations) the cost of turning an object into another.We identify two important limitations of current supervised metric learning approaches. First, they allow to improve the performance of local algorithms such as k-nearest neighbors, but metric learning for global algorithms (such as linear classifiers) has not really been studied so far. Second, and perhaps more importantly, the question of the generalization ability of metric learning methods has been largely ignored.In this thesis, we propose theoretical and algorithmic contributions that address these limitations. Our first contribution is the derivation of a new kernel function built from learned edit probabilities. Unlike other string kernels, it is guaranteed to be valid and parameter-free. Our second contribution is a novel framework for learning string and tree edit similarities inspired by the recent theory of (epsilon,gamma,tau)-good similarity functions and formulated as a convex optimization problem. Using uniform stability arguments, we establish theoretical guarantees for the learned similarity that give a bound on the generalization error of a linear classifier built from that similarity. In our third contribution, we extend the same ideas to metric learning from feature vectors by proposing a bilinear similarity learning method that efficiently optimizes the (epsilon,gamma,tau)-goodness. The similarity is learned based on global constraints that are more appropriate to linear classification. Generalization guarantees are derived for our approach, highlighting that our method minimizes a tighter bound on the generalization error of the classifier. Our last contribution is a framework for establishing generalization bounds for a large class of existing metric learning algorithms. It is based on a simple adaptation of the notion of algorithmic robustness and allows the derivation of bounds for various loss functions and regularizers.

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Bioengineering, Biomedical Engineering, 2009. / Includes bibliographical references.

This thesis investigates the role of linguistically-motivated generative models of syntax and semantic structure in natural language processing (NLP). Syntactic well-formedness is crucial in language generation, but most statistical models do not account for the hierarchical structure of sentences. Many applications exhibiting natural language understanding rely on structured semantic representations to enable querying, inference and reasoning. Yet most semantic parsers produce domain-specific or inadequately expressive representations. We propose a series of generative transition-based models for dependency syntax which can be applied as both parsers and language models while being amenable to supervised or unsupervised learning. Two models are based on Markov assumptions commonly made in NLP: The first is a Bayesian model with hierarchical smoothing, the second is parameterised by feed-forward neural networks. The Bayesian model enables careful analysis of the structure of the conditioning contexts required for generative parsers, but the neural network is more accurate. As a language model the syntactic neural model outperforms both the Bayesian model and n-gram neural networks, pointing to the complementary nature of distributed and structured representations for syntactic prediction. We propose approximate inference methods based on particle filtering. The third model is parameterised by recurrent neural networks (RNNs), dropping the Markov assumptions. Exact inference with dynamic programming is made tractable here by simplifying the structure of the conditioning contexts. We then shift the focus to semantics and propose models for parsing sentences to labelled semantic graphs. We introduce a transition-based parser which incrementally predicts graph nodes (predicates) and edges (arguments). This approach is contrasted against predicting top-down graph traversals. RNNs and pointer networks are key components in approaching graph parsing as an incremental prediction problem. The RNN architecture is augmented to condition the model explicitly on the transition system configuration. We develop a robust parser for Minimal Recursion Semantics, a linguistically-expressive framework for compositional semantics which has previously been parsed only with grammar-based approaches. Our parser is much faster than the grammar-based model, while the same approach improves the accuracy of neural Abstract Meaning Representation parsing.

This study examines the ways in which public participation in the production of scientific knowledge, influences the practices and expertise of the scientists in Galaxy Zoo, an online Big Data citizen science initiative. The need for citizen science in the field of Astronomy arose in response to the challenges of rapid advances in data gathering technologies, which demanded pattern recognition capabilities that were too advanced for existing computer algorithms. To address these challenges, Galaxy Zoo scientists recruited volunteers through their online website, a strategy which proved to be remarkably reliable and efficient. In doing so, they opened up the boundaries of scientific processes to the public. This shift has led to important outcomes in terms of the scientific discovery of new Astronomical objects; the creation and refining of scientific practices; and the development of new forms of expertise among key actors while they continue to pursue their scientific goals. This thesis attempts to answer the over-arching research question: How is citizen science shaping the practices and expertise of Galaxy Zoo scientists? The emergence of new practices and development of the expertise in the domain of managing citizen science projects were observed through following the work of the Galaxy Zoo scientists and in particular the Principal Investigator and the project's Technical Lead, from February 2010 to April 2013. A broadly ethnographic approach was taken, which allowed the study to be sensitive to the uncertainty and unprecedented events that characterised the development of Galaxy Zoo as a pioneering project in the field of data-intensive citizen science. Unstructured interviewing was the major source of data on the work of the PI and TL; while the communication between these participants, the broader Science Team and their inter-institutional collaborators was captured through analyses of the team emailing list, their official blog and their social media posts. The process of data analysis was informed by an initial conceptualisation of Galaxy Zoo as a knowledge production system and the concept of knowledge object (Knorr-Cetina,1999), as an unfolding epistemic entity, became a primary analytical tool. Since the direction and future of Galaxy Zoo involved addressing new challenges, the study demanded periodic recursive analysis of the conceptual framework and the knowledge objects of both Galaxy Zoo and the present examination of its development. The key findings were as follows. The involvement of public volunteers shaped the practices of the Science Team, while they pursued robust scientific outcomes. Changes included: negotiating collaborations; designing the classification tasks for the volunteers; re-examining data reduction methods and data release policies; disseminating results; creating new epistemic communities; and science communication. In addition, new kinds of expertise involved in running Galaxy Zoo were identified. The relational and adaptive aspects of expertise were seen as important. It was therefore proposed that the development of the expertise in running citizen science projects should be recognised as a domain-expertise in its own right. In Galaxy Zoo, the development of the expertise could be attributed to a combined understanding of: the design principles of doing good science; innovation in methods; and creating a dialogic space for scientists and volunteers. The empirical and theoretical implications of this study therefore lie in (i) identifying emergent practices in citizen science while prioritising scientific knowledge production and (ii) a re-examination of expertise for science in the emerging context of data-intensive science.

Die Erstellung von Lerninhalten ist einer der wichtigsten Prozesse im E-Learning. Die vorliegende Arbeit zeigt einen Ansatz zur Wiederverwendung von Lerninhalten der zum einen die Kosten des Erstellungsprozesses verringern kann und zum anderen effektive Methoden zur Verwaltung aufzeigt. Basis des Ansatzes ist ein vierstufiges Content-Modell (Assets, Lernmaterialien, Lernmodule und Veranstaltungen), welches die Lerninhalte anhand der Granularität aufteilt. Dieses Modell berücksichtigt dabei aktuelle E-Learning-Standards bezüglich der Inhalte und der Metadaten, wodurch eine systemunabhängige Wiederverwendung möglich ist. Zur Verarbeitung von generischen Repräsentationen, wie Materialien im XML-Format, wurde das Konzept der Templates aufgegriffen und um die so genannten Content-Varianten erweitert. Diese ermöglichen die Präsentation von verschiedenen Ausprägungen der Materialien, beispielsweise bezüglich des Ausgabeformates, der Sprache, des Schwierigkeitsgrades von Aufgaben oder der Version. In der Arbeit wird weiterhin ein entsprechendes Konzept zur Systementwicklung einer Lernplattform aufgezeigt. Dieses ist insbesondere durch die Aufteilung in verschiedene Teilsysteme gekennzeichnet, welche eine flexible Konfiguration und Platzierung anhand der Anforderungen an die Wiederverwendung ermöglicht. / The preparation of learning content is one of the most important process in E-Learning. This thesis shows an approach to reuse learning content. On the one hand the costs of the creation process can be reduced and on the other hand effective methods for administration are pointed out. Starting point of the approach is a four-level content model (assets, learning materials, learning modules and seminars), which divides learning contents on the basis of granularity. This model considers thereby current E-Learning-standards concerning content and metadata, whereby an open reuse is possible. For the processing of generic representations, like materials in the XML format, the concept of the Templates was taken up and extended by the content variants. These make the presentation of different developments of the materials possible, for example concerning the output format, the language, the degree of difficulty of tasks or the version. Further this thesis pointed out an appropriate concept for the system development of a learning platform. This is in particular characterized by the partitioning into different subsystems, which makes possible a flexible configuration and placement concerning to the requirements to the reuse.

1 EINLEITUNG Wissenschaft findet heute zunehmend digital unterstützt statt. Der Einsatz von Datenbanken, Mailinglisten, Blogs, Wikis und sozialen Netzwerken verändert dabei nicht nur die Praxis der wissenschaftlichen Kommunikation und Publikation, auch der Prozess der Produktion von Erkenntnis wird dadurch nachhaltig beeinflusst (vgl. Nentwich 2003, Nentwich/König 2012). Bereits 1999 stellte Michael Nentwich in einem Working Paper des Max-Planck-Instituts für Gesellschaftsforschung mit dem Titel „Cyberscience“ die These auf, dass Computer und Internet das Potenzial zu qualitativen Veränderungen im Wissenschaftssystem hätten (vgl. Nentwich 1999). Der Begriff der E-Science verweist ebenfalls auf grundlegende Veränderungen im Bereich der Wissenschaft, setzt den Schwerpunkt jedoch vor allem auf eine durch vernetzte Rechnertechnik (Grid-Technologie) daten-intensivierte Forschung, die nach Ansicht einiger Autoren sogar ein neues Paradigma begründen könnte (vgl. Hey/ Tansley/Tolle 2009). [...]

This work proposes a strategy for visual perception in the context of autonomous driving. Despite the growing research aiming to implement self-driving cars, no artificial system can claim to have reached the driving performance of a human, yet. Humans---when not distracted or drunk---are still the best drivers you can currently find. Hence, the theories about the human mind and its neural organization could reveal precious insights on how to design a better autonomous driving agent. This dissertation focuses specifically on the perceptual aspect of driving, and it takes inspiration from four key theories on how the human brain achieves the cognitive capabilities required by the activity of driving. The first idea lies at the foundation of current cognitive science, and it argues that thinking nearly always involves some sort of mental simulation, which takes the form of imagery when dealing with visual perception. The second theory explains how the perceptual simulation takes place in neural circuits called convergence-divergence zones, which expand and compress information to extract abstract concepts from visual experience and code them into compact representations. The third theory highlights that perception---when specialized for a complex task as driving---is refined by experience in a process called perceptual learning. The fourth theory, namely the free-energy principle of predictive brains, corroborates the role of visual imagination as a fundamental mechanism of inference. In order to implement these theoretical principles, it is necessary to identify the most appropriate computational tools currently available. Within the consolidated and successful field of deep learning, I select the artificial architectures and strategies that manifest a sounding resemblance with their cognitive counterparts. Specifically, convolutional autoencoders have a strong correspondence with the architecture of convergence-divergence zones and the process of perceptual abstraction. The free-energy principle of predictive brains is related to variational Bayesian inference and the use of recurrent neural networks. In fact, this principle can be translated into a training procedure that learns abstract representations predisposed to predicting how the current road scenario will change in the future. The main contribution of this dissertation is a method to learn conceptual representations of the driving scenario from visual information. This approach forces a semantic internal organization, in the sense that distinct parts of the representation are explicitly associated to specific concepts useful in the context of driving. Specifically, the model uses as few as 16 neurons for each of the two basic concepts here considered: vehicles and lanes. At the same time, the approach biases the internal representations towards the ability to predict the dynamics of objects in the scene. This property of temporal coherence allows the representations to be exploited to predict plausible future scenarios and to perform a simplified form of mental imagery. In addition, this work includes a proposal to tackle the problem of opaqueness affecting deep neural networks. I present a method that aims to mitigate this issue, in the context of longitudinal control for automated vehicles. A further contribution of this dissertation experiments with higher-level spaces of prediction, such as occupancy grids, which could conciliate between the direct application to motor controls and the biological plausibility.

Dans cette thèse, nous avons étudié les problèmes de décisions séquentielles, avec comme application la gestion de stocks d'énergie. Traditionnellement, ces problèmes sont résolus par programmation dynamique stochastique. Mais la grande dimension, et la non convexité du problème, amènent à faire des simplifications sur le modèle pour pouvoir faire fonctionner ces méthodes. Nous avons donc étudié une méthode alternative, qui ne requiert pas de simplifications du modèle: Monte Carlo Tree Search (MCTS). Nous avons commencé par étendre le MCTS classique (qui s'applique aux domaines finis et déterministes) aux domaines continus et stochastiques. Pour cela, nous avons utilisé la méthode de Double Progressive Widening (DPW), qui permet de gérer le ratio entre largeur et profondeur de l'arbre, à l'aide de deux méta paramètres. Nous avons aussi proposé une heuristique nommée Blind Value (BV) pour améliorer la recherche de nouvelles actions, en utilisant l'information donnée par les simulations passées. D'autre part, nous avons étendu l'heuristique RAVE aux domaines continus. Enfin, nous avons proposé deux nouvelles méthodes pour faire remonter l'information dans l'arbre, qui ont beaucoup amélioré la vitesse de convergence sur deux cas tests. Une part importante de notre travail a été de proposer une façon de mêler MCTS avec des heuristiques rapides pré-existantes. C'est une idée particulièrement intéressante dans le cas de la gestion d'énergie, car ces problèmes sont pour le moment résolus de manière approchée. Nous avons montré comment utiliser Direct Policy Search (DPS) pour rechercher une politique par défaut efficace, qui est ensuite utilisée à l'intérieur de MCTS. Les résultats expérimentaux sont très encourageants. Nous avons aussi appliqué MCTS à des processus markoviens partiellement observables (POMDP), avec comme exemple le jeu de démineur. Dans ce cas, les algorithmes actuels ne sont pas optimaux, et notre approche l'est, en transformant le POMDP en MDP, par un changement de vecteur d'état. Enfin, nous avons utilisé MCTS dans un cadre de méta-bandit, pour résoudre des problèmes d'investissement. Le choix d'investissement est fait par des algorithmes de bandits à bras multiples, tandis que l'évaluation de chaque bras est faite par MCTS. Une des conclusions importantes de ces travaux est que MCTS en continu a besoin de très peu d'hypothèses (uniquement un modèle génératif du problème), converge vers l'optimum, et peut facilement améliorer des méthodes suboptimales existantes.

The World Wide Web (WWW) is a huge information network within which searching for relevant quality contents remains an open question. The ambiguity of natural language is traditionally one of the main reasons, which prevents search engines from retrieving information according to users' needs. However, the globalized access to the WWW via Weblogs or social networks has highlighted new problems. Web documents tend to be subjective, they mainly refer to actual events to the detriment of past events and their ever growing number contributes to the well-known problem of information overload. In this thesis, we present our contributions to digest information in real-world heterogeneous text environments (i.e. the Web) thus leveraging users' efforts to encounter relevant quality information. However, most of the works related to Information Digestion deal with the English language fostered by freely available linguistic tools and resources, and as such, cannot be directly replicated for other languages. To overcome this drawback, two directions may be followed: on the one hand, building resources and tools for a given language, or on the other hand, proposing language-independent approaches. Within the context of this report, we will focus on presenting language-independent unsupervised methodologies to (1) extract implicit knowledge about the language and (2) understand the explicit information conveyed by real-world texts, thus allowing to reach Multilingual Information Digestion.