It is well known that evolutionary algorithms can benefit from dynamic choices of the key parameters that control their behavior, to adjust their search strategy to the different stages of the optimization process. A prominent example where dynamic parameter choices have shown a provable super-constant speed-up is the (1 + (λ, λ)) Genetic Algorithm optimizing the OneMax function. While optimal parameter control policies result in linear expected running times, this is not possible with static parameter choices. This result has spurred a lot of interest in parameter control policies. However, many works, in particular theoretical running time analyses, focus on controlling one single parameter. Deriving policies for controlling multiple parameters remains very challenging. In this work, we reconsider the problem of the (1 + (λ, λ)) Genetic Algorithm optimizing OneMax. We decouple its four main parameters and investigate how well state-of-the-art deep reinforcement learning techniques can approximate good control policies. We show that although making deep reinforcement learning learn effectively is a challenging task, once it works, it is very powerful and is able to find policies that outperform all previously known control policies on the same benchmark. Based on the results found through reinforcement learning, we derive a simple control policy that consistently outperforms the default theory-recommended setting by 27% and the irace-tuned policy, the strongest existing control policy on this benchmark, by 13%, for all tested problem sizes up to 40,000.

Dynamic Algorithm Configuration (DAC) has garnered significant attention in recent years, particularly in the prevalence of machine learning and deep learning algorithms. Numerous studies have leveraged the robustness of decision-making in Reinforcement Learning (RL) to address the optimization challenges associated with algorithm configuration. However, making an RL agent work properly is a non-trivial task, especially in reward design, which necessitates a substantial amount of handcrafted knowledge based on domain expertise. In this work, we study the importance of reward design in the context of DAC via a case study on controlling the population size of the (1 + (λ, λ))-GA optimizing OneMax. We observed that a poorly designed reward can hinder the RL agent's ability to learn an optimal policy because of a lack of exploration, leading to both scalability and learning divergence issues. To address those challenges, we propose the application of a reward shaping mechanism to facilitate enhanced exploration of the environment by the RL agent. Our work not only demonstrates the ability of RL in dynamically configuring the (1 + (λ, λ))-GA, but also confirms the advantages of reward shaping in the scalability of RL agents across various sizes of OneMax problems.

To study the requirements needed for a humanlike language to develop, Language Emergence research uses jointly trained artificial agents which communicate to solve a task, the most popular of which is a referential game.The targets that agents refer to typically involve a single entity, which limits their ecological validity and the complexity of the emergent languages.Here, we present a simple multi-entity game in which targets include multiple entities that are spatially related.We ask whether agents dealing with multi-entity targets benefit from the use of graph representations, and explore four different graph schemes.Our game requires more sophisticated analyses to capture the extent to which the emergent languages are compositional, and crucially, what the decomposed features are.We find that emergent languages from our setup exhibit a considerable degree of compositionality, but not over all features.1

Unsupervised relation extraction (URE) extracts relations between named entities from raw text without manually-labelled data and existing knowledge bases (KBs).URE methods can be categorised into generative and discriminative approaches, which rely either on hand-crafted features or surface form.However, we demonstrate that by using only named entities to induce relation types, we can outperform existing methods on two popular datasets.We conduct a comparison and evaluation of our findings with other URE techniques, to ascertain the important features in URE.We conclude that entity types provide a strong inductive bias for URE. 1

Interpreting the inner workings of neural models is a key step in ensuring the robustness and trustworthiness of the models, but work on neural network interpretability typically faces a tradeoff: either the models are too constrained to be very useful, or the solutions found by the models are too complex to interpret.We propose a novel strategy for achieving interpretability that -in our experiments -avoids this trade-off.Our approach builds on the success of using probability as the central quantity, such as for instance within the attention mechanism.In our architecture, DoLFIn (Distributions over Latent Features for Interpretability), we do no determine beforehand what each feature represents, and features go altogether into an unordered set.Each feature has an associated probability ranging from 0 to 1, weighing its importance for further processing.We show that, unlike attention and saliency map approaches, this set-up makes it straight-forward to compute the probability with which an input component supports the decision the neural model makes.To demonstrate the usefulness of the approach, we apply DoLFIn to text classification, and show that DoLFIn not only provides interpretable solutions, but even slightly outperforms the classical CNN and BiLSTM text classifiers on the SST2 and AG-news datasets.

Modern entity linking systems rely on large collections of documents specifically annotated for the task (e.g., AIDA CoNLL).In contrast, we propose an approach which exploits only naturally occurring information: unlabeled documents and Wikipedia.Our approach consists of two stages.First, we construct a high recall list of candidate entities for each mention in an unlabeled document.Second, we use the candidate lists as weak supervision to constrain our document-level entity linking model.The model treats entities as latent variables and, when estimated on a collection of unlabelled texts, learns to choose entities relying both on local context of each mention and on coherence with other entities in the document.The resulting approach rivals fully-supervised state-of-the-art systems on standard test sets.It also approaches their performance in the very challenging setting: when tested on a test set sampled from the data used to estimate the supervised systems.By comparing to Wikipedia-only training of our model, we demonstrate that modeling unlabeled documents is beneficial.

