The Beth definability property, a well-known property from classical logic, is investigated in the context of description logics (DLs): if a general L-TBox implicitly defines an L-concept in terms of a given signature, where L is a DL, then does there always exist over this signature an explicit definition in L for the concept? This property has been studied before and used to optimize reasoning in DLs. In this paper a complete classification of Beth definability is provided for extensions of the basic DL ALC with transitive roles, inverse roles, role hierarchies, and/or functionality restrictions, both on arbitrary and on finite structures. Moreover, we present a tableau-based algorithm which computes explicit definitions of at most double exponential size. This algorithm is optimal because it is also shown that the smallest explicit definition of an implicitly defined concept may be double exponentially long in the size of the input TBox. Finally, if explicit definitions are allowed to be expressed in first-order logic then we show how to compute them in EXPTIME.

This paper addresses one of the key components of the mining process: the geological prediction of natural resources from spatially distributed measurements. We present a novel approach combining undirected graphical models with ensemble classifiers to provide 3D geological models from multiple sensors installed in an autonomous drill rig. Drill sensor measurements used for drilling automation, known as measurement-while-drilling (MWD) data, have the potential to provide an estimate of the geological properties of the rocks being drilled. The proposed method maps MWD parameters to rock types while considering spatial relationships, i.e., associating measurements obtained from neighboring regions. We use a conditional random field with local information provided by boosted decision trees to jointly reason about the rock categories of neighboring measurements. To validate the approach, MWD data was collected from a drill rig operating at an iron ore mine. Graphical models of the 3D structure present in real data sets possess a high number of nodes, edges and cycles, making them intractable for exact inference. We provide a comparison of three approximate inference methods to calculate the most probable distribution of class labels. The empirical results demonstrate the benefits of spatial modeling through graphical models to improve classification performance.

The paper describes a method of relation extraction, which is based on parsing the input text using a combination of a generic HPSG-based grammar and a highly focused domain- and relation-specific lexicon. We also show a method of unsupervised acquisition of such a lexicon from a large unlabeled corpus. Together, the methods introduce a novel approach to the “Open IE” task, which is superior in accuracy and in quality of relation identification to the existing approaches.

Socially Assistive Robotics (SAR) defines the research regarding robots which provide assistance to users through social interaction. Socially assistive robots are being studied for therapeutic use with children with autism spectrum disorders (ASD). It has been observed that children with ASD interact with robots differently than with people or toys. This may indicate an intrinsic interest in such machines, which could be applied as a robot augmentation for an intervention for children with ASD. Preliminary studies suggest that robots may act as intrinsically-rewarding social partners for children with autism. However, enabling a robot to understand social behavior, and do so while interacting with the child, is a challenging problem. Children are highly individual and thus technology used for social interaction requires recognition of a wide-range of social behavior. This work addresses the challenge of designing behaviors for socially assistive robots in order to enable them to recognize and appropriately respond to a child’s free-form behavior in unstructured play contexts. The focus on free-form behavior is inspired by and grounded in existing approaches to therapeutic intervention with children with ASD. This model emphasizes creating circles of communication and fostering engagement through play. A key aspect of this approach is to recognize social behavior and use “engagements” to bolster social interaction behavior, and to study the ethical implications of therapeutic robotics applications.

Many important problems can be compactly represented as quantified boolean formulas (QBF) and solved by general QBF solvers. To date QBF solvers have mainly focused on determining whether or not the input QBF is true or false. However, additional important information about an application can be gathered from its QBF formulation. In this paper we demonstrate that a circuit-based QBF solver can be exploited to obtain a Q-Resolution proof of the truth or the falsity of a QBF. QBFs have a natural interpretation as a two person game and our main result is to show how, via a simple computation, the moves for the winning player can be computed directly from these proofs. This result shows that the proof is a representation of the winning strategy. In previous approaches the winning strategy has often been represented in a way that makes it hard to verify. In our approach the correctness of the strategy follows directly from the correctness of the proof, which is relatively easy to verify.

Markov Decision Processes arise as a natural model for many renewable resources allocation problems. In many such problems, high stakes decisions with potentially catastrophic outcomes (such as the collapse of an entire ecosystem) need to be taken by carefully balancing social, economic, and ecologic goals. We introduce a broad class of such MDP models with a risk averse attitude of the decision maker, in order to obtain policies that are more balanced with respect to the welfare of future generations. We prove that they admit a closed form solution that can be efficiently computed. We show an application of the proposed framework to the Pacific Halibut marine fishery, obtaining new and more cautious policies. Our results strengthen findings of related policies from the literature by providing new evidence that a policy based on periodic closures of the fishery should be employed, in place of the one traditionally used that harvests a constant proportion of the stock every year.

This paper presents a plan recognition algorithm for inferring student behavior using virtual science laboratories. The algorithm extends existing plan recognition technology and was integrated with an existing educational application for chemistry. Automatic recognition of students’ activities in virtual laboratories can provide important information to teachers as well as serve as the basis for intelligent tutoring. Student use of virtual laboratories presents several challenges: Students may repeat activities indefinitely, interleave between activities, and engage in exploratory behavior using trial-anderror. The plan recognition algorithm uses a recursive grammar that heuristically generates plans on the fly, taking into account chemical reactions and effects to determine students’ intended high-level actions. The algorithm was evaluated empirically on data obtained from college students using virtual laboratory software for teaching chemistry. Results show that the algorithm was able to (1) infer the plans used by students to construct their models; (2) recognize such key processes as titration and dilution when they occurred in students’ work; (3) identify partial solutions; (4) isolate sequences of actions that were part of a single error.

Deliberation itself can be a computationally costly process and requires This paper shows how belief revision techniques an appropriate intention reconsideration policy which can be used in Defeasible Logic to change rulebased helps the agent to deliberate only when necessary. In this picture, theories characterizing the deliberation process it is still overlooked the problem of changing intentions of cognitive agents. We discuss intention reconsideration not because of the change of beliefs, but because the normative as a strategy to make agents compliant constraints require to do so.

This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. It is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure), which extends previous complexity results. Furthermore, a Fully Polynomial Time Approximation Scheme for MAP in networks with bounded treewidth and bounded number of states per variable is developed. Approximation schemes were thought to be impossible, but here it is shown otherwise under the assumptions just mentioned, which are adopted in most applications.

Extracting the relations that exist between two entities is an important step in numerousWeb-related tasks such as information extraction.A supervised relation extraction system that is trained to extract a particular relation type might not accurately extract a new type of a relation for which it has not been trained.However, it is costly to create training data manually for every new relation type that one might want to extract.We propose a method to adapt an existing relation extraction system to extractnew relation types with minimum supervision. Our proposed method comprises two stages: learning a lower-dimensional projection between different relations, and learning a relational classifier for the target relation type with instance sampling. We evaluate the proposed method using a dataset that contains 2000 instances for 20 different relation types. Our experimental results show that the proposed method achieves a statistically significant macro-average F-score of 62.77. Moreover, the proposed method outperforms numerous baselines and a previously proposed weakly-supervised relation extraction method.