Chemical space is so large that brute force searches for new interesting molecules are infeasible. High-throughput virtual screening via computer cluster simulations can speed up the discovery process by collecting very large amounts of data in parallel, e.g., up to hundreds or thousands of parallel measurements. Bayesian optimization (BO) can produce additional acceleration by sequentially identifying the most useful simulations or experiments to be performed next. However, current BO methods cannot scale to the large numbers of parallel measurements and the massive libraries of molecules currently used in high-throughput screening. Here, we propose a scalable solution based on a parallel and distributed implementation of Thompson sampling (PDTS). We show that, in small scale problems, PDTS performs similarly as parallel expected improvement (EI), a batch version of the most widely used BO heuristic. Additionally, in settings where parallel EI does not scale, PDTS outperforms other scalable baselines such as a greedy search, $\epsilon$-greedy approaches and a random search method. These results show that PDTS is a successful solution for large-scale parallel BO.

The problem of population recovery refers to estimating a distribution based on incomplete or corrupted samples. Consider a random poll of sample size $n$ conducted on a population of individuals, where each pollee is asked to answer $d$ binary questions. We consider one of the two polling impediments: (a) in lossy population recovery, a pollee may skip each question with probability $\epsilon$, (b) in noisy population recovery, a pollee may lie on each question with probability $\epsilon$. Given $n$ lossy or noisy samples, the goal is to estimate the probabilities of all $2^d$ binary vectors simultaneously within accuracy $\delta$ with high probability. This paper settles the sample complexity of population recovery. For lossy model, the optimal sample complexity is $\tilde\Theta(\delta^{-2\max\{\frac{\epsilon}{1-\epsilon},1\}})$, improving the state of the art by Moitra and Saks in several ways: a lower bound is established, the upper bound is improved and the result depends at most on the logarithm of the dimension. Surprisingly, the sample complexity undergoes a phase transition from parametric to nonparametric rate when $\epsilon$ exceeds $1/2$. For noisy population recovery, the sharp sample complexity turns out to be more sensitive to dimension and scales as $\exp(\Theta(d^{1/3} \log^{2/3}(1/\delta)))$ except for the trivial cases of $\epsilon=0,1/2$ or $1$. For both models, our estimators simply compute the empirical mean of a certain function, which is found by pre-solving a linear program (LP). Curiously, the dual LP can be understood as Le Cam's method for lower-bounding the minimax risk, thus establishing the statistical optimality of the proposed estimators. The value of the LP is determined by complex-analytic methods.

MrDeathJockey 20,277 views Breadth-first Search (BFS) on Graphs Part 2 - Implementation - Duration: 8:11.

Many AI applications rely on knowledge encoded in a locigal knowledge base (KB). The most essential benefit of such logical KBs is the opportunity to perform automatic reasoning which however requires a KB to meet some minimal quality criteria such as consistency. Without adequate tool assistance, the task of resolving such violated quality criteria in a KB can be extremely hard, especially when the problematic KB is large and complex. To this end, interactive KB debuggers have been introduced which ask a user queries whether certain statements must or must not hold in the intended domain. The given answers help to gradually restrict the search space for KB repairs. Existing interactive debuggers often rely on a pool-based strategy for query computation. A pool of query candidates is precomputed, from which the best candidate according to some query quality criterion is selected to be shown to the user. This often leads to the generation of many unnecessary query candidates and thus to a high number of expensive calls to logical reasoning services. We tackle this issue by an in-depth mathematical analysis of diverse real-valued active learning query selection measures in order to determine qualitative criteria that make a query favorable. These criteria are the key to devising efficient heuristic query search methods. The proposed methods enable for the first time a completely reasoner-free query generation for interactive KB debugging while at the same time guaranteeing optimality conditions, e.g. minimal cardinality or best understandability for the user, of the generated query that existing methods cannot realize. Further, we study different relations between active learning measures. The obtained picture gives a hint about which measures are more favorable in which situation or which measures always lead to the same outcomes, based on given types of queries.