Accurate entity linkers have been produced for domains and languages where annotated data (i.e., texts linked to a knowledge base) is available.However, little progress has been made for the settings where no or very limited amounts of labeled data are present (e.g., legal or most scientific domains).In this work, we show how we can learn to link mentions without having any labeled examples, only a knowledge base and a collection of unannotated texts from the corresponding domain.In order to achieve this, we frame the task as a multi-instance learning problem and rely on surface matching to create initial noisy labels.As the learning signal is weak and our surrogate labels are noisy, we introduce a noise detection component in our model: it lets the model detect and disregard examples which are likely to be noisy.Our method, jointly learning to detect noise and link entities, greatly outperforms the surface matching baseline.For a subset of entity categories, it even approaches the performance of supervised learning.

Entity linking involves aligning textual mentions of named entities to their corresponding entries in a knowledge base.Entity linking systems often exploit relations between textual mentions in a document (e.g., coreference) to decide if the linking decisions are compatible.Unlike previous approaches, which relied on supervised systems or heuristics to predict these relations, we treat relations as latent variables in our neural entity-linking model.We induce the relations without any supervision while optimizing the entity-linking system in an end-to-end fashion.Our multirelational model achieves the best reported scores on the standard benchmark (AIDA-CoNLL) and substantially outperforms its relation-agnostic version.Its training also converges much faster, suggesting that the injected structural bias helps to explain regularities in the training data.

Coreference evaluation metrics are hard to optimize directly as they are nondifferentiable functions, not easily decomposable into elementary decisions.Consequently, most approaches optimize objectives only indirectly related to the end goal, resulting in suboptimal performance.Instead, we propose a differentiable relaxation that lends itself to gradient-based optimisation, thus bypassing the need for reinforcement learning or heuristic modification of cross-entropy.We show that by modifying the training objective of a competitive neural coreference system, we obtain a substantial gain in performance.This suggests that our approach can be regarded as a viable alternative to using reinforcement learning or more computationally expensive imitation learning.

According to the principle of compositionality, the meaning of a sentence is computed from the meaning of its parts and the way they are syntactically combined.In practice, however, the syntactic structure is computed by automatic parsers which are far-from-perfect and not tuned to the specifics of the task.Current recursive neural network (RNN) approaches for computing sentence meaning therefore run into a number of practical difficulties, including the need to carefully select a parser appropriate for the task, deciding how and to what extent syntactic context modifies the semantic composition function, as well as on how to transform parse trees to conform to the branching settings (typically, binary branching) of the RNN.This paper introduces a new model, the Forest Convolutional Network, that avoids all of these challenges, by taking a parse forest as input, rather than a single tree, and by allowing arbitrary branching factors.We report improvements over the state-of-the-art in sentiment analysis and question classification.

We present a self-training approach to unsupervised dependency parsing that reuses existing supervised and unsupervised parsing algorithms.Our approach, called 'iterated reranking' (IR), starts with dependency trees generated by an unsupervised parser, and iteratively improves these trees using the richer probability models used in supervised parsing that are in turn trained on these trees.Our system achieves 1.8% accuracy higher than the stateof-the-part parser of Spitkovsky et al. (2013) on the WSJ corpus.

We propose the first implementation of an infinite-order generative dependency model. The model is based on a new recursive neural network architecture, the Inside-Outside Recursive Neural Network. This architecture allows information to flow not only bottom-up, as in traditional recursive neural networks, but also top-down. This is achieved by computing content as well as context representations for any constituent, and letting these rep-resentations interact. Experimental re-sults on the English section of the Uni-versal Dependency Treebank show that the infinite-order model achieves a per-plexity seven times lower than the tradi-tional third-order model using counting, and tends to choose more accurate parses in k-best lists. In addition, reranking with this model achieves state-of-the-art unla-belled attachment scores and unlabelled exact match scores. 1

Recommender systems provide personalized suggestions about items that users will find interesting. Typically, recommender systems require a user interface that can ``intelligently'' determine the interest of a user and use this information to make suggestions. The common solution, ``explicit ratings'', where users tell the system what they think about a piece of information, is well-understood and fairly precise. However, having to stop to enter explicit ratings can alter normal patterns of browsing and reading. A more ``intelligent'' method is to useimplicit ratings, where a rating is obtained by a method other than obtaining it directly from the user. These implicit interest indicators have obvious advantages, including removing the cost of the user rating, and that every user interaction with the system can contribute to an implicit rating.