Tina Quincy
Following: 225 - Followers: 6
April 30, 2016 at 11:27PM via Twitter http://twitter.com/evsidorova41178
Logic-based abduction finds important applications in artificial intelligence and related areas. One application example is in finding explanations for observed phenomena. Propositional abduction is a restriction of abduction to the propositional domain, and complexity-wise is in the second level of the polynomial hierarchy. Recent work has shown that exploiting implicit hitting sets and propositional satisfiability (SAT) solvers provides an efficient approach for propositional abduction. This paper investigates this earlier work and proposes a number of algorithmic improvements. These improvements are shown to yield exponential reductions in the number of SAT solver calls. More importantly, the experimental results show significant performance improvements compared to the the best approaches for propositional abduction.
The formalism of quantum theory in Hilbert space has been applied with success to the modeling and explanation of several cognitive phenomena, whereas traditional cognitive approaches were problematical. However, this 'quantum cognition paradigm' was recently challenged by its proven impossibility to simultaneously model 'question order effects' and 'response replicability'. In Part I of this paper we describe sequential dichotomic measurements within an operational and realistic framework for human cognition elaborated by ourselves, and represent them in a quantum-like 'extended Bloch representation' where the Born rule of quantum probability does not necessarily hold. In Part II we apply this mathematical framework to successfully model question order effects, response replicability and unpacking effects, thus opening the way toward quantum cognition beyond Hilbert space.
The research on human cognition has recently benefited from the use of the mathematical formalism of quantum theory in Hilbert space. However, cognitive situations exist which indicate that the Hilbert space structure, and the associated Born rule, would be insufficient to provide a satisfactory modeling of the collected data, so that one needs to go beyond Hilbert space. In Part I of this paper we follow this direction and present a general tension-reduction (GTR) model, in the ambit of an operational and realistic framework for human cognition. In this Part II we apply this non-Hilbertian quantum-like model to faithfully reproduce the probabilities of the 'Clinton/Gore' and 'Rose/Jackson' experiments on question order effects. We also explain why the GTR-model is needed if one wants to deal, in a fully consistent way, with response replicability and unpacking effects.
Advances in ICT are bringing into reality the vision of a large number of uniquely identifiable, interconnected objects and things that gather information from diverse physical environments and deliver the information to a variety of innovative applications and services. These sensing objects and things form the Internet of Things (IoT) that can improve energy and cost efficiency and automation in many different industry fields such as transportation and logistics, health care and manufacturing, and facilitate our everyday lives as well. IoT applications rely on real-time context data and allow sending information for driving the behaviors of users in intelligent environments.
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. We construct a k-nearest neighbor graph by extracting variable associations from the instance to be solved, in order to identify promising pairs of flipping variables in the neighborhood search. We also develop a 4-flip neighborhood local search algorithm that flips four variables alternately along 4-paths or 4-cycles in the k-nearest neighbor graph. We incorporate an efficient incremental evaluation of solutions and an adaptive control of penalty weights into the 4-flip neighborhood local search algorithm. Computational comparison with the latest solvers shows that our algorithm performs effectively for large-scale set covering and partitioning problems.
We review the task of Sentence Pair Scoring, popular in the literature in various forms --- slanted as Answer Sentence Selection, Paraphrasing, Semantic Text Scoring, Next Utterance Ranking, Recognizing Textual Entailment or e.g.\ a component of Memory Networks.
We argue that all such tasks are similar from the model perspective and propose new baselines by comparing the performance of common IR metrics and popular convolutional, recurrent and attention-based neural models across many Sentence Pair Scoring tasks and datasets. We discuss the problem of evaluating randomized models, propose a statistically grounded methodology, and attempt to improve comparisons by releasing new datasets that are much harder than some of the currently used well explored benchmarks.
To address the current research fragmentation in a future-proof way, we introduce a unified open source software framework with easily pluggable models and tasks, allowing easy evaluation of sentence models on a wide range of semantic natural language datasets. This allows us to outline a path towards a universal learned semantic model for machine reading tasks. We support this plan by experiments that demonstrate reusability of trained sentence models across tasks and corpora of very different nature.
We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation based on queries from the agents. The problem has received attention in computer science, mathematics, and economics. It has been a major open problem whether there exists a bounded and discrete envy-free protocol. We resolve the problem by proposing a discrete and bounded envy-free protocol for any number of agents.
This paper presents a procedural generation method that creates visually attractive levels for the Angry Birds game. Besides being an immensely popular mobile game, Angry Birds has recently become a test bed for various artificial intelligence technologies. We propose a new approach for procedurally generating Angry Birds levels using Chinese style and Japanese style building structures. A conducted experiment confirms the effectiveness of our approach with statistical significance.
Tensor factorization is an important approach to multiway data analysis. Compared with popular multilinear methods, nonlinear tensor factorization models are able to capture more complex relationships in data. However, they are computationally expensive and incapable of exploiting the data sparsity. To overcome these limitations, we propose a new tensor factorization model. The model employs a Gaussian process (GP) to capture the complex nonlinear relationships. The GP can be projected to arbitrary sets of tensor elements, and thus can avoid the expensive computation of the Kronecker product and is able to flexibly incorporate meaningful entries for training. Furthermore, to scale up the model to large data, we develop a distributed variational inference algorithm in MapReduce framework. To this end, we derive a tractable and tight variational evidence lower bound (ELBO) that enables efficient parallel computations and high quality inferences. In addition, we design a non-key-value Map-Reduce scheme that can prevent the costly data shuffling and fully use the memory-cache mechanism in fast MapReduce systems such as SPARK. Experiments demonstrate the advantages of our method over existing approaches in terms of both predictive performance and computational efficiency. Moreover, our approach shows a promising potential in the application of Click-Through-Rate (CTR) prediction for online advertising.
Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic sub-instances) provides a means of defining CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances, are decided by arc consistency (AC), a ubiquitous reduction operation in constraint solvers. We provide a characterisation of simple partially-ordered forbidden patterns which have this AC-solvability property. It turns out that BTP is just one of five such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes.
In this paper, we discuss software design issues related to the development of parallel computational intelligence algorithms on multi-core CPUs, using the new Java 8 functional programming features. In particular, we focus on probabilistic graphical models (PGMs) and present the parallelisation of a collection of algorithms that deal with inference and learning of PGMs from data. Namely, maximum likelihood estimation, importance sampling, and greedy search for solving combinatorial optimisation problems. Through these concrete examples, we tackle the problem of defining efficient data structures for PGMs and parallel processing of same-size batches of data sets using Java 8 features. We also provide straightforward techniques to code parallel algorithms that seamlessly exploit multi-core processors. The experimental analysis, carried out using our open source AMIDST (Analysis of MassIve Data STreams) Java toolbox, shows the merits of the proposed solutions.
Modern saturation-based Automated Theorem Provers typically implement the superposition calculus for reasoning about first-order logic with or without equality. Practical implementations of this calculus use a variety of literal selections and term orderings to tame the growth of the search space and help steer proof search. This paper introduces the notion of lookahead selection that estimates (looks ahead) the effect on the search space of selecting a literal. There is also a case made for the use of incomplete selection functions that attempt to restrict the search space instead of satisfying some completeness criteria. Experimental evaluation in the \Vampire\ theorem prover shows that both lookahead selection and incomplete selection significantly contribute to solving hard problems unsolvable by other methods.
This paper is motivated by a series of (related) questions as to whether a computer can have pleasure and pain, what pleasure (and intensity of pleasure) is, and, ultimately, what concepts of emotion are.
To determine what an emotion is, is a matter of conceptualization, namely, understanding and explicitly encoding the concept of emotion as people use it in everyday life. This is a notoriously difficult problem (Frijda, 1986, Fehr \& Russell, 1984). This paper firstly shows why this is a difficult problem by aligning it with the conceptualization of a few other so called semantic primitives such as "EXIST", "FORCE", "BIG" (plus "LIMIT"). The definitions of these thought-to-be-indefinable concepts, given in this paper, show what formal definitions of concepts look like and how concepts are constructed. As a by-product, owing to the explicit account of the meaning of "exist", the famous dispute between Einstein and Bohr is naturally resolved from linguistic point of view. Secondly, defending Frijda's view that emotion is action tendency (or Ryle's behavioral disposition (propensity)), we give a list of emotions defined in terms of action tendency. In particular, the definitions of pleasure and the feeling of beauty are presented.
Further, we give a formal definition of "action tendency", from which the concept of "intensity" of emotions (including pleasure) is naturally derived in a formal fashion. The meanings of "wish", "wait", "good", "hot" are analyzed.
Deep reinforcement learning is the learning of multiple levels of hierarchical representations for reinforcement learning. Hierarchical reinforcement learning focuses on temporal abstractions in planning and learning, allowing temporally-extended actions to be transferred between tasks. In this paper we combine one method for hierarchical reinforcement learning - the options framework - with deep Q-networks (DQNs) through the use of different "option heads" on the policy network, and a supervisory network for choosing between the different options. We show that in a domain where we have prior knowledge of the mapping between states and options, our augmented DQN achieves a policy competitive with that of a standard DQN, but with much lower sample complexity. This is achieved through a straightforward architectural adjustment to the DQN, as well as an additional supervised neural network.
Structured prediction is used in areas such as computer vision and natural language processing to predict structured outputs such as segmentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear program. Because of the complex scoring functions required to obtain accurate predictions, both learning and inference typically require the use of approximate solvers. We propose a theoretical explanation to the striking observation that approximations based on linear programming (LP) relaxations are often tight on real-world instances. In particular, we show that learning with LP relaxed inference encourages integrality of training instances, and that tightness generalizes from train to test data.
We consider data in the form of pairwise comparisons of n items, with the goal of precisely identifying the top k items for some value of k < n, or alternatively, recovering a ranking of all the items. We analyze the Copeland counting algorithm that ranks the items in order of the number of pairwise comparisons won, and show it has three attractive features: (a) its computational efficiency leads to speed-ups of several orders of magnitude in computation time as compared to prior work; (b) it is robust in that theoretical guarantees impose no conditions on the underlying matrix of pairwise-comparison probabilities, in contrast to some prior work that applies only to the BTL parametric model; and (c) it is an optimal method up to constant factors, meaning that it achieves the information-theoretic limits for recovering the top k-subset. We extend our results to obtain sharp guarantees for approximate recovery under the Hamming distortion metric, and more generally, to any arbitrary error requirement that satisfies a simple and natural monotonicity condition.
Group discussions are essential for organizing every aspect of modern life, from faculty meetings to senate debates, from grant review panels to papal conclaves. While costly in terms of time and organization effort, group discussions are commonly seen as a way of reaching better decisions compared to solutions that do not require coordination between the individuals (e.g. voting)---through discussion, the sum becomes greater than the parts. However, this assumption is not irrefutable: anecdotal evidence of wasteful discussions abounds, and in our own experiments we find that over 30% of discussions are unproductive.
We propose a framework for analyzing conversational dynamics in order to determine whether a given task-oriented discussion is worth having or not. We exploit conversational patterns reflecting the flow of ideas and the balance between the participants, as well as their linguistic choices. We apply this framework to conversations naturally occurring in an online collaborative world exploration game developed and deployed to support this research. Using this setting, we show that linguistic cues and conversational patterns extracted from the first 20 seconds of a team discussion are predictive of whether it will be a wasteful or a productive one.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
We describe a sketch interpretation system that detects and classifies clock numerals created by subjects taking the Clock Drawing Test, a clinical tool widely used to screen for cognitive impairments (e.g., dementia). We describe how it balances appearance and context, and document its performance on some 2,000 drawings (about 24K clock numerals) produced by a wide spectrum of patients. We calibrate the utility of different forms of context, describing experiments with Conditional Random Fields trained and tested using a variety of features. We identify context that contributes to interpreting otherwise ambiguous or incomprehensible strokes. We describe ST-slices, a novel representation that enables "unpeeling" the layers of ink that result when people overwrite, which often produces ink impossible to analyze if only the final drawing is examined. We characterize when ST-slices work, calibrate their impact on performance, and consider their breadth of applicability.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
Change detection is the study of detecting changes between two different images of a scene taken at different times. This paper proposes the concept of semantic change detection, which involves intuitively inserting semantic meaning into detected change areas. The problem to be solved consists of two parts, semantic segmentation and change detection. In order to solve this problem and obtain a high-level of performance, we propose an improvement to the hypercolumns representation, hereafter known as hypermaps, which effectively uses convolutional maps obtained from convolutional neural networks (CNNs). We also employ multi-scale feature representation captured by different image patches. We applied our method to the TSUNAMI Panoramic Change Detection dataset, and re-annotated the changed areas of the dataset via semantic classes. The results show that our multi-scale hypermaps provided outstanding performance on the re-annotated TSUNAMI dataset.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
Information and knowledge are transformable into each other. Information transformation into knowledge by the example of rule generation from OWL (Web Ontology Language) ontology has been shown during the development of the SWES (Semantic Web Expert System). The SWES is expected as an expert system for searching OWL ontologies from the Web, generating rules from the found ontologies and supplementing the SWES knowledge base with these rules. The purpose of this paper is to show knowledge transformation into information by the example of ontology generation from rules.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
As a genetics-based machine learning technique, zeroth-level classifier system (ZCS) is based on a discounted reward reinforcement learning algorithm, bucket-brigade algorithm, which optimizes the discounted total reward received by an agent but is not suitable for all multi-step problems, especially large-size ones. There are some undiscounted reinforcement learning methods available, such as R-learning, which optimize the average reward per time step. In this paper, R-learning is used as the reinforcement learning employed by ZCS, to replace its discounted reward reinforcement learning approach, and tournament selection is used to replace roulette wheel selection in ZCS. The modification results in classifier systems that can support long action chains, and thus is able to solve large multi-step problems.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
We provide two distributed confidence ball algorithms for solving linear bandit problems in peer to peer networks with limited communication capabilities. For the first, we assume that all the peers are solving the same linear bandit problem, and prove that our algorithm achieves the optimal asymptotic regret rate of any centralised algorithm that can instantly communicate information between the peers. For the second, we assume that there are clusters of peers solving the same bandit problem within each cluster, and we prove that our algorithm discovers these clusters, while achieving the optimal asymptotic regret rate within each one. Through experiments on several real-world datasets, we demonstrate the performance of proposed algorithms compared to the state-of-the-art.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
An important challenge in neuroevolution is to evolve complex neural networks with multiple modes of behavior. Indirect encodings can potentially answer this challenge. Yet in practice, indirect encodings do not yield effective multimodal controllers. Thus, this paper introduces novel multimodal extensions to HyperNEAT, a popular indirect encoding. A previous multimodal HyperNEAT approach called situational policy geometry assumes that multiple brains benefit from being embedded within an explicit geometric space. However, experiments here illustrate that this assumption unnecessarily constrains evolution, resulting in lower performance. Specifically, this paper introduces HyperNEAT extensions for evolving many brains without assuming geometric relationships between them. The resulting Multi-Brain HyperNEAT can exploit human-specified task divisions to decide when each brain controls the agent, or can automatically discover when brains should be used, by means of preference neurons. A further extension called module mutation allows evolution to discover the number of brains, enabling multimodal behavior with even less expert knowledge. Experiments in several multimodal domains highlight that multi-brain approaches are more effective than HyperNEAT without multimodal extensions, and show that brains without a geometric relation to each other outperform situational policy geometry. The conclusion is that Multi-Brain HyperNEAT provides several promising techniques for evolving complex multimodal behavior.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
Although agreement between annotators has been studied in the past from a statistical viewpoint, little work has attempted to quantify the extent to which this phenomenon affects the evaluation of computer vision (CV) object detection algorithms. Many researchers utilise ground truth (GT) in experiments and more often than not this GT is derived from one annotator's opinion. How does the difference in opinion affect an algorithm's evaluation? Four examples of typical CV problems are chosen, and a methodology is applied to each to quantify the inter-annotator variance and to offer insight into the mechanisms behind agreement and the use of GT. It is found that when detecting linear objects annotator agreement is very low. The agreement in object position, linear or otherwise, can be partially explained through basic image properties. Automatic object detectors are compared to annotator agreement and it is found that a clear relationship exists. Several methods for calculating GTs from a number of annotations are applied and the resulting differences in the performance of the object detectors are quantified. It is found that the rank of a detector is highly dependent upon the method used to form the GT. It is also found that although the STAPLE and LSML GT estimation methods appear to represent the mean of the performance measured using the individual annotations, when there are few annotations, or there is a large variance in them, these estimates tend to degrade. Furthermore, one of the most commonly adopted annotation combination methods--consensus voting--accentuates more obvious features, which results in an overestimation of the algorithm's performance. Finally, it is concluded that in some datasets it may not be possible to state with any confidence that one algorithm outperforms another when evaluating upon one GT and a method for calculating confidence bounds is discussed.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
The distribution of the best arm identification task on the user's devices offers several advantages for application purposes: scalability, reduction of deployment costs and privacy. We propose a distributed version of the algorithm Successive Elimination using a simple architecture based on a single server which synchronizes each task executed on the user's devices. We show that this algorithm is near optimal both in terms of transmitted number of bits and in terms of number of pulls per player. Finally, we propose an extension of this approach to distribute the contextual bandit algorithm Bandit Forest, which is able to finely exploit the user's data while guaranteeing the privacy.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
Protein secondary structure prediction is an important problem in bioinformatics. Inspired by the recent successes of deep neural networks, in this paper, we propose an end-to-end deep network that predicts protein secondary structures from integrated local and global contextual features. Our deep architecture leverages convolutional neural networks with different kernel sizes to extract multiscale local contextual features. In addition, considering long-range dependencies existing in amino acid sequences, we set up a bidirectional neural network consisting of gated recurrent unit to capture global contextual features. Furthermore, multi-task learning is utilized to predict secondary structure labels and amino-acid solvent accessibility simultaneously. Our proposed deep network demonstrates its effectiveness by achieving state-of-the-art performance, i.e., 69.7% Q8 accuracy on the public benchmark CB513, 76.9% Q8 accuracy on CASP10 and 73.1% Q8 accuracy on CASP11. Our model and results are publicly available.
Help us improve arXiv so we can better serve you. Take our user survey (survey closes April 27, 8PM EDT).
"><"<[MALICIOUS INJECTED SCRIPT CODE VULNERABILITY!]> |
Learning novel tasks is a complex cognitive activity requiring the learner to acquire diverse declarative and procedural knowledge. Prior ACT-R models of acquiring task knowledge from instruction focused on learning procedural knowledge from declarative instructions encoded in semantic memory. In this paper, we identify the requirements for designing compu- tational models that learn task knowledge from situated task- oriented interactions with an expert and then describe and evaluate a model of learning from situated interactive instruc- tion that is implemented in the Soar cognitive architecture.
This document provides the foundations behind the functionality provided by the $\rho$G library (http://ift.tt/1SKjhUe), focusing on the basic operations the library provides: subsumption, refinement of directed labeled graphs, and distance/similarity assessment between directed labeled graphs. $\rho$G development was initially supported by the National Science Foundation, by the EAGER grant IIS-1551338.