Machine learning seems to be the new hot topic these days. Everybody is talking about it since we've been seeing machines beat human players in chess, jeopardy, and now even Go. Our cars will be driven by artificial intelligence in the future, our jobs will be taken over by robots. There's a lot of hype, a lot of fear and uncertainty – as so often when new technology has the potential to disrupt our societies. However, when you talk to the people that are actually involved in developing these new types of intelligent algorithms, you get a quite different picture. Today, there's a lot of manual work involved in automating decision processes.

Conditional preference networks (CP-nets) are an intuitive and expressive representation for qualitative preferences. Such models must somehow be acquired. Psychologists argue that direct elicitation is suspect. On the other hand, learning general CP-nets from pairwise comparisons is NP-hard, and — for some notions of learning — this extends even to the simplest forms of CP-nets. We introduce a novel, concise encoding of binary-valued, tree-structured CP-nets that supports the first local-search-based CP-net learning algorithms. While exact learning of binary-valued, tree-structured CP-nets — for a strict, entailment-based notion of learning — is already in P, our algorithm is the first space-efficient learning algorithm that gracefully handles noisy (i.e., realistic) comparison sets.

We tackle the problem of providing engineering decision makers with relevant information extracted from data obtained via a process model based on deliberation and voting. We list examples of potential applications from the area of bug-fix scheduling for software, as well as space-vehicles 'go'-'no-go' decision making. In such application domains, important decisions have to be made hastily and therefore the decision factors have to be informed timely of the main issues discovered by the teams. A logic is proposed for reasoning with comments available in such deliberations. Search based algorithms are proposed which recommend the best justifications for a decision and retain the voting decisions for interested parties to tally. We have developed a Bayesian network for generating data by simulation based on probabilistic models that we can train from collected deliberation databases. The data generated in this way was used for evaluating the proposed search algorithm, showing how it can provide better than random recommendations of arguments to decision makers.

In the hedonic coalition formation game model Roles Based Hedonic Games (RBHG), agents view teams as compositions of available roles. An agent's utility for a partition is based upon which roles she and her teammates fulfill within the coalition. I show positive results for finding optimal or stable role matchings given a partitioning into teams. In settings such as massively multiplayer online games, a central authority assigns agents to teams but not necessarily to roles within them. For such settings, I consider the problems of optimizing expected utility and expected stability in RBHG. I show that the related optimization problems for partitioning are NP-hard. I introduce a local search heuristic method for approximating such solutions. I validate the heuristic by comparison to existing partitioning approaches using real-world data scraped from League of Legends games.

The idea of dynamic move chains has been described in a preceding paper [10]. Re-using an earlier piece of search allows the tree to be forward-pruned, which is known to be dangerous, because it can potentially remove new information that would only be realised through a more exhaustive search process. The justification is the integrity in the position and small changes between positions make it more likely that an earlier result still applies. Larger problems where exhaustive search is not possible would also like a method that can guess accurately. This paper has added to the forward-pruning technique by using 'move tables' that can act in the same way as Transposition Tables, but for moves not positions. They use an efficient memory structure and have put the design into the context of short or long-term memories. The long-term memory includes simply rote-learning of other players' games. The forward-pruning technique can also be fortified to help to remove some potential errors. Another idea is 'long branches'. This plays a short move sequence, before returning to a full search at the resulting leaf nodes. Therefore, with some configuration the dynamic tables can be reliably used and relatively independently of the position. This has advanced some of the future work theory of the earlier paper, and made more explicit where logical plans and more knowledge-based approaches might be applied. The author would argue that the process is a very human approach to searching for chess moves.

We present a data mining approach for reducing the search space of local search algorithms in a class of binary integer programs including the set covering and partitioning problems. The quality of locally optimal solutions typically improves if a larger neighborhood is used, while the computation time of searching the neighborhood increases exponentially. To overcome this, we extract variable associations from the instance to be solved in order to identify promising pairs of flipping variables in the neighborhood search. Based on this, we develop a 4-flip neighborhood local search algorithm that incorporates an efficient incremental evaluation of solutions and an adaptive control of penalty weights. Computational results show that the proposed method improves the performance of the local search algorithm for large-scale set covering and partitioning problems.