On the role of search for learning from examples

Gold (1967) discovered a fundamental enumeration technique, the socalled identification-by-enumeration, a simple but powerful class of algorithms for learning from examples (inductive inference). We introduce a variety of more sophisticated (and more powerful) enumeration techniques and characterize their power. We conclude with the thesis that enumeration techniques are even universal in that each solvable learning problem in inductive inference can be solved by an adequate enumeration technique. This thesis is technically motivated and discussed.     

基于一阶逻辑的可满足求解方法研究进展

基于命题逻辑的布尔可满足SAT存在描述能力弱、抽象层次低、求解复杂度高等问题,而基于一阶逻辑的可满足性模理论SMT采用高层建模语言,表达能力更强,更接近于字级设计,避免将问题转化到位级求解,在硬件RTL级验证、程序验证与实时系统验证等领域得到了广泛应用。针对近年来涌现的众多SMT求解方法,依据方法的求解方式进行了分类与对比。而后,对3种主流的求解方法Eager方法、Lazy方法和DPLL(T)方法的实现进行了概要介绍。最后,讨论了SMT求解方法当前所面临的主要挑战以及在SMT求解方面的一些研究成果,并对今后的研究进行了展望。     

On a decidable generalized quantifier logic corresponding to a decidable fragment of first-order logic

Van Lambalgen (1990) proposed a translation from a language containing a generalized quantifierQ into a first-order language enriched with a family of predicatesR _i, for every arityi (or an infinitary predicateR) which takesQxg(x, y₁,..., y_n) to x(R(x, y₁,..., y₁) (x,y₁,...,y_n)) (y ₁,...,y_n are precisely the free variables ofQx). The logic ofQ (without ordinary quantifiers) corresponds therefore to the fragment of first-order logic which contains only specially restricted quantification. We prove that it is decidable using the method of analytic tableaux. Related results were obtained by Andréka and Németi (1994) using the methods of algebraic logic.     

Boosting complete techniques thanks to local search methods

In this paper, an efficient heuristic allowing one to localize inconsistent kernels in propositional knowledge‐bases is described. Then, it is shown that local search techniques can boost the performance of logically complete methods for SAT. More precisely, local search techniques can be used to guide the branching strategy of logically complete techniques like Davis and Putnam's one, giving rise to significant performance improvements, in particular when addressing locally inconsistent problems. Moreover, this approach appears very competitive in the context of consistent SAT instances, too. This revised version was published online in June 2006 with corrections to the Cover Date.     

粗糙逻辑中理论相容性的拓扑刻画

有关文献将计量化方法应用于粗糙逻辑之中,建立起了用以处理近似推理问题的粗糙逻辑度量空间理论。拟借助于粗糙逻辑度量空间理论,从拓扑学的角度给出粗糙逻辑理论相容性的等价刻画。     

Empirical investigation of stochastic local search for maximum satisfiability

The maximum satisfiability (MAX-SAT) problem is an important NP-hard problem in theory, and has a broad range of applications in practice. Stochastic local search (SLS) is becoming an increasingly popular method for solving MAX-SAT. Recently, a powerful SLS algorithm called CCLS shows efficiency on solving random and crafted MAX-SAT instances. However, the performance of CCLS on solving industrial MAX-SAT instances lags far behind. In this paper, we focus on experimentally analyzing the performance of SLS algorithms for solving industrial MAXSAT instances. First, we conduct experiments to analyze why CCLS performs poor on industrial instances. Then we propose a new strategy called additive BMS (Best from Multiple Selections) to ease the serious issue. By integrating CCLS and additive BMS, we develop a new SLS algorithm for MAXSAT called CCABMS, and related experiments indicate the efficiency of CCABMS. Also, we experimentally analyze the effectiveness of initialization methods on SLS algorithms for MAX-SAT, and combine an effective initialization method with CCABMS, resulting in an enhanced algorithm. Experimental results show that our enhanced algorithm performs better than its state-of-the-art SLS competitors on a large number of industrial MAX-SAT instances.     

On the use of design defect examples to detect model refactoring opportunities

Design defects are symptoms of design decay, which can lead to several maintenance problems. To detect these defects, most of existing research is based on the definition of rules that represent a combination of software metrics. These rules are sometimes not enough to detect design defects since it is difficult to find the best threshold values; the rules do not take into consideration the programming context, and it is challenging to find the best combination of metrics. As an alternative, we propose in this paper to identify design defects using a genetic algorithm based on the similarity/distance between the system under study and a set of defect examples without the need to define detection rules. We tested our approach on four open-source systems to identify three potential design defects. The results of our experiments confirm the effectiveness of the proposed approach.     

Understanding the role of noise in stochastic local search: Analysis and experiments

Stochastic local search (SLS) algorithms have recently been proven to be among the best approaches to solving computationally hard problems. SLS algorithms typically have a number of parameters, optimized empirically, that characterize and determine their performance. In this article, we focus on the noise parameter. The theoretical foundation of SLS, including an understanding of how to the optimal noise varies with problem difficulty, is lagging compared to the strong empirical results obtained using these algorithms. A purely empirical approach to understanding and optimizing SLS noise, as problem instances vary, can be very computationally intensive. To complement existing experimental results, we formulate and analyze several Markov chain models of SLS in this article. In particular, we compute expected hitting times and show that they are rational functions for individual problem instances as well as their mixtures. Expected hitting time curves are analytical counterparts to noise response curves reported in the experimental literature. Hitting time analysis using polynomials and convex functions is also discussed. In addition, we present examples and experimental results illustrating the impact of varying noise probability on SLS run time. In experiments, where most probable explanations in Bayesian networks are computed, we use synthetic problem instances as well as problem instances from applications. We believe that our results provide an improved theoretical understanding of the role of noise in stochastic local search, thereby providing a foundation for further progress in this area.     

