Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press 【DBLP Link】
【Paper Link】 【Pages】:
【Authors】: Carlos Ansótegui ; Maria Luisa Bonet ; Jordi Levy
【Abstract】: We present and implement a Weighted Partial MaxSAT solver based on successive calls to a SAT solver. We prove the correctness of our algorithm and compare our solver with other Weighted Partial MaxSAT solvers.
【Keywords】: MaxSAT solvers
【Paper Link】 【Pages】:
【Authors】: Ignacio Araya ; Gilles Trombettoni ; Bertrand Neveu
【Abstract】: We propose in this paper a new interval constraint propagation algorithm, called MOnotonic Hull Consistency (Mohc), that exploits monotonicity of functions. The propagation is standard, but the Mohc-Revise procedure, used to filter/contract the variable domains w.r.t. an individual constraint, uses monotonic versions of the classical HC4-Revise and BoxNarrow procedures. Mohc-Revise appears to be the first adaptive revise procedure ever proposed in (interval) constraint programming. Also, when a function is monotonic w.r.t. every variable, Mohc-Revise is proven to compute the optimal/sharpest box enclosing all the solutions of the corresponding constraint (hull consistency). Very promising experimental results suggest that Mohc has the potential to become an alternative to the state-of-the-art HC4 and Box algorithms.
【Keywords】: constraint propagation; intervals; monotonicity
【Paper Link】 【Pages】:
【Authors】: Gilles Audemard ; George Katsirelos ; Laurent Simon
【Abstract】: Modern complete SAT solvers almost uniformly implement variations of the clause learning framework introduced by Grasp and Chaff. The success of these solvers has been theoretically explained by showing that the clause learning framework is an implementation of a proof system which is as poweful as resolution. However, exponential lower bounds are known for resolution, which suggests that significant advances in SAT solving must come from implementations of more powerful proof systems. We present a clause learning SAT solver that uses extended resolution. It is based on a restriction of the application of the extension rule. This solver outperforms existing solvers on application instances from recent SAT competitions as well as on instances that are provably hard for resolution.
【Keywords】: satisfiability; resolution
【Paper Link】 【Pages】:
【Authors】: Russell Bent ; Alan Berscheid ; G. Loren Toole
【Abstract】: Within the electric power literature the transmission expansion planning problem (TNEP) refers to the problem of how to upgrade an electric power network to meet future demands. As this problem is a complex, non-linear, and non-convex optimization problem, researchers have traditionally focused on approximate models of power flows. Existing approaches are often tightly coupled to the approximation choice. Until recently, these approximations have produced results that are straight-forward to adapt to the more complex (real) problem. However, the power grid is evolving towards a state where the adaptations are no longer easy (e.g. large amounts of limited control, renewable generation) that necessitates new optimization techniques. In this paper, we propose a local search variation of the powerful Limited Discrepancy Search (LDLS) that encapsulates the complexity of power flows in a black box that may be queried for information about the quality of a proposed expansion. This allows the development of a new optimization algorithm that is independent of the underlying power model.
【Keywords】: transmission network expansion planning;tnep;local search; simulation optimization
【Paper Link】 【Pages】:
【Authors】: Christian Bessiere ; George Katsirelos ; Nina Narodytska ; Claude-Guy Quimper ; Toby Walsh
【Abstract】: We study propagation algorithms for the conjunction of two AllDifferent constraints. Solutions of an AllDifferent constraint can be seen as perfect matchings on the variable/value bipartite graph. Therefore, we investigate the problem of finding simultaneous bipartite matchings. We present an extension of the famous Hall theorem which characterizes when simultaneous bipartite matchings exists. Unfortunately, finding such matchings is NP-hard in general. However, we prove a surprising result that finding a simultaneous matching on a convex bipartite graph takes just polynomial time. Based on this theoretical result, we provide the first polynomial time bound consistency algorithm for the conjunction of two AllDifferent constraints. We identify a pathological problem on which this propagator is exponentially faster compared to existing propagators. Our experiments show that this new propagator can offer significant benefits over existing methods.
【Keywords】: constraint programming; constraint satisfaction; computational complexity; global constraints
【Paper Link】 【Pages】:
【Authors】: Teresa Maria Breyer ; Richard E. Korf
【Abstract】: This paper analyzes the performance of IDA using additive heuristics. We show that the reduction in the number of nodes expanded using multiple independent additive heuristics is the product of the reductions achieved by the individual heuristics. First, we formally state and prove this result on unit edge-cost undirected graphs with a uniform branching factor. Then, we empirically verify it on a model of the 4-peg Towers of Hanoi problem. We also run experiments on the multiple sequence alignment problem showing more general applicability to non-unit edge-cost directed graphs. Then, we extend an existing model to predict the performance of IDA with a single pattern database to independent additive disjoint pattern databases. This is the first analysis of the performance of independent additive heuristics.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Teresa Maria Breyer ; Richard E. Korf
【Abstract】: We present a new technique to compress pattern databases to provide consistent heuristics without loss of information. We store the heuristic estimate modulo three, requiring only two bits per entry or in a more compact representation, only 1.6 bits. This allows us to store a pattern database with more entries in the same amount of memory as an uncompressed pattern database. These compression techniques are most useful where lossy compression using cliques or their generalization is not possible or where adjacent entries in the pattern database are not highly correlated. We compare both techniques to the best existing compression methods for the Top-Spin puzzle, Rubik's cube, the 4-peg Towers of Hanoi problem, and the 24 puzzle. Under certain conditions, our best implementations for the Top-Spin puzzle and Rubik's cube outperform the respective state of the art solvers by a factor of four.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Shaowei Cai ; Kaile Su ; Qingliang Chen
【Abstract】: A number of algorithms have been proposed for the Minimum Vertex Cover problem. However, they are far from satisfactory, especially on hard instances. In this paper, we introduce Edge Weighting Local Search (EWLS), a new local search algorithm for the Minimum Vertex Cover problem. EWLS is based on the idea of extending a partial vertex cover into a vertex cover. A key point of EWLS is to find a vertex set that provides a tight upper bound on the size of the minimum vertex cover. To this purpose, EWLS employs an iterated local search procedure, using an edge weighting scheme which updates edge weights when stuck in local optima. Moreover, some sophisticated search strategies have been taken to improve the quality of local optima. Experimental results on the broadly used DIMACS benchmark show that EWLS is competitive with the current best heuristic algorithms, and outperforms them on hard instances. Furthermore, on a suite of difficult benchmarks, EWLS delivers the best results and sets a new record on the largest instance.
【Keywords】: Minimum Vertex Cover; Local Search; Edge Weighting
【Paper Link】 【Pages】:
【Authors】: Patrick Eyerich ; Thomas Keller ; Malte Helmert
【Abstract】: We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost. We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.
【Keywords】: Canadian Traveler's Problem; UCT; hindsight optimization
【Paper Link】 【Pages】:
【Authors】: Ariel Felner ; Carsten Moldenhauer ; Nathan R. Sturtevant ; Jonathan Schaeffer
【Abstract】: On the surface, bidirectional search (BDS) is an attractive idea with the potential for significant asymptotic reductions in search effort. However, the results in practice often fall far short of expectations. We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Searc (SFBDS). Unlike traditional BDS which keeps two frontiers, SFBDS uses a single frontier. Each node in the tree can be seen as an independent task of finding the shortest path between the current start and current goal. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. Theoretical results give insights as to when this approach will work and experimental data validates the algorithm for a broad range of domains.
【Keywords】: search;heuristics
【Paper Link】 【Pages】:
【Authors】: Fedor V. Fomin ; Daniel Lokshtanov ; Venkatesh Raman ; Saket Saurabh
【Abstract】: We present a fast local search algorithm that finds an improved solution (if there is any) in the k-exchange neighborhood of the given solutionto an instance of Weighted Feedback Arc Set in Tournaments. More precisely,given an arc weighted tournament T on n vertices and a feedback arc set F (a set of arcs whose deletion from T turns it into a directed acyclic graph), our algorithm decides in time O(2 o ( k ) n log n) if there is a feedback arc set of smaller weight and that differs from F in at most k arcs. To our knowledge this is the first algorithm searching the k -exchange neighborhood of an NP-complete problem that runs in (parameterized) subexponential time. Using this local search algorithm for Weighted Feedback Arc Set in Tournaments, we obtain subexponential time algorithms for a local search variant of Kemeny Ranking — a problem in social choice theory and of One-Sided Cross Minimization — a problem in graph drawing.
【Keywords】: Constraints; Satisfiability; Search; Social Choice;
【Paper Link】 【Pages】:
【Authors】: Alexandra Goultiaeva ; Fahiem Bacchus
【Abstract】: Search based solvers for Quantified Boolean Formulas (QBF) have adapted the SAT solver techniques of unit propagation and clause learning to prune falsifying assignments. The technique of cube learning has been developed to help them prune satisfying assignments. Cubes, however, have not been able to achieve the same degree of effectiveness as clauses. In this paper we demonstrate how a circuit representation for QBF can support the propagation of dual truth values. The dual values support the identical techniques of unit propagation and clause learning, except now it is satisfying assignments rather than falsifying assignments that are pruned. Dual value propagation thus exploits the circuit representation and the duality of QBF formulas so that the same effective SAT techniques can now be used to prune both falsifying and satisfyingly assignments. We show empirically that dual propagation yields significantperformance improvements and advances the state of the art in QBF solving.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Marijn Heule ; Toby Walsh
【Abstract】: We define the concept of an internal symmetry. This is a symmety within a solution of a constraint satisfaction problem. We compare this to solution symmetry, which is a mapping between different solutions of the same problem. We argue that we may be able to exploit both types of symmetry when finding solutions. We illustrate the potential of exploiting internal symmetries on two benchmark domains: Van der Waerden numbers and graceful graphs. By identifying internal symmetries we are able to extend the state of the art in both cases.
【Keywords】: Symmetry; constraint programming; constraint satisfaction; graceful labelling; Van der Waerden
【Paper Link】 【Pages】:
【Authors】: Eric Huang ; Richard E. Korf
【Abstract】: The rectangle packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. We propose two new benchmarks, one where the orientation of the rectangles is fixed and one where it is free, that include rectangles of various aspect ratios. The new benchmarks avoid certain properties of easy instances, which we identify as instances where rectangles have dimensions in common or where a few rectangles occupy most of the area. Our benchmarks are much more difficult for the previous state-of-the-art solver, requiring orders of magnitude more time, compared to similar-sized instances from a popular benchmark consisting only of squares. On the new benchmarks, we improve upon the previous strategy used to handle dominance conditions, we define a variable order over non-square rectangles that generalizes previous strategies, and we present a way to adjust the sizes of intervals of values for each rectangle's x-coordinates. Using these techniques together, we can solve the new oriented benchmark about 500 times faster, and the new unoriented benchmark about 40 times faster than the previous state-of-the-art.
【Keywords】: search; constraint satisfaction; scheduling; rectangle packing
【Paper Link】 【Pages】:
【Authors】: Ruoyun Huang ; Yixin Chen ; Weixiong Zhang
【Abstract】: Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from the STRIPS formalism. We introduce a novel SAT encoding scheme based on the SAS+ formalism. It exploits the structural information in the SAS+ formalism, resulting in more compact SAT instances and reducing the number of clauses by up to 50 fold. Our results show that this encoding scheme improves upon the STRIPS-based encoding, in terms of both time and memory efficiency.
【Keywords】: Planning; Satisfiability; Encoding;
【Paper Link】 【Pages】:
【Authors】: Tomoyuki Kaneko
【Abstract】: The depth first proof number search (df-pn) is an effective and popular algorithm for solving and-or tree problems by using proof and disproof numbers. This paper presents a simple but effective parallelization of the df-pn search algorithm for a shared-memory system. In this parallelization, multiple agents autonomously conduct the df-pn with a shared transposition table. For effective cooperation of agents, virtual proof and disproof numbers are introduced for each node, which is an estimation of future proof and disproof numbers by using the number of agents working on the node's descendants as a possible increase. Experimental results on large checkmate problems in shogi, which is a popular chess variant in Japan, show that reasonable increases in speed were achieved with small overheads in memory.
【Keywords】: df-pn; game programming; shogi
【Paper Link】 【Pages】:
【Authors】: Shant Karakashian ; Robert J. Woodward ; Christopher G. Reeson ; Berthe Y. Choueiry ; Christian Bessiere
【Abstract】: Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. In this paper, we study the relational consistency property R ( ,m ) C, which is equivalent to m-wise consistency proposed in relational databases. We also define wR ( ,m ) C, a weaker variant of this property. We propose an algorithm for enforcing these properties on a Constraint Satisfaction Problem by tightening the existing relations and without introducing new ones. We empirically show that wR(*,m)C solves in a backtrack-free manner all the instances of some CSP benchmark classes, thus hinting at the tractability of those classes.
【Keywords】: CSP; non-binary constraints; local consistency; relational consistency; search; backtracking
【Paper Link】 【Pages】:
【Authors】: Akihiro Kishimoto
【Abstract】: Depth-first proof-number search (df-pn) is powerful AND/OR tree search to solve positions in games. However, df-pn has a notorious problem of infinite loops when applied to domains with repetitions. Df-pn(r) cures it by ignoring proof and disproof numbers that may lead to infinite loops. This paper points out that df-pn(r) has a serious issue of underestimating proof and disproof numbers, while it also suffers from the overestimation problem occurring in directed acyclic graph. It then presents two practical solutions to these problems. While bypassing infinite loops, the threshold controlling algorithm (TCA) solves the underestimation problem by increasing the thresholds of df-pn. The source node detection algorithm (SNDA) detects the cause of overestimation and modifies the computation of proof and disproof numbers. Both TCA and SNDA are implemented on top of df-pn to solve tsume-shogi (checkmating problem in Japanese chess). Results show that df-pn with TCA and SNDA is far superior to df-pn(r). Our tsume-shogi solver is able to solve several difficult positions previously unsolved by any other solvers.
【Keywords】: AND/OR tree search;df-pn;TCA;SNDA
【Paper Link】 【Pages】:
【Authors】: Bradford John Larsen ; Ethan Burns ; Wheeler Ruml ; Robert Holte
【Abstract】: In problem domains where an informative heuristic evaluation function is not known or not easily computed, abstraction can be used to derive admissible heuristic values. Optimal path lengths in the abstracted problem are consistent heuristic estimates for the original problem. Pattern databases are the traditional method of creating such heuristics, but they exhaustively compute costs for all abstract states and are thus usually appropriate only when all instances share the same single goal state. Hierarchical heuristic search algorithms address these shortcomings by searching for paths in the abstract space on an as-needed basis. However, existing hierarchical algorithms search less efficiently than pattern database constructors: abstract nodes may be expanded many times during the course of a base-level search. We present a novel hierarchical heuristic search algorithm, called Switchback, that uses an alternating direction of search to avoid abstract node re-expansions. This algorithm is simple to implement and demonstrates superior performance to existing hierarchical heuristic search algorithms on several standard benchmarks.
【Keywords】: heuristic search; abstraction; pattern database; problem solving
【Paper Link】 【Pages】:
【Authors】: Jimmy Ho-Man Lee ; Ka Lun Leung
【Abstract】: Weighted Constraint Satisfaction is made practical by powerful consistency techniques, such as AC, FDAC and EDAC, which reduce search space effectively and efficiently during search, but they are designed for only binary and ternary constraints. To allow soft global constraints, usually of high arity, to enjoy the same benefits, Lee and Leung give polynomial time algorithms to enforce generalized AC (GAC) and FDAC (FDGAC) for projection-safe soft non-binary constraints. Generalizing the stronger EDAC is less straightforward. In this paper, we first reveal the oscillation problem when enforcing EDAC on constraints sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC and generalize it to weak EDGAC for non-binary constraints. Weak EDGAC is stronger than FDGAC and GAC, but weaker than VAC and soft k -consistency for k > 2. We also show that weak EDGAC* can be enforced in polynomial time for projection-safe constraints. Extensive experimentation confirms the efficiency of our proposal.
【Keywords】: WCSP; Global Constraints; Soft Constraints
【Paper Link】 【Pages】:
【Authors】: Chu Min Li ; Zhe Quan
【Abstract】: State-of-the-art branch-and-bound algorithms for the maximum clique problem (Maxclique) frequently use an upper bound based on a partition P of a graph into independent sets for a maximum clique of the graph, which cannot be very tight for imperfect graphs. In this paper we propose a new encoding from Maxclique into MaxSAT and use MaxSAT technology to improve the upper bound based on the partition P. In this way, the strength of specific algorithms for Maxclique in partitioning a graph and the strength of MaxSAT technology in propositional reasoning are naturally combined to solve Maxclique. Experimental results show that the approach is very effective on hard random graphs and on DIMACS Maxclique benchmarks, and allows to close an open DIMACS problem.
【Keywords】: Branch-and-Bound; Maxclique; MaxSAT; Exact Algorithm for Maxclique
【Paper Link】 【Pages】:
【Authors】: Jeffrey Richard Long ; Nathan R. Sturtevant ; Michael Buro ; Timothy Furtak
【Abstract】: Perfect Information Monte Carlo (PIMC) search is a practical technique for playing imperfect information games that are too large to be optimally solved. Although PIMC search has been criticized in the past for its theoretical deficiencies, in practice it has often produced strong results in a variety of domains. In this paper, we set out to resolve this discrepancy. The contributions of the paper are twofold. First, we use synthetic game trees to identify game properties that result in strong or weak performance for PIMC search as compared to an optimal player. Second, we show how these properties can be detected in real games, and demonstrate that they do indeed appear to be good predictors of the strength of PIMC search. Thus, using the tools established in this paper, it should be possible to decide a priori whether PIMC search will be an effective approach to new and unexplored games.
【Keywords】: Games; TreeSearch; Planning
【Paper Link】 【Pages】:
【Authors】: Yuri Malitsky ; Meinolf Sellmann ; Radoslaw Szymanek
【Abstract】: We present a highly efficient incremental algorithm for propagating bounded knapsack constraints. Our algorithm is based on the sublinear filtering algorithm for binary knapsack constraints by Katriel et al. and achieves similar speed-ups of one to two orders of magnitude when compared with its linear-time counterpart. We also show that the representation of bounded knapsacks as binary knapsacks leads to ineffective filtering behavior. Experiments on standard knapsack benchmarks show that the new algorithm significantly outperforms existing methods for handling bounded knapsack constraints.
【Keywords】: bounded knapsack; filtering
【Paper Link】 【Pages】:
【Authors】: Alex Nash ; Sven Koenig ; Craig A. Tovey
【Abstract】: Grids with blocked and unblocked cells are often used to represent continuous 2D and 3D environments in robotics and video games. The shortest paths formed by the edges of 8-neighbor 2D grids can be up to 8% longer than the shortest paths in the continuous environment. Theta typically finds much shorter paths than that by propagating information along graph edges (to achieve short runtimes) without constraining paths to be formed by graph edges (to find short "any-angle" paths). We show in this paper that the shortest paths formed by the edges of 26-neighbor 3D grids can be 13% longer than the shortest paths in the continuous environment, which highlights the need for smart path planning algorithms in 3D. Theta can be applied to 3D grids in a straight-forward manner, but it performs a line-of-sight check for each unexpanded visible neighbor of each expanded vertex and thus it performs many more line-of-sight checks per expanded vertex on a 26-neighbor 3D grid than on an 8-neighbor 2D grid. We therefore introduce Lazy Theta, a variant of Theta which uses lazy evaluation to perform only one line-of-sight check per expanded vertex (but with slightly more expanded vertices). We show experimentally that Lazy Theta finds paths faster than Theta on 26-neighbor 3D grids, with one order of magnitude fewer line-of-sight checks and without an increase in path length.
【Keywords】: A, Any-Angle Search, Grids, Path Planning, Heuristic Search, Robotics, Theta, Video Games
【Paper Link】 【Pages】:
【Authors】: Nir Pochter ; Aviv Zohar ; Jeffrey S. Rosenschein ; Ariel Felner
【Abstract】: In various domains, such as computer games, robotics, and transportation networks, shortest paths may need to be found quickly. Search time can be significantly reduced if it is known which parts of the graph include ``swamps''---areas that cannot lie on the only available shortest path, and can thus safely be pruned during search. We introduce an algorithm for detecting hierarchies of swamps, and exploiting them. Experiments support our claims of improved efficiency, showing significant reduction in search time.
【Keywords】: Swamps; Search; A*; Heuristic Search
【Paper Link】 【Pages】:
【Authors】: Anika Schumann ; Jinbo Huang ; Martin Sachenbacher
【Abstract】: The goal of testing is to discriminate between multiple hypotheses about a system - for example, different fault diagnoses - by applying input patterns and verifying or falsifying the hypotheses from the observed outputs. Definitely discriminating tests (DDTs) are those input patterns that are guaranteed to discriminate between different hypotheses of non-deterministic systems. Finding DDTs is important in practice, but can be very expensive. Even more challenging is the problem of finding a DDT that minimizes the cost of the testing process, i.e., an input pattern that can be most cheaply enforced and that is a DDT. This paper addresses both problems. We show how we can transform a given problem into a Boolean structure in decomposable negation normal form (DNNF), and extract from it a Boolean formula whose models correspond to DDTs. This allows us to harness recent advances in both knowledge compilation and satisfiability for efficient and scalable DDT computation in practice. Furthermore, we show how we can generate a DNNF structure compactly encoding all DDTs of the problem and use it to obtain a cost-optimal DDT in time linear in the size of the structure. Experimental results from a real-world application show that our method can compute DDTs in less than 1 second for instances that were previously intractable, and cost-optimal DDTs in less than 20 seconds where previous approaches could not even compute an arbitrary DDT.
【Keywords】: Diagnosis, Model-based Reasoning, Constraints, Satisfiability
【Paper Link】 【Pages】:
【Authors】: Bryan Silverthorn ; Risto Miikkulainen
【Abstract】: Different solvers for computationally difficult problems such as satisfiability (SAT) perform best on different instances. Algorithm portfolios exploit this phenomenon by predicting solvers' performance on specific problem instances, then shifting computational resources to the solvers that appear best suited. This paper develops a new approach to the problem of making such performance predictions: natural generative models of solver behavior. Two are proposed, both following from an assumption that problem instances cluster into latent classes: a mixture of multinomial distributions, and a mixture of Dirichlet compound multinomial distributions. The latter model extends the former to capture burstiness, the tendency of solver outcomes to recur. These models are integrated into an algorithm portfolio architecture and used to run standard SAT solvers on competition benchmarks. This approach is found competitive with the most prominent existing portfolio, SATzilla, which relies on domain-specific, hand-selected problem features; the latent class models, in contrast, use minimal domain knowledge. Their success suggests that these models can lead to more powerful and more general algorithm portfolio methods.
【Keywords】: SAT; satisfiability; portfolio methods; latent class models
【Paper Link】 【Pages】:
【Authors】: Trevor Scott Standley
【Abstract】: In cooperative pathfinding problems, non-interfering paths that bring each agent from its current state to its goal state must be planned for multiple agents. We present the first practical, admissible, and complete algorithm for solving problems of this kind. First, we propose a technique called operator decomposition, which can be used to reduce the branching factors of many search algorithms, including algorithms for cooperative pathfinding. We then show how a type of independence common in instances of cooperative pathfinding problems can be exploited. Next, we take the idea of exploiting independent subproblems further by adding improvements that allow the algorithm to recognize many more cases of such independence. Finally, we show empirically that these techniques drastically improve the performance of the standard admissible algorithm for the cooperative pathfinding problem, and that their combination results in a complete algorithm capable of optimally solving relatively large problems in milliseconds.
【Keywords】: Admissible; Heuristic Search; Cooperative Pathfinding; Multi-Agent Pathfinding; Multi-robot Pathfinding;
【Paper Link】 【Pages】:
【Authors】: David H. Stern ; Horst Samulowitz ; Ralf Herbrich ; Thore Graepel ; Luca Pulina ; Armando Tacchella
【Abstract】: We consider the task of assigning experts from a portfolio of specialists in order to solve a set of tasks. We apply a Bayesian model which combines collaborative filtering with a feature-based description of tasks and experts to yield a general framework for managing a portfolio of experts. The model learns an embedding of tasks and problems into a latent space in which affinity is measured by the inner product. The model can be trained incrementally and can track non-stationary data, tracking potentially changing expert and task characteristics. The approach allows us to use a principled decision theoretic framework for expert selection, allowing the user to choose a utility function that best suits their objectives. The model component for taking into account the performance feedback data is pluggable, allowing flexibility. We apply the model to manage a portfolio of algorithms to solve hard combinatorial problems. This is a well studied area and we demonstrate a large improvement on the state of the art in one domain (constraint solving) and in a second domain (combinatorial auctions) created a portfolio that performed significantly better than any single algorithm.
【Keywords】: Algorithm Portfolios;Recommender System;Machine Learning;Expert Portfolios;QBF;Linear Programming
【Paper Link】 【Pages】:
【Authors】: Roni Stern ; Tamar Kulberis ; Ariel Felner ; Robert Holte
【Abstract】: We present an algorithm that exploits the complimentary benefits of best-first search (BFS) and depth-first search (DFS) by performing limited DFS lookaheads from the frontier of BFS. We show that this continuum requires significantly less memory than BFS. In addition, a time speedup is also achieved when choosing the lookahead depth correctly. We demonstrate this idea for breadth-first search and for A*. Additionally, we show that when using inconsistent heuristics, Bidirectional Pathmax (BPMX), can be implemented very easily on top of the lookahead phase. Experimental results on several domains demonstrate the benefits of all our ideas.
【Keywords】: Heuristic search; Lookahead; Best-first search
【Paper Link】 【Pages】:
【Authors】: Dejian Tu ; Songshan Guo ; Hu Qin ; Wee-Chong Oon ; Andrew Lim
【Abstract】: The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are represented by vertex lists in existing literature. However, when the TSPPD requires that the loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a variable neighbourhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Experiments show that our VNS heuristic is superior to the current best heuristics for TSPPDL in terms of both solution quality and computing time.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Suguru Ueda ; Atsushi Iwasaki ; Makoto Yokoo ; Marius-Calin Silaghi ; Katsutoshi Hirayama ; Toshihiro Matsui
【Abstract】: Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Coalition Structure generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a Coalition Structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, one might assume that the computational costs required in this approach would be too expensive, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve n-th power of 2 DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS with quality guarantees. More specifically, we develop an algorithm with parameter k that can find a CS whose social surplus is at least max(k/(w+1), 2k/n) of the optimal CS, where w is the tree width of a constraint graph. When k=1, the complexity of this algorithm is about the same as solving just one DCOP. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing an efficient CSG algorithm with quality guarantees.
【Keywords】: Coalition Structure Generation; Distributed Constraint Optimization Problem; Multi-agent System
【Paper Link】 【Pages】:
【Authors】: Michael Veksler ; Ofer Strichman
【Abstract】: PCS is a CSP solver that can produce a machine-checkable deductive proof in case it decides that the input problem is unsatisfiable. The roots of the proof may be nonclausal constraints, whereas the rest of the proof is based on resolution of signed clauses, ending with the empty clause. PCS uses parameterized, constraint-specific inference rules in order to bridge between the nonclausal and the clausal parts of the proof. The consequent of each such rule is a signed clause that is 1) logically implied by the nonclausal premise, and 2) strong enough to be the premise of the consecutive proof steps. The resolution process itself is integrated in the learning mechanism, and can be seen as a generalization to CSP of a similar solution that is adopted by competitive SAT solvers.
【Keywords】: csp;proof;cnf
【Paper Link】 【Pages】:
【Authors】: Lin Xu ; Holger Hoos ; Kevin Leyton-Brown
【Abstract】: The AI community has achieved great success in designing high-performance algorithms for hard combinatorial problems, given both considerable domain knowledge and considerable effort by human experts. Two influential methods aim to automate this process: automated algorithm configuration and portfolio-based algorithm selection. The former has the advantage of requiring virtually no domain knowledge, but produces only a single solver; the latter exploits per-instance variation, but requires a set of relatively uncorrelated candidate solvers. Here, we introduce Hydra, a novel technique for combining these two methods, thereby realizing the benefits of both. Hydra automatically builds a set of solvers with complementary strengths by iteratively configuring new algorithms. It is primarily intended for use in problem domains for which an adequate set of candidate solvers does not already exist. Nevertheless, we tested Hydra on a widely studied domain, stochastic local search algorithms for SAT, in order to characterize its performance against a well-established and highly competitive baseline. We found that Hydra consistently achieved major improvements over the best existing individual algorithms, and always at least roughly matched — and indeed often exceeded — the performance of the best portfolios of these algorithms.
【Keywords】: automated algorithm design; portfolio-based algorithm selection; automated algorithm configuration; SAT; stochastic local search
【Paper Link】 【Pages】:
【Authors】: Junping Zhou ; Minghao Yin ; Chunguang Zhou
【Abstract】: The rigorous theoretical analyses of algorithms for #SAT have been proposed in the literature. As we know, previous algorithms for solving #SAT have been analyzed only regarding the number of variables as the parameter. However, the time complexity for solving #SAT instances depends not only on the number of variables, but also on the number of clauses. Therefore, it is significant to exploit the time complexity from the other point of view, i.e. the number of clauses. In this paper, we present algorithms for solving #2-SAT and #3-SAT with rigorous complexity analyses using the number of clauses as the parameter. By analyzing the algorithms, we obtain the new worst-case upper bounds O(1.1892m) for #2-SAT and O(1.4142m) for #3-SAT, where m is the number of clauses.
【Keywords】: model counting; upper bound; complexity analyses; #SAT.
【Paper Link】 【Pages】:
【Authors】: Bin Cao ; Dou Shen ; Kuansan Wang ; Qiang Yang
【Abstract】: Analyzing clickthrough log data is important for improving search performance as well as understanding user behaviors. In this paper, we propose a novel collaborative ranking model to tackle two difficulties in analyzing clickthrough log. First, previous studies have shown that users tend to click top-ranked results even they are less relevant. Therefore, we use pairwise ranking relation to avoid the position bias in clicks. Second, since click data are extremely sparse with respect to each query or user, we construct a collaboration model to eliminate the sparseness problem. We also find that the proposed model and previous popular used click-based models address different aspects of clickthrough log data. We further propose a hybrid model that can achieve significant improvement compared to the baselines on a large-scale real world dataset.
【Keywords】: clickthrough log; collaborative ranking
【Paper Link】 【Pages】:
【Authors】: Weike Pan ; Evan Wei Xiang ; Nathan Nan Liu ; Qiang Yang
【Abstract】: Data sparsity is a major problem for collaborative filtering (CF) techniques in recommender systems, especially for new users and items. We observe that, while our target data are sparse for CF systems, related and relatively dense auxiliary data may already exist in some other more mature application domains. In this paper, we address the data sparsity problem in a target domain by transferring knowledge about both users and items from auxiliary data sources. We observe that in different domains the user feedbacks are often heterogeneous such as ratings vs. clicks. Our solution is to integrate both user and item knowledge in auxiliary data sources through a principled matrix-based transfer learning framework that takes into account the data heterogeneity. In particular, we discover the principle coordinates of both users and items in the auxiliary data matrices, and transfer them to the target domain in order to reduce the effect of data sparsity. We describe our method, which is known as coordinate system transfer or CST, and demonstrate its effectiveness in alleviating the data sparsity problem in collaborative filtering. We show that our proposed method can significantly outperform several state-of-the-art solutions for this problem.
【Keywords】: transfer learning; collaborative filtering
【Paper Link】 【Pages】:
【Authors】: Vincent Wenchen Zheng ; Bin Cao ; Yu Zheng ; Xing Xie ; Qiang Yang
【Abstract】: With the increasing popularity of location tracking services such as GPS, more and more mobile data are being accumulated. Based on such data, a potentially useful service is to make timely and targeted recommendations for users on places where they might be interested to go and activities that they are likely to conduct. For example, a user arriving in Beijing might wonder where to visit and what she can do around the Forbidden City. A key challenge for such recommendation problems is that the data we have on each individual user might be very limited, while to make useful and accurate recommendations, we need extensive annotated location and activity information from user trace data. In this paper, we present a new approach, known as user-centered collaborative location and activity filtering (UCLAF), to pull many users’ data together and apply collaborative filtering to find like-minded users and like-patterned activities at different locations. We model the userlocation- activity relations with a tensor representation, and propose a regularized tensor and matrix decomposition solution which can better address the sparse data problem in mobile information retrieval. We empirically evaluate UCLAF using a real-world GPS dataset collected from 164 users over 2.5 years, and showed that our system can outperform several state-of-the-art solutions to the problem.
【Keywords】: collaborative filtering; mobile recommendation
【Paper Link】 【Pages】:
【Authors】: Alessandro Artale ; Roman Kontchakov ; Vladislav Ryzhikov ; Michael Zakharyaschev
【Abstract】: We design minimal temporal description logics that are capa- ble of expressing various aspects of temporal conceptual data models and investigate their computational complexity. We show that, depending on the required types of temporal and atemporal constraints, the satisfiability problem for temporal knowledge bases in the resulting logics can be NLOGSPACE-, NP- and PSPACE-complete, as well as undecidable.
【Keywords】: Description Logic; Temporal Logic; Conceptual Data Model
【Paper Link】 【Pages】:
【Authors】: Vernon Asuncion ; Fangzhen Lin ; Yan Zhang ; Yi Zhou
【Abstract】: In this paper, we propose a translation from normal first-order logic programs under the answer set semantics to first-order theories on finite structures. Specifically, we introduce ordered completions which are modifications of Clark's completions with some extra predicates added to keep track of the derivation order, and show that on finite structures, classical models of the ordered-completion of a normal logic program correspond exactly to the answer sets (stable models) of the logic program.
【Keywords】: logic programming, answer set programming, ordered completion, finite structure
【Paper Link】 【Pages】:
【Authors】: Vaishak Belle ; Gerhard Lakemeyer
【Abstract】: Approaches to reasoning about knowledge in imperfect information games typically involve an exhaustive description of the game, the dynamics characterized by a tree and the incompleteness in knowledge by information sets. Such specifications depend on a modeler's intuition, are tedious to draft and vague on where the knowledge comes from. Also, formalisms proposed so far are essentially propositional, which, at the very least, makes them cumbersome to use in realistic scenarios. In this paper, we propose to model imperfect information games in a new multi-agent epistemic variant of the situation calculus. By using the concept of only-knowing, the beliefs and non-beliefs of players after any sequence of actions, sensing or otherwise, can be characterized as entailments in this logic. We show how de re vs. de dicto belief distinctions come about in the framework. We also obtain a regression theorem for multi-agent beliefs, which reduces reasoning about beliefs after actions to reasoning about beliefs in the initial situation.
【Keywords】: Knowledge Representation Languages; Game Theory; Nonmonotonic Reasoning; Action, Change, and Causality; Cognitive Robotics
【Paper Link】 【Pages】:
【Authors】: Meghyn Bienvenu ; Hélène Fargier ; Pierre Marquis
【Abstract】: In this paper, we study the knowledge compilation task for propositional epistemic logic S5. We first extend many of the queries and transformations considered in the classical knowledge compilation map to S5. We then show that the notion of disjunctive normal form (DNF) can be profitably extended to the epistemic case; we prove that the DNF fragment of S5, when appropriately defined, satisfies essentially the same queries and transformations as its classical counterpart.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Ronen I. Brafman ; Yagil Engel
【Abstract】: Recently, Brafman and Engel (2009) proposed new concepts of marginal and conditional utility that obey additive analogues of the chain rule and Bayes rule, which they employed to obtain a directed graphical model of utility functions that resembles Bayes nets. In this paper we carry this analogy a step farther by showing that the notion of utility independence, built on conditional utility, satisfies identical properties to those of probabilistic independence. This allows us to formalize the construction of graphical models for utility functions, directed and undirected, and place them on the firm foundations of Pearl and Paz's axioms of semi-graphoids. With this strong equivalence in place, we show how algorithms used for probabilistic reasoning such as Belief Propagation (Pearl 1988) can be replicated to reasoning about utilities with the same formal guarantees, and open the way to the adaptation of additional algorithms.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Gerhard Brewka ; Miroslaw Truszczynski ; Stefan Woltran
【Abstract】: We study methods to specify preferences among subsets of a set (a universe ). The methods we focus on are of two types. The first one assumes the universe comes with a preference relation on its elements and attempts to lift that relation to subsets of the universe. That approach has limited expressivity but results in orderings that capture interesting general preference principles. The second method consists of developing formalisms allowing the user to specify "atomic" improvements, and generating from them preferences on the powerset of the universe. We show that the particular formalism we propose is expressive enough to capture the lifted preference relations of the first approach, and generalizes propositional CP-nets. We discuss the importance of domain-independent methods for specifying preferences on sets for knowledge representation formalisms, selecting the formalism of argumentation frameworks as an illustrative example.
【Keywords】: Preferences, knowledge representation languages, argumentation
【Paper Link】 【Pages】:
【Authors】: Diego Calvanese ; Giuseppe De Giacomo ; Maurizio Lenzerini ; Moshe Y. Vardi
【Abstract】: The study of node-selection query languages for (finite) trees has been a major topic in the recent research on query lan- guages for Web documents. On one hand, there has been an extensive study of XPath and its various extensions. On the other hand, query languages based on classical logics, such as first-order logic (FO) or monadic second-order logic (MSO), have been considered. Results in this area typically relate an Xpath-based language to a classical logic. What has yet to emerge is an XPath-related language that is expressive as MSO, and at the same time enjoys the computational proper- ties of XPath, which are linear query evaluation and exponen- tial query-containment test. In this paper we propose μXPath, which is the alternation-free fragment of XPath extended with fixpoint operators. Using two-way alternating automata, we show that this language does combine desired expressiveness and computational properties, placing it as an attractive can- didate as the definite query language for trees.
【Keywords】: knowledge representation; query languages; XML; fixpoints; automata
【Paper Link】 【Pages】:
【Authors】: Yin Chen ; Yan Zhang ; Yi Zhou
【Abstract】: An answer set program with variables is first-order definable on finite structures if the set of its finite answer sets can be captured by a first-order sentence, otherwise this program is first-order indefinable on finite structures. In this paper, we study the problem of first-order indefinability of answer set programs. We provide an Ehrenfeucht-Fraisse game-theoretic characterization for the first-order indefinability of answer set programs on finite structures. As an application of this approach, we show that the well-known finding Hamiltonian cycles program is not first-order definable on finite structures. We then define two notions named the 0-1 property and unbounded cycles or paths under the answer set semantics, from which we develop two sufficient conditions that may be effectively used in proving a program's first-order indefinability on finite structures under certain circumstances.
【Keywords】: logic programming; nonmonotonic reasoning; knowledge representation; computational complexity of reasoning
【Paper Link】 【Pages】:
【Authors】: Ernest Davis
【Abstract】: We carry out a comparative study of the expressive power of different ontologies of matter in terms of the ease with which simple physical knowledge can be represented. In particular, we consider five ontologies of models of matter: particle models, fields, two ontologies for continuous material, and a hybrid model. We evaluate these in terms of how easily eleven benchmark physical laws and scenarios can be represented.
【Keywords】: qualitative physical reasoning; commonsense reasoning; ontology of matter
【Paper Link】 【Pages】:
【Authors】: Giuseppe De Giacomo ; Paolo Felli ; Fabio Patrizi ; Sebastian Sardiña
【Abstract】: In this paper, we review a series of agent behavior synthesis problems under full observability and nondeterminism (partial controllability), ranging from conditional planning, to recently introduced agent planning programs, and to sophisticated forms of agent behavior compositions, and show that all of them can be solved by model checking two-player game structures. These structures are akin to transition systems/Kripke structures, usually adopted in model checking, except that they distinguish (and hence allow to separately quantify) between the actions/moves of two antagonistic players. We show that using them we can implement solvers for several agent behavior synthesis problems.
【Keywords】: Reasoning About Actions; Synthesis; Agent Composition; Planning
【Paper Link】 【Pages】:
【Authors】: Thomas Eiter ; Wolfgang Faber ; Mushthofa Mushthofa
【Abstract】: Answer Set Programming (ASP) has been deployed in many applications, thanks to the availability of efficient solvers. Most programs encountered in practice have an important property: Their predicate arities are bounded by a constant, and in this case it is known that the relevant computations can be done using polynomial space. However, all competitive ASP systems rely on grounding, due to which they may use exponential space for these programs. We present three evaluation methods that respect the polynomial space bound and a generic framework architecture for realization. Experimental results for a prototype implementation indicate that the methods are effective. They show not only benign space consumption, but interestingly also good runtime compared to some state of the art ASP solvers.
【Keywords】: Nonmonotonic Reasoning; Logic Programming; Computational Complexity of Reasoning
【Paper Link】 【Pages】:
【Authors】: Joohyung Lee ; Ravi Palla
【Abstract】: We show how the situation calculus can be reformulated in terms of the first-order stable model semantics. A further transformation into answer set programs allows us to use an answer set solver to perform propositional reasoning about the situation calculus. We also provide an ASP style encoding method for Reiter's basic action theories, which tells us how the solution to the frame problem in ASP is related to the solution in the situation calculus.
【Keywords】: answer set programming; situation calculus; stable model semantics
【Paper Link】 【Pages】:
【Authors】: Jason Jingshi Li ; Jochen Renz
【Abstract】: The next challenge in qualitative spatial and temporal reasoning is to develop calculi that deal with different aspects of space and time. One approach to achieve this is to combine existing calculi that cover the different aspects. This, however, can lead to calculi that have a very large number of relations and it is a matter of ongoing discussions within the research community whether such large calculi are too large to be useful. In this paper we develop a procedure for reasoning about some of the largest known calculi, the Rectangle Algebra and the Block Algebra with about 10 661 relations. We demonstrate that reasoning over these calculi is possible and can be done efficiently in many cases. This is a clear indication that one of the main goals of the field can be achieved: highly expressive spatial and temporal representations that support efficient reasoning.
【Keywords】: Geometric, Spatial and Temporal Reasoning; Qualitative Reasoning; SAT and CSP Modeling and Formulations
【Paper Link】 【Pages】:
【Authors】: Sanjiang Li ; Weiming Liu
【Abstract】: Topological relations between spatial objects are the most important kind of qualitative spatial information. Dozens of relation models have been proposed in the past two decades. These models usually make a small number of distinctions and therefore can only cope with spatial information at a fixed granularity of spatial knowledge. In this paper, we propose a topological relation model in which the topological relation between two convex plane regions can be uniquely represented as a circular string over the alphabet {u; v; x; y}. A linear algorithm is given to compute the topological relation between two convex polygons. The infinite relation calculus could be used in hierarchical spatial reasoning as well as in qualitative shape description.
【Keywords】: qualitative spatial reasoning; topological relation; convex region; intersection; computational geometry
【Paper Link】 【Pages】:
【Authors】: Yongmei Liu ; Bing Li
【Abstract】: In a previous paper, Liu argued for the importance of establishing a precise theoretical foundation for program debugging from first principles. In this paper, we present a first step towards a theoretical exploration of program debugging algorithms. The starting point of our work is the recent debugging approach based on predicate switching. The idea is to switch the outcome of an instance of a predicate to bring the program execution to a successful completion and then identify the fault by examining the switched predicate. However, no theoretical analysis of the approach is available. In this paper, we generalize the above idea, and propose the bounded debugging via multiple predicate switching (BMPS) algorithm, which locates faults through switching the outcomes of instances of multiple predicates to get a successful execution where each loop is executed for a bounded number of times. Clearly, BMPS can be implemented by resorting to a SAT solver. We focus attention on RHS faults, that is, faults that occur in the control predicates and right-hand-sides of assignment statements. We prove that for conditional programs, BMPS is quasi-complete for RHS faults in the sense that some part of any true diagnosis will be returned by BMPS; and for iterative programs, when the bound is sufficiently large, BMPS is also quasi-complete for RHS faults. Initial experimentation with debugging small C programs showed that BMPS can quickly and effectively locate the faults.
【Keywords】: Diagnosis and Abductive Reasoning; Action, Change, and Causality; Model-Based Reasoning
【Paper Link】 【Pages】:
【Authors】: Jianbing Ma ; Weiru Liu ; Salem Benferhat
【Abstract】: Belief revision performs belief change on an agent's beliefs when new evidence (either of the form of a propositional formula or of the form of a total pre-order on a set of interpretations) is received. Jeffrey's rule is commonly used for revising probabilistic epistemic states when new information is probabilistically uncertain. In this paper, we propose a general epistemic revision framework where new evidence is of the form of a partial epistemic state. Our framework extends Jeffrey's rule with uncertain inputs and covers well-known existing frameworks such as ordinal conditional function (OCF) or possibility theory. We then define a set of postulates that such revision operators shall satisfy and establish representation theorems to characterize those postulates. We show that these postulates reveal common characteristics of various existing revision strategies and are satisfied by OCF conditionalization, Jeffrey's rule of conditioning and possibility conditionalization. Furthermore, when reducing to the belief revision situation, our postulates can induce most of Darwiche and Pearl's postulates.
【Keywords】: Belief Revision; Epistemic State; Jeffrey's Rule; Belief Change
【Paper Link】 【Pages】:
【Authors】: Jianbing Ma ; Weiru Liu ; Anthony Hunter
【Abstract】: When merging belief sets from different agents, the result is normally a consistent belief set in which the inconsistency between the original sources is not represented. As probability theory is widely used to represent uncertainty, an interesting question therefore is whether it is possible to induce a probability distribution when merging belief sets. To this end, we first propose two approaches to inducing a probability distribution on a set of possible worlds, by extending the principle of indifference on possible worlds. We then study how the (in)dependence relations between atoms can influence the probability distribution. We also propose a set of properties to regulate the merging of belief sets when a probability distribution is output. Furthermore, our merging operators satisfy the well known Konieczny and Pino-Perez postulates if we use the set of possible worlds which have the maximal induced probability values. Our study shows that taking an induced probability distribution as a merging result can better reflect uncertainty and inconsistency among the original knowledge bases.
【Keywords】: Knowledge Bases; Belief Merging; Probability Distribution; Principle of Indifference
【Paper Link】 【Pages】:
【Authors】: Thammanit Pipatsrisawat ; Adnan Darwiche
【Abstract】: We consider in this paper the size of a Decomposable Negation Normal Form (DNNF) that respects a given vtree (known as structured DNNF). This representation of propositional knowledge bases was introduced recently and shown to include OBDD as a special case (an OBDD variable ordering is a special type of vtree). We provide a lower bound on the size of any structured DNNF and discuss three particular instances of this bound, which correspond to three distinct subsets of structured DNNF (including OBDD). We show that our lower bound subsumes the influential Sieling and Wegener’s lower bound for OBDDs, which is typically used for identifying variable orderings that will cause a blowup in the OBDD size. We show that our lower bound allows for similar usage but with respect to vtrees, which provide structure for DNNFs in the same way that variable orderings provide structure for OBDDs. We finally discuss some of the theoretical and practical implications of our lower bound.
【Keywords】: knowledge compilation; knowledge representation; propositional logic; compilation language; OBDD; binary decision diagram; DNNF
【Paper Link】 【Pages】:
【Authors】: Yuan Ren ; Jeff Z. Pan ; Yuting Zhao
【Abstract】: Large scale ontology applications require efficient and robust description logic (DL) reasoning services. Expressive DLs usually have very high worst case complexity while tractable DLs are restricted in terms of expressive power. This brings a new challenge: can users use expressive DLs to build their ontologies and still enjoy the efficient services as in tractable languages. In this paper, we present a soundness preserving approximate reasoning framework for TBox reasoning in OWL2-DL. The ontologies are encoded into EL++ with additional data structures. A tractable algorithm is presented to classify such approximation by realizing more and more inference patterns. Preliminary evaluation shows that our approach can classify existing benchmarks in large scale efficiently with a high recall.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Ganesh Ram Santhanam ; Samik Basu ; Vasant Honavar
【Abstract】: Dominance testing, the problem of determining whether an outcome is preferred over another, is of fundamental importance in many applications. Hence, there is a need for algorithms and tools for dominance testing. CP-nets and TCP-nets are some of the widely studied languages for representing and reasoning with preferences. We reduce dominance testing in TCP-nets to reachability analysis in a graph of outcomes. We provide an encoding of TCP-nets in the form of a Kripke structure for CTL. We show how to compute dominance using NuSMV, a model checker for CTL. We present results of experiments that demonstrate the feasibility of our approach to dominance testing.
【Keywords】: Dominance; Qualitative Preferences; Preference Reasoning; Model Checking; Temporal Logic; Kripke Structure
【Paper Link】 【Pages】:
【Authors】: Steven Schockaert ; Henri Prade
【Abstract】: Inconsistencies between different information sources may arise because of statements that are inaccurate, albeit not completely false. In such scenarios, the most natural way to restore consistency is often to interpret assertions in a more flexible way, i.e. to enlarge (or relax) their meaning. As this process inherently requires extra-logical information about the meaning of atoms, extensions of classical merging operators are needed. In this paper, we introduce syntactic merging operators, based on possibilistic logic, which employ background knowledge about the similarity of atomic propositions to appropriately relax propositional statements.
【Keywords】: information merging; possibilistic logic; similarity-based reasoning
【Paper Link】 【Pages】:
【Authors】: Zhe Wang ; Kewen Wang ; Rodney W. Topor
【Abstract】: Revising knowledge bases (KBs) in description logics (DLs) in a syntax-independent manner is an important, nontrivial problem for the ontology management and DL communities. Several attempts have been made to adapt classical model-based belief revision and update techniques to DLs, but they are restricted in several ways. In particular, they do not provide operators or algorithms for general DL KB revision. The key difficulty is that, unlike propositional logic, a DL KB may have infinitely many models with complex (and possibly infinite) structures, making it difficult to define and compute revisions in terms of models. In this paper, we study general KBs in a specific DL in the DL-Lite family. We introduce the concept of features for such KBs, develop an alternative semantic characterization of KBs using features (instead of models), define two specific revision operators for KBs, and present the first algorithm for computing best approximations for syntax-independent revisions of KBs.
【Keywords】: knowledge representation; description logic; revision; ontology
【Paper Link】 【Pages】:
【Authors】: Heng Zhang ; Mingsheng Ying
【Abstract】: The stable model semantics was recently generalized by Ferraris, Lee and Lifschitz to the full first-order language with a syntax translation approach that is very similar to McCarthy's circumscription. In this paper, we investigate the decidability and undecidability of various fragments of first-order language under both semantics of stable models and circumscription. Some maximally decidable classes and undecidable classes are identified. The results obtained in the paper show that the boundaries between decidability and undecidability for these two semantics are very different in spite of the similarity of definition. Moreover, for all fragments considered in the paper, decidability under the semantics of circumscription coincides with that in classical first-order logic. This seems rather counterintuitive due to the second-order definition of circumscription and the high undecidability of first-order circumscription.
【Keywords】: Stable Model Semantics; Circumscription; Decidability; Satisfiability
【Paper Link】 【Pages】:
【Authors】: Saeed Amizadeh ; Milos Hauskrecht
【Abstract】: Pairwise Markov Networks (PMN) are an important class of Markov networks which, due to their simplicity, are widely used in many applications such as image analysis, bioinformatics, sensor networks, etc. However, learning of Markov networks from data is a challenging task; there are many possible structures one must consider and each of these structures comes with its own parameters making it easy to overfit the model with limited data. To deal with the problem, recent learning methods build upon the L1 regularization to express the bias towards sparse network structures. In this paper, we propose a new and more flexible framework that let us bias the structure, that can, for example, encode the preference to networks with certain local substructures which as a whole exhibit some special global structure. We experiment with and show the benefit of our framework on two types of problems: learning of modular networks and learning of traffic networks models.
【Keywords】: Pairwise Markov Networks; L1-regularization; Variational Approximation; Structural Priors
【Paper Link】 【Pages】:
【Authors】: Javad Azimi ; Xiaoli Fern ; Alan Fern ; Elizabeth Burrows ; Frank Chaplen ; Yanzhen Fan ; Hong Liu ; Jun Jaio ; Rebecca Schaller
【Abstract】: Motivated by a real-world problem, we study a novel budgeted optimization problem where the goal is to optimize an unknown function f ( x ) given a budget. In our setting, it is not practical to request samples of f ( x ) at precise input values due to the formidable cost of precise experimental setup. Rather, we may request a constrained experiment, which is a subset r of the input space for which the experimenter returns x in r and f ( x ). Importantly, as the constraints become looser, the experimental cost decreases, but the uncertainty about the location x of the next observation increases. Our goal is to manage this trade-off by selecting a sequence of constrained experiments to best optimize f within the budget. We introduce cost-sensitive policies for selecting constrained experiments using both model-free and model-based approaches, inspired by policies for unconstrained settings. Experiments on synthetic functions and functions derived from real-world experimental data indicate that our policies outperform random selection, that the model-based policies are superior to model-free ones, and give insights into which policies are preferable overall.
【Keywords】: Bayesian Constraint Optimization, Budgeted Optimization, Gaussian Process
【Paper Link】 【Pages】:
【Authors】: Sumit Basu ; Danyel Fisher ; Steven M. Drucker ; Hao Lu
【Abstract】: Interactive clustering refers to situations in which a human labeler is willing to assist a learning algorithm in automatically clustering items. We present a related but somewhat different task, assisted clustering, in which a user creates explicit groups of items from a large set and wants suggestions on what items to add to each group. While the traditional approach to interactive clustering has been to use metric learning to induce a distance metric, our situation seems equally amenable to classification. Using clusterings of documents from human subjects, we found that one or the other method proved to be superior for a given cluster, but not uniformly so. We thus developed a hybrid mechanism for combining the metric learner and the classifier. We present results from a large number of trials based on human clusterings, in which we show that our combination scheme matches and often exceeds the performance of a method which exclusively uses either type of learner.
【Keywords】: clustering; interactive clustering; learning; sorting; interactive machine learning
【Paper Link】 【Pages】:
【Authors】: Will Bridewell ; Ljupco Todorovski
【Abstract】: People constantly apply acquired knowledge to new learning tasks, but machines almost never do. Research on transfer learning attempts to address this dissimilarity. Working within this area, we report on a procedure that learns and transfers constraints in the context of inductive process modeling, which we review. After discussing the role of constraints in model induction, we describe the learning method, MISC, and introduce our metrics for assessing the cost and benefit of transferred knowledge. The reported results suggest that cross-domain transfer is beneficial in the scenarios that we investigated, lending further evidence that this strategy is a broadly effective means for increasing the efficiency of learning systems. We conclude by discussing the aspects of inductive process modeling that encourage effective transfer, by reviewing related strategies, and by describing future research plans for constraint induction and transfer learning.
【Keywords】: transfer learning; inductive process modeling; scientific discovery
【Paper Link】 【Pages】:
【Authors】: Bin Cao ; Sinno Jialin Pan ; Yu Zhang ; Dit-Yan Yeung ; Qiang Yang
【Abstract】: Transfer learning aims at reusing the knowledge in some source tasks to improve the learning of a target task. Many transfer learning methods assume that the source tasks and the target task be related, even though many tasks are not related in reality. However, when two tasks are unrelated, the knowledge extracted from a source task may not help, and even hurt, the performance of a target task. Thus, how to avoid negative transfer and then ensure a "safe transfer" of knowledge is crucial in transfer learning. In this paper, we propose an Adaptive Transfer learning algorithm based on Gaussian Processes (AT-GP), which can be used to adapt the transfer learning schemes by automatically estimating the similarity between a source and a target task. The main contribution of our work is that we propose a new semi-parametric transfer kernel for transfer learning from a Bayesian perspective, and propose to learn the model with respect to the target task, rather than all tasks as in multi-task learning. We can formulate the transfer learning problem as a unified Gaussian Process (GP) model. The adaptive transfer ability of our approach is verified on both synthetic and real-world datasets.
【Keywords】: transfer learning; Gaussian process; negative transfer
【Paper Link】 【Pages】:
【Authors】: Chun Chen ; Zhengguang Chen ; Jiajun Bu ; Can Wang ; Lijun Zhang ; Cheng Zhang
【Abstract】: In many real world applications, labeled data are usually expensive to get, while there may be a large amount of unlabeled data. To reduce the labeling cost, active learning attempts to discover the most informative data points for labeling. Recently, Optimal Experimental Design (OED) techniques have attracted an increasing amount of attention. OED is concerned with the design of experiments that minimizes variances of a parameterized model. Typical design criteria include D-, A-, and E-optimality. However, all these criteria are based on an ordinary linear regression model which aims to minimize the empirical error whereas the geometrical structure of the data space is not well respected. In this paper, we propose a novel optimal experimental design approach for active learning, called Laplacian G-Optimal Design (LapGOD), which considers both discriminating and geometrical structures. By using Laplacian Regularized Least Squares which incorporates manifold regularization into linear regression, our proposed algorithm selects those data points that minimizes the maximum variance of the predicted values on the data manifold. We also extend our algorithm to nonlinear case by using kernel trick. The experimental results on various image databases have shown that our proposed LapGOD active learning algorithm can significantly enhance the classification accuracy if the selected data points are used as training data.
【Keywords】: Active Learning;Classification;Kernel Methods
【Paper Link】 【Pages】:
【Authors】: Shuo Chen ; Jianwen Zhang ; Guangyun Chen ; Changshui Zhang
【Abstract】: As the Internet-based crowdsourcing services become more and more popular, learning from multiple teachers or sources has received more attention of the researchers in the machine learning area. In this setting, the learning system is dealing with samples and labels provided by multiple teachers, who in common cases, are non-expert. Their labeling styles and behaviors are usually diverse, some of which are even detrimental to the learning system. Thus, simply putting them together and utilizing the algorithms designed for single-teacher scenario would be not only improper, but also damaging. The problem calls for more specific methods. Our work focuses on a case where the teachers are composed of good ones and irresponsible ones. By irresponsible, we mean the teacher who takes the labeling task not seriously and label the sample at random without inspecting the sample itself. This behavior is quite common when the task is not attractive enough and the teacher just wants to finish it as soon as possible. Sometimes, the irresponsible teachers could take a considerable part among all the teachers. If we do not take out their effects, our learning system would be ruined with no doubt. In this paper, we propose a method for picking out the good teachers with promising experimental results. It works even when the irresponsible teachers are dominating in numbers.
【Keywords】: Muti-Teacher; Crowdsourcing; Irresponsible Teacher; k-Nearest Neighbor; Spectral Clustering
【Paper Link】 【Pages】:
【Authors】: Xi Chen ; Yan Liu ; Han Liu ; Jaime G. Carbonell
【Abstract】: An important challenge in understanding climate change is to uncover the dependency relationships between various climate observations and forcing factors. Graphical lasso, a recently proposed L 1 penalty based structure learning algorithm, has been proven successful for learning underlying dependency structures for the data drawn from a multivariate Gaussian distribution. However, climatological data often turn out to be non-Gaussian, e.g. cloud cover, precipitation, etc. In this paper, we examine nonparametric learning methods to address this challenge. In particular, we develop a methodology to learn dynamic graph structures from spatial-temporal data so that the graph structures at adjacent time or locations are similar. Experimental results demonstrate that our method not only recovers the underlying graph well but also captures the smooth variation properties on both synthetic data and climate data. An important challenge in understanding climate change is to uncover the dependency relationships between various climate observations and forcing factors. Graphical lasso, a recently proposed An important challenge in understanding climate change is to uncover the dependency relationships between various climate observations and forcing factors. Graphical lasso, a recently proposed L 1 penalty based structure learning algorithm, has been proven successful for learning underlying dependency structures for the data drawn from a multivariate Gaussian distribution. However, climatological data often turn out to be non-Gaussian, e.g. cloud cover, precipitation, etc. In this paper, we examine nonparametric learning methods to address this challenge. In particular, we develop a methodology to learn dynamic graph structures from spatial-temporal data so that the graph structures at adjacent time or locations are similar. Experimental results demonstrate that our method not only recovers the underlying graph well but also captures the smooth variation properties on both synthetic data and climate data.
【Keywords】: Graph Structure Learning, Spatial-Temporal Data Mining, Climate Data Analysis
【Paper Link】 【Pages】:
【Authors】: Cassio Polpo de Campos ; Qiang Ji
【Abstract】: This paper addresses exact learning of Bayesian network structure from data based on the Bayesian Dirichlet score function and its derivations. We describe useful properties that strongly reduce the computational costs of many known methods without losing global optimality guarantees. We show empirically the advantages of the properties in terms of time and memory consumptions, demonstrating that state-of-the-art methods, with the use of such properties, might handle larger data sets than those currently possible.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Eric Eaton ; Gary Holness ; Daniel McFarlane
【Abstract】: We present an interactive learning method that enables a user to iteratively refine a regression model. The user examines the output of the model, visualized as the vertical axis of a 2D scatterplot, and provides corrections by repositioning individual data instances to the correct output level. Each repositioned data instance acts as a control point for altering the learned model, using the geometry underlying the data. We capture the underlying structure of the data as a manifold, on which we compute a set of basis functions as the foundation for learning. Our results show that manifold-based interactive learning improves performance monotonically with each correction, outperforming alternative approaches.
【Keywords】: manifold learning; interactive learning; spectral graph theory; Laplacian regularization; human-computer interaction
【Paper Link】 【Pages】:
【Authors】: Kun Gai ; Changshui Zhang
【Abstract】: We introduce a new discriminative piecewise linear model for classification. A two-step method is developed to construct the model. In the first step, we sample some boundary points that lie between positive and negative data, as well as corresponding directions from negative data to positive data. The sampling result gives a discriminative nonparametric decision surface, which preserves enough information to correctly classify all training data. To simplify this surface, in the second step we propose a nonparametric approach for linear surface segmentation using Dirichlet process mixtures. The final result is a piecewise linear model, in which the number of linear surface pieces is automatically determined by the Bayesian inference according to data. Experiments on both synthetic and real data verify the effectiveness of the proposed model.
【Keywords】: Piecewise linear, boundary point, discriminative, nonparametric, Dirichlet process
【Paper Link】 【Pages】:
【Authors】: Xin Geng ; Kate Smith-Miles ; Zhi-Hua Zhou
【Abstract】: One of the main difficulties in facial age estimation is the lack of sufficient training data for many ages. Fortunately, the faces at close ages look similar since aging is a slow and smooth process. Inspired by this observation, in this paper, instead of considering each face image as an example with one label (age), we regard each face image as an example associated with a label distribution. The label distribution covers a number of class labels, representing the degree that each label describes the example. Through this way, in addition to the real age, one face image can also contribute to the learning of its adjacent ages. We propose an algorithm named IIS-LLD for learning from the label distributions, which is an iterative optimization process based on the maximum entropy model. Experimental results show the advantages of IIS-LLD over the traditional learning methods based on single-labeled data.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Sepp Hartung ; Jiong Guo ; Christian Komusiewicz ; Rolf Niedermeier ; Johannes Uhlmann
【Abstract】: We perform new theoretical as well as first-time experimental studies for the NP-hard problem to find a closest ultrametric for given dissimilarity data on pairs. This is a central problem in the area of hierarchical clustering, where so far only polynomial-time approximation algorithms were known. In contrast, we develop efficient preprocessing algorithms (known as kernelization in parameterized algorithmics) with provable performance guarantees and a simple search tree algorithm. These are used to find optimal solutions. Our experiments with synthetic and biological data show the effectiveness of our algorithms and demonstrate that an approximation algorithm due to Ailon and Charikar [FOCS 2005] often gives (almost) optimal solutions.
【Keywords】: fixed-parameter algorithmics, hierarchical clustering
【Paper Link】 【Pages】:
【Authors】: Zhen Guo ; Shenghuo Zhu ; Zhongfei Zhang ; Yun Chi ; Yihong Gong
【Abstract】: The latent topic model plays an important role in the unsupervised learning from a corpus, which provides a probabilistic interpretation of the corpus in terms of the latent topic space. An underpinning assumption which most of the topic models are based on is that the documents are assumed to be independent of each other. However, this assumption does not hold true in reality and the relations among the documents are available in different ways, such as the citation relations among the research papers. To address this limitation, in this paper we present a Bernoulli Process Topic (BPT) model, where the interdependence among the documents is modeled by a random Bernoulli process. In the BPT model a document is modeled as a distribution over topics that is a mixture of the distributions associated with the related documents. Although BPT aims at obtaining a better document modeling by incorporating the relations among the documents, it could also be applied to many applications including detecting the topics from corpora and clustering the documents. We apply the BPT model to several document collections and the experimental comparisons against several state-of-the-art approaches demonstrate the promising performance.
【Keywords】: unsupervised learning; topic model; text mining
【Paper Link】 【Pages】:
【Authors】: Yahong Han ; Fei Wu ; Jinzhu Jia ; Yueting Zhuang ; Bin Yu
【Abstract】: Multi-task learning aims at combining information across tasks to boost prediction performance, especially when the number of training samples is small and the number of predictors is very large. In this paper, we first extend the Sparse Discriminate Analysis (SDA) of Clemmensen et al.. We call this Multi-task Sparse Discriminate Analysis (MtSDA). MtSDA formulates multi-label prediction as a quadratic optimization problem whereas SDA obtains single labels via a nearest class mean rule. Second, we propose a class of equicorrelation matrices to use in MtSDA which includes the identity matrix. MtSDA with both matrices are compared with singletask learning (SVM and LDA+SVM) and multi-task learning (HSML). The comparisons are made on real data sets in terms of AUC and F-measure. The data results show that MtSDA outperforms other methods substantially almost all the time and in some cases MtSDA with the equicorrelation matrix substantially outperforms MtSDA with identity matrix.
【Keywords】: Multi-task Learning; Multi-task Sparse Discriminate Analysis
【Paper Link】 【Pages】:
【Authors】: Ran He ; Bao-Gang Hu ; Wei-Shi Zheng ; Yanqing Guo
【Abstract】: This paper proposes a novel robust sparse representation method, called the two-stage sparse representation (TSR), for robust recognition on a large-scale database. Based on the divide and conquer strategy, TSR divides the procedure of robust recognition into outlier detection stage and recognition stage. In the first stage, a weighted linear regression is used to learn a metric in which noise and outliers in image pixels are detected. In the second stage, based on the learnt metric, the large-scale dataset is firstly filtered into a small set according to the nearest neighbor criterion. Then a sparse representation is computed by the non-negative least squares technique. The sparse solution is unique and can be optimized efficiently. The extensive numerical experiments on several public databases demonstrate that the proposed TSR approach generally obtains better classification accuracy than the state of the art Sparse Representation Classification (SRC). At the same time, by using the TSR, a significant reduction of computational cost is reached by over fifty times in comparison with the SRC, which enables the TSR to be deployed more suitably for large-scale dataset.
【Keywords】: sparse representation; large-scale; metric learning; robust
【Paper Link】 【Pages】:
【Authors】: Kshitij Judah ; Saikat Roy ; Alan Fern ; Thomas G. Dietterich
【Abstract】: We consider the problem of incorporating end-user advice into reinforcement learning (RL). In our setting, the learner alternates between practicing, where learning is based on actual world experience, and end-user critique sessions where advice is gathered. During each critique session the end-user is allowed to analyze a trajectory of the current policy and then label an arbitrary subset of the available actions as good or bad. Our main contribution is an approach for integrating all of the information gathered during practice and critiques in order to effectively optimize a parametric policy. The approach optimizes a loss function that linearly combines losses measured against the world experience and the critique data. We evaluate our approach using a prototype system for teaching tactical battle behavior in a real-time strategy game engine. Results are given for a significant evaluation involving ten end-users showing the promise of this approach and also highlighting challenges involved in inserting end-users into the RL loop.
【Keywords】: Reinforcement Learning; Human-Computer Interaction; Intelligent User Interfaces
【Paper Link】 【Pages】:
【Authors】: Hassan Khosravi ; Oliver Schulte ; Tong Man ; Xiaoyuan Xu ; Bahareh Bina
【Abstract】: Many machine learning applications that involve relational databases incorporate first-order logic and probability. Markov Logic Networks (MLNs) are a prominent statistical relational model that consist of weighted first order clauses. Many of the current state-of-the-art algorithms for learning MLNs have focused on relatively small datasets with few descriptive attributes, where predicates are mostly binary and the main task is usually prediction of links between entities. This paper addresses what is in a sense a complementary problem: learning the structure of an MLN that models the distribution of discrete descriptive attributes on medium to large datasets, given the links between entities in a relational database. Descriptive attributes are usually nonbinary and can be very informative, but they increase the search space of possible candidate clauses. We present an efficient new algorithm for learning a directed relational model (parametrized Bayes net), which produces an MLN structure via a standard moralization procedure for converting directed models to undirected models. Learning MLN structure in this way is 200-1000 times faster and scores substantially higher in predictive accuracy than benchmark algorithms on three relational databases.
【Keywords】: Statistical Relational Learning; Learning Graphical Models; Markov Logic Networks
【Paper Link】 【Pages】:
【Authors】: Mayank Lahiri ; Manuel Cebrián
【Abstract】: Diffusion processes taking place in social networks are used to model a number of phenomena, such as the spread of human or computer viruses, and the adoption of products in viral marketing campaigns. It is generally difficult to obtain accurate information about how such spreads actually occur, so a variety of stochastic diffusion models are used to simulate spreading processes in networks instead. We show that a canonical genetic algorithm with a spatially distributed population, when paired with specific forms of Holland's synthetic hyperplane-defined objective functions, can simulate a large and rich class of diffusion models for social networks. These include standard diffusion models, such as the Independent Cascade and Competing Processes models. In addition, our Genetic Algorithm Diffusion Model (GADM) can also model complex phenomena such as information diffusion. We demonstrate an application of the GADM to modeling information flow in a large, dynamic social network derived from e-mail headers.
【Keywords】: genetic algorithms; social networks; diffusion processes; hyperplane defined functions
【Paper Link】 【Pages】:
【Authors】: Yu-Feng Li ; James T. Kwok ; Zhi-Hua Zhou
【Abstract】: In this paper, we study cost-sensitive semi-supervised learning where many of the training examples are unlabeled and different misclassification errors are associated with unequal costs. This scenario occurs in many real-world applications. For example, in some disease diagnosis, the cost of erroneously diagnosing a patient as healthy is much higher than that of diagnosing a healthy person as a patient. Also, the acquisition of labeled data requires medical diagnosis which is expensive, while the collection of unlabeled data such as basic health information is much cheaper. We propose the CS4VM (Cost-Sensitive Semi-Supervised Support Vector Machine) to address this problem. We show that the CS4VM, when given the label means of the unlabeled data, closely approximates the supervised cost-sensitive SVM that has access to the ground-truth labels of all the unlabeled data. This observation leads to an efficient algorithm which first estimates the label means and then trains the CS4VM with the plug-in label means by an efficient SVM solver. Experiments on a broad range of data sets show that the proposed method is capable of reducing the total cost and is computationally efficient.
【Keywords】: cost-sensitive learning, semi-supervised learning, support vector machine
【Paper Link】 【Pages】:
【Authors】: Haifeng Liu ; Zhaohui Wu
【Abstract】: Non-negative matrix factorization (NMF), as a useful decomposition method for multivariate data, has been widely used in pattern recognition, information retrieval and computer vision. NMF is an effective algorithm to find the latent structure of the data and leads to a parts-based representation. However, NMF is essentially an unsupervised method and can not make use of label information. In this paper, we propose a novel semi-supervised matrix decomposition method, called Constrained Non-negative Matrix Factorization, which takes the label information as additional constraints. Specifically, we require that the data points sharing the same label have the same coordinate in the new representation space. This way, the learned representations can have more discriminating power. We demonstrate the effectiveness of this novel algorithm through a set of evaluations on real world applications.
【Keywords】: non-negative matrix factorization; dimensionality reduction; clustering
【Paper Link】 【Pages】:
【Authors】: Jialu Liu ; Deng Cai ; Xiaofei He
【Abstract】: Gaussian Mixture Model (GMM) is one of the most popular data clustering methods which can be viewed as a linear combination of different Gaussian components. In GMM, each cluster obeys Gaussian distribution and the task of clustering is to group observations into different components through estimating each cluster's own parameters. The Expectation-Maximization algorithm is always involved in such estimation problem. However, many previous studies have shown naturally occurring data may reside on or close to an underlying submanifold. In this paper, we consider the case where the probability distribution is supported on a submanifold of the ambient space. We take into account the smoothness of the conditional probability distribution along the geodesics of data manifold. That is, if two observations are close in intrinsic geometry, their distributions over different Gaussian components are similar. Simply speaking, we introduce a novel method based on manifold structure for data clustering, called Locally Consistent Gaussian Mixture Model (LCGMM). Specifically, we construct a nearest neighbor graph and adopt Kullback-Leibler Divergence as the distance measurement to regularize the objective function of GMM. Experiments on several data sets demonstrate the effectiveness of such regularization.
【Keywords】: Gaussian Mixture Model; Manifold
【Paper Link】 【Pages】:
【Authors】: Wei Liu ; Xinmei Tian ; Dacheng Tao ; Jianzhuang Liu
【Abstract】: Vectored data frequently occur in a variety of fields, which are easy to handle since they can be mathematically abstracted as points residing in a Euclidean space. An appropriate distance metric in the data space is quite demanding for a great number of applications. In this paper, we pose robust and tractable metric learning under pairwise constraints that are expressed as similarity judgements between data pairs. The major features of our approach include: 1) it maximizes the gap between the average squared distance among dissimilar pairs and the average squared distance among similar pairs; 2) it is capable of propagating similar constraints to all data pairs; and 3) it is easy to implement in contrast to the existing approaches using expensive optimization such as semidefinite programming. Our constrained metric learning approach has widespread applicability without being limited to particular backgrounds. Quantitative experiments are performed for classification and retrieval tasks, uncovering the effectiveness of the proposed approach.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Yang Liu ; Yan Liu ; Keith C. C. Chan
【Abstract】: Dimensionality reduction plays an important role in many machine learning and pattern recognition tasks. In this paper, we present a novel dimensionality reduction algorithm called multilinear maximum distance embedding (M2DE), which includes three key components. To preserve the local geometry and discriminant information in the embedded space, M2DE utilizes a new objective function, which aims to maximize the distances between some particular pairs of data points, such as the distances between nearby points and the distances between data points from different classes. To make the mapping of new data points straightforward, and more importantly, to keep the natural tensor structure of high-order data, M2DE integrates multilinear techniques to learn the transformation matrices sequentially. To provide reasonable and stable embedding results, M2DE employs the L1-norm, which is more robust to outliers, to measure the dissimilarity between data points. Experiments on various datasets demonstrate that M2DE achieves good embedding results of high-order data for classification tasks.
【Keywords】: Dimensionality reduction; L1-norm optimization; manifold learning; multilinear maximum distance embedding
【Paper Link】 【Pages】:
【Authors】: Marc E. Maier ; Brian J. Taylor ; Huseyin Oktay ; David Jensen
【Abstract】: Methods for discovering causal knowledge from observational data have been a persistent topic of AI research for several decades. Essentially all of this work focuses on knowledge representations for propositional domains. In this paper, we present several key algorithmic and theoretical innovations that extend causal discovery to relational domains. We provide strong evidence that effective learning of causal models is enhanced by relational representations. We present an algorithm, relational PC, that learns causal dependencies in a state-of-the-art relational representation, and we identify the key representational and algorithmic innovations that make the algorithm possible. Finally, we prove the algorithm's theoretical correctness and demonstrate its effectiveness on synthetic and real data sets.
【Keywords】: Causal Discovery; Relational Learning
【Paper Link】 【Pages】:
【Authors】: Yadong Mu ; Shuicheng Yan
【Abstract】: Non-metric distances are often more reasonable compared with metric ones in terms of consistency with human perceptions. However, existing locality-sensitive hashing (LSH) algorithms can only support data which are gauged with metrics. In this paper we propose a novel locality-sensitive hashing algorithm targeting such non-metric data. Data in original feature space are embedded into an implicit reproducing kernel Krein space and then hashed to obtain binary bits. Here we utilize the norm-keeping property of p-stable functions to ensure that two data's collision probability reflects their non-metric distance in original feature space. We investigate various concrete examples to validate the proposed algorithm. Extensive empirical evaluations well illustrate its effectiveness in terms of accuracy and retrieval speedup.
【Keywords】: locality sensitive hashing; non-metric; kernel methods
【Paper Link】 【Pages】:
【Authors】: Michael J. Paul ; Roxana Girju
【Abstract】: This paper presents the Topic-Aspect Model (TAM), a Bayesian mixture model which jointly discovers topics and aspects. We broadly define an aspect of a document as a characteristic that spans the document, such as an underlying theme or perspective. Unlike previous models which cluster words by topic or aspect, our model can generate token assignments in both of these dimensions, rather than assuming words come from only one of two orthogonal models. We present two applications of the model. First, we model a corpus of computational linguistics abstracts, and find that the scientific topics identified in the data tend to include both a computational aspect and a linguistic aspect. For example, the computational aspect of GRAMMAR emphasizes parsing, whereas the linguistic aspect focuses on formal languages. Secondly, we show that the model can capture different viewpoints on a variety of topics in a corpus of editorials about the Israeli-Palestinian conflict. We show both qualitative and quantitative improvements in TAM over two other state-of-the-art topic models.
【Keywords】: topic models;Bayesian modeling;unsupervised learning;natural language processing
【Paper Link】 【Pages】:
【Authors】: Wei Ping ; Ye Xu ; Kexin Ren ; Chi-Hung Chi ; Shen Furao
【Abstract】: Multi-instance learning, as other machine learning tasks, also suffers from the curse of dimensionality. Although dimensionality reduction methods have been investigated for many years, multi-instance dimensionality reduction methods remain untouched. On the other hand, most algorithms in multi- instance framework treat instances in each bag as independently and identically distributed samples, which fails to utilize the structure information conveyed by instances in a bag. In this paper, we propose a multi-instance dimensionality reduction method, which treats instances in each bag as non-i.i.d. samples. We regard every bag as a whole entity and define a bag margin objective function. By maximizing the margin of positive and negative bags, we learn a subspace to obtain more salient representation of original data. Experiments demonstrate the effectiveness of the proposed method.
【Keywords】: Dimensionality Reduction;Multi-Instance Learning;Non-i.i.d. Samples
【Paper Link】 【Pages】:
【Authors】: Stefan Pintilie ; Ali Ghodsi
【Abstract】: Dimensionality reduction is the process by which a set of data points in a higher dimensional space are mapped to a lower dimension while maintaining certain properties of these points relative to each other. One important property is the preservation of the three angles formed by a triangle consisting of three neighboring points in the high dimensional space. If this property is maintained for those same points in the lower dimensional embedding then the result is a conformal map. However, many of the commonly used nonlinear dimensionality reduction techniques, such as Locally Linear Embedding (LLE) or Laplacian Eigenmaps (LEM), do not produce conformal maps. Post-processing techniques formulated as instances of semi-definite programming (SDP) problems can be applied to the output of either LLE or LEM to produce a conformal map. However, the effectiveness of this approach is limited by the computational complexity of SDP solvers. This paper will propose an alternative post-processing algorithm that produces a conformal map but does not require a solution to a SDP problem and so is more computationally efficient thus allowing it to be applied to a wider selection of datasets. Using this alternative solution, the paper will also propose a new algorithm for 3D object classification. An interesting feature of the 3D classification algorithm is that it is invariant to the scale and the orientation of the surface.
【Keywords】: Data Mining; Classification; Machine Learning; Unsupervised Learning
【Paper Link】 【Pages】:
【Authors】: Ian Porteous ; Arthur U. Asuncion ; Max Welling
【Abstract】: Matrix factorization is a fundamental technique in machine learning that is applicable to collaborative filtering, information retrieval and many other areas. In collaborative filtering and many other tasks, the objective is to fill in missing elements of a sparse data matrix. One of the biggest challenges in this case is filling in a column or row of the matrix with very few observations. In this paper we introduce a Bayesian matrix factorization model that performs regression against side information known about the data in addition to the observations. The side information helps by adding observed entries to the factored matrices. We also introduce a nonparametric mixture model for the prior of the rows and columns of the factored matrices that gives a different regularization for each latent class. Besides providing a richer prior, the posterior distribution of mixture assignments reveals the latent classes. Using Gibbs sampling for inference, we apply our model to the Netflix Prize problem of predicting movie ratings given an incomplete user-movie ratings matrix. Incorporating rating information with gathered metadata information, our Bayesian approach outperforms other matrix factorization techniques even when using fewer dimensions.
【Keywords】: Matrix Factorization; Bayesian; Collaborative Filtering;
【Paper Link】 【Pages】:
【Authors】: Buyue Qian ; Ian Davidson
【Abstract】: A significant challenge to make learning techniques more suitable for general purpose use in AI is to move beyond i) complete supervision, ii) low dimensional data and iii) a single label per instance. Solving this challenge would allow making predictions for high dimensional large dataset with multiple (but possibly incomplete) labelings. While other work has addressed each of these problems separately, in this paper we show how to address them together, namely the problem of semi-supervised dimension reduction for multi-labeled classification, SSDR-MC. To our knowledge this is the first paper that attempts to address all challenges together. In this work, we study a novel joint learning framework which performs optimization for dimension reduction and multi-label inference in semi-supervised setting. The experimental results validate the performance of our approach, and demonstrate the effectiveness of connecting dimension reduction and learning.
【Keywords】: Data Mining; Semi-Supervised Learning; Classification
【Paper Link】 【Pages】:
【Abstract】: Nonnegative Matrix Factorization (NMF) is a widely used technique in many applications such as clustering. It approximates the nonnegative data in an original high dimensional space with a linear representation in a low dimensional space by using the product of two nonnegative matrices. In many applications with data such as human faces or digits, data often reside on multiple manifolds, which may overlap or intersect. But the traditional NMF method and other existing variants of NMF do not consider this. This paper proposes a novel clustering algorithm that explicitly models the intrinsic geometrical structure of the data on multiple manifolds with NMF. The idea of the proposed algorithm is that a data point generated by several neighboring points on a specific manifold in the original space should be constructed in a similar way in the low dimensional subspace. A set of experimental results on two real world datasets demonstrate the advantage of the proposed algorithm.
【Keywords】: Nonnegative Matrix Factorization; Clustering; Multiple Manifold Learning
【Paper Link】 【Pages】:
【Authors】: Yangqiu Song ; Shimei Pan ; Shixia Liu ; Furu Wei ; Michelle X. Zhou ; Weihong Qian
【Abstract】: In this paper, we present a constrained co-clustering approach for clustering textual documents. Our approach combines the benefits of information-theoretic co-clustering and constrained clustering. We use a two-sided hidden Markov random field (HMRF) to model both the document and word constraints. We also develop an alternating expectation maximization (EM) algorithm to optimize the constrained co-clustering model. We have conducted two sets of experiments on a benchmark data set: (1) using human-provided category labels to derive document and word constraints for semi-supervised document clustering, and (2) using automatically extracted named entities to derive document constraints for unsupervised document clustering. Compared to several representative constrained clustering and co-clustering approaches, our approach is shown to be more effective for high-dimensional, sparse text data.
【Keywords】: constrained clustering; co-clustering; semi-supervised learning
【Paper Link】 【Pages】:
【Authors】: Yu-Yin Sun ; Michael K. Ng ; Zhi-Hua Zhou
【Abstract】: Multi-instance learning deals with problems that treat bags of instances as training examples. In single-instance learning problems, dimensionality reduction is an essential step for high-dimensional data analysis and has been studied for years. The curse of dimensionality also exists in multiinstance learning tasks, yet this difficult task has not been studied before. Direct application of existing single-instance dimensionality reduction objectives to multi-instance learning tasks may not work well since it ignores the characteristic of multi-instance learning that the labels of bags are known while the labels of instances are unknown. In this paper, we propose an effective model and develop an efficient algorithm to solve the multi-instance dimensionality reduction problem. We formulate the objective as an optimization problem by considering orthonormality and sparsity constraints in the projection matrix for dimensionality reduction, and then solve it by the gradient descent along the tangent space of the orthonormal matrices. We also propose an approximation for improving the efficiency. Experimental results validate the effectiveness of the proposed method.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Yu-Yin Sun ; Yin Zhang ; Zhi-Hua Zhou
【Abstract】: Multi-label learning deals with data associated with multiple labels simultaneously. Previous work on multi-label learning assumes that for each instance, the “full” label set associated with each training instance is given by users. In many applications, however, to get the full label set for each instance is difficult and only a “partial” set of labels is available. In such cases, the appearance of a label means that the instance is associated with this label, while the absence of a label does not imply that this label is not proper for the instance. We call this kind of problem “weak label” problem. In this paper, we propose the WELL (WEak Label Learning) method to solve the weak label problem. We consider that the classification boundary for each label should go across low density regions, and that each label generally has much smaller number of positive examples than negative examples. The objective is formulated as a convex optimization problem which can be solved efficiently. Moreover, we exploit the correlation between labels by assuming that there is a group of low-rank base similarities, and the appropriate similarities between instances for different labels can be derived from these base similarities. Experiments validate the performance of WELL.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Qing Tan ; Qing He ; Zhongzhi Shi
【Abstract】: Curve extraction is an important and basic technique in image processing and computer vision. Due to the complexity of the images and the limitation of segmentation algorithms, there are always a large number of noisy pixels in the segmented binary images. In this paper, we present an approach based on ant colony system (ACS) to detect nonparametric curves from a binary image containing discontinuous curves and noisy points. Compared with the well-known Hough transform (HT) method, the ACS-based curve extraction approach can deal with both regular and irregular curves without knowing their shapes in advance. The proposed approach has many characteristics such as faster convergence, implicit parallelism and strong ability to deal with highly-noised images. Moreover, our approach can extract multiple curves from an image, which is impossible for the previous genetic algorithm based approach. Experimental results show that the proposed ACS-based approach is effective and efficient.
【Keywords】: ant colony optimization; curve extraction; genetic algorithm
【Paper Link】 【Pages】:
【Authors】: Joel Veness ; Kee Siong Ng ; Marcus Hutter ; David Silver
【Abstract】: This paper introduces a principled approach for the design of a scalable general reinforcement learning agent. This approach is based on a direct approximation of AIXI, a Bayesian optimality notion for general reinforcement learning agents. Previously, it has been unclear whether the theory of AIXI could motivate the design of practical algorithms. We answer this hitherto open question in the affirmative, by providing the first computationally feasible approximation to the AIXI agent. To develop our approximation, we introduce a Monte Carlo Tree Search algorithm along with an agent-specific extension of the Context Tree Weighting algorithm. Empirically, we present a set of encouraging results on a number of stochastic, unknown, and partially observable domains.
【Keywords】: Reinforcement Learning; Universal Artificial Intelligence
【Paper Link】 【Pages】:
【Authors】: Thomas J. Walsh ; Sergiu Goschin ; Michael L. Littman
【Abstract】: Recent advancements in model-based reinforcement learning have shown that the dynamics of many structured domains (e.g. DBNs) can be learned with tractable sample complexity, despite their exponentially large state spaces. Unfortunately, these algorithms all require access to a planner that computes a near optimal policy, and while many traditional MDP algorithms make this guarantee, their computation time grows with the number of states. We show how to replace these over-matched planners with a class of sample-based planners — whose computation time is independent of the number of states — without sacrificing the sample-efficiency guarantees of the overall learning algorithms. To do so, we define sufficient criteria for a sample-based planner to be used in such a learning system and analyze two popular sample-based approaches from the literature. We also introduce our own sample-based planner, which combines the strategies from these algorithms and still meets the criteria for integration into our learning system. In doing so, we define the first complete RL solution for compactly represented (exponentially sized) state spaces with efficiently learnable dynamics that is both sample efficient and whose computation time does not grow rapidly with the number of states.
【Keywords】: reinforcement learning; sample-based planning; markov decision process
【Paper Link】 【Pages】:
【Authors】: Hua Wang ; Heng Huang ; Chris H. Q. Ding
【Abstract】: Many real life applications brought by modern technologies often have multiple data sources, which are usually characterized by both attributes and pairwise similarities at the same time. For example in webpage ranking, a webpage is usually represented by a vector of term values, and meanwhile the internet linkages induce pairwise similarities among the webpages. Although both attributes and pairwise similarities are useful for class membership inference, many traditional embedding algorithms only deal with one type of input data. In order to make use of the both types of data simultaneously, in this work, we propose a novel Discriminant Laplacian Embedding (DLE) approach. Supervision information from training data are integrated into DLE to improve the discriminativity of the resulted embedding space. By solving the ambiguity problem in computing the scatter matrices caused by data points with multiple labels, we successfully extend the proposed DLE to multi-label classification. In addition, through incorporating the label correlations, the classification performance using multi-label DLE is further enhanced. Promising experimental results in extensive empirical evaluations have demonstrated the effectiveness of our approaches.
【Keywords】: Semi-supervised Learning; Linear Discriminant Analysis; Laplacian Embedding
【Paper Link】 【Pages】:
【Authors】: Aaron Wilson ; Alan Fern ; Prasad Tadepalli
【Abstract】: Bayesian inference is an appealing approach for leveraging prior knowledge in reinforcement learning (RL). In this paper we describe an algorithm for discovering different classes of roles for agents via Bayesian inference. In particular, we develop a Bayesian policy search approach for Multi-Agent RL (MARL), which is model-free and allows for priors on policy parameters. We present a novel optimization algorithm based on hybrid MCMC, which leverages both the prior and gradient information estimated from trajectories. Our experiments in a complex real-time strategy game demonstrate the effective discovery of roles from supervised trajectories, the use of discovered roles for successful transfer to similar tasks, and the discovery of roles through reinforcement learning.
【Keywords】: Reinforcement Learning;Bayesian Reinforcement Learning;Stochastic Simulation
【Paper Link】 【Pages】:
【Authors】: Danny Wyatt ; Tanzeem Choudhury ; Jeff A. Bilmes
【Abstract】: The current methods used to mine and analyze temporal social network data make two assumptions: all edges have the same strength, and all parameters are time-homogeneous. We show that those assumptions may not hold for social networks and propose an alternative model with two novel aspects: (1) the modeling of edges as multi-valued variables that can change in intensity, and (2) the use of a curved exponential family framework to capture time-inhomogeneous properties while retaining a parsimonious and interpretable model. We show that our model outperforms traditional models on two real-world social network data sets.
【Keywords】: Social Networks, Temporal Models, Machine Learning
【Paper Link】 【Pages】:
【Authors】: Zenglin Xu ; Rong Jin ; Shenghuo Zhu ; Michael R. Lyu ; Irwin King
【Abstract】: Multiple Kernel Learning (MKL) can be formulated as a convex-concave minmax optimization problem, whose saddle point corresponds to the optimal solution to MKL. Most MKL methods employ the L1-norm simplex constraints on the combination weights of kernels, which therefore involves optimization of a non-smooth function of the kernel weights. These methods usually divide the optimization into two cycles: one cycle deals with the optimization on the kernel combination weights, and the other cycle updates the parameters of SVM. Despite the success of their efficiency, they tend to discard informative complementary kernels. To improve accuracy, we introduce smoothness to the optimization procedure. Furthermore, we transform the optimization into a single smooth convex optimization problem and employ the Nesterov’s method to efficiently solve the optimization problem. Experiments on benchmark data sets demonstrate that the proposed algorithm clearly improves current MKL methods in a number scenarios.
【Keywords】: Multiple Kernel Learning; Smooth Optimization; Classification
【Paper Link】 【Pages】:
【Authors】: Makoto Yamada ; Masashi Sugiyama
【Abstract】: The discovery of non-linear causal relationship under additive non-Gaussian noise models has attracted considerable attention recently because of their high flexibility. In this paper, we propose a novel causal inference algorithm called least-squares independence regression (LSIR). LSIR learns the additive noise model through minimization of an estimator of the squared-loss mutual information between inputs and residuals. A notable advantage of LSIR over existing approaches is that tuning parameters such as the kernel width and the regularization parameter can be naturally optimized by cross-validation, allowing us to avoid overfitting in a data-dependent fashion. Through experiments with real-world datasets, we show that LSIR compares favorably with the state-of-the-art causal inference method.
【Keywords】: causal inference, dependence minimizing regression; least-squares mutual information
【Paper Link】 【Pages】:
【Authors】: Yi Yang ; Feiping Nie ; Shiming Xiang ; Yueting Zhuang ; Wenhua Wang
【Abstract】: Over the past few years, a large family of manifold learning algorithms have been proposed, and applied to various applications. While designing new manifold learning algorithms has attracted much research attention, fewer research efforts have been focused on out-of-sample extrapolation of learned manifold. In this paper, we propose a novel algorithm of manifold learning. The proposed algorithm, namely Local and Global Regressive Mapping (LGRM), employs local regression models to grasp the manifold structure. We additionally impose a global regression term as regularization to learn a model for out-of-sample data extrapolation. Based on the algorithm, we propose a new manifold learning framework. Our framework can be applied to any manifold learning algorithms to simultaneously learn the low dimensional embedding of the training data and a model which provides explicit mapping of the out-of-sample data to the learned manifold. Experiments demonstrate that the proposed framework uncover the manifold structure precisely and can be freely applied to unseen data.
【Keywords】: Manifold learning, Out of Sample
【Paper Link】 【Pages】:
【Authors】: Jianwen Zhang ; Changshui Zhang
【Abstract】: Traditional clustering methods deal with a single clustering task on a single data set. However, in some newly emerging applications, multiple similar clustering tasks are involved simultaneously. In this case, we not only desire a partition for each task, but also want to discover the relationship among clusters of different tasks. It's also expected that the learnt relationship among tasks can improve performance of each single task. In this paper, we propose a general framework for this problem and further suggest a specific approach. In our approach, we alternatively update clusters and learn relationship between clusters of different tasks, and the two phases boost each other. Our approach is based on the general Bregman divergence, hence it's suitable for a large family of assumptions on data distributions and divergences. Empirical results on several benchmark data sets validate the approach.
【Keywords】: Multitask learning; Clustering; Bregman divergence
【Paper Link】 【Pages】:
【Authors】: Yan-Ming Zhang ; Yu Zhang ; Dit-Yan Yeung ; Cheng-Lin Liu ; Xinwen Hou
【Abstract】: Graph-based semi-supervised learning methods are based on some smoothness assumption about the data. As a discrete approximation of the data manifold, the graph plays a crucial role in the success of such graph-based methods. In most existing methods, graph construction makes use of a predefined weighting function without utilizing label information even when it is available. In this work, by incorporating label information, we seek to enhance the performance of graph-based semi-supervised learning by learning the graph and label inference simultaneously. In particular, we consider a particular setting of semi-supervised learning called transductive learning. Using the LogDet divergence to define the objective function, we propose an iterative algorithm to solve the optimization problem which has closed-form solution in each step. We perform experiments on both synthetic and real data to demonstrate improvement in the graph and in terms of classification accuracy.
【Keywords】: semi-supervised learning; transductive learning; classification;
【Paper Link】 【Pages】:
【Authors】: Yi Zhang
【Abstract】: Many problems in information extraction, text mining, natural language processing and other fields exhibit the same property: multiple prediction tasks are related in the sense that their outputs (labels) satisfy certain constraints. In this paper, we propose an active learning framework exploiting such relations among tasks. Intuitively, with task outputs coupled by constraints, active learning can utilize not only the uncertainty of the prediction in a single task but also the inconsistency of predictions across tasks. We formalize this idea as a cross-task value of information criteria, in which the reward of a labeling assignment is propagated and measured over all relevant tasks reachable through constraints. A specific example of our framework leads to the cross entropy measure on the predictions of coupled tasks, which generalizes the entropy in the classical single-task uncertain sampling. We conduct experiments on two real-world problems: web information extraction and document classification. Empirical results demonstrate the effectiveness of our framework in actively collecting labeled examples for multiple related tasks.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Zheng Zhao ; Lei Wang ; Huan Liu
【Abstract】: Spectral feature selection identifies relevant features by measuring their capability of preserving sample similarity. It provides a powerful framework for both supervised and unsupervised feature selection, and has been proven to be effective in many real-world applications. One common drawback associated with most existing spectral feature selection algorithms is that they evaluate features individually and cannot identify redundant features. Since redundant features can have significant adverse effect on learning performance, it is necessary to address this limitation for spectral feature selection. To this end, we propose a novel spectral feature selection algorithm to handle feature redundancy, adopting an embedded model. The algorithm is derived from a formulation based on a sparse multi-output regression with a L 2,1 -norm constraint. We conduct theoretical analysis on the properties of its optimal solutions, paving the way for designing an efficient path-following solver. Extensive experiments show that the proposed algorithm can do well in both selecting relevant features and removing redundancy.
【Keywords】: feature selection, multi-output regression, L2-1 norm regularization, sparse learning, dimension reduction, machine learning, data mining
【Paper Link】 【Pages】:
【Authors】: Guoqiang Zhong ; Wu-Jun Li ; Dit-Yan Yeung ; Xinwen Hou ; Cheng-Lin Liu
【Abstract】: In this paper, we propose a novel supervised extension of GPLVM, called Gaussian process latent random field (GPLRF), by enforcing the latent variables to be a Gaussian Markov random field with respect to a graph constructed from the supervisory information.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Alon Altman ; Robert Kleinberg
【Abstract】: Tournament solution concepts, selecting winners based on a pairwise dominance relation are an important structure often used in sports, as well as elections, and argumentation theory. Manipulation of such choice rules by coalitions of agents are a significant problem in most common rules. We deal with the problem of the manipulation of randomized choice rules by coalitions varying from a single agent, to two or more agents. We define two notions of coalitional manipulations of such choice rules based on whether or not utility is transferable. We show useful choice rules satisfying both notions of non-manipulability, and for the transferable utility case provide bounds on the level of Condorcet consistency.
【Keywords】: Tournaments; Manipulation; Coalitions
【Paper Link】 【Pages】:
【Authors】: Itai Ashlagi ; Moshe Tennenholtz ; Aviv Zohar
【Abstract】: Previous work on machine scheduling has considered the case of agents who control the scheduled jobs and attempt to minimize their own completion time. We argue that in cloud and grid computing settings, different machines cannot be considered to be fully cooperative as they may belong to competing economic entities, and that agents can easily move their jobs between competing providers. We therefore consider a setting in which the machines are also controlled by selfish agents, and attempt to maximize their own gains by strategically selecting their scheduling policy. We analyze the equilibria that arise due to competition in this 2-sided setting. In particular, not only do we require that the jobs will be in equilibrium with one another, but also that the schedulers' policies will be in equilibrium. We also consider different mixtures of classic deterministic scheduling policies and random scheduling policies.
【Keywords】: Scheduling; Competition; Cloud Computing; Equilibrium
【Paper Link】 【Pages】:
【Authors】: Yoram Bachrach ; Nadja Betzler ; Piotr Faliszewski
【Abstract】: We study the computational complexity of the counting version of the Possible-Winner problem for elections. In the Possible-Winner problem we are given a profile of voters, each with a partial preference order, and ask if there are linear extensions of the votes such that a designated candidate wins. We also analyze a special case of Possible-Winner, the Manipulation problem. We provide polynomial-time algorithms for counting manipulations in a class of scoring protocols and in several other voting rules. We show #P-hardness of the counting variant of Possible-Winner for plurality and veto and give a simple yet general and practically useful randomized algorithm for a variant of Possible-Winner for all voting rules for which a winner can be computed in polynomial time.
【Keywords】: counting; possible winner; manipulation; scoring protocols; voting
【Paper Link】 【Pages】:
【Authors】: Yoram Bachrach ; Reshef Meir ; Kyomin Jung ; Pushmeet Kohli
【Abstract】: We consider optimizing the coalition structure in Coalitional Skill Games (CSGs), a succinct representation of coalitional games. In CSGs, the value of a coalition depends on the tasks its members can achieve. The tasks require various skills to complete them, and agents may have different skill sets. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that CSGs can represent any characteristic function, and consider optimal coalition structure generation in this representation. We provide hardness results, showing that in general CSGs, as well as in very restricted versions of them, computing the optimal coalition structure is hard. On the positive side, we show that the problem can be reformulated as constraint satisfaction on a hyper graph, and present an algorithm that finds the optimal coalition structure in polynomial time for instances with bounded tree-width and number of tasks.
【Keywords】: Cooperative Games; Coalitional Skill Games; Coalition Structure Generation
【Paper Link】 【Pages】:
【Authors】: Ronen I. Brafman ; Carmel Domshlak ; Yagil Engel ; Moshe Tennenholtz
【Abstract】: Connecting between standard AI planning constructs and a classical cooperative model of transferable-utility coalition games, we introduce the notion of transferable-utility (TU) planning games. The key representational property of these games is that coalitions are valued implicitly based on their ability to carry out efficient joint plans. On the side of the expressiveness, we show that existing succinct representations of monotonic TU games can be efficiently compiled into TU planning games. On the side of computation, TU planning games allow us to provide some of the strongest to date tractability results for core-existence and core-membership queries in succinct TU coalition games.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Felix Brandt ; Markus Brill ; Edith Hemaspaandra ; Lane A. Hemaspaandra
【Abstract】: For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. It is important to learn how robust these hardness protection results are, in order to find whether they can be relied on in practice. This paper shows that for voters who follow the most central political-science model of electorates — single-peaked preferences — those protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we show that NP-hard bribery problems — including those for Kemeny and Llull elections- — fall to polynomial time. By using single-peaked preferences to simplify combinatorial partition challenges, we show that NP-hard partition-of-voters problems fall to polynomial time. We furthermore show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Θ 2 p -complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.
【Keywords】: Social Choice; Preferences; Computational Complexity of Reasoning
【Paper Link】 【Pages】:
【Authors】: Mickey Brautbar ; Michael Kearns ; Umar Syed
【Abstract】: We consider risk-sensitive generalizations of Nash and correlated equilibria in noncooperative games. We prove that, except for a class of degenerate games, unless a two-player game has a pure Nash equilibrium, it does not have a risk-sensitive Nash equilibrium. We also show that every game has a risk-sensitive correlated equilibrium. The striking contrast between these existence results is due to the different sources of randomization in Nash (private randomization) and correlated equilibria (third-party randomization).
【Keywords】: game theory
【Paper Link】 【Pages】:
【Authors】: Andriy Burkov ; Brahim Chaib-draa
【Abstract】: This paper presents a technique for approximating, up to any precision, the set of subgame-perfect equilibria (SPE) in repeated games with discounting. The process starts with a single hypercube approximation of the set of SPE payoff profiles. Then the initial hypercube is gradually partitioned on to a set of smaller adjacent hypercubes, while those hypercubes that cannot contain any SPE point are gradually withdrawn. Whether a given hypercube can contain an equilibrium point is verified by an appropriate mixed integer program. A special attention is paid to the question of extracting players' strategies and their representability in form of finite automata.
【Keywords】: multiagent systems; game theory; repeated games; subgame-perfect equilibrium; computation
【Paper Link】 【Pages】:
【Authors】: Ioannis Caragiannis ; Dimitris Kalaitzis ; Evangelos Markakis
【Abstract】: We consider approval voting elections in which each voter votes for a (possibly empty) set of candidates and the outcome consists of a set of k candidates for some parameter k, e.g., committee elections. We are interested in the minimax approval voting rule in which the outcome represents a compromise among the voters, in the sense that the maximum distance between the preference of any voter and the outcome is as small as possible. This voting rule has two main drawbacks. First, computing an outcome that minimizes the maximum distance is computationally hard. Furthermore, any algorithm that always returns such an outcome provides incentives to voters to misreport their true preferences. In order to circumvent these drawbacks, we consider approximation algorithms, i.e., algorithms that produce an outcome that approximates the minimax distance for any given instance. Such algorithms can be considered as alternative voting rules. We present a polynomial-time 2-approximation algorithm that uses a natural linear programming relaxation for the underlying optimization problem and deterministically rounds the fractional solution in order to compute the outcome; this result improves upon the previously best known algorithm that has an approximation ratio of 3. We are furthermore interested in approximation algorithms that are resistant to manipulation by (coalitions of) voters, i.e., algorithms that do not motivate voters to misreport their true preferences in order to improve their distance from the outcome. We complement previous results in the literature with new upper and lower bounds on strategyproof and group-strategyproof algorithms.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Ioannis Caragiannis ; Ariel D. Procaccia
【Abstract】: In cooperative multiagent systems an alternative that maximizes the social welfare — the sum of utilities — can only be selected if each agent reports its full utility function. This may be infeasible in environments where communication is restricted. Employing a voting rule to choose an alternative greatly reduces the communication burden, but leads to a possible gap between the social welfare of the optimal alternative and the social welfare of the one that is ultimately elected. Procaccia and Rosenschein have introduced the concept of distortion to quantify this gap. In this paper, we present the notion of embeddings into voting rules: functions that receive an agent's utility function and return the agent's vote. We establish that very low distortion can be obtained using randomized embeddings, especially when the number of agents is large compared to the number of alternatives. We investigate our ideas in the context of three prominent voting rules with low communication costs: Plurality, Approval, and Veto. Our results arguably provide a compelling reason for employing voting in cooperative multiagent systems.
【Keywords】: Social choice
【Paper Link】 【Pages】:
【Authors】: Archie C. Chapman ; Alessandro Farinelli ; Enrique Munoz de Cote ; Alex Rogers ; Nicholas R. Jennings
【Abstract】: We develop an efficient algorithm for computing pure strategy Nash equilibria that satisfy various criteria (such as the utilitarian or Nash-Bernoulli social welfare functions) in games with sparse interaction structure. Our algorithm, called Valued Nash Propagation (VNP), integrates the optimisation problem of maximising a criterion with the constraint satisfaction problem of finding a game's equilibria to construct a criterion that defines a c -semiring. Given a suitably compact game structure, this criterion can be efficiently optimised using message-passing. To this end, we first show that VNP is complete in games whose interaction structure forms a hypertree. Then, we go on to provide theoretic and empirical results justifying its use on games with arbitrary structure; in particular, we show that it computes the optimum >82% of the time and otherwise selects an equilibrium that is always within 2% of the optimum on average.
【Keywords】: Game theory, distributed optimisation
【Paper Link】 【Pages】:
【Authors】: Yiling Chen ; John K. Lai ; David C. Parkes ; Ariel D. Procaccia
【Abstract】: Cake cutting is a common metaphor for the division of a heterogeneous divisible good. There are numerous papers that study the problem of fairly dividing a cake; a small number of them also take into account self-interested agents and consequent strategic issues, but these papers focus on fairness and consider a strikingly weak notion of truthfulness. In this paper we investigate the problem of cutting a cake in a way that is truthful and fair, where for the first time our notion of dominant strategy truthfulness is the ubiquitous one in social choice and computer science. We design both deterministic and randomized cake cutting algorithms that are truthful and fair under different assumptions with respect to the valuation functions of the agents.
【Keywords】: Cake cutting; Mechanism design
【Paper Link】 【Pages】:
【Authors】: Yann Chevaleyre ; Jérôme Lang ; Nicolas Maudet ; Jérôme Monnot
【Abstract】: In some voting situations, some new candidates may show up in the course of the process. In this case, we may want to determine which of the initial candidates are possible winners, given that a fixed number k of new candidates will be added. Focusing on scoring rules, we give complexity results for the above possible winner problem.
【Keywords】: computational social choice
【Paper Link】 【Pages】:
【Authors】: Edith Elkind ; Piotr Faliszewski ; Arkadii M. Slinko
【Abstract】: We consider the problem of manipulating elections via cloning candidates. In our model, a manipulator can replace each candidate c by one or more clones, i.e., new candidates that are so similar to c that each voter simply replaces c in his vote with the block of c 's clones. The outcome of the resulting election may then depend on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of prominent voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with the related problem of control via adding candidates.
【Keywords】: elections; cloning; computational complexity;
【Paper Link】 【Pages】:
【Authors】: Edith Elkind ; Piotr Faliszewski ; Arkadii M. Slinko
【Abstract】: We explore the relationship between two approaches to rationalizing voting rules: the maximum likelihood estimation (MLE) framework originally suggested by Condorcet and recently studied by Conitzer, Rognlie, and Xia, and the distance rationalizability (DR) framework of Elkind, Faliszewski, and Slinko. The former views voting as an attempt to reconstruct the correct ordering of the candidates given noisy estimates (i.e., votes), while the latter explains voting as search for the nearest consensus outcome. We provide conditions under which an MLE interpretation of a voting rule coincides with its DR interpretation, and classify a number of classic voting rules, such as Kemeny, Plurality, Borda and Single Transferable Vote (STV), according to how well they fit each of these frameworks. The classification we obtain is more precise than the ones that result from using MLE or DR alone: indeed, we show that the MLE approach can be used to guide our search for a more refined notion of distance rationalizability and vice versa.
【Keywords】: voting; distance rationalizability; maximum likelihood estimation; Kemeny; STV; plurality; Borda
【Paper Link】 【Pages】:
【Authors】: Umberto Grandi ; Ulle Endriss
【Abstract】: We consider problems where several individuals each need to make a yes/no choice regarding a number of issues and these choices then need to be aggregated into a collective choice. Depending on the application at hand, different combinations of yes/no may be considered rational. We can describe such rationality assumptions in terms of a propositional formula. The question then arises whether or not a given aggregation procedure will lift the rationality assumptions from the individual to the collective level, i.e., whether the collective choice will be rational whenever all individual choices are. To address this question, for each of a number of simple fragments of the language of propositional logic, we provide an axiomatic characterisation of the class of aggregation procedures that will lift all rationality assumptions expressible in that fragment.
【Keywords】: Computational Social Choice ; Binary Aggregation ; Combinatorial Domains
【Paper Link】 【Pages】:
【Authors】: John Grant ; Sarit Kraus ; Michael Wooldridge
【Abstract】: Intentions have been widely studied in AI, both in the context of decision-making within individual agents and in multi-agent systems. Work on intentions in multi-agent systems has focused on joint intention models, which characterise the mental state of agents with a shared goal engaged in teamwork. In the absence of shared goals, however, intentions play another crucial role in multi-agent activity: they provide a basis around which agents can mutually coordinate activities. Models based on shared goals do not attempt to account for or explain this role of intentions. In this paper, we present a formal model of multi-agent systems in which belief-desire-intention agents choose their intentions taking into account the intentions of others. To understand rational mental states in such a setting, we formally define and investigate notions of multi-agent intention equilibrium, which are related to equilibrium concepts in game theory.
【Keywords】: intentions; equilibrium; BDI models; game theory
【Paper Link】 【Pages】:
【Authors】: Manish Jain ; Erim Kardes ; Christopher Kiekintveld ; Fernando Ordóñez ; Milind Tambe
【Abstract】: Security games, and important class of Stackelberg games, are used in deployed decision-support tools in use by LAX police and the Federal Air Marshals Service. The algorithms used to solve these games find optimal randomized schedules to allocate security resources for infrastructure protection. Unfortunately, the state of the art algorithms either fail to scale or to provide a correct solution for large problems with arbitrary scheduling constraints. We introduce ASPEN, a branch-and-price approach that overcomes these limitations based on two key contributions: (i) A column-generation approach that exploits a novel network flow representation, avoiding a combinatorial explosion of schedule allocations; (ii) A branch-and-bound algorithm that generates bounds via a fast algorithm for solving security games with relaxed scheduling constraints. ASPEN is the first known method for efficiently solving massive security games with arbitrary schedules.
【Keywords】: Game Theory, Stackelberg Games, Branch and Price, Mixed Integer Linear Programs
【Paper Link】 【Pages】:
【Authors】: Patrick R. Jordan ; Michael P. Wellman
【Abstract】: Many computational problems in game theory, such as finding Nash equilibria, are algorithmically hard to solve. This limitation forces analysts to limit attention to restricted subsets of the entire strategy space. We develop algorithms to identify rationally closed subsets of the strategy space under given size constraints. First, we modify an existing family of algorithms for rational closure in two-player games to compute a related rational closure concept, called formations , for n -player games. We then extend these algorithms to apply in cases where the utility function is partially specified, or there is a bound on the size of the restricted profile space. Finally, we evaluate the performance of these algorithms on a class of random games.
【Keywords】: Formations; Algorithmic game theory
【Paper Link】 【Pages】:
【Authors】: Dmytro Korzhyk ; Vincent Conitzer ; Ronald Parr
【Abstract】: Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (security personnel) can commit to a mixed strategy, a so-called Stackelberg model. As pointed out by Kiekintveld et al. (2009), in these applications, generally, multiple resources need to be assigned to multiple targets, resulting in an exponential number of pure strategies for the defender. In this paper, we study how to compute optimal Stackelberg strategies in such games, showing that this can be done in polynomial time in some cases, and is NP-hard in others.
【Keywords】: Game Theory
【Paper Link】 【Pages】:
【Authors】: Sébastien Lahaie
【Abstract】: We present the design and analysis of an approximately incentive-compatible combinatorial auction. In just a single run, the auction is able to extract enough value information from bidders to compute approximate truth-inducing payments. This stands in contrast to current auction designs that need to repeat the allocation computation as many times as there are bidders to achieve incentive compatibility. The auction is formulated as a kernel method, which allows for flexibility in choosing the price structure via a kernel function. Our main result characterizes the extent to which our auction is incentive-compatible in terms of the complexity of the chosen kernel function. Our analysis of the auction's properties is based on novel insights connecting the notion of stability in statistical learning theory to that of universal competitive equilibrium in the auction literature.
【Keywords】: auctions; kernel methods; incentives
【Paper Link】 【Pages】:
【Authors】: Raz Lin ; Sarit Kraus ; Yinon Oshrat ; Ya'akov (Kobi) Gal
【Abstract】: Computer agents are increasingly deployed in settings in which they make decisions with people, such as electronic commerce, collaborative interfaces, and cognitive assistants. However, the scientific evaluation of computational strategies for human-computer decision-making is a costly process, involving time, effort and personnel. This paper investigates the use of Peer Designed Agents (PDA) — computer agents developed by human subjects — as a tool for facilitating the evaluation process of automatic negotiators that were developed by researchers. It compared the performance between automatic negotiators that interacted with PDAs to automatic negotiators that interacted with actual people in different domains. The experiments included more than 300 human subjects and 50 PDAs developed by students. Results showed that the automatic negotiators outperformed PDAs in the same situations in which they outperformed people, and that on average, they exhibited the same measure of generosity towards their negotiation partners. These patterns were significant for all types of domains, and for all types of automated negotiators, despite the fact that there were individual differences between the behavior of PDAs and people. The study thus provides an empirical proof that PDAs can alleviate the evaluation process of automatic negotiators, and facilitate their design.
【Keywords】: peer designed agents; evaluation techniques; automated negotiation
【Paper Link】 【Pages】:
【Authors】: Reshef Meir ; Maria Polukarov ; Jeffrey S. Rosenschein ; Nicholas R. Jennings
【Abstract】: Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to AI. In such situations, agents' individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. Based on the fact that agents may have incentives to vote strategically and misreport their real preferences, a number of recent papers have explored different possibilities for avoiding or eliminating such manipulations. In contrast to most prior work, this paper focuses on convergence of strategic behavior to a decision from which no voter will want to deviate. We consider scenarios where voters cannot coordinate their actions, but are allowed to change their vote after observing the current outcome. We focus on the Plurality voting rule, and study the conditions under which this iterative game is guaranteed to converge to a Nash equilibrium (i.e., to a decision that is stable against further unilateral manipulations). We show for the first time how convergence depends on the exact attributes of the game, such as the tie-breaking scheme, and on assumptions regarding agents' weights and strategies.
【Keywords】: social choice, voting, plurality, equilibrium, convergence
【Paper Link】 【Pages】:
【Authors】: Abraham Othman ; Tuomas Sandholm
【Abstract】: Using a model of agent behavior based around envy-reducing strategies, we describe an iterated combinatorial auction in which the allocation and prices converge to a solution in the core of the agents' true valuations. In each round of the iterative auction mechanism, agents act on envy quotes produced by the mechanism: hints that suggest the prices of the bundles they are interested in. We describe optimal methods of generating envy quotes for various core-selecting mechanisms. Prior work on core-selecting combinatorial auctions has required agents to have perfect information about every agent's valuations to achieve a solution in the core. In contrast, here a core solution is reached even in the private information setting.
【Keywords】: Game Theory; Mechanism Design; Combinatorial Auctions; Envy
【Paper Link】 【Pages】:
【Authors】: Ariel D. Procaccia
【Abstract】: The Gibbard-Satterthwaite Theorem asserts that any reasonable voting rule cannot be strategyproof. A large body of research in AI deals with circumventing this theorem via computational considerations; the goal is to design voting rules that are computationally hard, in the worst-case, to manipulate. However, recent work indicates that the prominent voting rules are usually easy to manipulate. In this paper, we suggest a new CS-oriented approach to circumventing Gibbard-Satterthwaite, using randomization and approximation. Specifically, we wish to design strategyproof randomized voting rules that are close, in a standard approximation sense, to prominent score-based (deterministic) voting rules. We give tight lower and upper bounds on the approximation ratio achievable via strategyproof randomized rules with respect to positional scoring rules, Copeland, and Maximin.
【Keywords】: Social choice
【Paper Link】 【Pages】:
【Authors】: Amirali Salehi-Abari ; Tony White
【Abstract】: Recent work has demonstrated that several trust and reputation models can be exploited by malicious agents with cyclical behaviour. In each cycle, the malicious agent with cyclical behaviour first regains a high trust value after a number of cooperations and then abuses its gained trust by engaging in a bad transaction. Using a game theoretic formulation, Salehi-Abari and White have proposed the AER model that is resistant to exploitation by cyclical behaviour. Their simulation results imply that FIRE, Regret, and a model due to Yu and Singh, can always be exploited with an appropriate value for the period of cyclical behaviour. Furthermore, their results demonstrate that this is not so for the proposed adaptive scheme. This paper provides a mathematical analysis of the properties of five trust models when faced with cyclical behaviour of malicious agents. Three main results are proven. First, malicious agents can always select a cycle period that allows them to exploit the four models of FIRE, Regret, Probabilistic models, and Yu and Singh indefinitely. Second, malicious agents cannot select a single, finite cycle period that allows them to exploit the AER model forever. Finally, the number of cooperations required to achieve a given trust value increases monotonically with each cycle. In addition to the mathematical analysis, this paper empirically shows how malicious agents can use the theorems proven in this paper to mount efficient attacks on trust models.
【Keywords】: Trust Models; Exploitation; Mathematical Analysis; Con-man Agent; Vulnerability; Attack
【Paper Link】 【Pages】:
【Authors】: David Sarne ; Simon Shamoun ; Eli Rata
【Abstract】: This paper investigates search techniques for multi-agent settings in which the most suitable agent, according to given criteria, needs to be found. In particular, it considers the case where the searching agent incurs a cost for learning the value of an agent and the goal is to minimize the expected overall cost of search by iteratively increasing the extent of search. This kind of search is applicable to various domains, including auctions, first responders, and sensor networks. Using an innovative transformation of the extents-based sequence to a probability-based one, the optimal sequence is proved to consist of either a single search iteration or an infinite sequence of increasing search extents. This leads to a simplified characterization of the the optimal search sequence from which it can be derived. This method is also highly useful for legacy economic-search applications, where all agents are considered suitable candidates and the goal is to optimize the search process as a whole. The effectiveness of the method for both best-valued search and economic search is demonstrated numerically using a synthetic environment.
【Keywords】: Multiagent Systems; Sequential Decision Making; eCommerce
【Paper Link】 【Pages】:
【Authors】: Travis C. Service ; Julie A. Adams
【Abstract】: Coalition formation is a fundamental problem in multi-agent systems. In characteristic function games (CFGs), each coalition C of agents is assigned a value indicating the joint utility those agents will receive if C is formed. CFGs are an important class of cooperative games; however, determining the optimal coalition structure, partitioning of the agents into a set of coalitions that maximizes the social welfare, currently requires O (3 n ) time for n agents. In light of the high computational complexity of the coalition structure generation problem, a natural approach is to relax the optimality requirement and attempt to find an approximate solution that is guaranteed to be close to optimal. Unfortunately, it has been shown that guaranteeing a solution within any factor of the optimal requires Ω(2 n ) time. Thus, the best that can be hoped for is to find an algorithm that returns solutions that are guaranteed to be as close to the optimal as possible, in as close to O (2 n ) time as possible. This paper contributes to the state-of-the-art by presenting an algorithm that achieves better quality guarantees with lower worst case running times than all currently existing algorithms. Our approach is also the first algorithm to guarantee a constant factor approximation ratio, 1/8, in the optimal time of O (2 n . The previous best ratio obtainable in O (2 n ) was 2/ n .
【Keywords】: coalition structure generation; coalition formation; characteristic function game
【Paper Link】 【Pages】:
【Authors】: Sven Seuken ; Jie Tang ; David C. Parkes
【Abstract】: In distributed work systems, individual users perform work for other users. A significant challenge in these systems is to provide proper incentives for users to contribute as much work as they consume, even when monitoring is not possible. We formalize the problem of designing "incentive-compatible accounting mechanisms" that measure the net contributions of users, despite relying on voluntary reports. We introduce the Drop-Edge Mechanism that removes any incentive for a user to manipulate via misreports about work contributed or consumed. We prove that Drop-Edge provides a good approximation to a user's net contribution, and is accurate in the limit as the number of users grows. We demonstrate very good welfare properties in simulation compared to an existing, manipulable mechanism. In closing, we show the power of sybil attacks in accounting mechanisms and discuss our ongoing work, including a real-world implementation and evaluation of the Drop-Edge Mechanism in a BitTorrent client.
【Keywords】: mechanism design; distributed work systems; misreports; sybil attacks
【Paper Link】 【Pages】:
【Authors】: Ankit Sharma ; Tuomas Sandholm
【Abstract】: In many auctions, agents bid more aggressively than self-interest would prescribe. This can be explained by spite, where the agent's utility not only increases in the agent's surplus but also decreases as the other bidders' surpluses increase. Spite can stem from long-term benefits from making competitors worse off and from inherent psychological effects. There have been important recent game-theoretic analyses of spiteful bidding assuming all agents are equally spiteful. We present, to our knowledge, the first auction analysis in the more realistic setting where bidders may be spiteful to different extents. We show that the equilibrium bidding function can still be written in the same form — except that the spite factor is replaced by an expressed spite factor. This leads to bidders expressing spites that are higher or lower than their true spite depending on others' spite. Perhaps surprisingly, in the two-bidder case, the mapping from true spite to expressed spite is the same across all common auction mechanisms. Furthermore, even with two bidders, important properties of symmetric-spite settings cease to hold: the allocation can be inefficient and the revenue ranking may reverse between first- and second-price auctions. We also show that in sealed-bid auctions under asymmetric valuation distributions, there can be a "bargaining problem" in selecting bids. Finally, we study the generalization where agents can have different extents of spite toward different other bidders.
【Keywords】: Auctions and Market-Based Systems, Game Theory, E-Commerce
【Paper Link】 【Pages】:
【Authors】: Ruben Stranders ; Francesco Maria Delle Fave ; Alex Rogers ; Nicholas R. Jennings
【Abstract】: We present an on-line decentralised algorithm for coordinating mobile sensors for a broad class of information gathering tasks. These sensors can be deployed in unknown and possibly hostile environments, where uncertainty and dynamism are endemic. Such environments are common in the areas of disaster response and military surveillance. Our coordination approach itself is based on work by Stranders et al. (2009), that uses the max-sum algorithm to coordinate mobile sensors for monitoring spatial phenomena. In particular, we generalise and extend their approach to any domain where measurements can be valued. Also, we introduce a clustering approach that allows sensors to negotiate over paths to the most relevant locations, as opposed to a set of fixed directions, which results in a significantly improved performance. We demonstrate our algorithm by applying it to two challenging and distinct information gathering tasks. In the first–pursuit-evasion (PE)–sensors need to capture a target whose movement might be unknown. In the second–patrolling (P)–sensors need to minimise loss from intrusions that occur within their environment. In doing so, we obtain the first decentralised coordination algorithms for these domains. Finally, in each domain, we empirically evaluate our approach in a simulated environment, and show that it outperforms two state of the art greedy algorithms by 30% (PE) and 44% (P), and an existing approach based on the Travelling Salesman Problem by 52% (PE) and 30% (P).
【Keywords】: mobile sensors; decentralised coordination; max sum
【Paper Link】 【Pages】:
【Authors】: Jason Tsai ; Zhengyu Yin ; Jun-young Kwak ; David Kempe ; Christopher Kiekintveld ; Milind Tambe
【Abstract】: Law enforcement agencies frequently must allocate limited resources to protect targets embedded in a network, such as important buildings in a city road network. Since intelligent attackers may observe and exploit patterns in the allocation, it is crucial that the allocations be randomized. We cast this problem as an attacker-defender Stackelberg game: the defender’s goal is to obtain an optimal mixed strategy for allocating resources. The defender’s strategy space is exponential in the number of resources, and the attacker’s exponential in the network size. Existing algorithms are therefore useless for all but the smallest networks. We present a solution approach based on two key ideas: (i) A polynomial-sized game model obtained via an approximation of the strategy space, solved efficiently using a linear program; (ii) Two efficient techniques that map solutions from the approximate game to the original, with proofs of correctness under certain assumptions. We present in-depth experimental results, including an evaluation on part of the Mumbai road network.
【Keywords】: Game Theory, Resource Allocation, Security, Stackelberg Games
【Paper Link】 【Pages】:
【Authors】: William E. Walsh ; Craig Boutilier ; Tuomas Sandholm ; Rob Shields ; George L. Nemhauser ; David C. Parkes
【Abstract】: The use of simple auction mechanisms like the GSP in online advertising can lead to significant loss of efficiency and revenue when advertisers have rich preferences — even simple forms of expressiveness like budget constraints can lead to suboptimal outcomes. While the optimal allocation of inventory can provide greater efficiency and revenue, natural formulations of the underlying optimization problems grow exponentially in the number of features of interest, presenting a key practical challenge. To address this problem, we propose a means for automatically partitioning inventory into abstract channels so that the least relevant features are ignored. Our approach, based on LP/MIP column and constraint generation, dramatically reduces the size of the problem, thus rendering optimization computationally feasible at practical scales. Our algorithms allow for principled tradeoffs between tractability and solution quality. Numerical experiments demonstrate the computational practicality of our approach as well as the quality of the resulting abstractions.
【Keywords】: advertising auctions, electronic commerce, expressive auctions
【Paper Link】 【Pages】:
【Authors】: Virginia Vassilevska Williams
【Abstract】: We consider a very natural problem concerned with game manipulation. Let G be a directed graph where the nodes represent players of a game, and an edge from u to v means that u can beat v in the game. (If an edge ( u, v ) is not present, one cannot match u and v. ) Given G and a "favorite" node A , is it possible to set up the bracket of a balanced single-elimination tournament so that A is guaranteed to win, if matches occur as predicted by G? We show that the problem is NP-complete for general graphs. For the case when G is a tournament graph we give several interesting conditions on the desired winner A for which there exists a balanced single-elimination tournament which A wins, and it can be found in polynomial time.
【Keywords】: agenda control; tournament graph; single-elimination; manipulation
【Paper Link】 【Pages】:
【Authors】: James R. Wright ; Kevin Leyton-Brown
【Abstract】: It is standard in multiagent settings to assume that agents will adopt Nash equilibrium strategies. However, studies in experimental economics demonstrate that Nash equilibrium is a poor description of human players' initial behavior in normal-form games. In this paper, we consider a wide range of widely-studied models from behavioral game theory. For what we believe is the first time, we evaluate each of these models in a meta-analysis, taking as our data set large-scale and publicly-available experimental data from the literature. We then propose modifications to the best-performing model that we believe make it more suitable for practical prediction of initial play by humans in normal-form games.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Feng Wu ; Shlomo Zilberstein ; Xiaoping Chen
【Abstract】: Trial-based approaches offer an efficient way to solve single-agent MDPs and POMDPs. These approaches allow agents to focus their computations on regions of the environment they encounter during the trials, leading to significant computational savings. We present a novel trial-based dynamic programming (TBDP) algorithm for DEC-POMDPs that extends these benefits to multi-agent settings. The algorithm uses trial-based methods for both belief generation and policy evaluation. Policy improvement is implemented efficiently using linear programming and a sub-policy reuse technique that helps bound the amount of memory. The results show that TBDP can produce significant value improvements and is much faster than the best existing planning algorithms.
【Keywords】: Multi-Agent Planning; Cooperation and Coordination; Decentralized POMDPs
【Paper Link】 【Pages】:
【Authors】: Lirong Xia ; Vincent Conitzer
【Abstract】: In computational social choice, one important problem is to take the votes of a subelectorate (subset of the voters), and summarize them using a small number of bits. This needs to be done in such a way that, if all that we know is the summary, as well as the votes of voters outside the subelectorate, we can conclude which of the m alternatives wins. This corresponds to the notion of compilation complexity, the minimum number of bits required to summarize the votes for a particular rule, which was introduced by Chevaleyre et al. [IJCAI-09]. We study three different types of compilation complexity. The first, studied by Chevaleyre et al., depends on the size of the subelectorate but not on the size of the complement (the voters outside the subelectorate). The second depends on the size of the complement but not on the size of the subelectorate. The third depends on both. We first investigate the relations among the three types of compilation complexity. Then, we give upper and lower bounds on all three types of compilation complexity for the most prominent voting rules. We show that for l -approval (when l ≤ m /2), Borda, and Bucklin, the bounds for all three types are asymptotically tight, up to a multiplicative constant; for l-approval (when l > m /2), plurality with runoff, all Condorcet consistent rules that are based on unweighted majority graphs (including Copeland and voting trees), and all Condorcet consistent rules that are based on the order of pairwise elections (including ranked pairs and maximin), the bounds for all three types are asymptotically tight up to a multiplicative constant when the sizes of the subelectorate and its complement are both larger than m 1+ε for some ε > 0.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Lirong Xia ; Vincent Conitzer
【Abstract】: We consider settings in which voters vote in sequence, each voter knows the votes of the earlier voters and the preferences of the later voters, and voters are strategic. This can be modeled as an extensive-form game of perfect information, which we call a Stackelberg voting game. We first propose a dynamic-programming algorithm for finding the backward-induction outcome for any Stackelberg voting game when the rule is anonymous; this algorithm is efficient if the number of alternatives is no more than a constant. We show how to use compilation functions to further reduce the time and space requirements. Our main theoretical results are paradoxes for the backward-induction outcomes of Stackelberg voting games. We show that for any n ≥ 5 and any voting rule that satisfies nonimposition and with a low domination index, there exists a profile consisting of n voters, such that the backward-induction outcome is ranked somewhere in the bottom two positions in almost every voter’s preferences. Moreover, this outcome loses all but one of its pairwise elections. Furthermore, we show that many common voting rules have a very low (= 1) domination index, including all majority-consistent voting rules. For the plurality and nomination rules, we show even stronger paradoxes. Finally, using our dynamic-programming algorithm, we run simulations to compare the backward-induction outcome of the Stackelberg voting game to the winner when voters vote truthfully, for the plurality and veto rules. Surprisingly, our experimental results suggest that on average, more voters prefer the backward-induction outcome.
【Keywords】: Stackelberg voting game; dynamic-programming; paradoxes
【Paper Link】 【Pages】:
【Authors】: Chongjie Zhang ; Victor R. Lesser
【Abstract】: Due to the non-stationary environment, learning in multi-agent systems is a challenging problem. This paper first introduces a new gradient-based learning algorithm, augmenting the basic gradient ascent approach with policy prediction. We prove that this augmentation results in a stronger notion of convergence than the basic gradient ascent, that is, strategies converge to a Nash equilibrium within a restricted class of iterated games. Motivated by this augmentation, we then propose a new practical multi-agent reinforcement learning (MARL) algorithm exploiting approximate policy prediction. Empirical results show that it converges faster and in a wider variety of situations than state-of-the-art MARL algorithms.
【Keywords】: Multi-agent reinforcement learning; Policy Prediction; Games; Nash Equilibrium
【Paper Link】 【Pages】:
【Authors】: Dongmo Zhang ; Laurent Perrussel
【Abstract】: Dynamic auctions are trading mechanisms for discovering market-clearing prices and efficient allocations based on price adjustment processes. This paper studies the computational issues of dynamic auctions for selling multiple indivisible items. Although the decision problem of efficient allocations in a dynamic auction in general is intractable, it can be solved in polynomial time if the economy under consideration satisfies the condition of Gross Substitutes and Complements, which is known as the most general condition that guarantees the existence of Walrasian equilibrium. We propose a polynomial algorithm that can be used to find efficient allocations and introduce a double-direction auction procedure to discover a Walrasian equilibrium in polynomial time.
【Keywords】: dynamic auction, double-direction auction, combinatorial auction
【Paper Link】 【Pages】:
【Authors】: Xiaoming Zheng ; Sven Koenig
【Abstract】: We study the distributed allocation of tasks to cooperating robots in real time, where each task has to be assigned to exactly one robot so that the sum of the latencies of all tasks is as small as possible. We propose a new auction-like algorithm, called Sequential Incremental-Value (SIV) auction, which assigns tasks to robots in multiple rounds. The idea behind SIV auctions is to assign as many tasks per round to robots as possible as long as their individual costs for performing these tasks are at most a given bound, which increases exponentially from round to round. Our theoretical results show that the team costs of SIV auctions are at most a constant factor larger than minimal.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: James Y. Zou ; Sujit Gujar ; David C. Parkes
【Abstract】: We study a problem of dynamic allocation without money. Agents have arrivals and departures and strict preferences over items. Strategyproofness requires the use of an arrival-priority serial-dictatorship (APSD) mechanism, which is ex post Pareto efficient but has poor ex ante efficiency as measured through average rank efficiency. We introduce the scoring-rule (SR) mechanism, which biases in favor of allocating items that an agent values above the population consensus. The SR mechanism is not strategyproof but has tolerable manipulability in the sense that: (i) if every agent optimally manipulates, it reduces to APSD, and (ii) it significantly outperforms APSD for rank efficiency when only a fraction of agents are strategic. The performance of SR is also robust to mistakes by agents that manipulate on the basis of inaccurate information about the popularity of items.
【Keywords】: Mechanism Design; Game Theory; Auctions and Market Based Systems
【Paper Link】 【Pages】:
【Authors】: Hilmar Finnsson ; Yngvi Björnsson
【Abstract】: The aim of General Game Playing (GGP) is to create intelligent agents that can automatically learn how to play many different games at an expert level without any human intervention. One of the main challenges such agents face is to automatically learn knowledge-based heuristics in real-time, whether for evaluating game positions or for search guidance. In recent years, GGP agents that use Monte-Carlo simulations to reason about their actions have become increasingly more popular. For competitive play such an approach requires an effective search-control mechanism for guiding the simulation playouts. In here we introduce several schemes for automatically learning search guidance based on both statistical and reinforcement learning techniques. We compare the different schemes empirically on a variety of games and show that they improve significantly upon the current state-of-the-art in simulation-control in GGP. For example, in the chess-like game Skirmish, which has proved a particularly challenging game for simulation-based GGP agents, an agent employing one of the proposed schemes achieves 97% winning rate against an unmodified agent.
【Keywords】: general game playing; search; machine learning
【Paper Link】 【Pages】:
【Authors】: Andrew Guillory ; Sumit Basu ; Dan Morris
【Abstract】: We consider the problem of automatic vocal melody transcription: translating an audio recording of a sung melody into a musical score. While previous work has focused on finding the closest notes to the singer's tracked pitch, we instead seek to recover the melody the singer intended to sing. Often, the melody a singer intended to sing differs from what they actually sang; our hypothesis is that this occurs in a singer-specific way. For example, a given singer may often be flat in certain parts of her range, or another may have difficulty with certain intervals. We thus pursue methods for singer-specific training which use learning to combine different methods for pitch prediction. In our experiments with human subjects, we show that via a short training procedure we can learn a singer-specific pitch predictor and significantly improve transcription of intended pitch over other methods. For an average user, our method gives a 20 to 30 percent reduction in pitch classification errors with respect to a baseline method which is comparable to commercial voice transcription tools. For some users, we achieve even more dramatic reductions. Our best results come from a combination of singer-specific-learning with non-singer-specific feature selection. We also discuss the implications of our work for training more general control signals. We make our experimental data available to allow others to replicate or extend our results.
【Keywords】: machine learning; pitch classification
【Paper Link】 【Pages】:
【Authors】: Yuewei Lin ; Bin Fang ; Yuanyan Tang
【Abstract】: This paper presents a computational framework for saliency maps. It employs the Earth Mover's Distance based on weighted-Histogram (EMD-wH) to measure the center-surround difference, instead of the Difference-of-Gaussian (DoG) filter used by traditional models. In addition, the model employs not only the traditional features such as colors, intensity and orientation but also the local entropy which expresses the local complexity. The major advantage of combining the local entropy map is that it can detect the salient regions which are not complex regions. Also, it uses a general framework to integrate the feature dimensions instead of summing the features directly. This model considers both local and global salient information, in contrast to the existing models that consider only one or the other. Furthermore, the "large scale bias" and "central bias" hypotheses are used in this model to select the fixation locations in the saliency map of different scales. The performance of this model is assessed by comparing their saliency maps and human fixation density. The results from this model are finally compared to those from other bottom-up models for reference.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Eric Jeffrey Peterson ; Thomas F. Stahovich ; Eric Doi ; Christine Alvarado
【Abstract】: Objects in freely-drawn sketches often have no spatial or temporal separation, making object recognition difficult. We present a two-step stroke-grouping algorithm that first classifies individual strokes according to the type of object to which they belong, then groups strokes with like classifications into clusters representing individual objects. The first step facilitates clustering by naturally separating the strokes, and both steps fluidly integrate spatial and temporal information. Our approach to grouping is unique in its formulation as an efficient classification task rather than, for example, an expensive search task. Our single-stroke classifier performs at least as well as existing single-stroke classifiers on text vs. nontext classification, and we present the first three-way single-stroke classification results. Our stroke grouping results are the first reported of their kind; our grouping algorithm correctly groups between 86% and 91% of the ink in diagrams from two domains, with between 69% and 79% of shapes being perfectly clustered.
【Keywords】: Stroke Grouping; Sketch Understanding; Classification
【Paper Link】 【Pages】:
【Authors】: Stephan Schiffel
【Abstract】: We develop a method for detecting symmetries in arbitrary games and exploiting these symmetries when using tree search to play the game. Games in the General Game Playing domain are given as a set of logic based rules defining legal moves, their effects and goals of the players. The presented method transforms the rules of a game into a vertex-labeled graph such that automorphisms of the graph correspond with symmetries of the game. The algorithm detects many kinds of symmetries that often occur in games, e.g., rotation and reflection symmetries of boards, interchangeable objects, and symmetric roles. A transposition table is used to efficiently exploit the symmetries in many games.
【Keywords】: Artificial Intelligence; General Game Playing; Symmetry; Symmetry Detection; Search
【Paper Link】 【Pages】:
【Authors】: Dafna Shahaf ; Eric Horvitz
【Abstract】: We discuss challenges and opportunities for developing generalized task markets where human and machine intelligence are enlisted to solve problems, based on a consideration of the competencies, availabilities, and pricing of different problem-solving resources. The approach couples human computation with machine learning and planning, and is aimed at optimizing the flow of subtasks to people and to computational problem solvers. We illustrate key ideas in the context of Lingua Mechanica, a project focused on harnessing human and machine translation skills to perform translation among languages. We present infrastructure and methods for enlisting and guiding human and machine computation for language translation, including details about the hardness of generating plans for assigning tasks to solvers. Finally, we discuss studies performed with machine and human solvers, focusing on components of a Lingua Mechanica prototype.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Michael Thielscher
【Abstract】: A General Game Player is a system that can play previously unknown games given nothing but their rules. The Game Description Language (GDL) has been developed as a high-level knowledge representation formalism for axiomatising the rules of any game, and a basic requirement of a General Game Player is the ability to reason logically about a given game description. In this paper, we address the fundamental limitation of existing GDL to be confined to deterministic games with complete information about the game state. To this end, we develop an extension of GDL that is both simple and elegant yet expressive enough to allow to formalise the rules of arbitrary (discrete and finite) n -player games with randomness and incomplete state knowledge. We also show that this extension suffices to provide players with all information they need to reason about their own knowledge as well as that of the other players up front and during game play.
【Keywords】: General Game Playing; Knowledge Representation
【Paper Link】 【Pages】:
【Authors】: Michael Thielscher ; Sebastian Voigt
【Abstract】: A general game player is a system that understands the rules of unknown games and learns to play these games well without human intervention. A major challenge for research in General Game Playing is to endow a player with the ability to extract and prove game-specific knowledge from the mere game rules. We define a formal language to express temporally extended — yet local — properties of games. We also develop a provably correct proof theory for this language using the paradigm of Answer Set Programming, and we report on experiments with a practical implementation of this proof system in combination with a successful general game player.
【Keywords】: General Game Playing; Automated Reasoning and Theorem Proving; Logic Programming
【Paper Link】 【Pages】:
【Authors】: Bi Chen ; Leilei Zhu ; Daniel Kifer ; Dongwon Lee
【Abstract】: In this paper, we propose a generative model to automatically discover the hidden associations between topics words and opinion words. By applying those discovered hidden associations, we construct the opinion scoring models to extract statements which best express opinionists’ standpoints on certain topics. For experiments, we apply our model to the political area. First, we visualize the similarities and dissimilarities between Republican and Democratic senators with respect to various topics. Second, we compare the performance of the opinion scoring models with 14 kinds of methods to find the best ones. We find that sentences extracted by our opinion scoring models can effectively express opinionists’ standpoints.
【Keywords】: opinion mining
【Paper Link】 【Pages】:
【Authors】: David K. Elson ; Kathleen McKeown
【Abstract】: We describe a method for identifying the speakers of quoted speech in natural-language textual stories. We have assembled a corpus of more than 3,000 quotations, whose speakers (if any) are manually identified, from a collection of 19th and 20th century literature by six authors. Using rule-based and statistical learning, our method identifies candidate characters, determines their genders, and attributes each quote to the most likely speaker. We divide the quotes into syntactic classes in order to leverage common discourse patterns, which enable rapid attribution for many quotes. We apply learning algorithms to the remainder and achieve an overall accuracy of 83%.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Jagadeesh Jagarlamudi ; Seth Juarez ; Hal Daumé III
【Abstract】: Kernelized sorting is an approach for matching objects from two sources (or domains) that does not require any prior notion of similarity between objects across the two sources. Unfortunately, this technique is highly sensitive to initialization and high dimensional data. We present variants of kernelized sorting to increase its robustness and performance on several Natural Language Processing (NLP) tasks: document matching from parallel and comparable corpora, machine transliteration and even image processing. Empirically we show that, on these tasks, a semi-supervised variant of kernelized sorting outperforms matching canonical correlation analysis.
【Keywords】: Kernelized Sorting, Semi Supervised technique, Alignment, NLP, matching
【Paper Link】 【Pages】:
【Authors】: Michal Ptaszynski ; Jacek Maciejewski ; Pawel Dybala ; Rafal Rzepka ; Kenji Araki
【Abstract】: This paper presents CAO, a system for affect analysis of emoticons. Emoticons are strings of symbols widely used in text-based online communication to convey emotions. It extracts emoticons from input and determines specific emotions they express. Firstly, by matching the extracted emoticons to a raw emoticon database, containing over ten thousand emoticon samples extracted from the Web and annotated automatically. The emoticons for which emotion types could not be determined using only this database, are automatically divided into semantic areas representing "mouths" or "eyes," based on the theory of kinesics. The areas are automatically annotated according to their co-occurrence in the database. The annotation is firstly based on the eye-mouth-eye triplet, and if no such triplet is found, all semantic areas are estimated separately. This provides the system coverage exceeding 3 million possibilities. The evaluation, performed on both training and test sets, confirmed the system's capability to sufficiently detect and extract any emoticon, analyze its semantic structure and estimate the potential emotion types expressed. The system achieved nearly ideal scores, outperforming existing emoticon analysis systems.
【Keywords】: Natural-Language Processing; Text Classification; Information Extraction; Human-Computer Interaction; Intelligent User Interfaces; Affect analysis; Emoticon; Facemark;
【Paper Link】 【Pages】:
【Authors】: John J. Tanner ; Fernando Gomez
【Abstract】: While there has been much research into using selectional preferences for word sense disambiguation (WSD), much difficulty has been encountered. To facilitate study into this difficulty and aid in WSD in general, a database of the selectional preferences of non-pertainym prenomial adjectives extracted from the Google Web 1T 5-gram Corpus is proposed. A variety of methods for computing the preferences of each adjective over a set of noun categories from WordNet have been evaluated via simulated disambiguation of pseudohomonyms. The best method of these involves computing for each noun category the ratio of single-word common (i.e. not proper) noun lemma types which can co-occur with a given adjective to the number of single-word common noun lemmata whose estimated frequency is greater than a threshold based on the frequency of the adjective. The database produced by this procedure will be made available to the public.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Hao Xiong ; Haitao Mi ; Yang Liu ; Qun Liu
【Abstract】: Parsing plays an important role in semantic role labeling (SRL) because most SRL systems infer semantic relations from 1-best parses. Therefore, parsing errors inevitably lead to labeling mistakes. To alleviate this problem, we propose to use packed forest, which compactly encodes all parses for a sentence. We design an algorithm to exploit exponentially many parses to learn semantic relations efciently. Experimental results on the CoNLL-2005 shared task show that using forests achieves an absolute improvement of 1.2% in terms of F1 score over using 1-best parses and 0.6% over using 50-best parses.
【Keywords】: Natural Language Processing;Semantics
【Paper Link】 【Pages】:
【Authors】: Xiaofeng Yu ; Wai Lam
【Abstract】: Traditional information extraction systems adopt pipeline strategies, which are highly ineffective and suffer from several problems such as error propagation. Typically, pipeline models fail to produce highly-accurate final output. On the other hand, there has been growing interest in integrated or joint models which explore mutual benefits and perform multiple subtasks simultaneously to avoid problems caused by pipeline models. However, building such systems usually increases computational complexity and requires considerable engineering. This paper presents a general, strongly-coupled, and bidirectional architecture based on discriminatively trained factor graphs for information extraction. First we introduce joint factors connecting variables of relevant subtasks to capture dependencies and interactions between them. We then propose a strong bidirectional MCMC sampling inference algorithm which allows information to flow in both directions to find the approximate MAP solution for all subtasks. Extensive experiments on entity identification and relation extraction using real-world data illustrate the promise of our approach.
【Keywords】: Information Extraction; Machine Learning
【Paper Link】 【Pages】:
【Authors】: Christopher Amato ; Blai Bonet ; Shlomo Zilberstein
【Abstract】: Existing controller-based approaches for centralized and decentralized POMDPs are based on automata with output known as Moore machines. In this paper, we show that several advantages can be gained by utilizing another type of automata, the Mealy machine. Mealy machines are more powerful than Moore machines, provide a richer structure that can be exploited by solution methods, and can be easily incorporated into current controller-based approaches. To demonstrate this, we adapted some existing controller-based algorithms to use Mealy machines and obtained results on a set of benchmark domains. The Mealy-based approach always outperformed the Moore-based approach and often outperformed the state-of-the-art algorithms for both centralized and decentralized POMDPs. These findings provide fresh and general insights for the improvement of existing algorithms and the development of new ones.
【Keywords】: Planning under uncertainty; POMDPs; DEC-POMDPs
【Paper Link】 【Pages】:
【Authors】: Bikramjit Banerjee ; Landon Kraemer ; Jeremy Lyle
【Abstract】:
Multi-Agent Plan Recognition (MAPR) seeks to identify the dynamic team structures and team behaviors from the observations of the activity-sequences of a set of intelligent agents, based on a library of known team-activities (plan library). It has important applications in analyzing data from automated monitoring, surveillance, and intelligence analysis in general. In this paper, we formalize MAPR using a basic model that explicates the cost of abduction in single agent plan recognition by "flattening" or decompressing the (usually compact, hierarchical) plan library. We show that single-agent plan recognition with a decompressed library can be solved in time polynomial in the input size, while it is known that with a compressed (by partial ordering constraints) library it is NP-complete. This leads to an important insight: that although the compactness of the plan library plays an important role in the hardness of single-agent plan recognition (as recognized in the existing literature), that is not the case with multiple agents. We show, for the first time, that MAPR is NP-complete even when the (multi-agent) plan library is fully decompressed. As with previous solution approaches, we break the problem into two stages: hypothesis generation and hypothesis search. We show that Knuth's Algorithm X'' (with the efficientdancing links'' representation) is particularly suited for our model, and can be adapted to perform a branch and bound search for the second stage, in this model. We show empirically that this new approach leads to significant pruning of the hypothesis space in MAPR.
【Keywords】: multi-agent plan recognition, multi-agent teams, multi-agent systems, plan recognition
【Paper Link】 【Pages】:
【Authors】: Pablo Samuel Castro ; Doina Precup
【Abstract】: Knowledge transfer has been suggested as a useful approach for solving large Markov Decision Processes. The main idea is to compute a decision-making policy in one environment and use it in a different environment, provided the two are ”close enough”. In this paper, we use bisimulation-style metrics (Ferns et al., 2004) to guide knowledge transfer. We propose algorithms that decide what actions to transfer from the policy computed on a small MDP task to a large task, given the bisimulation distance between states in the two tasks. We demonstrate the inherent ”pessimism” of bisimulation metrics and present variants of this metric aimed to overcome this pessimism, leading to improved action transfer. We also show that using this approach for transferring temporally extended actions (Sutton et al., 1999) is more successful than using it exclusively with primitive actions. We present theoretical guarantees on the quality of the transferred policy, as well as promising empirical results.
【Keywords】: Markov Decision Processes; Knowledge transfer; Bisimulation metrics; Options
【Paper Link】 【Pages】:
【Authors】: Carmel Domshlak ; Erez Karpas ; Shaul Markovitch
【Abstract】: It is well known that there cannot be a single "best" heuristic for optimal planning in general. One way of overcoming this is by combining admissible heuristics (e.g. by using their maximum), which requires computing numerous heuristic estimates at each state. However, there is a tradeoff between the time spent on computing these heuristic estimates for each state, and the time saved by reducing the number of expanded states. We present a novel method that reduces the cost of combining admissible heuristics for optimal search, while maintaining its benefits. Based on an idealized search space model, we formulate a decision rule for choosing the best heuristic to compute at each state. We then present an active online learning approach for that decision rule, and employ the learned model to decide which heuristic to compute at each state. We evaluate this technique empirically, and show that it substantially outperforms each of the individual heuristics that were used, as well as their regular maximum.
【Keywords】: search;optimal search;learning;planning
【Paper Link】 【Pages】:
【Authors】: Wenyuan Guo ; Tze-Yun Leong
【Abstract】: Model minimization in Factored Markov Decision Processes (FMDPs) is concerned with finding the most compact partition of the state space such that all states in the same block are action-equivalent. This is an important problem because it can potentially transform a large FMDP into an equivalent but much smaller one, whose solution can be readily used to solve the original model. Previous model minimization algorithms are iterative in nature, making opaque the relationship between the input model and the output partition. We demonstrate that given a set of well-defined concepts and operations on partitions, we can express the model minimization problem in an analytic fashion. The theoretical results developed can be readily applied to solving problems such as estimating the size of the minimum partition, refining existing algorithms, and so on.
【Keywords】: Markov Decision Processes
【Paper Link】 【Pages】:
【Authors】: Sonal Gupta ; Raymond J. Mooney
【Abstract】: Recognizing activities in real-world videos is a difficult problem exacerbated by background clutter, changes in camera angle & zoom, and rapid camera movements. Large corpora of labeled videos can be used to train automated activity recognition systems, but this requires expensive human labor and time. This paper explores how closed captions that naturally accompany many videos can act as weak supervision that allows automatically collecting "labeled" data for activity recognition. We show that such an approach can improve activity retrieval in soccer videos. Our system requires no manual labeling of video clips and needs minimal human supervision. We also present a novel caption classifier that uses additional linguistic information to determine whether a specific comment refers to an ongoing activity. We demonstrate that combining linguistic analysis and automatically trained activity recognizers can significantly improve the precision of video retrieval.
【Keywords】: Closed Captions; Weak Supervision; Video Retrieval; Human Action Recognition; Captioned Video; Multimodal Learning
【Paper Link】 【Pages】:
【Authors】: Ruijie He ; Emma Brunskill ; Nicholas Roy
【Abstract】: Planning in large, partially observable domains is challenging, especially when a long-horizon lookahead is necessary to obtain a good policy. Traditional POMDP planners that plan a different potential action for each future observation can be prohibitively expensive when planning many steps ahead. An efficient solution for planning far into the future in fully observable domains is to use temporally-extended sequences of actions, or "macro-actions." In this paper, we present a POMDP algorithm for planning under uncertainty with macro-actions (PUMA) that automatically constructs and evaluates open-loop macro-actions within forward-search planning, where the planner branches on observations only at the end of each macro-action. Additionally, we show how to incrementally refine the plan over time, resulting in an anytime algorithm that provably converges to an epsilon-optimal policy. In experiments on several large POMDP problems which require a long horizon lookahead, PUMA outperforms existing state-of-the art solvers.
【Keywords】: Planning under Uncertainty; POMDPs;
【Paper Link】 【Pages】:
【Authors】: Jörg Hoffmann ; Ingo Weber ; Frank Michael Kraft
【Abstract】: In several application areas for Planning, in particular helping with the creation of new processes in Business Process Management (BPM), a major obstacle lies in the modeling. Obtaining a suitable model to plan with is often prohibitively complicated and/or costly. Our core observation in this work is that, for software-architectural purposes, SAP is already using a model that is essentially a variant of PDDL. That model describes the behavior of Business Objects, in terms of status variables and how they are affected by system transactions. We show herein that one can leverage the model to obtain (a) a promising BPM planning application which incurs hardly any modeling costs, and (b) an interesting planning benchmark. We design a suitable planning formalism and an adaptation of FF, and we perform large-scale experiments. Our prototype is part of a research extension to the SAP NetWeaver platform.
【Keywords】: Artificial Intelligence; Planning; Business Process Management
【Paper Link】 【Pages】:
【Authors】: Li Ling Ko ; David Hsu ; Wee Sun Lee ; Sylvie C. W. Ong
【Abstract】: The behavior of a complex system often depends on parameters whose values are unknown in advance. To operate effectively, an autonomous agent must actively gather information on the parameter values while progressing towards its goal. We call this problem parameter elicitation. Partially observable Markov decision processes (POMDPs) provide a principled framework for such uncertainty planning tasks, but they suffer from high computational complexity. However, POMDPs for parameter elicitation often possess special structural properties, specifically, factorization and symmetry. This work identifies these properties and exploits them for efficient solution through a factored belief representation. The experimental results show that our new POMDP solvers outperform SARSOP and MOMDP, two of the fastest general-purpose POMDP solvers available, and can handle significantly larger problems.
【Keywords】: POMDPs; Planning under Uncertainty; Sequential Decision Making; Reasoning under Uncertainty; Reasoning about Plans, Processes and Actions
【Paper Link】 【Pages】:
【Authors】: Andrey Kolobov ; Mausam ; Daniel S. Weld
【Abstract】: The results of the latest International Probabilistic Planning Competition (IPPC-2008) indicate that the presence of dead ends, states with no trajectory to the goal, makes MDPs hard for modern probabilistic planners. Implicit dead ends, states with executable actions but no path to the goal, are particularly challenging; existing MDP solvers spend much time and memory identifying these states. As a first attempt to address this issue, we propose a machine learning algorithm called SIXTHSENSE. SIXTHSENSE helps existing MDP solvers by finding nogoods, conjunctions of literals whose truth in a state implies that the state is a dead end. Importantly, our learned nogoods are sound, and hence the states they identify are true dead ends. SIXTHSENSE is very fast, needs little training data, and takes only a small fraction of total planning time. While IPPC problems may have millions of dead ends, they may typically be represented with only a dozen or two no-goods. Thus, nogood learning efficiently produces a quick and reliable means for dead-end recognition. Our experiments show that the nogoods found by SIXTHSENSE routinely reduce planning space and time on IPPC domains, enabling some planners to solve problems they could not previously handle.
【Keywords】: MDP; dead ends; planning under uncertainty
【Paper Link】 【Pages】:
【Authors】: Matthew Molineaux ; Matthew Klenk ; David W. Aha
【Abstract】: Planning in dynamic continuous environments requires reasoning about nonlinear continuous effects, which previous Hierarchical Task Network (HTN) planners do not support. In this paper, we extend an existing HTN planner with a new state projection algorithm. To our knowledge, this is the first HTN planner that can reason about nonlinear continuous effects. We use a wait action to instruct this planner to consider continuous effects in a given state. We also introduce a new planning domain to demonstrate the benefits of planning with nonlinear continuous effects. We compare our approach with a linear continuous effects planner and a discrete effects HTN planner on a benchmark domain, which reveals that its additional costs are largely mitigated by domain knowledge. Finally, we present an initial application of this algorithm in a practical domain, a Navy training simulation, illustrating the utility of this approach for planning in dynamic continuous environments.
【Keywords】: HTN Planning; Continuous Planning; Mixed Discrete-Continuous Planning
【Paper Link】 【Pages】:
【Authors】: Miquel Ramírez ; Hector Geffner
【Abstract】: Plan recognition is the problem of inferring the goals and plans of an agent after observing its behavior. Recently, it has been shown that this problem can be solved efficiently, without the need of a plan library, using slightly modified planning algorithms. In this work, we extend this approach to the more general problem of probabilistic plan recognition where a probability distribution over the set of goals is sought under the assumptions that actions have deterministic effects and both agent and observer have complete information about the initial state. We show that this problem can be solved efficiently using classical planners provided that the probability of a partially observed execution given a goal is defined in terms of the cost difference of achieving the goal under two conditions: complying with the observations, and not complying with them. This cost, and hence the posterior goal probabilities, are computed by means of two calls to a classical planner that no longer has to be modified in any way. A number of examples is considered to illustrate the quality, flexibility, and scalability of the approach.
【Keywords】: Plan and Activity Recognition; Planning
【Paper Link】 【Pages】:
【Authors】: Kevin Regan ; Craig Boutilier
【Abstract】: The precise specification of reward functions for Markov decision processes (MDPs) is often extremely difficult, motivating research into both reward elicitation and the robust solution of MDPs with imprecisely specified reward (IRMDPs). We develop new techniques for the robust optimization of IRMDPs, using the minimax regret decision criterion, that exploit the set of nondominated policies, i.e., policies that are optimal for some instantiation of the imprecise reward function. Drawing parallels to POMDP value functions, we devise a Witness-style algorithm for identifying nondominated policies. We also examine several new algorithms for computing minimax regret using the nondominated set, and examine both practically and theoretically the impact of approximating this set. Our results suggest that a small subset of the nondominated set can greatly speed up computation, yet yield very tight approximations to minimax regret.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Adam Sadilek ; Henry A. Kautz
【Abstract】: Recent research has shown that surprisingly rich models of human behavior can be learned from GPS (positional) data. However, most research to date has concentrated on modeling single individuals or aggregate statistical properties of groups of people. Given noisy real-world GPS data, we---in contrast---consider the problem of modeling and recognizing activities that involve multiple related individuals playing a variety of roles. Our test domain is the game of capture the flag---an outdoor game that involves many distinct cooperative and competitive joint activities. We model the domain using Markov logic, a statistical relational language, and learn a theory that jointly denoises the data and infers occurrences of high-level activities, such as capturing a player. Our model combines constraints imposed by the geometry of the game area, the motion model of the players, and by the rules and dynamics of the game in a probabilistically and logically sound fashion. We show that while it may be impossible to directly detect a multi-agent activity due to sensor noise or malfunction, the occurrence of the activity can still be inferred by considering both its impact on the future behaviors of the people involved as well as the events that could have preceded it. We compare our unified approach with three alternatives (both probabilistic and nonprobabilistic) where either the denoising of the GPS data and the detection of the high-level activities are strictly separated, or the states of the players are not considered, or both. We show that the unified approach with the time window spanning the entire game, although more computationally costly, is significantly more accurate.
【Keywords】: activity recognition; human behavior modeling; statistical relational learning; location-based reasoning; GPS; Markov logic; capture the flag; games
【Paper Link】 【Pages】:
【Authors】: Scott Sanner ; Kristian Kersting
【Abstract】: Partially-observable Markov decision processes (POMDPs) provide a powerful model for sequential decision-making problems with partially-observed state and are known to have (approximately) optimal dynamic programming solutions. Much work in recent years has focused on improving the efficiency of these dynamic programming algorithms by exploiting symmetries and factored or relational representations. In this work, we show that it is also possible to exploit the full expressive power of first-order quantification to achieve state, action, and observation abstraction in a dynamic programming solution to relationally specified POMDPs. Among the advantages of this approach are the ability to maintain compact value function representations, abstract over the space of potentially optimal actions, and automatically derive compact conditional policy trees that minimally partition relational observation spaces according to distinctions that have an impact on policy values. This is the first lifted relational POMDP solution that can optimally accommodate actions with a potentially infinite relational space of observation outcomes.
【Keywords】: POMDPs; Sequential Decision Making; Relational Models
【Paper Link】 【Pages】:
【Authors】: Georgios Theocharous ; Sridhar Mahadevan
【Abstract】: Partially Observable Markov Decision Processes (POMDPs) are a well-established and rigorous framework for sequential decision-making under uncertainty. POMDPs are well-known to be intractable to solve exactly, and there has been significant work on finding tractable approximation methods. One well-studied approach is to find a compression of the original POMDP by projecting the belief states to a lower-dimensional space. We present a novel dimensionality reduction method for POMDPs based on locality preserving non-negative matrix factorization. Unlike previous approaches, such as Krylov compression and regular non-negative matrix factorization, our approach preserves the local geometry of the belief space manifold. We present results on standard benchmark POMDPs showing improved performance over previously explored compression algorithms for POMDPs.
【Keywords】: POMDPs; Non-negative Matrix Factorization
【Paper Link】 【Pages】:
【Authors】: Chenggang Wang ; Roni Khardon
【Abstract】: Relational Markov Decision Processes (MDP) are a useful abstraction for stochastic planning problems since one can develop abstract solutions for them that are independent of domain size or instantiation. While there has been an increased interest in developing relational fully observable MDPs, there has been very little work on relational partially observable MDPs (POMDP), which deal with uncertainty in problem states in addition to stochastic action effects. This paper provides a concrete formalization of relational POMDPs making several technical contributions toward their solution. First, we show that to maintain correctness one must distinguish between quantification over states and quantification over belief states; this implies that solutions based on value iteration are inherently limited to the finite horizon case. Second, we provide a symbolic dynamic programing algorithm for finite horizon relational POMDPs, solving them at an abstract level, by lifting the propositional incremental pruning algorithm. Third, we show that this algorithm can be implemented using first order decision diagrams, a compact representation for functions over relational structures, that has been recently used to solve relational MDPs.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Craig Boutilier ; Kevin Regan ; Paolo Viappiani
【Abstract】: Most frameworks for utility elicitation assume a predefined set of features over which user preferences are expressed. We consider utility elicitation in the presence of subjective or user-defined features, whose definitions are not known in advance. We treat the problem of learning a user's feature definition as one of concept learning, but whose goal is to learn only enough about the concept definition to enable a good decision to be made. This is complicated by the fact that user utility is unknown. We describe computational procedures for identifying optimal alternatives w.r.t minimax regret in the presence of both utility and concept uncertainty; and develop several heuristic query strategies that focus simultaneously on reduction of relevant concept and utility uncertainty.
【Keywords】: utility elicitation; minimax regret; concept learning
【Paper Link】 【Pages】:
【Authors】: Peng Dai ; Mausam ; Daniel S. Weld
【Abstract】: Crowd-sourcing is a recent framework in which human intelligence tasks are outsourced to a crowd of unknown people ("workers") as an open call (e.g., on Amazon's Mechanical Turk). Crowd-sourcing has become immensely popular with hoards of employers ("requesters"), who use it to solve a wide variety of jobs, such as dictation transcription, content screening, etc. In order to achieve quality results, requesters often subdivide a large task into a chain of bite-sized subtasks that are combined into a complex, iterative workflow in which workers check and improve each other's results. This paper raises an exciting question for AI — could an autonomous agent control these workflows without human intervention, yielding better results than today's state of the art, a fixed control program? We describe a planner, TurKontrol, that formulates workflow control as a decision-theoretic optimization problem, trading off the implicit quality of a solution artifact against the cost for workers to achieve it. We lay the mathematical framework to govern the various decisions at each point in a popular class of workflows. Based on our analysis we implement the workflow control algorithm and present experiments demonstrating that TurKontrol obtains much higher utilities than popular fixed policies.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Eun Yong Kang ; Ilya Shpitser ; Eleazar Eskin
【Abstract】: There have been many efforts to identify causal graphical features such as directed edges between random variables from observational data. Recently, Tian et al. proposed a new dynamic programming algorithm which computes marginalized posterior probabilities of directed edge features over all the possible structures in O( n 3 n ) time when the number of parents per node is bounded by a constant, where n is the number of variables of interest. However the main drawback of this approach is that deciding a single appropriate threshold for the existence of the directed edge feature is difficult due to the scale difference of the posterior probabilities between the directed edges forming v- structures and the directed edges not forming v -structures. We claim that computing posterior probabilities of both adjacencies and v -structures is necessary and more effective for discovering causal graphical features, since it allows us to find a single appropriate decision threshold for the existence of the feature that we are testing. For efficient computation, we provide a novel dynamic programming algorithm which computes the posterior probabilities of all of n ( n – 1)/2 adjacency and n ( n –1 choose 2) v -structure features in O( n 3 * 3 n ) time.
【Keywords】: graphical models; learning; Markov equivalence
【Paper Link】 【Pages】:
【Authors】: Kristian Kersting ; Youssef El Massaoudi ; Fabian Hadiji ; Babak Ahmadi
【Abstract】: Lifted inference, handling whole sets of indistinguishable objects together, is critical to the effective application of probabilistic relational models to realistic real world tasks. Recently, lifted belief propagation (LBP) has been proposed as an efficient approximate solution of this inference problem. It runs a modified BP on a lifted network where nodes have been grouped together if they have — roughly speaking — identical computation trees, the tree-structured “unrolling” of the underlying graph rooted at the nodes. In many situations, this purely syntactic criterion is too pessimistic: message errors decay along paths. Intuitively, for a long chain graph with weak edge potentials, distant nodes will send and receive identical messages yet their computation trees are quite different. To overcome this, we propose iLBP, a novel, easy-to-implement, informed LBP approach that interleaves lifting and modified BP iterations. In turn, we can efficiently monitor the true BP messages sent and received in each iteration and group nodes accordingly. As our experiments show, iLBP can yield significantly faster more lifted network while not degrading performance. Above all, we show that iLBP is faster than BP when solving the problem of distributing data to a large network, an important real-world application where BP is faster than uninformed LBP.
【Keywords】: Lifted Inference; Belief Propagation; Statistical Relational Learning; Content Distribution
【Paper Link】 【Pages】:
【Authors】: Aniruddh Nath ; Pedro M. Domingos
【Abstract】: Many problems require repeated inference on probabilistic graphical models, with different values for evidence variables or other changes. Examples of such problems include utility maximization, MAP inference, online and interactive inference, parameter and structure learning, and dynamic inference. Since small changes to the evidence typically only affect a small region of the network, repeatedly performing inference from scratch can be massively redundant. In this paper, we propose expanding frontier belief propagation (EFBP), an efficient approximate algorithm for probabilistic inference with incremental changes to the evidence (or model). EFBP is an extension of loopy belief propagation (BP) where each run of inference reuses results from the previous ones, instead of starting from scratch with the new evidence; messages are only propagated in regions of the network affected by the changes. We provide theoretical guarantees bounding the difference in beliefs generated by EFBP and standard BP, and apply EFBP to the problem of expected utility maximization in influence diagrams. Experiments on viral marketing and combinatorial auction problems show that EFBP can converge much faster than BP without significantly affecting the quality of the solutions.
【Keywords】: Probabilistic Inference; Relational Probabilistic Models; Graphical Models
【Paper Link】 【Pages】:
【Authors】: Aniruddh Nath ; Pedro M. Domingos
【Abstract】: Lifting can greatly reduce the cost of inference on first-order probabilistic graphical models, but constructing the lifted network can itself be quite costly. In online applications (e.g., video segmentation) repeatedly constructing the lifted network for each new inference can be extremely wasteful, because the evidence typically changes little from one inference to the next. The same is true in many other problems that require repeated inference, like utility maximization, MAP inference, interactive inference, parameter and structure learning, etc. In this paper, we propose an efficient algorithm for updating the structure of an existing lifted network with incremental changes to the evidence. This allows us to construct the lifted network once for the initial inference problem, and amortize the cost over the subsequent problems. Experiments on video segmentation and viral marketing problems show that the algorithm greatly reduces the cost of inference without affecting the quality of the solutions.
【Keywords】: Probabilistic Inference; Relational Probabilistic Models; Graphical Models
【Paper Link】 【Pages】:
【Authors】: Emma Rollon ; Rina Dechter
【Abstract】: Mini-Bucket Elimination (MBE) is a well-known approximation algorithm deriving lower and upper bounds on quantities of interest over graphical models. It relies on a procedure that partitions a set of functions, called bucket, into smaller subsets, called mini-buckets. The method has been used with a single partitioning heuristic throughout, so the impact of the partitioning algorithm on the quality of the generated bound has never been investigated. This paper addresses this issue by presenting a framework within which partitioning strategies can be described, analyzed and compared. We derive a new class of partitioning heuristics from first-principles geared for likelihood queries, demonstrate their impact on a number of benchmarks for probabilistic reasoning and show that the results are competitive (often superior) to state-of-the-art bounding schemes.
【Keywords】: Probabilistic Inference; Bayesian Networks; Graphical Models
【Paper Link】 【Pages】:
【Authors】: Son Thanh To ; Tran Cao Son ; Enrico Pontelli
【Abstract】: The paper presents an investigation of the use of two alternative forms of CNF formulae—prime implicates and minimal CNF—to compactly represent belief states in the context of conformant planning. For each representation, we define a transition function for computing the successor belief state resulting from the execution of an action in a belief state; results concerning soundness and completeness are provided. The paper describes a system (PIP) which dynamically selects either of these two forms to represent belief states, and an experimental evaluation of PIP against state-of-the-art conformant planners. The results show that PIP has the potential of scaling up better than other planners in problems rich in disjunctive information about the initial state.
【Keywords】: Conformant Planning, Prime Implicate
【Paper Link】 【Pages】:
【Authors】: Long Tran-Thanh ; Archie C. Chapman ; Enrique Munoz de Cote ; Alex Rogers ; Nicholas R. Jennings
【Abstract】: We introduce the budget–limited multi–armed bandit (MAB), which captures situations where a learner’s actions are costly and constrained by a fixed budget that is incommensurable with the rewards earned from the bandit machine, and then describe a first algorithm for solving it. Since the learner has a budget, the problem’s duration is finite. Consequently an optimal exploitation policy is not to pull the optimal arm repeatedly, but to pull the combination of arms that maximises the agent’s total reward within the budget. As such, the rewards for all arms must be estimated, because any of them may appear in the optimal combination. This difference from existing MABs means that new approaches to maximising the total reward are required. To this end, we propose an epsilon–first algorithm, in which the first epsilon of the budget is used solely to learn the arms’ rewards (exploration), while the remaining 1 − epsilon is used to maximise the received reward based on those estimates (exploitation). We derive bounds on the algorithm’s loss for generic and uniform exploration methods, and compare its performance with traditional MAB algorithms under various distributions of rewards and costs, showing that it outperforms the others by up to 50%.
【Keywords】: sequential decision making; unsupervised learning; multi-armed bandits
【Paper Link】 【Pages】:
【Authors】: Guy Van den Broeck ; Ingo Thon ; Martijn van Otterlo ; Luc De Raedt
【Abstract】: We introduce DTProbLog, a decision-theoretic extension of Prolog and its probabilistic variant ProbLog. DTProbLog is a simple but expressive probabilistic programming language that allows the modeling of a wide variety of domains, such as viral marketing. In DTProbLog, the utility of a strategy (a particular choice of actions) is defined as the expected reward for its execution in the presence of probabilistic effects. The key contribution of this paper is the introduction of exact, as well as approximate, solvers to compute the optimal strategy for a DTProbLog program and the decision problem it represents, by making use of binary and algebraic decision diagrams. We also report on experimental results that show the effectiveness and the practical usefulness of the approach.
【Keywords】: decision theory; statistical relational learning; logic programming
【Paper Link】 【Pages】:
【Authors】: Nicola Basilico ; Nicola Gatti ; Federico Villa
【Abstract】: Use of game theoretical models to derive randomized mobile robot patrolling strategies has recently received a growing attention. We focus on the problem of patrolling environments with arbitrary topologies using multiple robots. We address two important issues cur rently open in the literature. We determine the smallest number of robots needed to patrol a given environment and we compute the optimal patrolling strategies along several coordination dimensions. Finally, we experimentally evaluate the proposed techniques.
【Keywords】: Multi-Robot Systems, Game Theory, Multiagent Systems
【Paper Link】 【Pages】:
【Authors】: Subhrajit Bhattacharya
【Abstract】: Goal-directed path planning is one of the basic and widely studied problems in the field of mobile robotics. Homotopy classes of trajectories, arising due to the presence of obstacles, are defined as sets of trajectories that can be transformed into each other by gradual bending and stretching without colliding with obstacles. The problem of finding least-cost paths restricted to a specific homotopy class or finding least-cost paths that do not belong to certain homotopy classes arises frequently in such applications as predicting paths for dynamic entities and computing heuristics for path planning with dynamic constraints. In the present work, we develop a compact way of representing homotopy classes and propose an efficient method of graph search-based optimal path planning with constraints on homotopy classes. The method is based on representing the environment of the robot as a complex plane and making use of the Cauchy Integral Theorem. We prove optimality of the method and show its efficiency experimentally.
【Keywords】: Motion and Path Planning; Planning Algorithms; Heuristic Search
【Paper Link】 【Pages】:
【Authors】: Takuma Otsuka ; Kazuhiro Nakadai ; Toru Takahashi ; Kazunori Komatani ; Tetsuya Ogata ; Hiroshi G. Okuno
【Abstract】: Our goal is to develop an interactive music robot, i.e., a robot that presents a musical expression together with humans. A music interaction requires two important functions: synchronization with the music and musical expression, such as singing and dancing. Many instrument-performing robots are only capable of the latter function, they may have difficulty in playing live with human performers. The synchronization function is critical for the interaction. We classify synchronization and musical expression into two levels: (1) the rhythm level and (2) the melody level. Two issues in achieving two-layer synchronization and musical expression are: (1) simultaneous estimation of the rhythm structure and the current part of the music and (2) derivation of the estimation confidence to switch behavior between the rhythm level and the melody level. This paper presents a score following algorithm, incremental audio to score alignment, that conforms to the two-level synchronization design using a particle filter. Our method estimates the score position for the melody level and the tempo for the rhythm level. The reliability of the score position estimation is extracted from the probability distribution of the score position. Experiments are carried out using polyphonic jazz songs. The results confirm that our method switches levels in accordance with the difficulty of the score estimation. When the tempo of the music is less than 120 (beats per minute; bpm), the estimated score positions are accurate and reported; when the tempo is over 120 (bpm), the system tends to report only the tempo to suppress the error in the reported score position predictions.
【Keywords】: Robotics; music robot; score following; musical interaction; auditory scene analysis; human-robot interaction
【Paper Link】 【Pages】:
【Authors】: Jia Pan ; Christian Lauterbach ; Dinesh Manocha
【Abstract】: We present novel randomized algorithms for solving global motion planning problems that exploit the computational capabilities of many-core GPUs. Our approach uses thread and data parallelism to achieve high performance for all components of sample-based algorithms, including random sampling, nearest neighbor computation, local planning, collision queries and graph search. The approach can efficiently solve both the multi-query and single-query versions of the problem and obtain considerable speedups over prior CPU-based algorithms. We demonstrate the efficiency of our algorithms by applying them to a number of 6DOF planning benchmarks in 3D environments. Overall, this is the first algorithm that can perform real-time motion planning and global navigation using commodity hardware.
【Keywords】: motion planning; GPU
【Paper Link】 【Pages】:
【Authors】: Stephen Tully ; George Kantor ; Howie Choset
【Abstract】: This paper presents a novel recursive maximum a posteriori update for the Kalman formulation of undelayed bearing-only SLAM. The estimation update step is cast as an optimization problem for which we can prove the global minimum is reachable via a bidirectional search using Gauss-Newton's method along a one-dimensional manifold. While the filter is designed for mapping just one landmark, it is easily extended to full-scale multiple-landmark SLAM. We provide this extension via a formulation of bearing-only FastSLAM. With experiments, we demonstrate accurate and convergent estimation in situations where an EKF solution would diverge.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Patricia Gutierrez ; Pedro Meseguer
【Abstract】: We have found that some messages of BnB-ADOPT are redundant. Removing most of those redundant messages we obtain BnB-ADOPT + , which achieves the optimal solution and terminates. In practice, BnB-ADOPT + causes substantial reductions on communication costs with respect to the original algorithm.
【Keywords】: distributed constraint optimization; redundant messages
【Paper Link】 【Pages】:
【Authors】: Pavel Surynek
【Abstract】: An optimization variant of a problem of path planning for multiple robots is addressed in this work. The task is to find spatial-temporal path for each robot of a group of robots such that each robot can reach its destination by navigating through these paths. In the optimization variant of the problem, there is an additional requirement that the makespan of the solution must be as small as possible. A proof of the claim that optimal path planning for multiple robots is NP‑complete is sketched in this short paper.
【Keywords】: graph pebbling; multi-robot; path planning; complexity; motion puzzle
【Paper Link】 【Pages】:
【Authors】: Hua Wang ; Chris H. Q. Ding ; Heng Huang
【Abstract】: Many existing approaches employ one-vs-rest method to decompose a multi-label classification problem into a set of 2- class classification problems, one for each class. This method is valid in traditional single-label classification, it, however, incurs training inconsistency in multi-label classification, because in the latter a data point could belong to more than one class. In order to deal with this problem, in this work, we further develop classicalK-Nearest Neighbor classifier and propose a novel Class Balanced K-Nearest Neighbor approach for multi-label classification by emphasizing balanced usage of data from all the classes. In addition, we also propose a Class Balanced Linear Discriminant Analysis approach to address high-dimensional multi-label input data. Promising experimental results on three broadly used multi-label data sets demonstrate the effectiveness of our approach.
【Keywords】: multi-label classification; one-vs-other; k-nearest neighbor; linear discriminant analysis
【Paper Link】 【Pages】:
【Authors】: Fabian Buchwald ; Tobias Girschick ; Eibe Frank ; Stefan Kramer
【Abstract】: Many methods for quantitative structure-activity relationships (QSARs) deliver point estimates only, without quantifying the uncertainty inherent in the prediction. One way to quantify the uncertainy of a QSAR prediction is to predict the conditional density of the activity given the structure instead of a point estimate. If a conditional density estimate is available, it is easy to derive prediction intervals of activities. In this paper, we experimentally evaluate and compare three methods for conditional density estimation for their suitability in QSAR modeling. In contrast to traditional methods for conditional density estimation, they are based on generic machine learning schemes, more specifically, class probability estimators. Our experiments show that a kernel estimator based on class probability estimates from a random forest classifier is highly competitive with Gaussian process regression, while taking only a fraction of the time for training. Therefore, generic machine-learning based methods for conditional density estimation may be a good and fast option for quantifying uncertainty in QSAR modeling.
【Keywords】: chemoinformatics and QSAR; supervised learning; statistical analysis
【Paper Link】 【Pages】:
【Authors】: Franco Mascia ; Elisa Cilia ; Mauro Brunato ; Andrea Passerini
【Abstract】: Fully characterizing structural and functional sites in proteins is a fundamental step in understanding their roles in the cell. This extremely challenging combinatorial problem requires determining the number of sites in the protein and the set of residues involved in each of them. We formulate it as a distance-based supervised clustering task, where training proteins are employed to learn a proper distance function between residues. A partial clustering is then returned by searching for maximum-weight cliques in the resulting weighted graph representation of proteins. A novel stochastic local search algorithm is proposed to efficiently generate approximate solutions. Our method achieves substantial improvements over a previous structured-output approach for metal binding site prediction. Significant improvements over the current state-of-the-art are also achieved in predicting catalytic sites from 3D structure in enzymes.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Siamak (Moshen) Ravanbakhsh ; Barnabás Póczos ; Russell Greiner
【Abstract】: Some real-world problems are partially decomposable, in that they can be decomposed into a set of coupled sub- problems, that are each relatively easy to solve. However, when these sub-problem share some common variables, it is not sufficient to simply solve each sub-problem in isolation. We develop a technology for such problems, and use it to address the challenge of finding the concentrations of the chemicals that appear in a complex mixture, based on its one-dimensional 1H Nuclear Magnetic Resonance (NMR) spectrum. As each chemical involves clusters of spatially localized peaks, this requires finding the shifts for the clusters and the concentrations of the chemicals, that collectively pro- duce the best match to the observed NMR spectrum. Here, each sub-problem requires finding the chemical concentrations and cluster shifts that can appear within a limited spectrum range; these are coupled as these limited regions can share many chemicals, and so must agree on the concentrations and cluster shifts of the common chemicals. This task motivates CEED: a novel extension to the Cross-Entropy stochastic optimization method constructed to address such partially decomposable problems. Our experimental results in the NMR task show that our CEED system is superior to other well-known optimization methods, and indeed produces the best-known results in this important, real-world application.
【Keywords】: Optimization , Bioinformatics , NMR , Nuclear Magnetic Resonance , Decomposable
【Paper Link】 【Pages】:
【Authors】: Qingguo Wang ; Mian Pan ; Yi Shang ; Dmitry Korkin
【Abstract】: Finding the longest common subsequence (LCS) of multiple strings is an NP-hard problem, with many applications in the areas of bioinformatics and computational genomics. Although significant efforts have been made to address the problem and its special cases, the increasing complexity and size of biological data require more efficient methods applicable to an arbitrary number of strings. In this paper, a novel search algorithm, MLCS-A, is presented for the general case of multiple LCS (or MLCS) problems. MLCS-A is a variant of the A algorithm. It maximizes a new heuristic estimate of the LCS in each search step so that the longest common subsequence can be found. As a natural extension of MLCS-A, a fast algorithm, MLCS-APP, is also proposed to deal with large volume of biological data for which finding a LCS within reasonable time is impossible. The benchmark test shows that MLCS-APP is able to extract common subsequences close to the optimal ones and that MLCS-APP significantly outperforms existing heuristic approaches. When applied to 8 protein domain families, MLCS-APP produced more accurate results than existing multiple sequence alignment methods.
【Keywords】: A*; Search; Longest Common Subsequence; Multiple Longest Common Subsequence; Computational Biology
【Paper Link】 【Pages】:
【Authors】: Muhammad Aurangzeb Ahmad ; David A. Huffaker ; Jing Wang ; Jeffrey William Treem ; Marshall Scott Poole ; Jaideep Srivastava
【Abstract】: There is a large body of work on the evolution of graphs in various domains, which shows that many real graphs evolve in a similar manner. In this paper we study a novel type of network formed by mentor-apprentice relationships in a massively multiplayer online role playing game. We observe that some of the static and dynamic laws which have been observed in many other real world networks are not observed in this network. Consequently well known graph generators like Preferential Attachment, Forest Fire, Butterfly, RTM, etc., cannot be applied to such mentoring networks. We propose a novel generative model to generate networks with the characteristics of mentoring networks.
【Keywords】: Generative Models; Mentoring Networks; Social Networks
【Paper Link】 【Pages】:
【Authors】: Sumit Bhatia ; Prasenjit Mitra
【Abstract】: Online forums contain valuable human-generated information. End-users looking for information would like to find only those threads in forums where relevant information is present. Due to the distinctive characteristics of forum pages from generic web pages, special techniques are required to organize and search for information in these forums. Threads and pages in forums are different from other webpages in their hyperlinking patterns. Forum posts also have associated social and non-textual metadata. In this paper, we propose a model for online thread retrieval based on inference networks that utilizes the structural properties of forum threads. We also investigate the effects of incorporating various relevance indicators in our model. We empirically show the effectiveness of our proposed model using real-world data.
【Keywords】: forum search;thread retrieval;search;inference networks
【Paper Link】 【Pages】:
【Authors】: Andrew Carlson ; Justin Betteridge ; Bryan Kisiel ; Burr Settles ; Estevam R. Hruschka Jr. ; Tom M. Mitchell
【Abstract】: We consider here the problem of building a never-ending language learner; that is, an intelligent computer agent that runs forever and that each day must (1) extract, or read, information from the web to populate a growing structured knowledge base, and (2) learn to perform this task better than on the previous day. In particular, we propose an approach and a set of design principles for such an agent, describe a partial implementation of such a system that has already learned to extract a knowledge base containing over 242,000 beliefs with an estimated precision of 74% after running for 67 days, and discuss lessons learned from this preliminary attempt to build a never-ending learning agent.
【Keywords】: information extraction; web mining; semi-supervised learning
【Paper Link】 【Pages】:
【Authors】: Yuqiang Chen ; Ou Jin ; Gui-Rong Xue ; Jia Chen ; Qiang Yang
【Abstract】: Advertising in the case of textual Web pages has been studied extensively by many researchers. However, with the increasing amount of multimedia data such as image, audio and video on the Web, the need for recommending advertisement for the multimedia data is becoming a reality. In this paper, we address the novel problem of visual contextual advertising, which is to directly advertise when users are viewing images which do not have any surrounding text. A key challenging issue of visual contextual advertising is that images and advertisements are usually represented in image space and word space respectively, which are quite different with each other inherently. As a result, existing methods for Web page advertising are inapplicable since they represent both Web pages and advertisement in the same word space. In order to solve the problem, we propose to exploit the social Web to link these two feature spaces together. In particular, we present a unified generative model to integrate advertisements, words and images. Specifically, our solution combines two parts in a principled approach: First, we transform images from a image feature space to a word space utilizing the knowledge from images with annotations from social Web. Then, a language model based approach is applied to estimate the relevance between transformed images and advertisements. Moreover, in this model, the probability of recommending an advertisement can be inferred efficiently given an image, which enables potential applications to online advertising.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Jeff Huang ; Anna Kazeykina
【Abstract】: Web search engines respond to a query by returning more results than can be reasonably reviewed. These results typically include the title, link, and snippet of content from the target link. Each result has the potential to be useful or useless and thus reviewing it has a cost and potential benefit. This paper studies the behavior of a rational agent in this setting, whose objective is to maximize the probability of finding a satisfying result while minimizing cost. We propose two similar agents with different capabilities: one that only compares result snippets relatively and one that predicts from the result snippet whether the result will be satisfying. We prove that the optimal strategy for both agents is a stopping rule: the agent reviews a fixed number of results until the marginal cost is greater than the marginal expected benefit, maximizing the overall expected utility. Finally, we discuss the relationship between rational agents and search users and how our findings help us understand reviewing behaviors.
【Keywords】: search; rational agent; decision theory; reviewing strategies
【Paper Link】 【Pages】:
【Authors】: Jian Huang ; Cong Yu
【Abstract】: It is often desirable to extract structured information from raw web pages for better information browsing, query answering, and pattern mining. many such Information Extraction (IE) technologies are costly and applying them at the web-scale is impractical. In this paper, we propose a novel prioritization approach where candidate pages from the corpus are ordered according to their expected contribution to the extraction results and those with higher estimated potential are extracted earlier. Systems employing this approach can stop the extraction process at any time when the resource gets scarce (i.e., not all pages in the corpus can be processed), without worrying about wasting extraction effort on unimportant pages. More specifically, we define a novel notion to measure the value of extraction results and design various mechanisms for estimating a candidate page’s contribution to this value. We further design and build the Extraction Prioritization (EP) system with efficient scoring and scheduling algorithms, and experimentally demonstrate that EP significantly outperforms the naive approach and is more flexible than the classifier approach.
【Keywords】: prioritization; web information extraction
【Paper Link】 【Pages】:
【Authors】: Yoshiyuki Inagaki ; Narayanan Sadagopan ; Georges Dupret ; Anlei Dong ; Ciya Liao ; Yi Chang ; Zhaohui Zheng
【Abstract】: Recency ranking refers to the ranking of web results by accounting for both relevance and freshness. This is particularly important for "recency sensitive" queries such as breaking news queries. In this study, we propose a set of novel click features to improve machine learned recency ranking. Rather than computing simple aggregate click through rates, we derive these features using the temporal click through data and query reformulation chains. One of the features that we use is click buzz that captures the spiking interest of a url for a query. We also propose time weighted click through rates which treat recent observations as being exponentially more important. The promotion of fresh content is typically determined by the query intent which can change dynamically over time. Quite often users query reformulations convey clues about the query's intent. Hence we enrich our click features by following query reformulations which typically benefit the first query in the chain of reformulations. Our experiments show these novel features can improve the NDCG5 of a major online search engine's ranking for "recency sensitive" queries by up to 1.57%. This is one of the very few studies that exploits temporal click through data and query reformulations for recency ranking.
【Keywords】: web search ranking; recency; user clicks; machine learned models
【Paper Link】 【Pages】:
【Authors】: Saurabh Kataria ; Prasenjit Mitra ; Sumit Bhatia
【Abstract】: In an interlinked corpus of documents, the context in which a citation appears provides extra information about the cited document. However, associating terms in the context to the cited document remains an open problem. We propose a novel document generation approach that statistically incorporates the context in which a document links to another document. We quantitatively show that the proposed generation scheme explains the linking phenomenon better than previous approaches. The context information along with the actual content of the document provides significant improvements over the previous approaches for various real world evaluation tasks such as link prediction and log-likelihood estimation on unseen content. The proposed method is more scalable to large collection of documents compared to the previous approaches.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Mitesh M. Khapra ; Raghavendra Udupa ; A. Kumaran ; Pushpak Bhattacharyya
【Abstract】: We address the problem of mining name transliterations from comparable corpora in languages P and Q in the following resource-poor scenario: Parallel names in PQ are not available for training. Parallel names in PR and RQ are available for training. We propose a novel solution for the problem by computing a common geometric feature space for P,Q and R where name transliterations are mapped to similar vectors. We employ Canonical Correlation Analysis (CCA) to compute the common geometric feature space using only parallel names in PR and RQ and without requiring parallel names in PQ. We test our algorithm on data sets in several languages and show that it gives results comparable to the state-of-the-art transliteration mining algorithms that use parallel names in PQ for training.
【Keywords】: Transliteration Mining, Bridge Languages, CCA
【Paper Link】 【Pages】:
【Authors】: Babak Khosravifar ; Jamal Bentahar ; Ahmad Moazin ; Philippe Thiran
【Abstract】: Maintaining a sound reputation mechanism requires a robust control and investigation. In this paper, we propose a game-theoretic analysis of a reputation mechanism that objectively maintains accurate reputation evaluation of selfish agent-based web services. In this framework, web services are ranked using their reputation as a result of provided feedback reflecting consumers' satisfaction about the offered services. However, selfish web services may alter their public reputation level by managing to get fake feedback. In this paper, game-theoretic analysis investigates the payoffs of different situations and elaborates on the facts that discourage web services to act maliciously.
【Keywords】: Web services, game theory, reputation, agents
【Paper Link】 【Pages】:
【Authors】: Jinhan Kim ; Sanghoon Lee ; Seung-won Hwang ; Sunghun Kim
【Abstract】: Software developers increasingly rely on information from the Web, such as documents or code examples on Application Programming Interfaces (APIs), to facilitate their development processes. However, API documents often do not include enough information for developers to fully understand the API usages, while searching for good code examples requires non-trivial efforts. To address this problem, we propose a novel code search engine, combining the strength of browsing documents and searching for code examples, by returning documents embedded with high-quality code example summaries mined from the Web. Our evaluation results show that our approach provides code examples with high precision and boosts programmer productivity.
【Keywords】: API documents; Search Engine; Code example
【Paper Link】 【Pages】:
【Authors】: Masahiro Kimura ; Kazumi Saito ; Kouzou Ohara ; Hiroshi Motoda
【Abstract】: We address the problem of predicting the expected opinion share over a social network at a target time from the opinion diffusion data under the value-weighted voter model with multiple opinions. The value update algorithm ensures that it converges to a correct solution and the share prediction results outperform a simple linear extrapolation approximation when the available data is limited. We further show in an extreme case of complete network that the opinion with the highest value eventually takes over, and the expected share prediction problem with uniform opinion value is not well-defined and any opinion can win.
【Keywords】: social network analysis; opinion share prediction; learning
【Paper Link】 【Pages】:
【Authors】: Fangtao Li ; Minlie Huang ; Xiaoyan Zhu
【Abstract】: With the development of Web 2.0, sentiment analysis has now become a popular research problem to tackle. Recently, topic models have been introduced for the simultaneous analysis for topics and the sentiment in a document. These studies, which jointly model topic and sentiment, take the advantage of the relationship between topics and sentiment, and are shown to be superior to traditional sentiment analysis tools. However, most of them make the assumption that, given the parameters, the sentiments of the words in the document are all independent. In our observation, in contrast, sentiments are expressed in a coherent way. The local conjunctive words, such as “and” or “but”, are often indicative of sentiment transitions. In this paper, we propose a major departure from the previous approaches by making two linked contributions. First, we assume that the sentiments are related to the topic in the document, and put forward a joint sentiment and topic model, i.e. Sentiment-LDA. Second, we observe that sentiments are dependent on local context. Thus, we further extend the Sentiment-LDA model to Dependency-Sentiment-LDA model by relaxing the sentiment independent assumption in Sentiment-LDA. The sentiments of words are viewed as a Markov chain in Dependency-Sentiment-LDA. Through experiments, we show that exploiting the sentiment dependency is clearly advantageous, and that the Dependency-Sentiment-LDA is an effective approach for sentiment analysis.
【Keywords】: Sentiment Analysis; Topic Model; Sentiment Classification
【Paper Link】 【Pages】:
【Abstract】: In Service-Oriented Computing (SOC) environments, the trustworthiness of each service is critical for a service client when selecting one from a large pool of services. The trust value of a service is usually in the range of [0,1] and is evaluated from the ratings given by service clients, which represent the subjective belief of these service clients on the satisfaction of delivered services. So a trust value can be taken as the subjective probability, with which one party believes that another party can perform an action in a certain situation. Hence, subjective probability theory should be adopted in trust evaluation. In addition, in SOC environments, a service usually invokes other services offered by different service providers forming a composite service. Thus, the global trust of a composite service should be evaluated based on complex invocation structures. In this paper, firstly, based on Bayesian inference, we propose a novel method to evaluate the subjective trustworthiness of a service component from a series of ratings given by service clients. Secondly, we interpret the trust dependency caused by service invocations as conditional probability, which is evaluated based on the subjective trust values of service components. Furthermore, we propose a joint subjective probability method to evaluate the subjective global trust of a composite service on the basis of trust dependency. Finally, we introduce the results of our conducted experiments to illustrate the properties of our proposed subjective global trust inference method.
【Keywords】: Composite services; Trust evaluation; Subjective probability
【Paper Link】 【Pages】:
【Authors】: Xiao Ling ; Daniel S. Weld
【Abstract】: Research on information extraction (IE) seeks to distill relational tuples from natural language text, such as the contents of the WWW. Most IE work has focussed on identifying static facts, encoding them as binary relations. This is unfortunate, because the vast majority of facts are fluents, only holding true during an interval of time. It is less helpful to extract PresidentOf(Bill-Clinton, USA) without the temporal scope 1/20/93 — 1/20/01. This paper presents TIE, a novel, information-extraction system, which distills facts from text while inducing as much temporal information as possible. In addition to recognizing temporal relations between times and events, TIE performs global inference, enforcing transitivity to bound the start and ending times for each event. We introduce the notion of temporal entropy as a way to evaluate the performance of temporal IE systems and present experiments showing that TIE outperforms three alternative approaches.
【Keywords】: Temporal Information Extraction
【Paper Link】 【Pages】:
【Authors】: Guanfeng Liu ; Yan Wang ; Mehmet A. Orgun
【Abstract】: Online social networks are becoming increasingly popular and are being used as the means for a variety of rich activities. This demands the evaluation of the trustworthiness between two unknown participants along a certain social trust path between them in the social network. However, there are usually many social trust paths between participants. Thus, a challenging problem is finding which social trust path is the optimal one that can yield the most trustworthy evaluation result. In this paper, we first present a new complex social network structure and a new concept of Quality of Trust (QoT) to illustrate the ability to guarantee a certain level of trustworthiness in trust evaluation. We then model the optimal social trust path selection as a Multi-Constrained Optimal Path (MCOP) selection problem which is NP-Complete. For solving this problem, we propose an efficient approximation algorithm MONTE K based on the Monte Carlo method. The results of our experiments conducted on a real dataset of social networks illustrate that our proposed algorithm significantly outperforms existing approaches in both efficiency and the quality of selected social trust paths.
【Keywords】: trust; trust path; social networks;
【Paper Link】 【Pages】:
【Authors】: Hao Ma ; Michael R. Lyu ; Irwin King
【Abstract】: In order to improve the user search experience, Query Suggestion, a technique for generating alternative queries to Web users, has become an indispensable feature for commercial search engines. However, previous work mainly focuses on suggesting relevant queries to the original query while ignoring the diversity in the suggestions, which will potentially dissatisfy Web users' information needs. In this paper, we present a novel unified method to suggest both semantically relevant and diverse queries to Web users. The proposed approach is based on Markov random walk and hitting time analysis on the query-URL bipartite graph. It can effectively prevent semantically redundant queries from receiving a high rank, hence encouraging diversities in the results. We evaluate our method on a large commercial clickthrough dataset in terms of relevance measurement and diversity measurement. The experimental results show that our method is very effective in generating both relevant and diverse query suggestions.
【Keywords】: Diversity; Query Suggestion; Random Walk; Hitting Time
【Paper Link】 【Pages】:
【Authors】: James P. McGlothlin ; Latifur R. Khan
【Abstract】: As the semantic web grows in popularity and enters the mainstream of computer technology, RDF (Resource Description Framework) datasets are becoming larger and more complex. Advanced semantic web ontologies, especially in medicine and science, are developing. As more complex ontologies are developed, there is a growing need for efficient queries that handle inference. In areas such as research, it is vital to be able to perform queries that retrieve not just facts but also inferred knowledge and uncertain information. OWL (Web Ontology Language) defines rules that govern provable inference in semantic web datasets. In this paper, we detail a database schema using bit vectors that is designed specifically for RDF datasets. We introduce a framework for materializing and storing inferred triples. Our bit vector schema enables storage of inferred knowledge without a query performance penalty. Inference queries are simplified and performance is improved. Our evaluation results demonstrate that our inference solution is more scalable and efficient than the current state-of-the-art. There are also standards being developed for representing probabilistic reasoning within OWL ontologies. We specify a framework for materializing uncertain information and probabilities using these ontologies. We define a multiple vector schema for representing probabilities and classifying uncertain knowledge using thresholds. This solution increases the breadth of information that can be efficiently retrieved.
【Keywords】: semantic web; ontology; inference; query optimization; information retrieval; uncertainty reasoning; resource description framework; database schema
【Paper Link】 【Pages】:
【Authors】: Mathias Niepert ; Christian Meilicke ; Heiner Stuckenschmidt
【Abstract】: Ontology matching is the problem of determining correspondences between concepts, properties, and individuals of different heterogeneous ontologies. With this paper we present a novel probabilistic-logical framework for ontology matching based on Markov logic. We define the syntax and semantics and provide a formalization of the ontology matching problem within the framework. The approach has several advantages over existing methods such as ease of experimentation, incoherence mitigation during the alignment process, and the incorporation of a-priori confidence values. We show empirically that the approach is efficient and more accurate than existing matchers on an established ontology alignment benchmark dataset.
【Keywords】: ontology matching; markov logic; statistical relational learning
【Paper Link】 【Pages】:
【Authors】: Tim Paek ; Michael Gamon ; Scott Counts ; David Maxwell Chickering ; Aman Dhesi
【Abstract】: As users of social networking websites expand their network of friends, they are often flooded with newsfeed posts and status updates, most of which they consider to be "unimportant" and not newsworthy. In order to better understand how people judge the importance of their newsfeed, we conducted a study in which Facebook users were asked to rate the importance of their newsfeed posts as well as their friends. We learned classifiers of newsfeed and friend importance to identify predictive sets of features related to social media properties, the message text, and shared background information. For classifying friend importance, the best performing model achieved 85% accuracy and 25% error reduction. By leveraging this model for classifying newsfeed posts, the best newsfeed classifier achieved 64% accuracy and 27% error reduction.
【Keywords】: social media; triage; newsfeed; Facebook
【Paper Link】 【Pages】:
【Authors】: Meesun Song ; Wonkyu Lee ; Junghwan Kim
【Abstract】: Today social network services like blogs, communities, and social networking sites dominate the web. As Web 2.0 has evolved this way, analyzing social networks has become a promising research issue. There have already been several researches on social network analysis based on users' activities in social services. Most of them focus on the links among the users such as citation, trackback, and comment. However, few studies have analyzed the relations within message threads. In general, they considered the one-way relationship from a comment writer to a post writer. Since users communicate with each other primarily by posting comments one after another, the message threads are key to analyzing latent social relationships. In this paper, we propose a novel method to extract the social relations hidden behind message threads. To evaluate our algorithms, we developed an evaluation system and measured the performances. In addition, since the typical node-edge diagram for social network visualization is not intuitive or readable, we also introduce a novel visualization and interaction method suitable for social relation exploration. Further, we expect our work will help enhance social recommendations, advertisements and personalization.
【Keywords】: social relation analysis; social network analysis
【Paper Link】 【Pages】:
【Authors】: Giorgos Stoilos ; Bernardo Cuenca Grau ; Ian Horrocks
【Abstract】: Conjunctive query answering is a key reasoning service for many ontology-based applications. In order to improve scalability, many Semantic Web query answering systems give up completeness (i.e., they do not guarantee to return all query answers). It may be useful or even critical to the designers and users of such systems to understand how much and what kind of information is (potentially) being lost. We present a method for generating test data that can be used to provide at least partial answers to these questions, a purpose for which existing benchmarks are not well suited. In addition to developing a general framework that formalises the problem, we describe practical data generation algorithms for some popular ontology languages, and present some very encouraging results from our preliminary evaluation.
【Keywords】: Semantic Web; Evaluation; Ontologies; Completeness; Query Answering
【Paper Link】 【Pages】:
【Authors】: Umberto Straccia ; Nuno Lopes ; Gergely Lukacsy ; Axel Polleres
【Abstract】: We describe a generic framework for representing and reasoning with annotated Semantic Web data, formalise the annotated language, the corresponding deductive system, and address the query answering problem. We extend previous contributions on RDF annotations by providing a unified reasoning formalism and allowing the seamless combination of different annotation domains. We demonstrate the feasibility of our method by instantiating it on (i) temporal RDF; (ii) fuzzy RDF; (iii) and their combination. A prototype shows that implementing and combining new domains is easy and that RDF stores can easily be extended to our framework.
【Keywords】: RDFS; Annotation; Fuzzy Logic; Temporal Logic
【Paper Link】 【Pages】:
【Authors】: Jiao Tao ; Evren Sirin ; Jie Bao ; Deborah L. McGuinness
【Abstract】: In many data-centric semantic web applications, it is desirable to use OWL to encode the Integrity Constraints (IC) that must be satisfied by instance data. However, challenges arise due to the Open World Assumption (OWA) and the lack of a Unique Name Assumption (UNA) in OWL’s standard semantics. In particular, conditions that trigger constraint violations in systems using the ClosedWorld Assumption (CWA), will generate new inferences in standard OWL-based reasoning applications. In this paper, we present an alternative IC semantics for OWL that allows applications to work with the CWA and the weak UNA. Ontology modelers can choose which OWL axioms to be interpreted with our IC semantics. Thus application developers are able to combine open world reasoning with closed world constraint validation in a flexible way. We also show that IC validation can be reduced to query answering under certain conditions. Finally, we describe our prototype implementation based on the OWL reasoner Pellet.
【Keywords】: Integrity Constraints; OWL; Description Logics; SPARQL
【Paper Link】 【Pages】:
【Authors】: Jia Wang ; Qing Li ; Yuanzhu Peter Chen ; Jiafen Liu ; Chen Zhang ; Zhangxi Lin
【Abstract】: Self-publication of news on Web sites is becoming a common application platform to enable more engaging interaction among users. Discussion in the form of comments following news postings can be effectively facilitated if the service provider can recommend articles based on not only the original news itself but also the thread of changing comments. This turns the traditional news recommendation to a "discussion moderator" that can intelligently assist online forums. In this work, we present a framework to implement such adaptive news recommendation. In addition, to alleviate the problem of recommending essentially identical articles, the relationship (duplication, generalization or specialization) between suggested news articles and the original posting is investigated. Experiments indicate that our proposed solutions provide an enhanced news recommendation service in forum-based social media.
【Keywords】: news recommendation; recommender; user comments; content-based filtering
【Paper Link】 【Pages】:
【Authors】: Hao Wu ; Jiajun Bu ; Chun Chen ; Can Wang ; Guang Qiu ; Lijun Zhang ; Jianfeng Shen
【Abstract】: In the form of topic discussions, users interact with each other to share knowledge and exchange information in online forums. Modeling the evolution of topic discussion reveals how information propagates on Internet and can thus help understand sociological phenomena and improve the performance of applications such as recommendation systems. In this paper, we argue that a user’s participation in topic discussions is motivated by either her friends or her own preferences. Inspired by the theory of information flow, we propose dynamic topic discussion models by mining influential relationships between users and individual preferences. Reply relations of users are exploited to construct the fundamental influential social network. The property of discussed topics and time lapse factor are also considered in our modeling. Furthermore, we propose a novel measure called ParticipationRank to rank users according to how important they are in the social network and to what extent they prefer to participate in the discussion of a certain topic. The experiments show our model can simulate the evolution of topic discussions well and predict the tendency of user’s participation accurately.
【Keywords】: online forum; topic discussion; information flow; random walk; user modeling; social network; topic modeling
【Paper Link】 【Pages】:
【Authors】: Songhua Xu ; Shaohui Yang ; Francis Chi-Moon Lau
【Abstract】: We introduce several novel word features for keyword extraction and headline generation. These new word features are derived according to the background knowledge of a document as supplied by Wikipedia. Given a document, to acquire its background knowledge from Wikipedia, we first generate a query for searching the Wikipedia corpus based on the key facts present in the document. We then use the query to find articles in the Wikipedia corpus that are closely related to the contents of the document. With the Wikipedia search result article set, we extract the inlink, outlink, category and infobox information in each article to derive a set of novel word features which reflect the document's background knowledge. These newly introduced word features offer valuable indications on individual words' importance in the input document. They serve as nice complements to the traditional word features derivable from explicit information of a document. In addition, we also introduce a word-document fitness feature to charcterize the influence of a document's genre on the keyword extraction and headline generation process. We study the effectiveness of these novel word features for keyword extraction and headline generation by experiments and have obtained very encouraging results.
【Keywords】: word feature; keyword extraction; headline generation
【Paper Link】 【Pages】:
【Authors】: Zhenglu Yang ; Jianjun Yu ; Masaru Kitsuregawa
【Abstract】: Top- k approximate querying on string collections is an important data analysis tool for many applications, and it has been exhaustively studied. However, the scale of the problem has increased dramatically because of the prevalence of the Web. In this paper, we aim to explore the efficient top- k similar string matching problem. Several efficient strategies are introduced, such as length aware and adaptive q -gram selection. We present a general q -gram based framework and propose two efficient algorithms based on the strategies introduced. Our techniques are experimentally evaluated on three real data sets and show a superior performance.
【Keywords】: top-k, similar string search, efficiency
【Paper Link】 【Pages】:
【Authors】: Junjie Yao ; Bin Cui ; Yuxin Huang ; Xin Jin
【Abstract】: Burst detection is an important topic in temporal stream analysis. Usually, only the textual features are used in burst detection. In the theme extraction from current prevailing social media content, it is necessary to consider not only textual features but also the pervasive collaborative context, e.g., resource lifetime and user activity. This paper explores novel approaches to combine multiple sources of such indication for better burst extraction. We systematically investigate the characters of collaborative context, i.e., metadata frequency, topic coverage and user attractiveness. First, a robust state based model is utilized to detect bursts from individual streams. We then propose a learning method to combine these burst pulses. Experiments on a large real dataset demonstrate the remarkable improvements over the traditional methods.
【Keywords】: burst detection; social media; temporal analysis, social context
【Paper Link】 【Pages】:
【Authors】: Chi-Hsin Yu ; Hsin-Hsi Chen
【Abstract】: Good and generous knowledge sources, reliable and efficient induction patterns, and automatic and controllable quality assertion approaches are three critical issues to commonsense knowledge (CSK) acquisition. This paper employs Open Mind Common Sense (OMCS), a volunteers-contributed CSK database, to study the first and the third issues. For those stylized CSK, our result shows that over 40% of CSK for four predicate types in OMCS can be found in the web, which contradicts to the assumption that CSK is not communicated in texts. Moreover, we propose a commonsense knowledge classifier trained from OMCS, and achieve high precision in some predicate types, e.g., 82.6% in HasProperty. The promising results suggest new ways of analyzing and utilizing volunteer-contributed knowledge to design systems automatically mining commonsense knowledge from the web.
【Keywords】: Commonsense Knowledge Analysis; Commonsense Knowledge Classification; OMCS
【Paper Link】 【Pages】:
【Authors】: Tom Chao Zhou ; Hao Ma ; Michael R. Lyu ; Irwin King
【Abstract】: Social tagging systems have emerged as an effective way for users to annotate and share objects on the Web. However, with the growth of social tagging systems, users are easily overwhelmed by the large amount of data and it is very difficult for users to dig out information that he/she is interested in. Though the tagging system has provided interest-based social network features to enable the user to keep track of other users' tagging activities, there is still no automatic and effective way for the user to discover other users with common interests. In this paper, we propose a User Recommendation (UserRec) framework for user interest modeling and interest-based user recommendation, aiming to boost information sharing among users with similar interests. Our work brings three major contributions to the research community: (1) we propose a tag-graph based community detection method to model the users' personal interests, which are further represented by discrete topic distributions; (2) the similarity values between users' topic distributions are measured by Kullback-Leibler divergence (KL-divergence), and the similarity values are further used to perform interest-based user recommendation; and (3) by analyzing users' roles in a tagging system, we find users' roles in a tagging system are similar to Web pages in the Internet. Experiments on tagging dataset of Web pages (Yahoo!~Delicious) show that UserRec outperforms other state-of-the-art recommender system approaches.
【Keywords】: User Recommendation; Tagging System; User Interests Modeling
【Paper Link】 【Pages】:
【Authors】: Barry O'Sullivan
【Abstract】: Constraint programming can be divided very crudely into modeling and solving. Modeling defines the problem, in terms of variables that can take on different values, subject to restrictions (constraints) on which combinations of variables are allowed. Solving finds values for all the variables that simultaneously satisfy all the constraints. However, the impact of constraint programming has been constrained by a lack of "user-friendliness''. Constraint programming has a major "declarative" aspect, in that a problem model can be handed off for solution to a variety of standard solving methods. These methods are embedded in algorithms, libraries, or specialized constraint programming languages. To fully exploit this declarative opportunity however, we must provide more assistance and automation in the modeling process, as well as in the design of application-specific problem solvers. Automated modelling and solving in constraint programming presents a major challenge for the artificial intelligence community. Artificial intelligence, and in particular machine learning, is a natural field in which to explore opportunities for moving more of the burden of constraint programming from the user to the machine. This paper presents technical challenges in the areas of constraint model acquisition, formulation and reformulation, synthesis of filtering algorithms for global constraints, and automated solving. We also present the metrics by which success and progress can be measured.
【Keywords】: Constraint Programming; Machine Learning; Optimization
【Paper Link】 【Pages】:
【Authors】: Sven Seuken ; Kamal Jain ; David C. Parkes
【Abstract】: The next decade will see an abundance of new intelligent systems, many of which will be market-based. Soon, users will interact with many new markets, perhaps without even knowing it: when driving their car, when listening to a song, when backing up their files, or when surfing the web. We argue that these new systems can only be successful if a new approach is chosen towards designing them. In this paper we introduce the general problem of "Hidden Market Design." The design of a "weakly hidden" market involves reducing some of the market complexities and providing a user interface (UI) that makes the interaction seamless for the user. A "strongly hidden market" is one where some semantic aspect of a market is hidden altogether (e.g., budgets, prices, combinatorial constraints). We show that the intersection of UI design and market design is of particular importance for this research agenda. To illustrate hidden market design, we give a series of potential applications. We hope that the problem of hidden market design will inspire other researchers and lead to new research in this direction, paving the way for more successful market-based systems in the future.
【Keywords】: market design; UI design; e-commerce; HCI
【Paper Link】 【Pages】:
【Authors】: Peter Stone ; Gal A. Kaminka ; Sarit Kraus ; Jeffrey S. Rosenschein
【Abstract】: As autonomous agents proliferate in the real world, both in software and robotic settings, they will increasingly need to band together for cooperative activities with previously unfamiliar teammates. In such ad hoc team settings, team strategies cannot be developed a priori. Rather, an agent must be prepared to cooperate with many types of teammates: it must collaborate without pre-coordination. This paper challenges the AI community to develop theory and to implement prototypes of ad hoc team agents. It defines the concept of ad hoc team agents, specifies an evaluation paradigm, and provides examples of possible theoretical and empirical approaches to challenge. The goal is to encourage progress towards this ambitious, newly realistic, and increasingly important research goal.
【Keywords】: Artificial Intelligence; Autonomous Agents; Multiagent Systems; Teamwork
【Paper Link】 【Pages】:
【Authors】: Jeff Yan
【Abstract】: Collusion is a major unsolved security problem in online bridge: by illicitly exchanging card information over the telephone, instant messenger or the like, cheaters can gain huge advantages over honest players. It is very hard if not impossible to prevent collusion from happening. Instead, we motivate an AI-based detection approach and discuss its challenges. We challenge the AI community to create automated methods for detecting collusive traces left in game records with an accuracy that can be achieved by human masters.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Michael Brenner
【Abstract】: An AI system that is to create a story (autonomously or in interaction with human users) requires capabilities from many subfields of AI in order to create characters that themselves appear to act intelligently and believably in a coherent story world. Specifically, the system must be able to reason about the physical actions and verbal interactions of the characters as well as their perceptions of the world. Furthermore it must make the characters act believably--i.e. in a goal-directed yet emotionally plausible fashion. Finally, it must cope with (and embrace!) the dynamics of a multiagent environment where beliefs, sentiments, and goals may change during the course of a story and where plans are thwarted, adapted and dropped all the time. In this paper, we describe a representational and algorithmic framework for modelling such dynamic story worlds, Continual Multiagent Planning. It combines continual planning (i.e. an integrated approach to planning and execution) with a rich description language for modelling epistemic and affective states, desires and intentions, sensing and communication. Analysing story examples generated by our implemented system we show the benefits of such an integrated approach for dynamic plot generation.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Scott E. Friedman ; Kenneth D. Forbus
【Abstract】: Understanding conceptual change is an important problem in modeling human cognition and in making integrated AI systems that can learn autonomously. This paper describes a model of explanation-based conceptual change, integrating sketch understanding, analogical processing, qualitative models, truth-maintenance, and heuristic-based reasoning within the Companions cognitive architecture. Sketch understanding is used to automatically encode stimuli in the form of comic strips. Qualitative models and conceptual quantities are constructed for new phenomena via analogical reasoning and heuristics. Truth-maintenance is used to integrate conceptual and episodic knowledge into explanations, and heuristics are used to modify existing conceptual knowledge in order to produce better explanations. We simulate the learning and revision of the concept of force, testing the concepts learned via a questionnaire of sketches given to students, showing that our model follows a similar learning trajectory.
【Keywords】: conceptual change; learning; cognitive architectures
【Paper Link】 【Pages】:
【Authors】: Chad Hogg ; Ugur Kuter ; Hector Muñoz-Avila
【Abstract】: We consider how to learn Hierarchical Task Networks (HTNs) for planning problems in which both the quality of solution plans generated by the HTNs and the speed at which those plans are found is important. We describe an integration of HTN Learning with Reinforcement Learning to both learn methods by analyzing semantic annotations on tasks and to produce estimates of the expected values of the learned methods by performing Monte Carlo updates. We performed an experiment in which plan quality was inversely related to plan length. In two planning domains, we evaluated the planning performance of the learned methods in comparison to two state-of-the-art satisficing classical planners, FastForward and SGPlan6, and one optimal planner, HSP. The results demonstrate that a greedy HTN planner using the learned methods was able to generate higher quality solutions than SGPlan6 in both domains and FastForward in one. Our planner, FastForward, and SGPlan6 ran in similar time, while HSP was exponentially slower.
【Keywords】: planning; hierarchical task networks; reinforcement learning
【Paper Link】 【Pages】:
【Authors】: Unmesh Kurup ; Nicholas L. Cassimatis
【Abstract】: Many problems in AI, including planning, logical reasoning and probabilistic inference, have been shown to reduce to (weighted) constraint satisfaction. While there are a number of approaches for solving such problems, the recent gains in efficiency of the satisfiability approach have made SAT solvers a popular choice. Modern propositional SAT solvers are efficient for a wide variety of problems. However, particularly in the case of spatial reasoning, conversion to propositional SAT can sometimes result in a large number of variables and/or clauses. Moreover, spatial reasoning problems can often be more efficiently solved if the agent is able to exploit the geometric nature of space to make better choices during search and backtracking. The result of these two drawbacks — larger problem sizes and inefficient search — is that even simple spatial constraint problems are often intractable in the SAT approach. In this paper we propose a spatial reasoning system that provides significant performance improvements in constraint satisfaction problems involving spatial predicates. The key to our approach is to integrate a diagrammatic representation with a DPLL-based backtracking algorithm that is specialized for spatial reasoning. The resulting integrated system can be applied to larger and more complex problems than current approaches and can be adopted to improve performance in a variety of problems ranging from planning to probabilistic inference
【Keywords】: spatial reasoning; Satisfiability-Modulo Theories
【Paper Link】 【Pages】:
【Authors】: Lanny Lin ; Michael Roscheck ; Michael A. Goodrich ; Bryan S. Morse
【Abstract】: Current practice in Wilderness Search and Rescue (WiSAR) is analogous to an intelligent system designed to gather and analyze information to find missing persons in remote areas. The system consists of multiple parts - various tools for information management (maps, GPS, etc) distributed across personnel with different skills and responsibilities. Introducing a camera-equipped mini-UAV into this task requires autonomy and information technology that itself is an integrated intelligent system to be used by a sub-team that must be integrated into the overall intelligent system. In this paper, we identify key elements of the integration challenges along two dimensions: (a) attributes of intelligent system and (b) scale, meaning individual or group. We then present component technology that offload or supplement many responsibilities to autonomous systems, and finally describe how autonomy and information are integrated into user interfaces to better support distributed search across time and space. The integrated system was demoed for Utah County Search and Rescue personnel. A real searcher flew the UAV after minimal training and successfully located the simulated missing person in a wilderness area.
【Keywords】: Wilderness Search and Rescue; UAV; Integrated Intelligence
【Paper Link】 【Pages】:
【Authors】: Matthew Molineaux ; Matthew Klenk ; David W. Aha
【Abstract】: Modern complex games and simulations pose many challenges for an intelligent agent, including partial observability, continuous time and effects, hostile opponents, and exogenous events. We present ARTUE (Autonomous Response to Unexpected Events), a domain-independent autonomous agent that dynamically reasons about what goals to pursue in response to unexpected circumstances in these types of environments. ARTUE integrates AI research in planning, environment monitoring, explanation, goal generation, and goal management. To explain our conceptualization of the problem ARTUE addresses, we present a new conceptual framework, goal-driven autonomy, for agents that reason about their goals. We evaluate ARTUE on scenarios in the TAO Sandbox, a Navy training simulation, and demonstrate its novel architecture, which includes components for Hierarchical Task Network planning, explanation, and goal management. Our evaluation shows that ARTUE can perform well in a complex environment and that each component is necessary and contributes to the performance of the integrated system.
【Keywords】: Autonomous Agents; Goal-Directed Autonomy;AI and Games; Explanation; HTN Planning; Goal Generation and Management
【Paper Link】 【Pages】:
【Authors】: Chunki Park ; Will Bridewell ; Pat Langley
【Abstract】: Quantitative modeling plays a key role in the natural sciences, and systems that address the task of inductive process modeling can assist researchers in explaining their data. In the past, such systems have been limited to data sets that recorded change over time, but many interesting problems involve both spatial and temporal dynamics. To meet this challenge, we introduce SCISM, an integrated intelligent system which solves the task of inducing process models that account for spatial and temporal variation. We also integrate SCISM with a constraint learning method to reduce computation during induction. Applications to ecological modeling demonstrate that each system fares well on the task, but that the enhanced system does so much faster than the baseline version.
【Keywords】: inductive process modeling; integrated intelligence; scientific discovery
【Paper Link】 【Pages】:
【Authors】: Kartik Talamadupula ; J. Benton ; Paul W. Schermerhorn ; Subbarao Kambhampati ; Matthias Scheutz
【Abstract】: In this paper, we present an integrated planning and robotic architecture that actively directs an agent engaged in an urban search and rescue (USAR) scenario. We describe three salient features that comprise the planning component of this system, namely (1) the ability to plan in a world open with respect to objects, (2) execution monitoring and replanning abilities, and (3) handling soft goals, and detail the interaction of these parts in representing and solving the USAR scenario at hand. We show that though insufficient in an individual capacity, the integration of this trio of features is sufficient to solve the scenario that we present. We test our system with an example problem that involves soft and hard goals, as well as goal deadlines and action costs, and show that the planner is capable of incorporating sensing actions and execution monitoring in order to produce goal-fulfilling plans that maximize the net benefit accrued.
【Keywords】: planning; robotics; integration; usar; search; rescue
【Paper Link】 【Pages】:
【Authors】: Samuel Wintermute
【Abstract】: In this paper, we consider the problem of reinforcement learning in spatial tasks. These tasks have many states that can be aggregated together to improve learning efficiency. In an agent, this aggregation can take the form of selecting appropriate perceptual processes to arrive at a qualitative abstraction of the underlying continuous state. However, for arbitrary problems, an agent is unlikely to have the perceptual processes necessary to discriminate all relevant states in terms of such an abstraction. To help compensate for this, reinforcement learning can be integrated with an imagery system, where simple models of physical processes are applied within a low-level perceptual representation to predict the state resulting from an action. Rather than abstracting the current state, abstraction can be applied to the predicted next state. Formally, it is shown that this integration broadens the class of perceptual abstraction methods that can be used while preserving the underlying problem. Empirically, it is shown that this approach can be used in complex domains, and can be beneficial even when formal requirements are not met.
【Keywords】: reinforcement learning; imagery; abstraction; cognitive architecture; Soar; state-action aggregation; state aggregation; spatial reasoning
【Paper Link】 【Pages】:
【Authors】: Joseph Z. Xu ; John E. Laird
【Abstract】: We present an instance-based, online method for learning action models in unanticipated, relational domains. Our algorithm memorizes pre- and post-states of transitions an agent encounters while experiencing the environment, and makes predictions by using analogy to map the recorded transitions to novel situations. Our algorithm is implemented in the Soar cognitive architecture, integrating its task-independent episodic memory module and analogical reasoning implemented in procedural memory. We evaluate this algorithm’s prediction performance in a modified version of the blocks world domain and the taxi domain. We also present a reinforcement learning agent that uses our model learning algorithm to significantly speed up its convergence to an optimal policy in the modified blocks world domain.
【Keywords】: action modeling; soar; analogy; episodic memory; model-based reinforcement learning
【Paper Link】 【Pages】:
【Authors】: Jordan Frank ; Shie Mannor ; Doina Precup
【Abstract】: Activity recognition based on data from mobile wearable devices is becoming an important application area for machine learning. We propose a novel approach based on a combination of feature extraction using time-delay embedding and supervised learning. The computational requirements are considerably lower than existing approaches, so the processing can be done in real time on a low-powered portable device such as a mobile phone. We evaluate the performance of our algorithm on a large, noisy data set comprising over 50 hours of data from six different subjects, including activities such as running and walking up or down stairs. We also demonstrate the ability of the system to accurately classify an individual from a set of 25 people, based only on the characteristics of their walking gait. The system requires very little parameter tuning, and can be trained with small amounts of data.
【Keywords】: activity recognition; gait recognition; machine learning; supervised learning
【Paper Link】 【Pages】:
【Authors】: Joshua Mason Joseph ; Finale Doshi-Velez ; Nicholas Roy
【Abstract】: Constructing models of mobile agents can be difficult without domain-specific knowledge. Parametric models flexible enough to capture all mobility patterns that an expert believes are possible are often large, requiring a great deal of training data. In contrast, nonparametric models are extremely flexible and can generalize well with relatively little training data. We propose modeling the mobility patterns of moving agents as a mixture of Gaussian processes (GP) with a Dirichlet process (DP) prior over mixture weights. The GP provides a flexible representation for each individual mobility pattern, while the DP assigns observed trajectories to particular mobility patterns. Both the GPs and the DP adjust the model's complexity based on available data, implicitly avoiding issues of over-fitting or under-fitting. We apply our model to a helicopter-based tracking task, where the mobility patterns of the tracked agents — cars — are learned from real data collected from taxis in the greater Boston area.
【Keywords】: Machine Learning for Control and Decision Making; Reinforcement Learning; Nonparametric Bayesian Statistics
【Paper Link】 【Pages】:
【Authors】: Çetin Meriçli ; Manuela M. Veloso
【Abstract】: Developing a robust, flexible, closed-loop walking algorithm for a humanoid robot is a challenging task due to the complex dynamics of the general biped walk. Common analytical approaches to biped walk use simplified models of the physical reality. Such approaches are partially successful as they lead to failures of the robot walk in terms of unavoidable falls. Instead of further refining the analytical models, in this work we investigate the use of human corrective demonstrations, as we realize that a human can visually detect when the robot may be falling. We contribute a two-phase biped walk learning approach, which we experiment on the Aldebaran NAO humanoid robot. In the first phase, the robot walks following an analytical simplified walk algorithm, which is used as a black box, and we identify and save a walk cycle as joint motion commands. We then show how the robot can repeatedly and successfully play back the recorded motion cycle, even if in open-loop. In the second phase, we create a closed-loop walk by modifying the recorded walk cycle to respond to sensory data. The algorithm learns joint movement corrections to the open-loop walk based on the corrective feedback provided by a human, and on the sensory data, while walking autonomously. In our experimental results, we show that the learned closed-loop walking policy outperforms a hand-tuned closed-loop policy and the open-loop playback walk, in terms of the distance traveled by the robot without falling.
【Keywords】: Biped Walking, Learning from Demonstration
【Paper Link】 【Pages】:
【Authors】: Daniel Peebles ; Hong Lu ; Nicholas D. Lane ; Tanzeem Choudhury ; Andrew T. Campbell
【Abstract】: Modeling human behavior requires vast quantities of accurately labeled training data, but for ubiquitous people-aware applications such data is rarely attainable. Even researchers make mistakes when labeling data, and consistent, reliable labels from low-commitment users are rare. In particular, users may give identical labels to activities with characteristically different signatures (e.g., labeling eating at home or at a restaurant as "dinner") or may give different labels to the same context (e.g., "work" vs. "office"). In this scenario, labels are unreliable but nonetheless contain valuable information for classification. To facilitate learning in such unconstrained labeling scenarios, we propose Community-Guided Learning (CGL), a framework that allows existing classifiers to learn robustly from unreliably-labeled user-submitted data. CGL exploits the underlying structure in the data and the unconstrained labels to intelligently group crowd-sourced data. We demonstrate how to use similarity measures to determine when and how to split and merge contributions from different labeled categories and present experimental results that demonstrate the effectiveness of our framework.
【Keywords】: machine learning; community; labeling
【Paper Link】 【Pages】:
【Authors】: Jan Peters ; Katharina Mülling ; Yasemin Altun
【Abstract】: Policy search is a successful approach to reinforcement learning. However, policy improvements often result in the loss of information. Hence, it has been marred by premature convergence and implausible solutions. As first suggested in the context of covariant policy gradients, many of these problems may be addressed by constraining the information loss. In this paper, we continue this path of reasoning and suggest the Relative Entropy Policy Search (REPS) method. The resulting method differs significantly from previous policy gradient approaches and yields an exact update step. It can be shown to work well on typical reinforcement learning benchmark problems.
【Keywords】: reinforcement learning, policy search, motor primitive selection
【Paper Link】 【Pages】:
【Authors】: Jivko Sinapov ; Alexander Stoytchev
【Abstract】: Active object exploration is one of the hallmarks of human and animal intelligence. Research in psychology has shown that the use of multiple exploratory behaviors is crucial for learning about objects. Inspired by such research, recent work in robotics has demonstrated that by performing multiple exploratory behaviors a robot can dramatically improve its object recognition rate. But what is the cause of this improvement? To answer this question, this paper examines the conditions under which combining information from multiple behaviors and sensory modalities leads to better object recognition results. Two different problems are considered: interactive object recognition using auditory and proprioceptive feedback, and surface texture recognition using tactile and proprioceptive feedback. Analysis of the results shows that metrics designed to estimate classifier model diversity can explain the improvement in recognition accuracy. This finding establishes, for the first time, an important link between empirical studies of exploratory behaviors in robotics and theoretical results on boosting in machine learning.
【Keywords】: Robotics; Machine Learning and Robotics
【Paper Link】 【Pages】:
【Authors】: Dezhen Song ; Yiliang Xu
【Abstract】: We report a new filter for assisting the search for rare bird species. Since a rare bird only appears in front of the camera with very low occurrence (e.g. less than ten times per year) for very short duration (e.g. less than a fraction of a second), our algorithm must have very low false negative rate. We verify the bird body axis information with the known bird flying dynamics from the short video segment. Since a regular extended Kalman filter (EKF) cannot converge due to high measurement error and limited data, we develop a novel Probable Observation Data Set (PODS)-based EKF method. The new PODS-EKF searches the measurement error range for all probable observation data that ensures the convergence of the corresponding EKF in short time frame. The algorithm has been extensively tested in experiments. The results show that the algorithm achieves 95.0% area under ROC curve in physical experiment with close to zero false negative rate.
【Keywords】: Bird detection, vision, filter
【Paper Link】 【Pages】:
【Authors】: Luciano Spinello ; Kai Oliver Arras ; Rudolph Triebel ; Roland Siegwart
【Abstract】: People tracking is a key technology for autonomous systems, intelligent cars and social robots operating in populated environments. What makes the task difficult is that the appearance of humans in range data can change drastically as a function of body pose, distance to the sensor, self-occlusion and occlusion by other objects. In this paper we propose a novel approach to pedestrian detection in 3D range data based on supervised learning techniques to create a bank of classifiers for different height levels of the human body. In particular, our approach applies AdaBoost to train a strong classifier from geometrical and statistical features of groups of neighboring points at the same height. In a second step, the AdaBoost classifiers mutually enforce their evidence across different heights by voting into a continuous space. Pedestrians are finally found efficiently by mean-shift search for local maxima in the voting space. Experimental results carried out with 3D laser range data illustrate the robustness and efficiency of our approach even in cluttered urban environments. The learned people detector reaches a classification rate up to 96% from a single 3D scan.
【Keywords】: AI for robotics; machine learning applied to robotics; mobile robotics; three-dimensional machine perception; range sensing; pedestrian detection; people detection; machine learning
【Paper Link】 【Pages】:
【Authors】: Muralikrishna Sridhar ; Anthony G. Cohn ; David C. Hogg
【Abstract】: We present a method for unsupervised learning of event classes from videos in which multiple actions might occur simultaneously. It is assumed that all such activities are produced from an underlying set of event class generators. The learning task is then to recover this generative process from visual data. A set of event classes is derived from the most likely decomposition of the tracks into a set of labelled events involving subsets of interacting tracks. Interactions between subsets of tracks are modelled as a relational graph structure that captures qualitative spatio-temporal relationships between these tracks. The posterior probability of candidate solutions favours decompositions in which events of the same class have a similar relational structure, together with other measures of well-formedness. A Markov Chain Monte Carlo (MCMC) procedure is used to efficiently search for the MAP solution. This search moves between possible decompositions of the tracks into sets of unlabelled events and at each move adds a close to optimal labelling (for this decomposition) using spectral clustering. Experiments on real data show that the discovered event classes are often semantically meaningful and correspond well with groundtruth event classes assigned by hand.
【Keywords】: unsupervised learning of event classes; video activity understanding; scene interpretation; video activity analysis; learning from observation
【Paper Link】 【Pages】:
【Authors】: Seung-Joon Yi ; Byoung-Tak Zhang ; Daniel D. Lee
【Abstract】: We present a novel method to control a biped humanoid robot to walk on unknown inclined terrains, using an online learning algorithm to estimate in real-time the local terrain from proprioceptive and inertial sensors. Compliant controllers for the ankle joints are used to actively probe the surrounding surface, and the measured sensor data are combined to explicitly learn the global inclination and local disturbances of the terrain. These estimates are then used to adaptively modify the robot locomotion and control parameters. Results from both a physically-realistic computer simulation and experiments on a commercially available small humanoid robot show that our method can rapidly adapt to changing surface conditions to ensure stable walking on uneven surfaces.
【Keywords】: Bipedal; Walking; Uneven; Terrain;
【Paper Link】 【Pages】:
【Authors】: Ji Zhang ; Dezhen Song
【Abstract】: We report a new error-aware monocular visual odometry method that only uses vertical lines, such as vertical edges of buildings and poles in urban areas as landmarks. Since vertical lines are easy to extract, insensitive to lighting conditions/ shadows, and sensitive to robot movements on the ground plane, they are robust features if compared with regular point features or line features. We derive a recursive visual odometry method based on the vertical line pairs. We analyze how errors are propagated and introduced in the continuous odometry process by deriving the closed form representation of covariance matrix. We formulate the minimum variance ego-motion estimation problem and present a method that outputs weights for different vertical line pairs. The resulting visual odometry method is tested in physical experiments and compared with two existing methods that are based on point features and line features, respectively. The experiment results show that our method outperforms its two counterparts in robustness, accuracy, and speed. The relative errors of our method are less than 2% in experiments.
【Keywords】: Vertical line, vision odometry, mobile robots
【Paper Link】 【Pages】:
【Authors】: Mustafa Bilgic ; Lise Getoor
【Abstract】: Labeling nodes in a network is an important problem that has seen a growing interest. A number of methods that exploit both local and relational information have been developed for this task. Acquiring the labels for a few nodes at inference time can greatly improve the accuracy, however the question of figuring out which node labels to acquire is challenging. Previous approaches have been based on simple structural properties. Here, we present a novel technique, which we refer to as reflect and correct,that can learn and predict when the underlying classification system is likely to make mistakes and it suggests acquisitions to correct those mistakes.
【Keywords】: active inference; collective classification; statistical relational learning
【Paper Link】 【Pages】:
【Authors】: Blai Bonet ; Héctor Palacios ; Hector Geffner
【Abstract】: Finite-state controllers represent an effective action selection mechanisms widely used in domains such as video-games and mobile robotics. In contrast to the policies obtained from MDPs and POMDPs, finite-state controllers have two advantages: they are often extremely compact, and they are general, applying to many problems and not just one. A limitation of finite-state controllers, on the other hand, is that they are written by hand. In this paper, we address this limitation, presenting a method for deriving controllers automatically from models. The models represent a class of contingent problems where actions are deterministic and some fluents are observable. The problem of deriving a controller is converted into a conformant problem that is solved using classical planners, taking advantage of a complete translation into classical planning introduced recently. The controllers derived are ‘general’ in the sense that they do not solve the original problem only, but many variations as well, including changes in the size of the problem or in the uncertainty of the initial situation and action effects. Several experiments illustrating the automatic derivation of controllers are presented.
【Keywords】: Controllers; Robotics; Contingent planning; Conformant planning; Translation; POMDP
【Paper Link】 【Pages】:
【Authors】: Andrea Calì ; Georg Gottlob ; Michael Kifer ; Thomas Lukasiewicz ; Andreas Pieris
【Abstract】: Answering queries posed over knowledge bases is a central problem in knowledge representation and database theory. In the database area, checking query containment is an important query optimization and schema integration technique. In knowledge representation it has been used for object classification, schema integration, service discovery, and more. In the presence of a knowledge base, the problem of query containment is strictly related to that of query answering; indeed, the two are reducible to each other; we focus on the latter, and our results immediately extend to the former.
【Keywords】: Ontologies, query processing, semantic web, database constraints.
【Paper Link】 【Pages】:
【Authors】: Francesco Calimeri ; Susanna Cozza ; Giovambattista Ianni ; Nicola Leone
【Abstract】: This paper summarizes our line of research about the introduction of function symbols (functions) in Answer Set Programming (ASP) – a powerful language for knowledge representation and reasoning. The undecidability of reasoning on ASP with functions, implied that functions were subject to severe restrictions or disallowed at all, drastically limiting ASP applicability. We overcame most of the technical difficulties preventing this introduction, and we singled out a highly expressive class of programs with functions (FG-programs), allowing the (possibly recursive) use of function terms in the full ASP language with disjunction and negation. Reasoning on FG-programs is decidable, and they can express any computable function (causing membership in this class to be semi-decidable). We singled out also FD-programs, a subset of FG-programs which are effectively recognizable, while keeping the computability of reasoning. We implemented all results into the DLV system, thus obtaining an ASP system allowing to encode any computable function in a rich and fully declarative KRR language, ensuring termination on every FG program. Finally, we singled out the class of DFRP programs, where decidability of reasoning is guaranteed and Prolog-like functions are allowed.
【Keywords】: ASP; answer set programming; KRR; knowledge representation and reasoning; function symbols; logic programming
【Paper Link】 【Pages】:
【Authors】: Luc De Raedt ; Tias Guns ; Siegfried Nijssen
【Abstract】: Machine learning and data mining have become aware that using constraints when learning patterns and rules can be very useful. To this end, a large number of special purpose systems and techniques have been developed for solving such constraint-based mining and learning problems. These techniques have, so far, been developed independently of the general purpose tools and principles of constraint programming known within the field of artificial intelligence. This paper shows that off-the-shelf constraint programming techniques can be applied to various pattern mining and rule learning problems (cf. also (De Raedt, Guns, and Nijssen 2008; Nijssen, Guns, and De Raedt 2009)). This does not only lead to methodologies that are more general and flexible, but also provides new insights into the underlying mining problems that allow us to improve the state-of-the-art in data mining. Such a combination of constraint programming and data mining raises a number of interesting new questions and challenges.
【Keywords】: Constraint Programming; Data Mining; Machine Learning
【Paper Link】 【Pages】:
【Authors】: Mingyu Guo ; Vincent Conitzer
【Abstract】: In many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the decision that work in spite of such strategic behavior, usually by making untruthful behavior suboptimal. In automated mechanism design, the idea is to computationally search through the space of feasible mechanisms, rather than to design them analytically by hand. Unfortunately, the most straightforward approach to automated mechanism design does not scale to large instances, because it requires searching over a very large space of possible functions. In this paper, we describe an approach to automated mechanism design that is computationally feasible. Instead of optimizing over all feasible mechanisms, we carefully choose a parameterized subfamily of mechanisms. Then we optimize over mechanisms within this family, and analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily. We demonstrate the usefulness of our approach with two case studies.
【Keywords】: mechanism design; automated mechanism design; prior-free
【Paper Link】 【Pages】:
【Authors】: Felix Halim ; Panagiotis Karras ; Roland H. C. Yap
【Abstract】: The problem of dividing a sequence of values into segments occurs in database systems, information retrieval, and knowledge management. The challenge is to select a finite number of boundaries for the segments so as to optimize an objective error function defined over those segments. Although this optimization problem can be solved in polynomial time, the algorithm which achieves the minimum error does not scale well, hence it is not practical for applications with massive data sets. There is considerable research with numerous approximation and heuristic algorithms. Still, none of those approaches has resolved the quality-efficiency tradeoff in a satisfactory manner. In (Halim, Karras, and Yap 2009), we obtain near linear time algorithms which achieve both the desired scalability and near-optimal quality, thus dominating earlier approaches. In this paper, we show how two ideas from artificial intelligence, an efficient local search and recombination of multiple solutions reminiscent of genetic algorithms, are combined in a novel way to obtain state of the art histogram construction algorithms.
【Keywords】: local search; histogram; segmentation
【Paper Link】 【Pages】:
【Authors】: Mausam ; Stephen Soderland ; Oren Etzioni
【Abstract】: The bare minimum lexical resource required to translate between a pair of languages is a translation dictionary. Unfortunately, dictionaries exist only between a tiny fraction of the 49 million possible language-pairs making machine translation virtually impossible between most of the languages. This paper summarizes the last four years of our research motivated by the vision of panlingual communication. Our research comprises three key steps. First, we compile over 630 freely available dictionaries over the Web and convert this data into a single representation – the translation graph. Second, we build several inference algorithms that infer translations between word pairs even when no dictionary lists them as translations. Finally, we run our inference procedure offline to construct PANDICTIONARY– a sense-distinguished, massively multilingual dictionary that has translations in more than 1000 languages. Our experiments assess the quality of this dictionary and find that we have 4 times as many translations at a high precision of 0.9 compared to the English Wiktionary, which is the lexical resource closest to PANDICTIONARY.
【Keywords】: Multilinguality; Machien Translation; Lexical Translation; Translation Dictionaries; Probabilistic Inference over Graphs
【Paper Link】 【Pages】:
【Authors】: Matthew E. Taylor ; Katherine E. Coons ; Behnam Robatmili ; Bertrand A. Maher ; Doug Burger ; Kathryn S. McKinley
【Abstract】: As computer architectures become increasingly complex, hand-tuning compiler heuristics becomes increasingly tedious and time consuming for compiler developers. This paper presents a case study that uses a genetic algorithm to learn a compiler policy. The target policy implicitly balances communication and contention among processing elements of the TRIPS processor, a physically realized prototype chip. We learn specialized policies for individual programs as well as general policies that work well across all programs. We also employ a two-stage method that first classifies the code being compiled based on salient characteristics, and then chooses a specialized policy based on that classification. This work is particularly interesting for the AI community because it 1) emphasizes the need for increased collaboration between AI researchers and researchers from other branches of computer science and 2) discusses a machine learning setup where training on the custom hardware requires weeks of training, rather than the more typical minutes or hours.
【Keywords】: genetic algorithms; machine learning; compilers
【Paper Link】 【Pages】:
【Authors】: David Robert Martin Thompson ; Kevin Leyton-Brown
【Abstract】: Modern techniques for representing games and computing their Nash equilibria are approaching the point where they can be used to analyze market games. We demonstrate this by showing how the equilibria of different position auction mechanisms can be tractably identified using these techniques. These results enable detailed and quantitative comparisons of the different auction mechanisms — in terms of both efficiency and revenue — under different preference models and equilibrium selection criteria.
【Keywords】: Auctions and Market-Based Systems; E-Commerce; Game Theory
【Paper Link】 【Pages】:
【Authors】: Keith Vertanen ; Per Ola Kristensson
【Abstract】: Correcting recognition errors is often necessary in a speech interface. These errors not only reduce users' overall entry rate, but can also lead to frustration. While making fewer recognition errors is undoubtedly helpful, facilities for supporting user-guided correction are also critical. We explore how to better support user corrections using Parakeet — a continuous speech recognition system for mobile touch-screen devices. Parakeet's interface is designed for easy error correction on a handheld device. Users correct errors by selecting alternative words from a word confusion network and by typing on a predictive software keyboard. Our interface design was guided by computational experiments and used a variety of information sources to aid the correction process. In user studies, participants were able to write text effectively despite sometimes high initial recognition error rates. Using Parakeet as an example, we discuss principles we found were important for building an effective speech correction interface.
【Keywords】: speech recognition; touch screen; error correction; multimodal;
【Paper Link】 【Pages】:
【Authors】: Chih-Han Yu ; Radhika Nagpal
【Abstract】: Decentralized agent groups typically require complex mechanisms to accomplish coordinated tasks. In contrast, biological systems can achieve intelligent group behaviors with each agent performing simple sensing and actions. We summarize our recent papers on a biologically-inspired control framework for multi-agent tasks that is based on a simple and iterative control law. We theoretically analyze important aspects of this decentralized approach, such as the convergence and scalability, and further demonstrate how this approach applies to real-world applications with a diverse set of multi-agent applications. These results provide a deeper understanding of the contrast between centralized and decentralized algorithms in multi-agent tasks and autonomous robot control.
【Keywords】: Multiagent Systems; Biologically-inspired approaches and methods; Multi-Robot systems; Collective Intelligence; Distributed Problem Solving
【Paper Link】 【Pages】:
【Authors】: Hector Geffner
【Abstract】: The selection of the action to do next is one of the central problems faced by autonomous agents. In AI, three approaches have been used to address this problem: the programming-based approach, where the agent controller is given by the programmer, the learning-based approach, where the controller is induced from experience via a learning algorithm, and the model-based approach, where the controller is derived from a model of the problem. Planning in AI is best conceived as the model-based approach to action selection. The models represent the initial situation, actions, sensors, and goals. The main challenge in planning is computational, as all the models, whether accommodating feedback and uncertainty or not, are intractable in the worst case. In this article, I review some of the models considered in current planning research, the progress achieved in solving these models, and some of the open problems.
【Keywords】: planning, autonomous behavior
【Paper Link】 【Pages】:
【Authors】: Sven Koenig ; Pinar Keskinocak ; Craig A. Tovey
【Abstract】: Auctions are promising decentralized methods for teams of agents to allocate and re-allocate tasks among themselves in dynamic, partially known and time-constrained domains with positive or negative synergies among tasks. Auction-based coordination systems are easy to understand, simple to implement and broadly applicable. They promise to be efficient both in communication (since agents communicate only essential summary information) and in computation (since agents compute their bids in parallel). Artificial intelligence research has explored auction-based coordination systems since the early work on contract networks, mostly from an experimental perspective. This overview paper describes our recent progress towards creating a framework for the design and analysis of cooperative auctions for agent coordination.
【Keywords】: cooperative auction; agent coordination; sequential single-item auction; task allocation
【Paper Link】 【Pages】:
【Authors】: Sridhar Mahadevan
【Abstract】: Automatically constructing novel representations of tasks from analysis of state spaces is a longstanding fundamental challenge in AI. I review recent progress on this problem for sequential decision making tasks modeled as Markov decision processes. Specifically, I discuss three classes of representation discovery problems: finding functional, state, and temporal abstractions. I describe solution techniques varying along several dimensions: diagonalization or dilation methods using approximate or exact transition models; reward-specific vs reward-invariant methods; global vs. local representation construction methods; multiscale vs. flat discovery methods; and finally, orthogonal vs. redundant representa- tion discovery methods. I conclude by describing a number of open problems for future work.
【Keywords】: Sequential Decision Making; Markov Decision Processes; Feature Construction
【Paper Link】 【Pages】:
【Authors】: Brent Beer ; Ross Mead ; Jerry B. Weinberg
【Abstract】: As a robot formation increases in size or explores places where it is difficult for a human operator to interact, autonomous control becomes critical. We propose a distributed autonomous method for evaluating properties of multi-robot systems, and then discuss how this information can be applied to improve performance with respect to a given operation. We present this as an extension of our previous work on robot formations; however, the techniques described could be adapted to other multi-robot systems.
【Keywords】: Robot Formations; Multi-Robot Coordination; Distributed Systems
【Paper Link】 【Pages】:
【Authors】: Shanjun Cheng ; Anita Raja ; Victor R. Lesser
【Abstract】: Embedded systems consisting of collaborating agents capable of interacting with their environment are becoming ubiquitous. It is crucial for these systems to be able to adapt to the dynamic and uncertain characteristics of an open environment. In this paper, we argue that multiagent meta-level control (MMLC) is an effective way to determine when this adaptation process should be done and how much effort should be invested in adaptation as opposed to continuing with the current action plan. We describe a reinforcement learning based approach to learn decentralized meta-control policies offline. We then propose to use the learned reward model as input to a global optimization algorithm to avoid conflicting meta-level decisions between coordinating agents. Our initial experiments in the context of NetRads, a multiagent tornado tracking application show that MMLC significantly improves performance in a 3-agent network.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Halit Erdogan ; Olivier Bodenreider ; Esra Erdem
【Abstract】: We introduce a new method to find semantic inconsistencies (i.e., concepts with erroneous synonymity) in the Unified Medical Language System (UMLS). The idea is to identify the inconsistencies by comparing the semantic groups of hierarchically-related concepts using Answer Set Programming. With this method, we identified several inconsistent concepts in UMLS and discovered an interesting semantic pattern along hierarchies, which seems associated with wrong synonymy.
【Keywords】: UMLS, Answer Set Programming, Inconsistencies in UMLS
【Paper Link】 【Pages】:
【Authors】: Daniel S. Farenzena ; Luís C. Lamb ; Ricardo M. Araujo
【Abstract】: We propose a framework where humans and computers can collaborate seamlessly to solve problems. We do so by developing and applying a network model, namely Memenets, where human knowledge and reasoning are combined with machine computation to achieve problem-solving. The development of a Memenet is done in three steps: first, we simulate a machine-only network, as previous results have shown that memenets are efficient problem-solvers. Then, we perform an experiment with human agents organized in a online network. This allows us to investigate human behavior while solving problems in a social network and to postulate principles of agent communication in Memenets. These postulates describe an initial theory of how human-computer interaction functions inside social networks. In the third stage, postulates of step two allow one to combine human and machine computation to propose an integrated Memenet-based problem-solving computing model.
【Keywords】: Social computing; Memetic networks; Satisfiability; Human computation; Knowledge representation; Agents
【Paper Link】 【Pages】:
【Authors】: Shane Griffith ; Alexander Stoytchev
【Abstract】: The ability to form object categories is an important milestone in human infant development. We propose a framework that allows a robot to form a unified object categorization from several interactions with objects. This framework is consistent with the principle that robot learning should be ultimately grounded in the robot's perceptual and behavioral repertoire. This paper builds upon our previous work by adding more exploratory behaviors (now 6 instead of 1) and by employing consensus clustering for finding a single, unified object categorization. The framework was tested on a container/non-container categorization task with 20 objects.
【Keywords】: developmental robotics; object categorization; robots
【Paper Link】 【Pages】:
【Authors】: Yasaman Haghpanah ; Marie desJardins
【Abstract】: Many real-world applications, such as Supply Chain Management (SCM), can be modeled using multi-agent systems. One shortcoming of current SCM models is that their trust models are ad hoc and do not have a strong theoretical basis. We propose a trust model for SCM that is grounded in probabilistic game theory. In this model, trust can be gained through direct interactions, and/or by asking for information from other trustworthy agents. We will use this model to simulate and study supply chain market behavior.
【Keywords】: supply chain management, multi-agent systems, game theory, decision theory, trust, reputation
【Paper Link】 【Pages】:
【Authors】: Amal Chaminda Kaluarachchi ; Aparna S. Varde ; Jing Peng ; Anna Feldman
【Abstract】: This paper describes a system called SITAC based on our proposed approach to discover concepts (called SITACs) in text archives that are identical semantically but alter their names over time. Our approach integrates natural language processing, association rule mining and contextual similarity to discover SITACs in order to answer historical queries over text corpora.
【Keywords】: AR mining, Text Similarity,NLP
【Paper Link】 【Pages】:
【Authors】: Serdar Kecici ; Sanem Sariel Talay
【Abstract】: We consider planning domains with both discrete and continuous changes. Continuous change occurs especially when agents share time-dependent critical resources. In these cases, besides discrete and continuous changes, their interactions should also be taken into consideration. However concurrency of durative actions with interacting continuous effects cannot be exploited by existing temporal planners. To overcome this problem, we propose an action lifting approach and we analyze path sharing problem to illustrate interaction of continuous linear effects in the planning domain.
【Keywords】: temporal planning; continuous change; continuous linear change; path sharing; action lifting;
【Paper Link】 【Pages】:
【Authors】: Scott Kuindersma
【Abstract】: The ability to discover the effects of actions and apply this knowledge during goal-oriented action selection is a fundamental requirement of embodied intelligent agents. In our ongoing work, we hope to demonstrate the utility of learned control models for whole-body mobile manipulation. In this short paper we discuss preliminary work on learning a forward model of the dynamics of a balancing robot exploring simple arm movements. This model is then used to construct whole-body control strategies for regulating state variables using arm motion.
【Keywords】: whole-body control; mobile robotics; motor learning; L1 regularization
【Paper Link】 【Pages】:
【Authors】: Chendong Li
【Abstract】: The hardness of finite domain Constraint Satisfaction Problems (CSPs) is an important research topic in Constraint Programming (CP) community. In this paper, we study the association rule mining techniques together with rule deduction and propose a cascaded approach to extract interesting patterns of hard CSPs with functional constraints. Specifically, we generate random CSPs, collect controlling parameters and hardness characteristics by solving all the CSP instances. Afterwards, we apply association rule mining with rule deduction on the collected data set and further extract interesting patterns of the hardness of the randomly generated CSPs. As far as we know, this problem is investigated with data mining techniques for the first time.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Nan Li ; William W. Cohen ; Kenneth R. Koedinger
【Abstract】: Building an intelligent agent, which simulates human-level learning appropriate for learning math, science, or a second language, could potentially benefit both education in understanding human learning, and artificial intelligence in creating human-level intelligence. Recently, we have proposed an efficient approach to acquiring procedural knowledge using transfer learning. However, it operated as a separate module. In this paper, we describe how to integrate this module into a machine-learning agent, SimStudent, that learns procedural knowledge from examples and through problem solving. We illustrate this method in the domain of algebra, after which we consider directions for future research in this area.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Pei-Pei Li ; Xindong Wu ; Xuegang Hu
【Abstract】: Contrary to the previous beliefs that all arrived streaming data are labeled and the class labels are immediately availa- ble, we propose a Semi-supervised classification algorithm for data streams with concept drifts and UNlabeled data, called SUN. SUN is based on an evolved decision tree. In terms of deviation between history concept clusters and new ones generated by a developed clustering algorithm of k-Modes, concept drifts are distinguished from noise at leaves. Extensive studies on both synthetic and real data demonstrate that SUN performs well compared to several known online algorithms on unlabeled data. A conclusion is hence drawn that a feasible reference framework is provided for tackling concept drifting data streams with unlabeled data.
【Keywords】: Concept Drift; Unlabeled Data; Data Stream
【Paper Link】 【Pages】:
【Authors】: Zhao Li ; Xindong Wu
【Abstract】: Document clustering has been applied in web information retrieval, which facilitates users’ quick browsing by organizing retrieved results into different groups. Meanwhile, a tree-like hierarchical structure is wellsuited for organizing the retrieved results in favor of web users. In this regard, we introduce a new method for hierarchical clustering of web snippets by exploiting a phrase-based document index. In our method, a hierarchy of web snippets is built based on phrases instead of all snippets, and the snippets are then assigned to the corresponding clusters consisting of phrases. We show that, as opposed to the traditional hierarchical clustering, our method not only presents meaningful cluster labels but also improves clustering performance.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: Robert Louis Long ; Ross Mead ; Jerry B. Weinberg
【Abstract】: The field of multi-robot coordination, specifically robot formation control, is rapidly expanding, with many applications proposed. In our previous work, we considered the problem of establishing and maintaining a formation of robots given an already connected network. We now propose a distributed auction-based method to autonomously initialize and reorganize the network structure of a formation of robots.
【Keywords】: Multi-Robot Coordination; Distributed Robotics; Robotics
【Paper Link】 【Pages】:
【Authors】: James P. McGlothlin ; Latifur R. Khan
【Abstract】: There is a growing need for efficient and scalable semantic web queries that handle inference. There is also a growing interest in representing uncertainty in semantic web knowledge bases. In this paper, we present a bit vector schema specifically designed for RDF (Resource Description Framework) datasets. We propose a system for materializing and storing inferred knowledge using this schema. We show experimental results that demonstrate that our solution drastically improves the performance of inference queries. We also propose a solution for materializing uncertain information and probabilities using multiple bit vectors and thresholds.
【Keywords】: semantic web; ontology; uncertainty reasoning; inference; databases; query optimization; resource description framework
【Paper Link】 【Pages】:
【Authors】: Shiwali Mohan ; John E. Laird
【Abstract】: Relational representations in reinforcement learning allow for the use of structural information like the presence of objects and relationships between them in the description of value functions. Through this paper, we show that such representations allow for the inclusion of background knowledge that qualitatively describes a state and can be used to design agents that demonstrate learning behavior in domains with large state and actions spaces such as computer games.
【Keywords】: Reinforcement Learning; Soar; Computer Games; Relational Representation
【Paper Link】 【Pages】:
【Authors】: Scott Niekum
【Abstract】: Reward functions in reinforcement learning have largely been assumed given as part of the problem being solved by the agent. However, the psychological notion of intrinsic motivation has recently inspired inquiry into whether there exist alternate reward functions that enable an agent to learn a task more easily than the natural task-based reward function allows. This paper presents an efficient genetic programming algorithm to search for alternate reward functions that improve agent learning performance.
【Keywords】: intrinsic motivation; reinforcement learning; genetic programming
【Paper Link】 【Pages】:
【Authors】: Robert G. Price ; Scott D. Goodwin
【Abstract】: Forming teams using heterogeneous agents that perform well together to accomplish a task in a game can be a challenging problem. There can often be an enormous amount of combinations to look through, and having an agent that is really good at a particular task is no guarantee that agent will perform well on a team with members with different abilities. Picking a good team is important, as changing teams is often not allowed midway through a task.
【Keywords】: Games; Team Formation; Heterogeneous Agents
【Paper Link】 【Pages】:
【Authors】: Hamid Haidarian Shahri
【Abstract】: In this abstract, we compare semantic search (in the RDF model) with keyword search (in the relational model), and illustrate how these two search paradigms are different. This comparison addresses the following questions: (1) What can semantic search achieve that keyword search can not (in terms of behavior)? (2) Why is it difficult to simulate semantic search, using keyword search on the relational data model? We use the term keyword search, when the search is performed on data stored in the relational data model, as in traditional relational databases, and an example of keyword search in databases is [Hri02]. We use the term semantic search, when the search is performed on data stored in the RDF data model. Note that when the data is modeled in RDF, it inherently contains explicit typed relations or semantics, and hence the use of the term “semantic search.” Let us begin with an example, to illustrate the differences between semantic search and keyword search.
【Keywords】: Semantic Search; Linked Data
【Paper Link】 【Pages】:
【Authors】: Kaushik Subramanian
【Abstract】: In this paper a system was developed for robot behavior acquisition using kinesthetic demonstrations. It enables a humanoid robot to imitate constrained reaching gestures directed towards a target using a learning algorithm based on Gaussian Mixture Models. The imitation trajectory can be reshaped in order to satisfy the constraints of the task and it can adapt to changes in the initial conditions and to target displacements occurring during movement execution. The potential of this method was evaluated using experiments with the Nao, Aldebaran’s humanoid robot.
【Keywords】: Human Robot Interaction, Supervised Learning, Spatial Reasoning
【Paper Link】 【Pages】:
【Authors】: Tansel Uras ; Esra Erdem
【Abstract】: Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.
【Keywords】: planning
【Paper Link】 【Pages】:
【Authors】: Liping Wu ; Vladimir Sukhoy ; Alexander Stoytchev
【Abstract】: To function in human-inhabited environments a robot must be able to press buttons. There are literally thousands of different buttons, which produce various types of feedback when pressed. This work focuses on doorbell buttons, which provide auditory feedback. Our robot learned to predict if a specific pushing movement would press a doorbell button and produce a sound. The robot explored different buttons with random pushing behaviors and perceived the proprioceptive, tactile, and acoustic outcomes of these behaviors.
【Keywords】: Robotics; Manipulation; Exploration; Buttons; Learning from Experience
【Paper Link】 【Pages】:
【Authors】: Shuonan Dong
【Abstract】: Low-level direct commanding of space robots can be time consuming or impractical for complex systems with many degrees of freedom. My research will adaptively raise the level of interaction between the operator and the robot by (1) allowing the robot to learn implicit plans by detecting patterns in the interaction history, and (2) enabling the human to demonstrate continuous motions through teleoperation. Learned tasks and plans are recorded for future use. I introduce a novel representation of continuous actions called parameterized probabilistic flow tubes that I hypothesize will more closely encode a human's intended motions and provide flexibility during execution in new situations. I also introduce the use of planning for plan recognition in the domain of hybrid tasks.
【Keywords】: human-robot interaction; plan learning; plan recognition; action learning; hybrid motions; flow tubes; learning from demonstration
【Paper Link】 【Pages】:
【Authors】: Finale Doshi-Velez
【Abstract】: The objective of my doctoral research is bring together two fields: partially-observable reinforcement learning (PORL) and non-parametric Bayesian statistics (NPB) to address issues of statistical modeling and decision-making in complex, real-world domains.
【Keywords】: nonparametric Bayes; reinforcement learning
【Paper Link】 【Pages】:
【Authors】: Tom Erez
【Abstract】: Reinforcement Learning is a theoretical framework for optimizing the behavior of artificial agents. The notion that behavior in the natural world is in some sense optimal is explored by areas such as biomechanics and physical anthropology. These fields propose a variety of candidate optimality criteria as possible formulations of the principles underlying natural motion. Recent developments in computational biomechanics allow us to create articulated models of living creatures with a significant degree of biological realism. I aim to bring these elements together in my research by using Reinforcement Learning to generate optimized behavior in biomechanical simulations. Such a generative approach will allow us to examine critically postulated optimality criteria and investigate hypotheses that cannot be easily studied in the real world.
【Keywords】: reinforcement learning; biomechanics; optimal control
【Paper Link】 【Pages】:
【Authors】: Pooyan Fazli
【Abstract】: Area coverage is one of the emerging problems in multi-robot coordination. In this task a team of robots is cooperatively trying to observe or sweep an entire area, possibly containing obstacles, with their sensors or actuators. The goal is to build an efficient path for each robot which jointly ensure that every single point in the environment can be seen or swept by at least one of the robots while performing the task.
【Keywords】: Multi-Robot Systems; Teamwork; Coordination; Area Coverage; Offine Coverage; Heterogeneity; Open Systems; Online Coverage; Communication
【Paper Link】 【Pages】:
【Authors】: Lisa Friedland
【Abstract】: The goal of my work is to detect implicit social ties or closely-linked entities within a data set. In data consisting of people (or other entities) and their affiliations or discrete attributes, we identify unusually similar pairs of people, and we pose the question: Can their similarity be explained by chance, or it is due to a direct (“copying”) relationship between the people? The thesis will explore how to assess this question, and in particular how one’s judgments and confidence depend not only on the two people in question but also on properties of the entire data set. I will provide a framework for solving this problem and experiment with it across multiple synthetic and real-world data sets. My approach requires a model of the copying relationship, a model of independent people, and a method for distinguishing between them. I will focus on two aspects of the problem: (1) choosing background models to fit arbitrary, correlated affiliation data, and (2) understanding how the ability to detect copies is affected by factors like data sparsity and the numbers of people and affiliations, independent of the fit of the models.
【Keywords】: social network analysis; link prediction; affiliation network
【Paper Link】 【Pages】:
【Authors】: Sofia Lemons
【Abstract】: My research represents an approach to integrating planning and execution in time-sensitive environments. The primary focus is on a problem called continual on-line planning. New goals arrive stochastically during execution, the agent issues actions for execution one at a time, and the environment is otherwise deterministic. My dissertation will address this setting in three stages: optimizing total goal achievement time, handling on-line goal arrival during planning or execution, and adapting to changes in state also during planning or execution. My current approach to this problem is based on incremental heuristic search. The two central issues are the decision of which partial plans to elaborate during search and the decision of when to issue an action for execution. I have proposed an extension of Russell and Wefald's decision-theoretic A algorithm that is not limited by assumptions of an admissible heuristic like DTA. This algorithm, Decision Theoretic On-line Continual Search (DTOCS), handles the complexities of the on-line setting by balancing deliberative planning and real-time response.
【Keywords】: planning; search; real-time; on-line; heuristic; meta-reasoning
【Paper Link】 【Pages】:
【Authors】: Michelle Denise Leonhardt
【Abstract】: Embodied Conversational Agents (ECAs) are computergenerated characters whose purpose is to exhibit the same properties as humans in face-to-face conversation. The general goal of researchers in the field of ECAs is to create agents that can be more natural, believable and easy to use. In this paper, we are interested in increasing believability of ECAs. Specifically, we are interested in making the intentionality of the agent believable regarding actions and reactions that create the impression of an independent entity with goals and, specially, feelings.
【Keywords】:
【Paper Link】 【Pages】:
【Authors】: James MacGlashan
【Abstract】: I present skill bootstrapping, a proposed new research direction for agent learning and planning that allows an agent to start with low-level primitive actions, and develop skills that can be used for higher-level planning. Skills are developed over the course of solving many different problems in a domain, using reinforcement learning techniques to complement the benefits and disadvantages of heuristic-search planning. I describe the overall architecture of the proposed approach and discuss how it relates to other work.
【Keywords】: planning;learning;abstraction
【Paper Link】 【Pages】:
【Authors】: Mehdi Hafezi Manshadi
【Abstract】: We propose a system that bridges the gap between the two major approaches toward natural language processing: robust shallow text processing and domain-specific (often linguistically-based) deep understanding. We propose to use an existing linguistically motivated deep understanding system as the core and to leverage statistical techniques and external resources such as world knowledge to broaden coverage and increase robustness. We will also develop a semantic representation framework, which supports underspecification, granularity and incrementality, the critical factors of robustness in representing natural language semantics.
【Keywords】: Deep Language Understanding; Robust Language Processing; Semantic Representation
【Paper Link】 【Pages】:
【Authors】: James P. McGlothlin
【Abstract】: There is a growing need for scalable semantic web repositories which support inference and provide efficient queries. There is also a growing interest in representing uncertain knowledge in semantic web datasets and ontologies. In this paper, I present a bit vector schema specifically designed for RDF (Resource Description Framework) datasets. I propose a system for materializing and storing inferred knowledge using this schema. I show experimental results that demonstrate that this solution simplifies inference queries and drastically improves results. I also propose and describe a solution for materializing and persisting uncertain information and probabilities. Thresholds and bit vectors are used to provide efficient query access to this uncertain knowledge. My goal is to provide a semantic web repository that supports knowledge inference, uncertainty reasoning, and Bayesian networks, without sacrificing performance or scalability.
【Keywords】: semantic web; ontology; inference; query optimization; uncertainty reasoning; resource description framework
【Paper Link】 【Pages】:
【Authors】: Megan M. Olsen
【Abstract】: My thesis investigates fault tolerance for cooperative agent systems that have some equivalent of self-replication and self-death. Utilizing biologically-inspired mechanisms, I increase multi-agent system robustness for faulty agents when it is unknown exactly which agent is malfunctioning. It is important to determine new ways to increase robustness of a system, as otherwise it cannot be guaranteed to function in all situations and thus cannot be relied upon. Robustness of a system allows agents to recover from errors and thus function continuously, an increasingly important trait as agent systems are deployed in real world scenarios such as sensor networks or surveillance systems where faulty or malicious nodes could disrupt application performance. To achieve robustness, there must either be prevention of all errors, or a technique for recovering from errors after they have occurred. My thesis creates a new fault tolerance mechanism inspired by cancer biology to remove faulty agents, and then re-applies the developed technique to study the removal of biological cancer cells in simulation.
【Keywords】: multi-agent systems; fault tolerance; biologically inspired computing
【Paper Link】 【Pages】:
【Authors】: Ben George Weber
【Abstract】: A major challenge in the field of AI is combining symbolic and statistical techniques. My dissertation work aims to bridge this gap in the domain of real-time strategy games.
【Keywords】: planning;machine learning;real-time strategy
【Paper Link】 【Pages】:
【Authors】: Christopher Simpkins
【Abstract】: Creating artificial intelligent agents that are high-fidelity simulations of natural agents will require the engagement of behavioral scientists. However, agent programming systems that are accessible to behavioral scientists are too limited to create rich agents, and systems for creating rich agents are accessible mainly to computer scientists, not behavioral scientists. We are solving this problem by engaging behavioral scientists in the design of a programming language, and integrating reinforcement learning into the programming language. This strategy will help our language achieve adaptivity, modularity, and, most importantly, accessibility to behavioral scientists. In addition to allowing behavioral scientist to write rich agent programs, our language — AFABL (A Friendly Behavior Language) — will enable a true discipline of modular agent software engineering with broad implications for games, interactive storytelling, and social simulations.
【Keywords】: Agent Programming;Reinforcement Learning;Programming Languages;Software Engineering
【Paper Link】 【Pages】:
【Authors】: Lirong Xia
【Abstract】: When agents have conflicting preferences over a set of alternatives and they want to make a joint decision, a natural way to do so is by voting. How to design and analyze desirable voting rules has been studied by economists for centuries. In recent decades, technological advances, especially those in internet economy, have introduced many new applications for voting theory. For example, we can rate movies based on people’s preferences, as done on many movie recommendation sites. However, in such new applications, we always encounter a large number of alternatives or an overwhelming amount of information, which makes computation in voting process a big challenge. Such challenges have led to a burgeoning area—computational social choice, aiming to address problems in computational aspects of preference representation and aggregation in a multi-agent scenario. The high-level goal of my research is to better understand and prevent the agents’ (strategic) behavior in voting systems, as well as to design computationally efficient ways for agents to present their preferences and make a joint decision.
【Keywords】: Computational social choice; manipulation; multi-issue domain