Davy Van Nieuwenborgh, Stijn Heymans, Dirk Vermeir
462 - 466
We present an approximation theory for the extended answer set semantics, using the concept of an approximation constraint. Intuitively, an approximation constraint, while satisfied by a “perfect” solution, may be left unsatisfied in an approximate extended answer set. Approximations improve as the number of unsatisfied constraints decreases. We show how the framework can also capture the classical answer set semantics, thus providing an approximative version of the latter.
Binary possibilistic utility unifies two previously proposed qualitative decision models: optimistic and pessimistic utilities. All these decision models have been axiomatized in a von Neumann-Morgenstern setting. These axiomatizations have shown the formal similarity of these qualitative utilities and expected utility. Unfortunately in this framework, the representation of uncertainty has to be clearly assumed to be given. In a more general setting, without this restriction, optimistic and pessimistic utilities have been axiomatized à la Savage. This paper proposes a study of the axiomatics of binary possibilistic utility in a Savagean framework.
The fundamental operation of dominance testing, i.e., determining if one alternative is preferred to another, is in general very hard for methods of reasoning with qualitative conditional preferences such as CP-nets and conditional preference theories (CP-theories). It is therefore natural to consider approximations of preference, and upper approximations are of particular interest, since they can be used within a constraint optimisation algorithm to find some of the optimal solutions. Upper approximations for preference in CP-theories have previously been suggested, but they require consistency, as well as strong acyclicity conditions on the variables. We define an upper approximation of conditional preference for which dominance checking is efficient, and which can be applied very generally for CP-theories.
Various problems in artificial intelligence (AI) can be solved by translating them into a quantified boolean formula (QBF) and evaluating the resulting encoding. In this approach, a QBF solver is used as a black box in a rapid implementation of a more general reasoning system. Most of the current solvers for QBFs require formulas in prenex conjunctive normal form as input, which makes a further translation necessary, since the encodings are usually not in a specific normal form. This additional step increases the number of variables in the formula or disrupts the formula's structure. Moreover, the most important part of this transformation, prenexing, is not deterministic. In this paper, we focus on an alternative way to process QBFs without these drawbacks and describe a solver, qpro, which is able to handle arbitrary formulas. To this end, we extend algorithms for QBFs to the non-normal form case and compare qpro with the leading normal-form provers on problems from the area of AI.
One problem faced in knowledge engineering for Bayesian networks is the exponential growth of the number of parameters in their conditional probability tables (CPTs). The most common practical solution is application of the noisy-OR (or their generalization, the noisy-MAX) gates, which take advantage of independence of causal interactions and provide a logarithmic reduction of the number of parameters required to specify a CPT. In this paper, we propose an algorithm that fits a noisy-MAX distribution to an existing CPT and we apply it to search for noisy-MAX gates in three existing practical Bayesian networks. We show that noisy-MAX gate provides a surprisingly good fit for as many as 50% of CPTs in these networks. The importance of this finding is that it provides an empirical justification for the use of the noisy-MAX gate as a powerful knowledge engineering tool.
Klaus Brinker, Johannes Fürnkranz, Eyke Hüllermeier
489 - 493
Label ranking studies the problem of learning a mapping from instances to rankings over a predefined set of labels. Hitherto existing approaches to label ranking implicitly operate on an underlying (utility) scale which is not calibrated in the sense that it lacks a natural zero point. We propose a suitable extension of label ranking that incorporates the calibrated scenario and substantially extends the expressive power of these approaches. In particular, our extension suggests a conceptually novel technique for extending the common learning by pairwise comparison approach to the multilabel scenario, a setting previously not being amenable to the pairwise decomposition technique. We present empirical results in the area of text categorization and gene analysis, underscoring the merits of the calibrated model in comparison to state-of-the-art multilabel learning methods.
This paper proposes a novel approach to discover options in the form of conditionally terminating sequences, and shows how they can be integrated into reinforcement learning framework to improve the learning performance. The method utilizes stored histories of possible optimal policies and constructs a specialized tree structure online in order to identify action sequences which are used frequently together with states that are visited during the execution of such sequences. The tree is then used to implicitly run corresponding options. Effectiveness of the method is demonstrated empirically.
We formulate the problem of least squares temporal difference learning (LSTD) in the framework of least squares SVM (LS-SVM). To cope with the large amount (and possible sequential nature) of training data arising in reinforcement learning we employ a subspace based variant of LS-SVM that sequentially processes the data and is hence especially suited for online learning. This approach is adapted from the context of Gaussian process regression and turns the unwieldy original optimization problem (with computational complexity being cubic in the number of processed data) into a reduced problem (with computional complexity being linear in the number of processed data). We introduce a QR decomposition based approach to solve the resulting generalized normal equations incrementally that is numerically more stable than existing recursive least squares based update algorithms. We also allow a forgetting factor in the updates to track non-stationary target functions (i.e. for the use with optimistic policy iteration). Experimental comparison with standard CMAC function approximation indicate that LS-SVMs are well-suited for online RL.
We present a novel approach to machine learning, called ABML (argumentation based ML). This approach combines machine learning from examples with concepts from the field of argumentation. The idea is to provide expert's arguments, or reasons, for some of the learning examples. We require that the theory induced from the examples explains the examples in terms of the given reasons. Thus arguments constrain the combinatorial search among possible hypotheses, and also direct the search towards hypotheses that are more comprehensible in the light of expert's background knowledge. In this paper we implement ABCN2 as an extension of the CN2 rule learning algorithm, and analyze its advantages in comparison with the original CN2 algorithm.
Scaling discrete AdaBoost to handle real-valued weak hypotheses has often been done under the auspices of convex optimization, but little is generally known from the original boosting model standpoint. We introduce a novel generalization of discrete AdaBoost which departs from this mainstream of algorithms. From the theoretical standpoint, it formally displays the original boosting property; furthermore, it brings interesting computational and numerical improvements that make it significantly easier to handle “as is”. Conceptually speaking, it provides a new and appealing scaling to R of some well known facts about discrete (ada)boosting. Perhaps the most popular is an iterative weight modification mechanism, according to which examples have their weights decreased iff they receive the right class by the current discrete weak hypothesis. Our generalization to real values makes that decreasing weights affect only the examples on which the hypothesis' margin exceeds its average margin. Thus, while both properties coincide on the discrete case, examples that receive the right class can still be reweighted higher with real-valued weak hypotheses. From the experimental standpoint, our generalization displays the ability to produce low error formulas with particular cumulative margin distributions, and it provides a nice handling of those noisy domains that represent Achilles' heel for common Adaptive Boosting algorithms.
Lexical entailment is knowledge that may prove very useful for a variety of applications that deal with information implicit in a text. In this paper we address the problem of automatic discovery of pairs of verbs related by entailment. A specific challenge in this task is recognition of the direction of entailment in a pair. We model entailment by a number of linguistic cues as to local coherence between clauses. We first investigate the effect of these cues on the quality of the model and then evaluate it against human judgements. Our evaluation reveals that the model is capable of correctly identifying the direction in entailment-related pairs, although their separation from bidirectional pairs proves a more difficult task.
Machine learning approaches in natural language processing often require a large annotated corpus. We present a complementary approach that utilizes expert knowledge to overcome the scarceness of annotated data. In our framework KAFTIE, the expert could easily create a large number of rules in a systematic manner without the need of a knowledge engineer. Using KAFTIE, a knowledge base was built based on a small data set that outperforms machine learning algorithms trained on a much bigger data set for the task of recognizing temporal relations. Furthermore, our knowledge acquisition approach could be used in synergy with machine learning algorithms to both increase the performance of the machine learning algorithms and to reduce the expert's knowledge acquisition effort.
In the proposed approach, learning from large spatial-temporal data streams is addressed using the sequential training of support vector machines (SVM) on a series of smaller spatial data subsets collected over shorter periods. A set of representatives are selected from support vectors corresponding to an SVM trained with data of a limited spatial-temporal coverage. These representatives are merged with newly arrived data also corresponding to a limited spacetime segment. A new SVM is learned using both sources. Relying on selected representatives instead of propagating all support vectors to the next iteration allows efficient learning of semi-global SVMs in a non-stationary series consisting of correlated spatial datasets. The proposed method is evaluated on a challenging geoinformatics problem of aerosol retrieval from Terra satellite based Multi-angle Imaging Spectro Radiometer instrument. Regional features were discovered that allowed spatial partitioning of continental US to several semi-global regions. Developed semi-global SVM models were reused for efficient estimation of aerosol optical depth from radiances with a high level of accuracy on data cycles spanning several months. The obtained results provide evidence that SVMs trained as proposed have an extended spatial and temporal range of applicability as compared to SVM models trained on samples collected over shorter periods. In addition, the computational cost of training a semi-global SVM with selective support vector propagation (SSVP) was much lower than when training a global model using spatial observations from the entire period.
Leonardo Rigutini, Ernesto Di Iorio, Marco Ernandes, Marco Maggini
531 - 535
This paper addresses the problem of categorizing terms or lexical entities into a predefined set of semantic domains exploiting the knowledge available on-line in the Web. The proposed system can be effectively used for the automatic expansion of thesauri, limiting the human effort to the preparation of a small training set of tagged entities. The classification of terms is performed by modeling the contexts in which terms from the same class usually appear. The Web is exploited as a significant repository of contexts that are extracted by querying one or more search engines. In particular, it is shown how the required knowledge can be obtained directly from the snippets returned by the search engines without the overhead of document downloads. Since the Web is continuously updated “World Wide”, this approach allows us to face the problem of open-domain term categorization handling both the geographical and temporal variability of term semantics. The performances attained by different text classifiers are compared, showing that the accuracy results are very good independently of the specific model, thus validating the idea of using term contexts extracted from search engine snippets. Moreover, the experimental results indicate that only very few training examples are needed to reach the best performance (over 90% for the F1 measure).
We describe a generalized Q-learning type algorithm for reinforcement learning in competitive multi-agent games. We make the observation that in a competitive setting with adaptive agents an agent's actions will (likely) result in changes in the opponents policies. In addition to accounting for the estimated policies of the opponents, our algorithm also adjusts these future opponent policies by incorporating estimates of how the opponents change their policy as a reaction to ones own actions. We present results showing that agents that learn with this algorithm can successfully achieve high reward in competitive multi-agent games where myopic self-interested behavior conflicts with the long term individual interests of the players. We show that this approach successfully scales for multi-agent games of various sizes, in particular to the social dilemma type problems: from the small iterated Prisoner's Dilemma, to larger settings akin to Harding's Tragedy of the Commons. Thus, our multi-agent reinforcement algorithm is foresighted enough to correctly anticipate future rewards in the important problem class of social dilemmas, without having to resort to negotiation-like protocols or precoded strategies.
We present MSDA (Major Senses Discovery Algorithm) – a development over the context vector approach to (noun) sense discrimination [20, 24] that uses attributes and values instead of word features to cluster contexts, and does not require for the number of senses to be fixed beforehand. The algorithm achieves a precision of 89% on a dataset including both ambiguous and non-ambiguous nouns, twice that of previous algorithms.
Roberto Basili, Marco Cammisa, Alfio Massimiliano Gliozzo
548 - 552
An unsupervised methodology for Word Sense Disambiguation, called Dynamic Domain Sense Tagging, is presented. It relies on the convergence of two very well known unsupervised approaches (i.e. Domain Driven Disambiguation and Conceptual Density). For each target word a domain is dynamically modeled by expanding the its topical context, i.e. a set of words evoking the underlying/implict domain where the word is located. The estimation of the paradigmatic similarity within such a specific lexicon is assumed as a disambiguation model. The Conceptual Density measure is here used to account for paradigmatic associations, and the top scored senses of the target word are selected accordingly. Results confirm the impact of domain based representation in capturing useful paradigmatic generalizations, especially when small text fragments are available. In addition, the precision/recall tradeoff of the resulting method can be tuned in a meaningful way, allowing us to achieve impressively high precision scores in a purely unsupervised setting.
When you search for information regarding a particular person on the web, a search engine returns many pages. Some of these pages may be for people with the same name. How can we disambiguate these different people with the same name? This paper presents an unsupervised algorithm which produces unique phrases to disambiguate different people with the same name (i.e. namesakes). Our algorithm takes in a personal name and outputs multiple sets of phrases which uniquely identify the different namesakes on the web. These phrases could then be added to the query to narrow down the search to a specific namesake. We evaluated the algorithm on a collection of documents retreived from the Web. Experimental results show a significant improvement over the existing methods proposed for this task.
Grammar induction is one of the most important research areas of the natural language processing. The lack of a large Treebank, which is required in supervised grammar induction, in some natural languages such as Persian encouraged us to focus on unsupervised methods. We have found the Inside-Outside algorithm, introduced by Lari and Young, as a suitable platform to work on, and augmented IO with a history notion. The result is an improved unsupervised grammar induction method called History-based IO (HIO). Applying HIO to two very divergent natural languages (i.e., English and Persian) indicates that inducing more conditioned grammars improves the quality of the resultant grammar. Besides, our experiments on ATIS and WSJ show that HIO outperforms most current unsupervised grammar induction methods.
This article describes a semantic parser based on FrameNet semantic roles that uses a broad knowledge base created by interconnecting three major resources: FrameNet, VerbNet and PropBank. We link the above resources through a mapping between Intersective Levin classes, which are part of PropBank's annotation, and the FrameNet frames. By using Levin classes, we successfully detect FrameNet semantic roles without relying on the frame information. At the same time, the combined usage of the above resources increases the verb coverage and confers more robustness to our parser. The experiments with Support Vector Machines on automatic Levin class detection suggest that (a) tree kernels are well suited for the task and (b) Intersective Levin classes can be used to improve the accuracy of semantic parsing based on FrameNet roles.
Recent work on Semantic Role Labeling (SRL) has shown that syntactic information is critical to detect and extract predicate argument structures. As syntax is expressed by means of structured data, i.e. parse trees, its encoding in learning algorithms is rather complex.
In this paper, we apply tree kernels to encode the whole predicate argument structure in Support Vector Machines (SVMs). We extract from the sentence syntactic parse the subtrees that span potential argument structures of the target predicate and classify them in incorrect or correct structures by means of tree kernel based SVMs. Experiments on the PropBank collection show that the classification accuracy of correct/incorrect structures is remarkably high and helps to improve the accuracy of the SRL task. This is a piece of evidence that tree kernels provide a powerful mechanism to learn the complex relation between syntax and semantics.
In this work a model for planning with multivalued fluents and graded actions, based on the infinite valued Lukasiewicz logic, is introduced. In multivalued planning, fluents can assume truth values in the interval [0, 1] and actions can be executed at different application degrees also varying in [0, 1]. The notions of planning problem and solution plan also reflect a multivalued approach. Multivalued fluents and graded actions allow to model many real situations where some features of the world cannot be modeled with boolean values and where actions can be executed with varying strength which produces graded effects as well. Even if most existing planning models fail to address this kind of domains, our model is comparable with models allowing flexible actions and soft constraints. A correct/complete algorithm which solves bounded multivalued planning problems based on MIP compilation is also described and a prototype implementation is presented.