Design and analysis of stochastic local search for the multiobjective traveling salesman problem

Stochastic local search (SLS) algorithms are typically composed of a number of different components, each of which should contribute significantly to the final algorithm's performance. If the goal is to design and engineer effective SLS algorithms, the algorithm developer requires some insight into the importance and the behavior of possible algorithmic components. In this paper, we analyze algorithmic components of SLS algorithms for the multiobjective travelling salesman problem. The analysis is done using a careful experimental design for a generic class of SLS algorithms for multiobjective combinatorial optimization. Based on the insights gained, we engineer SLS algorithms for this problem. Experimental results show that these SLS algorithms, despite their conceptual simplicity, outperform a well-known memetic algorithm for a range of benchmark instances with two and three objectives.     

On Local Stratifiability of Logic Prograns and Databases

In this paper,we deal with the problem of verifying local stratifiability of logic programs and databases presented by Przymusinski.Necessary and sufficient condition for the local stratifiability of logic programs are presented and algorithms of performing the verification are developed.Finally,we prove that a database D B containing clauses with disjunctive consequents can be easily converted into a logic program P such that D B is locally statified iff P is locally stratified.     

On solutions to fuzzy stochastic differential equations with local martingales

This paper deals with a class of fuzzy stochastic differential equations (FSDEs) driven by a continuous local martingale under the Lipschitzian condition. Such equations can be useful in modeling hybrid systems, where the phenomena are simultaneously subjected to two kinds of uncertainties: randomness and fuzziness. The solutions of the FSDEs are the fuzzy stochastic processes, and their uniqueness is considered to be in a strong sense. Thus, the existence and uniqueness of solutions to the FSDEs under the Lipschitzian condition is first proven. Moreover, some asymptotic properties of the solutions to the FSDEs are investigated. Finally, an illustrating example on the interest term model is provided.     

Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools

Several grammar-based genetic programming algorithms have been proposed in the literature to automatically generate heuristics for hard optimization problems. These approaches specify the algorithmic building blocks and the way in which they can be combined in a grammar; the best heuristic for the problem being tackled is found by an evolutionary algorithm that searches in the algorithm design space defined by the grammar.In this work, we propose a novel representation of the grammar by a sequence of categorical, integer, and real-valued parameters. We then use a tool for automatic algorithm configuration to search for the best algorithm for the problem at hand. Our experimental evaluation on the one-dimensional bin packing problem and the permutation flowshop problem with weighted tardiness objective shows that the proposed approach produces better algorithms than grammatical evolution, a well-established variant of grammar-based genetic programming. The reasons behind such improvement lie both in the representation proposed and in the method used to search the algorithm design space.     

Exploring the logic of mobile search

After more than a decade of development work and hopes, the usage of mobile Internet has finally taken off. Now, we are witnessing the first signs of evidence of what might become the explosion of mobile content and applications that will be shaping the (mobile) Internet of the future. Similar to the wired Internet, search will become very relevant for the usage of mobile Internet. Current research on mobile search has applied a limited set of methodologies and has also generated a narrow outcome of meaningful results. This article covers new ground, exploring the use and visions of mobile search with a users' interview-based qualitative study. Its main conclusion builds upon the hypothesis that mobile search is sensitive to a mobile logic different than today's one. First, (advanced) users ask for accessing with their mobile devices the entire Internet, rather than subsections of it. Second, success is based on new added-value applications that exploit unique mobile functionalities. The authors interpret that such mobile logic involves fundamentally the use of personalised and context-based services.     

On learning to recognize 3-D objects from examples

Previous results on nonlearnability of visual concepts relied on the assumption that such concepts are represented as sets of pixels. The author uses an approach developed by Haussler (1989) to show that under an alternative, feature-based representation, recognition is probably approximately correct (PAC) learnable from a feasible number of examples in a distribution-free manner     

Application of stochastic control techniques to chaotic nonlinearsystems

A control algorithm based on stochastic control techniques is devised for chaotic nonlinear systems. The algorithm uses a state estimator based on the Kalman filter, and yields performance improvements in at least some regions of state space with respect to that obtainable by use of a controller utilizing only the conditional mean of the system state vector. The method is applied to two typical chaotic nonlinear systems (the Henon-Heiles system and the Lorenz system), and their behavior with control is explored numerically     

On detection of lines using search techniques and list processing

Two-line detection algorithms using best first and depth first search techniques, and another algorithm for line detection by joining the line segments based on the principle of A?, are proposed. The algorithms are suitable to detect lines from low-resolution low-contrast images. Shortcomings of conventional approaches, including tracking, have been discussed, and the power of proposed techniques over tracking is illustrated. Results of proposed algorithms are compared with one another. The advantage of these AI-based techniques is that lines of different confidence value (strength) and with at least a certain length can be detected, hence the effect of noise is greatly reduced.     

AGATHA: Using heuristic search to automate the construction of case law theories

In this paper we describe AGATHA, a program designed to automate the process of theory construction in case based domains. Given a seed case and a number of precedent cases, the program uses a set of argument moves to generate a search space for a dialogue between the parties to the dispute. Each move is associated with a set of theory constructors, and thus each point in the space can be associated with a theory intended to explain the seed case and the other cases in the domain. The space is large and so an heuristic search method is needed. This paper describes two methods based on A* and alpha/beta pruning and also a series of experiments designed to explore the appropriateness of different evaluation functions, the most useful precedents to use as seed cases and the quality of the resulting theories.