In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

Reinforcement learning systems are often concerned with balancing exploration of untested actions against exploitation of actions that are known to be good. The benefit of exploration can be estimated using the classi­ cal notion of Value of Informationthe expected im­ provement in future decision quality arising from the tnformation acquired by exploration. Estimating this quantity requires an assessment of the agent's uncer­ tainty about its current value estimates for states. In this paper we investigate ways to represent and rea­ son about this uncertainty in algorithms where the sys­ tem attempts to learn a model of its environment. We explicitly represent uncertainty about the parameters of the model and build probability distributions over Q­ values based on these. These distributions are used to compute a myopic approximation to the value of infor­ mation for each action and hence to select the action that best balances exploration and exploitation.
Model based Bayesian Exploration

Feature subset selection, as a special case of the general subset selection problem, has been the topic of a considerable number of studies due to the growing importance of data-mining applications. In the feature subset selection problem there are two main issues that need to be addressed: (i) Finding an appropriate measure function than can be fairly fast and robustly computed for high-dimensional data. (ii) A search strategy to optimize the measure over the subset space in a reasonable amount of time. In this article mutual information between features and class labels is considered to be the measure function. Two series expansions for mutual information are proposed, and it is shown that most heuristic criteria suggested in the literature are truncated approximations of these expansions. It is well-known that searching the whole subset space is an NP-hard problem. Here, instead of the conventional sequential search algorithms, we suggest a parallel search strategy based on semidefinite programming (SDP) that can search through the subset space in polynomial time. By exploiting the similarities between the proposed algorithm and an instance of the maximumcut problem in graph theory, the approximation ratio of this algorithm is derived and is compared with the approximation ratio of the backward elimination method. The experiments show that it can be misleading to judge the quality of a measure solely based on the classification accuracy, without taking the effect of the non-optimum search strategy into account.
A Semidefinite Programming Based Search Strategy for Feature Selection with Mutual Information Measure

Modern conflict-driven clause-learning (CDCL) Boolean SAT solvers provide efficient automatic analysis of real-world feature models (FM) of systems ranging from cars to operating systems. It is well-known that solver-based analysis of real-world FMs scale very well even though SAT instances obtained from such FMs are large, and the corresponding analysis problems are known to be NP-complete. To better understand why SAT solvers are so effective, we systematically studied many syntactic and semantic characteristics of a representative set of large real-world FMs. We discovered that a key reason why large real-world FMs are easy-toanalyze is that the vast majority of the variables in these models are unrestricted, i.e., the models are satisfiable for both true and false assignments to such variables under the current partial assignment. Given this discovery and our understanding of CDCL SAT solvers, we show that solvers can easily find satisfying assignments for such models without too many backtracks relative to the model size, explaining why solvers scale so well. Further analysis showed that the presence of unrestricted variables in these real-world models can be attributed to their high-degree of variability. Additionally, we experimented with a series of well-known nonbacktracking simplifications that are particularly effective in solving FMs. The remaining variables/clauses after simplifications, called the core, are so few that they are easily solved even with backtracking, further strengthening our conclusions. We explain the connection between our findings and backdoors, an idea posited by theorists to explain the power of SAT solvers. This connection strengthens our hypothesis that SAT-based analysis of FMs is easy. In contrast to our findings, previous research characterizes the difficulty of analyzing randomly-generated FMs in terms of treewidth. Our experiments suggest that the difficulty of analyzing realworld FMs cannot be explained in terms of treewidth. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. SPLC 2015, July 20 24, 2015, Nashville, TN, USA c © 2015 ACM. ISBN 978-1-4503-3613-0/15/07. . . $15.00 DOI: http://dx.doi.org/10.1145/2791060.2791070 CCS Concepts •Software and its engineering → Software product lines;

SAT-based Analysis of Large Real-world Feature Models is Easy

