bluuebunny/crossref_metadata_2025 huggingface dataset:
Mechanisms for Online Organ Matching
Authors: Mattei Nicholas , Saffidine Abdallah , Walsh Toby
Published: July 2017

Matching donations from deceased patients to patients on the waiting list account for over 85\% of all kidney transplants performed in Australia. We propose a simple mechanisms to perform this matching and compare this new mechanism with the more complex algorithm currently under consideration by the Organ and Tissue Authority in Australia. We perform a number of experiments using real world data provided by the Organ and Tissue Authority of Australia. We find that our simple mechanism is more efficient and fairer in practice compared to the other mechanism currently under consideration.
Deep Multiple Instance Hashing for Object-based Image Retrieval
Authors: Zhao Wanqing , Guan Ziyu , Luo Hangzai , Peng Jinye , Fan Jianping
Published: July 2017

Multi-keyword query is widely supported in text search engines. However, an analogue in image retrieval systems, multi-object query, is rarely studied. Meanwhile, traditional object-based image retrieval methods often involve multiple steps separately and need expensive location labeling for detecting objects. In this work, we propose a weakly-supervised Deep Multiple Instance Hashing (DMIH) framework for object-based image retrieval. DMIH integrates object detection and hashing learning on the basis of a popular CNN model to build the end-to-end relation between a raw image and the binary hashing codes of multiple objects in it. Specifically, we cast the object detection of each object class as a binary multiple instance learning problem where instances are object proposals extracted from multi-scale convolutional feature maps. For hashing training, we sample image pairs to learn their semantic relationships in terms of hash codes of the most probable proposals for owned labels as guided by object predictors. The two objectives benefit each other in learning. DMIH outperforms state-of-the-arts on public benchmarks for object-based image retrieval and achieves promising results for multi-object queries.
Tensor Completion with Side Information: A Riemannian Manifold Approach
Authors: Zhou Tengfei , Qian Hui , Shen Zebang , Zhang Chao , Xu Congfu
Published: July 2017

By restricting the iterate on a nonlinear manifold, the recently proposed Riemannian optimization methods prove to be both efficient and effective in low rank tensor completion problems. However, existing methods fail to exploit the easily accessible side information, due to their format mismatch. Consequently, there is still room for improvement. To fill the gap, in this paper, a novel Riemannian model is proposed to tightly integrate the original model and the side information by overcoming their inconsistency. For this model, an efficient Riemannian conjugate gradient descent solver is devised based on a new metric that captures the curvature of the objective. Numerical experiments suggest that our method is more accurate than the state-of-the-art without compromising the efficiency.
Diverse Neuron Type Selection for Convolutional Neural Networks
Authors: Zhu Guibo , Zhang Zhaoxiang , Zhang Xu-Yao , Liu Cheng-Lin
Published: July 2017

The activation function for neurons is a prominent element in the deep learning architecture for obtaining high performance. Inspired by neuroscience findings, we introduce and define two types of neurons with different activation functions for artificial neural networks: excitatory and inhibitory neurons, which can be adaptively selected by self-learning. Based on the definition of neurons, in the paper we not only unify the mainstream activation functions, but also discuss the complementariness among these types of neurons. In addition, through the cooperation of excitatory and inhibitory neurons, we present a compositional activation function that leads to new state-of-the-art performance comparing to rectifier linear units. Finally, we hope that our framework not only gives a basic unified framework of the existing activation neurons to provide guidance for future design, but also contributes neurobiological explanations which can be treated as a window to bridge the gap between biology and computer science.
Proactive and Reactive Coordination of Non-dedicated Agent Teams Operating in Uncertain Environments
Authors: Agrawal Pritee , Varakantham Pradeep
Published: July 2017

Domains such as disaster rescue, security patrolling etc. often feature dynamic environments where allocations of tasks to agents become ineffective due to unforeseen conditions that may require agents to leave the team. Agents leave the team either due to arrival of high priority tasks (e.g., emergency, accident or violation) or due to some damage to the agent. Existing research in task allocation has only considered fixed number of agents and in some instances arrival of new agents on the team. However, there is little or no literature that considers situations where agents leave the team after task allocation. To that end, we first provide a general model to represent non-dedicated teams. Second, we provide a proactive approach based on sample average approximation to generate a strategy that works well across different feasible scenarios of agents leaving the team. Furthermore, we also provide a 2-stage approach that provides a 2-stage policy that changes allocation based on observed state of the team. Third, we provide a reactive approach that rearranges the allocated tasks to better adapt to leaving agents. Finally, we provide a detailed evaluation of our approaches on existing benchmark problems.
Deterministic, Strategyproof, and Fair Cake Cutting
Authors: Menon Vijay , Larson Kate
Published: July 2017

We study the classic cake cutting problem from a mechanism design perspective, in particular focusing on deterministic mechanisms that are strategyproof and fair. We begin by looking at mechanisms that are non-wasteful and primarily show that for even the restricted class of piecewise constant valuations there exists no direct-revelation mechanism that is strategyproof and even approximately proportional. Subsequently, we remove the non-wasteful constraint and show another impossibility result stating that there is no strategyproof and approximately proportional direct-revelation mechanism that outputs contiguous allocations, again, for even the restricted class of piecewise constant valuations. In addition to the above results, we also present some negative results when considering an approximate notion of strategyproofness, show a connection between direct-revelation mechanisms and mechanisms in the Robertson-Webb model when agents have piecewise constant valuations, and finally also present a (minor) modification to the well-known Even-Paz algorithm that has better incentive-compatible properties for the cases when there are two or three agents.
Cake Cutting: Envy and Truth
Authors: Bei Xiaohui , Chen Ning , Huzhang Guangda , Tao Biaoshuai , Wu Jiajun
Published: July 2017

We study envy-free cake cutting with strategic agents, where each agent may manipulate his private information in order to receive a better allocation. We focus on piecewise constant utility functions and consider two scenarios: the general setting without any restriction on the allocations and the restricted setting where each agent has to receive a connected piece. We show that no deterministic truthful envy-free mechanism exists in the connected piece scenario, and the same impossibility result for the general setting with some additional mild assumptions on the allocations. Finally, we study a large market model where the economy is replicated and demonstrate that truth-telling converges to a Nash equilibrium.
Exploiting Music Play Sequence for Music Recommendation
Authors: Cheng Zhiyong , Shen Jialie , Zhu Lei , Kankanhalli Mohan , Nie Liqiang
Published: July 2017

Users leave digital footprints when interacting with various music streaming services. Music play sequence, which contains rich information about personal music preference and song similarity, has been largely ignored in previous music recommender systems. In this paper, we explore the effects of music play sequence on developing effective personalized music recommender systems. Towards the goal, we propose to use word embedding techniques in music play sequences to estimate the similarity between songs. The learned similarity is then embedded into matrix factorization to boost the latent feature learning and discovery. Furthermore, the proposed method only considers the k-nearest songs (e.g., k = 5) in the learning process and thus avoids the increase of time complexity. Experimental results on two public datasets demonstrate that our methods could significantly improve the performance of both rating prediction and top-n recommendation tasks.
Focused Depth-first Proof Number Search using Convolutional Neural Networks for the Game of Hex
Authors: Gao Chao , Müller Martin , Hayward Ryan
Published: July 2017

Proof Number search (PNS) is an effective algorithm for searching theoretical values on games with non-uniform branching factors. Focused depth-first proof number search (FDFPN) with dynamic widening was proposed for Hex where the branching factor is nearly uniform. However, FDFPN is fragile to its heuristic move ordering function. The recent advances of Convolutional Neural Networks (CNNs) have led to considerable progress in game playing. We investigate how to incorporate the strength of CNNs into solving, with application to the game of Hex. We describe FDFPN-CNN, a new focused DFPN search that uses convolutional neural networks. FDFPN-CNN integrates two CNNs trained from games played by expert players. The value approximation CNN provides reliable information for defining the widening size by estimating the value of the node to expand, while the policy CNN selects promising children nodes to the search. On 8x8 Hex, experimental results show FDFPN-CNN performs notably better than FDFPN, suggesting a promising direction for better solving Hex positions where learning from strong players is possible.
DeepAM: Migrate APIs with Multi-modal Sequence to Sequence Learning
Authors: Gu Xiaodong , Zhang Hongyu , Zhang Dongmei , Kim Sunghun
Published: July 2017

Computer programs written in one language are often required to be ported to other languages to support multiple devices and environments. When programs use language specific APIs (Application Programming Interfaces), it is very challenging to migrate these APIs to the corresponding APIs written in other languages. Existing approaches mine API mappings from projects that have corresponding versions in two languages. They rely on the sparse availability of bilingual projects, thus producing a limited number of API mappings. In this paper, we propose an intelligent system called DeepAM for automatically mining API mappings from a large-scale code corpus without bilingual projects. The key component of DeepAM is based on the multi-modal sequence to sequence learning architecture that aims to learn joint semantic representations of bilingual API sequences from big source code data. Experimental results indicate that DeepAM significantly increases the accuracy of API mappings as well as the number of API mappings when compared with the state-of-the-art approaches.
Playing Repeated Network Interdiction Games with Semi-Bandit Feedback
Authors: Guo Qingyu , An Bo , Tran-Thanh Long
Published: July 2017

We study repeated network interdiction games with no prior knowledge of the adversary and the environment, which can model many real world network security domains. Existing works often require plenty of available information for the defender and neglect the frequent interactions between both players, which are unrealistic and impractical, and thus, are not suitable for our settings. As such, we provide the first defender strategy, that enjoys nice theoretical and practical performance guarantees, by applying the adversarial online learning approach. In particular, we model the repeated network interdiction game with no prior knowledge as an online linear optimization problem, for which a novel and efficient online learning algorithm, SBGA, is proposed, which exploits the unique semi-bandit feedback in network security domains. We prove that SBGA achieves sublinear regret against adaptive adversary, compared with both the best fixed strategy in hindsight and a near optimal adaptive strategy. Extensive experiments also show that SBGA significantly outperforms existing approaches with fast convergence rate.
Game Engine Learning from Video
Authors: Guzdial Matthew , Li Boyang , Riedl Mark O.
Published: July 2017

Intelligent agents need to be able to make predictions about their environment. In this work we present a novel approach to learn a forward simulation model via simple search over pixel input. We make use of a video game, Super Mario Bros., as an initial test of our approach as it represents a physics system that is significantly less complex than reality. We demonstrate the significant improvement of our approach in predicting future states compared with a baseline CNN and apply the learned model to train a game playing agent. Thus we evaluate the algorithm in terms of the accuracy and value of its output model.
Multiple-Profile Prediction-of-Use Games
Authors: Perrault Andrew , Boutilier Craig
Published: July 2017

Prediction-of-use (POU) games (Robu et al., 2017) address the mismatch between energy supplier costs and the incentives imposed on consumers by a fixed-rate electricity tariff. However, the framework does not address how consumers should coordinate to maximize social welfare. To address this, we develop MPOU games, an extension of POU games in which agents report multiple acceptable electricity use profiles. We show that MPOU games share many attractive properties with POU games (e.g., convexity). Despite this, MPOU games introduce new incentive issues that prevent the consequences of convexity from being exploited directly, a problem we analyze and resolve. We validate our approach with experimental results using utility models learned from real electricity use data.
Exploring Personalized Neural Conversational Models
Authors: Kottur Satwik , Wang Xiaoyu , Carvalho Vitor
Published: July 2017

Modeling dialog systems is currently one of the most active problems in Natural Language Processing. Recent advancement in Deep Learning has sparked an interest in the use of neural networks in modeling language, particularly for personalized conversational agents that can retain contextual information during dialog exchanges. This work carefully explores and compares several of the recently proposed neural conversation models, and carries out a detailed evaluation on the multiple factors that can significantly affect predictive performance, such as pretraining, embedding training, data cleaning, diversity reranking, evaluation setting, etc. Based on the tradeoffs of different models, we propose a new generative dialogue model conditioned on speakers as well as context history that outperforms all previous models on both retrieval and generative metrics. Our findings indicate that pretraining speaker embeddings on larger datasets, as well as bootstrapping word and speaker embeddings, can significantly improve performance (up to 3 points in perplexity), and that promoting diversity in using Mutual Information based techniques has a very strong effect in ranking metrics.
Defending Against Man-In-The-Middle Attack in Repeated Games
Authors: Li Shuxin , Li Xiaohong , Hao Jianye , An Bo , Feng Zhiyong , Chen Kangjie , Zhang Chengwei
Published: July 2017

The Man-in-the-Middle (MITM) attack has become widespread in networks nowadays. The MITM attack would cause serious information leakage and result in tremendous loss to users. Previous work applies game theory to analyze the MITM attack-defense problem and computes the optimal defense strategy to minimize the total loss. It assumes that all defenders are cooperative and the attacker know defenders' strategies beforehand. However, each individual defender is rational and may not have the incentive to cooperate. Furthermore, the attacker can hardly know defenders' strategies ahead of schedule in practice. To this end, we assume that all defenders are self-interested and model the MITM attack-defense scenario as a simultaneous-move game. Nash equilibrium is adopted as the solution concept which is proved to be always unique. Given the impracticability of computing Nash equilibrium directly, we propose practical adaptive algorithms for the defenders and the attacker to learn towards the unique Nash equilibrium through repeated interactions. Simulation results show that the algorithms are able to converge to Nash equilibrium strategy efficiently.
How to Keep a Knowledge Base Synchronized with Its Encyclopedia Source
Authors: Liang Jiaqing , Zhang Sheng , Xiao Yanghua
Published: July 2017

Knowledge bases are playing an increasingly important role in many real-world applications.

However, most of these knowledge bases tend to be outdated, which limits the utility of these knowledge bases.

In this paper, we investigate how to keep the freshness of the knowledge base by synchronizing it with its data source (usually encyclopedia websites).

A direct solution is revisiting the whole encyclopedia periodically and rerun the entire pipeline of the construction of knowledge base like most existing methods.

However, this solution is wasteful and incurs massive overload of the network, which limits the update frequency and leads to knowledge obsolescence.

To overcome the weakness, we propose a set of synchronization principles upon which we build an Update System for knowledge Base (USB) with an update frequency predictor of entities as the core component.

We also design a set of effective features and realize the predictor.

We conduct extensive experiments to justify the effectiveness of the proposed system, model, as well as the underlying principles.

Finally, we deploy USB on a Chinese knowledge base to improve its freshness.
Unified Representation and Lifted Sampling for Generative Models of Social Networks
Authors: Robles-Granda Pablo , Moreno Sebastian , Neville Jennifer
Published: July 2017

Statistical models of network structure are widely used in network science to reason about the properties of complex systems—where the nodes and edges represent entities and their relationships. Recently, a number of generative network models (GNM) have been developed that accurately capture characteristics of real world networks, but since they are typically defined in a procedural manner, it is difficult to identify commonalities in their structure. Moreover, procedural definitions make it difficult to develop statistical sampling algorithms that are both efficient and correct. In this paper, we identify a family of GNMs that share a common latent structure and create a Bayesian network (BN) representation that captures their common form. We show how to reduce two existing GNMs to this representation. Then, using the BN representation we develop a generalized, efficient, and provably correct, sampling method that exploits parametric symmetries and deterministic context-specific dependence. Finally, we use the new representation to design a novel GNM and evaluate it empirically.
The Minds of Many: Opponent Modeling in a Stochastic Game
Authors: von der Osten Friedrich Burkhard , Kirley Michael , Miller Tim
Published: July 2017

The Theory of Mind provides a framework for an agent to predict the actions of adversaries by building an abstract model of their strategies using recursive nested beliefs. In this paper, we extend a recently introduced technique for opponent modeling based on Theory of Mind reasoning. Our extended multi-agent Theory of Mind model explicitly considers multiple opponents simultaneously. We introduce a stereotyping mechanism, which segments the agent population into sub-groups of agents with similar behavior. Here, sub-group profiles guide decision making in place of individual agent profiles. We evaluate our model using a multi-player stochastic game, which presents agents with the challenge of unknown adversaries in a partially-observable environment. Simulation results demonstrate that the model performs well under uncertainty and that stereotyping allows larger groups of agents to be modeled robustly. The findings strengthen results showing that Theory of Mind modeling is useful in many artificial intelligence applications.
Predicting Alzheimer's Disease Cognitive Assessment via Robust Low-Rank Structured Sparse Model
Authors: Xu Jie , Deng Cheng , Gao Xinbo , Shen Dinggang , Huang Heng
Published: July 2017

Alzheimer's disease (AD) is a neurodegenerative disorder with slow onset, which could result in the deterioration of the duration of persistent neurological dysfunction. How to identify the informative longitudinal phenotypic neuroimaging markers and predict cognitive measures are crucial to recognize AD at early stage. Many existing models related imaging measures to cognitive status using regression models, but they did not take full consideration of the interaction between cognitive scores. In this paper, we propose a robust low-rank structured sparse regression method (RLSR) to address this issue. The proposed model simultaneously selects effective features and learns the underlying structure between cognitive scores by utilizing novel mixed structured sparsity inducing norms and low-rank approximation. In addition, an efficient algorithm is derived to solve the proposed non-smooth objective function with proved convergence. Empirical studies on cognitive data of the ADNI cohort demonstrate the superior performance of the proposed method.
Optimal Escape Interdiction on Transportation Networks
Authors: Zhang Youzhi , An Bo , Tran-Thanh Long , Wang Zhen , Gan Jiarui , Jennings Nicholas R.
Published: July 2017

Preventing crimes or terrorist attacks in urban areas is challenging. Law enforcement officers need to respond quickly to catch the attacker on his escape route, which is subject to time-dependent traffic conditions on transportation networks. The attacker can strategically choose his escape path and driving speed to avoid being captured. Existing work on security resource allocation has not considered such scenarios with time-dependent strategies for both players. Therefore, in this paper, we study the problem of efficiently scheduling security resources for interdicting the escaping attacker. We propose: 1) a new defender-attacker security game model for escape interdiction on transportation networks; and 2) an efficient double oracle algorithm to compute the optimal defender strategy, which combines mixed-integer linear programming formulations for best response problems and effective approximation algorithms for improving the scalability of the algorithms. Experimental evaluation shows that our approach significantly outperforms baselines in solution quality and scales up to realistic-sized transportation networks with hundreds of intersections.
Why You Should Charge Your Friends for Borrowing Your Stuff
Authors: Shin Kijung , Lee Euiwoong , Eswaran Dhivya , Procaccia Ariel D.
Published: July 2017

We consider goods that can be shared with k-hop neighbors (i.e., the set of nodes within k hops from an owner) on a social network. We examine incentives to buy such a good by devising game-theoretic models where each node decides whether to buy the good or free ride. First, we find that social inefficiency, specifically excessive purchase of the good, occurs in Nash equilibria. Second, the social inefficiency decreases as k increases and thus a good can be shared with more nodes. Third, and most importantly, the social inefficiency can also be significantly reduced by charging free riders an access cost and paying it to owners, leading to the conclusion that organizations and system designers should impose such a cost. These findings are supported by our theoretical analysis in terms of the price of anarchy and the price of stability; and by simulations based on synthetic and real social networks.
Dynamic Compositional Neural Networks over Tree Structure
Authors: Liu Pengfei , Qiu Xipeng , Huang Xuanjing
Published: July 2017

Tree-structured neural networks have proven to be effective in learning semantic representations by exploitingsyntactic information. In spite of their success, most existing models suffer from the underfitting problem: they recursively use the same shared compositional function throughout the whole compositional process and lack expressive power due to inability to capture the richness of compositionality.In this paper, we address this issue by introducing the dynamic compositional neural networks over tree structure (DC-TreeNN), in which the compositional function is dynamically generated by a meta network.The role of meta-network is to capture the metaknowledge across the different compositional rules and formulate them. Experimental results on two typical tasks show the effectiveness of the proposed models.
Interactive Attention Networks for Aspect-Level Sentiment Classification
Authors: Ma Dehong , Li Sujian , Zhang Xiaodong , Wang Houfeng
Published: July 2017

Aspect-level sentiment classification aims at identifying the sentiment polarity of specific target in its context. Previous approaches have realized the importance of targets in sentiment classification and developed various methods with the goal of precisely modeling thier contexts via generating target-specific representations. However, these studies always ignore the separate modeling of targets. In this paper, we argue that both targets and contexts deserve special treatment and need to be learned their own representations via interactive learning. Then, we propose the interactive attention networks (IAN) to interactively learn attentions in the contexts and targets, and generate the representations for targets and contexts separately. With this design, the IAN model can well represent a target and its collocative context, which is helpful to sentiment classification. Experimental results on SemEval 2014 Datasets demonstrate the effectiveness of our model.
Conditional Generative Adversarial Networks for Commonsense Machine Comprehension
Authors: Wang Bingning , Liu Kang , Zhao Jun
Published: July 2017

Recently proposed Story Cloze Test [Mostafazadeh et al., 2016] is a commonsense machine comprehension application to deal with natural language understanding problem. This dataset contains a lot of story tests which require commonsense inference ability. Unfortunately, the training data is almost unsupervised where each context document followed with only one positive sentence that can be inferred from the context. However, in the testing period, we must make inference from two candidate sentences. To tackle this problem, we employ the generative adversarial networks (GANs) to generate fake sentence. We proposed a Conditional GANs in which the generator is conditioned by the context. Our experiments show the advantage of the CGANs in discriminating sentence and achieve state-of-the-art results in commonsense story reading comprehension task compared with previous feature engineering and deep learning methods.
Proportional Rankings
Authors: Skowron Piotr , Lackner Martin , Brill Markus , Peters Dominik , Elkind Edith
Published: July 2017

We extend the principle of proportional representation to rankings: given approval preferences, we aim to generate aggregate rankings so that cohesive groups of voters are represented proportionally in each initial segment of the ranking. Such rankings are desirable in situations where initial segments of different lengths may be relevant, e.g., in recommender systems, for hiring decisions, or for the presentation of competing proposals on a liquid democracy platform. We define what it means for rankings to be proportional, provide bounds for well-known aggregation rules, and experimentally evaluate the performance of these rules.
DDoS Event Forecasting using Twitter Data
Authors: Wang Zhongqing , Zhang Yue
Published: July 2017

Distributed Denial of Service (DDoS) attacks have been significant threats to the Internet. Traditional research in cyber security focuses on detecting emerging DDoS attacks by tracing network package flow. A characteristic of DDoS defense is that rescue time is limited since the launch of attack. More resilient detection and defence models are typically more costly. We aim at predicting the likelihood of DDoS attacks by monitoring relevant text streams in social media, so that the level of defense can be adjusted dynamically for maximizing cost-effect. To our knowledge, this is a novel and challenge research question for DDoS rescue. Because the input of this task is a text stream rather than a document, information should be collected both on the textual content of individual posts. We propose a fine-grained hierarchical stream model to capture semantic information over infinitely long history, and reveal burstiness and trends. Empirical evaluation shows that social text streams are indeed informative for DDoS forecasting, and our proposed hierarchical model is more effective compared to strong baseline text stream models and discrete bag-of-words models.
Improved Neural Machine Translation with Source Syntax
Authors: Wu Shuangzhi , Zhou Ming , Zhang Dongdong
Published: July 2017

Neural Machine Translation (NMT) based on the encoder-decoder architecture has recently achieved the state-of-the-art performance. Researchers have proven that extending word level attention to phrase level attention by incorporating source-side phrase structure can enhance the attention model and achieve promising improvement. However, word dependencies that can be crucial to correctly understand a source sentence are not always in a consecutive fashion (i.e. phrase structure), sometimes they can be in long distance. Phrase structures are not the best way to explicitly model long distance dependencies. In this paper we propose a simple but effective method to incorporate source-side long distance dependencies into NMT. Our method based on dependency trees enriches each source state with global dependency structures, which can better capture the inherent syntactic structure of source sentences. Experiments on Chinese-English and English-Japanese translation tasks show that our proposed method outperforms state-of-the-art SMT and NMT baselines.
A Correlated Topic Model Using Word Embeddings
Authors: Xun Guangxu , Li Yaliang , Zhao Wayne Xin , Gao Jing , Zhang Aidong
Published: July 2017

Conventional correlated topic models are able to capture correlation structure among latent topics by replacing the Dirichlet prior with the logistic normal distribution. Word embeddings have been proven to be able to capture semantic regularities in language. Therefore, the semantic relatedness and correlations between words can be directly calculated in the word embedding space, for example, via cosine values. In this paper, we propose a novel correlated topic model using word embeddings. The proposed model enables us to exploit the additional word-level correlation information in word embeddings and directly model topic correlation in the continuous word embedding space. In the model, words in documents are replaced with meaningful word embeddings, topics are modeled as multivariate Gaussian distributions over the word embeddings and topic correlations are learned among the continuous Gaussian topics. A Gibbs sampling solution with data augmentation is given to perform inference. We evaluate our model on the 20 Newsgroups dataset and the Reuters-21578 dataset qualitatively and quantitatively. The experimental results show the effectiveness of our proposed model.
Learning Conversational Systems that Interleave Task and Non-Task Content
Authors: Yu Zhou , Rudnicky Alexander , Black Alan
Published: July 2017

Task-oriented dialog systems have been applied in various tasks, such as automated personal assistants, customer service providers and tutors. These systems work well when users have clear and explicit intentions that are well-aligned to the systems' capabilities. However, they fail if users intentions are not explicit.To address this shortcoming, we propose a framework to interleave non-task content (i.e.everyday social conversation) into task conversations. When the task content fails, the system can still keep the user engaged with the non-task content. We trained a policy using reinforcement learning algorithms to promote long-turn conversation coherence and consistency, so that the system can have smooth transitions between task and non-task content.To test the effectiveness of the proposed framework, we developed a movie promotion dialog system. Experiments with human users indicate that a system that interleaves social and task content achieves a better task success rate and is also rated as more engaging compared to a pure task-oriented system.
AGRA: An Analysis-Generation-Ranking Framework for Automatic Abbreviation from Paper Titles
Authors: Zhang Jianbing , Sun Yixin , Huang Shujian , Nguyen Cam-Tu , Wang Xiaoliang , Dai Xinyu , Chen Jiajun , Yu Yang
Published: July 2017

People sometimes choose word-like abbreviations to refer to items with a long description. These abbreviations usually come from the descriptive text of the item and are easy to remember and pronounce, while preserving the key idea of the item. Coming up with a nice abbreviation is not an easy job, even for human. Previous assistant naming systems compose names by applying hand-written rules, which may not perform well. In this paper, we propose to view the naming task as an artificial intelligence problem and create a data set in the domain of academic naming. To generate more delicate names, we propose a three-step framework, including description analysis, candidate generation and abbreviation ranking, each of which is parameterized and optimizable. We conduct experiments to compare different settings of our framework with several analysis approaches from different perspectives. Compared to online or baseline systems, our framework could achieve the best results.
Segmenting Chinese Microtext: Joint Informal-Word Detection and Segmentation with Neural Networks
Authors: Zhang Meishan , Fu Guohong , Yu Nan
Published: July 2017

State-of-the-art Chinese word segmentation systems typically exploit supervised modelstrained on a standard manually-annotated corpus,achieving performances over 95% on a similar standard testing corpus.However, the performances may drop significantly when the same models are applied onto Chinese microtext.One major challenge is the issue of informal words in the microtext.Previous studies show that informal word detection can be helpful for microtext processing.In this work, we investigate it under the neural setting, by proposing a joint segmentation model that integrates the detection of informal words simultaneously.In addition, we generate training corpus for the joint model by using existing corpus automatically.Experimental results show that the proposed model is highly effective for segmentation of Chinese microtext.
Automatic Generation of Grounded Visual Questions
Authors: Zhang Shijie , Qu Lizhen , You Shaodi , Yang Zhenglu , Zhang Jiawan
Published: July 2017

In this paper, we propose the first model to be able to generate visually grounded questions with diverse types for a single image. Visual question generation is an emerging topic which aims to ask questions in natural language based on visual input. To the best of our knowledge, it lacks automatic methods to generate meaningful questions with various types for the same visual input.

To circumvent the problem, we propose a model that automatically generates visually grounded questions with varying types. Our model takes as input both images and the captions generated by a dense caption model, samples the most probable question types, and generates the questions in sequel. The experimental results on two real world datasets show that our model outperforms the strongest baseline in terms of both correctness and diversity with a wide margin.
Reduction Techniques for Model Checking and Learning in MDPs
Authors: Bharadwaj Suda , Le Roux Stephane , Perez Guillermo , Topcu Ufuk
Published: July 2017

Omega-regular objectives in Markov decision processes (MDPs) reduce to reachability: find a policy which maximizes the probability of reaching a target set of states. Given an MDP, an initial distribution, and a target set of states, such a policy can be computed by most probabilistic model checking tools. If the MDP is only partially specified, i.e., some prob- abilities are unknown, then model-learning techniques can be used to statistically approximate the probabilities and enable the computation of the de- sired policy. For fully specified MDPs, reducing the size of the MDP translates into faster model checking; for partially specified MDPs, into faster learning. We provide reduction techniques that al- low us to remove irrelevant transition probabilities: transition probabilities (known, or to be learned) that do not influence the maximal reachability probability. Among other applications, these reductions can be seen as a pre-processing of MDPs before model checking or as a way to reduce the number of experiments required to obtain a good approximation of an unknown MDP.
Beyond Forks: Finding and Ranking Star Factorings for Decoupled Search
Authors: Gnad Daniel , Poser Valerie , Hoffmann Jörg
Published: July 2017

Star-topology decoupling is a recent search reduction method for forward state space search. The idea basically is to automatically identify a star factoring, then search only over the center component in the star, avoiding interleavings across leaf components. The framework can handle complex star topologies, yet prior work on decoupled search considered only factoring strategies identifying fork and inverted-fork topologies. Here, we introduce factoring strategies able to detect general star topologies, thereby extending the reach of decoupled search to new factorings and to new domains, sometimes resulting in significant performance improvements. Furthermore, we introduce a predictive portfolio method that reliably selects the most suitable factoring for a given planning task, leading to superior overall performance.
Softpressure: A Schedule-Driven Backpressure Algorithm for Coping with Network Congestion
Authors: Hu Hsu-Chieh , Smith Stephen F.
Published: July 2017

We consider the problem of minimizing the the delay of jobs moving through a directed graph of service nodes. In this problem, each node may have several links and is constrained to serve one link at a time. As jobs move through the network, they can pass through a node only after they have been serviced by that node. The objective is to minimize the delay jobs incur sitting on queues waiting to be serviced. Two popular approaches to this problem are backpressure algorithm and schedule-driven control. In this paper, we present a hybrid approach of those two methods that incorporates the stability of queuing theory into the schedule-driven control. We then demonstrate how this hybrid method outperforms the other two in a real-time traffic signal control problem, where the nodes are traffic lights, the links are roads, and the jobs are vehicles. We show through simulations that, in scenarios with heavy congestion, the hybrid method results in 50% and 15% reductions in delay over schedule-driven control and backpressure respectively. A theoretical analysis also justifies our results.
Switched Linear Multi-Robot Navigation Using Hierarchical Model Predictive Control
Authors: Huang Chao , Chen Xin , Zhang Yifan , Qin Shengchao , Zeng Yifeng , Li Xuandong
Published: July 2017

Multi-robot navigation control in the absence of reference trajectory is rather challenging as it is expected to ensure stability and feasibility while still offer fast computation on control decisions. The intrinsic high complexity of switched linear dynamical robots makes the problem even more challenging. In this paper, we propose a novel HMPC based method to address the navigation problem of multiple robots with switched linear dynamics. We develop a new technique to compute the reachable sets of switched linear systems and use them to enable the parallel computation of control parameters. We present theoretical results on stability, feasibility and complexity of the proposed approach, and demonstrate its empirical advance in performance against other approaches.
Numeric Planning via Abstraction and Policy Guided Search
Authors: Illanes León , McIlraith Sheila A.
Published: July 2017

The real-world application of planning techniques often requires models with numeric fluents. However, these fluents are not directly supported by most planners and heuristics. We describe a family of planning algorithms that takes a numeric planning problem and produces an abstracted representation that can be solved using any classical planner. The resulting abstract plan is generalized into a policy and then used to guide the search in the original numeric domain. We prove that our approach is sound, and we evaluate it on a set of standard benchmarks. We show that it can provide competitive performance when compared to other well-known algorithms for numeric planning, and a significant performance improvement in certain domains.
Equi-Reward Utility Maximizing Design in Stochastic Environments
Authors: Keren Sarah , Pineda Luis , Gal Avigdor , Karpas Erez , Zilberstein Shlomo
Published: July 2017

We present the Equi Reward Utility Maximizing Design (ER-UMD) problem for redesigning stochastic environments to maximize agent performance. ER-UMD fits well contemporary applications that require offline design of environments where robots and humans act and cooperate. To find an optimal modification sequence we present two novel solution techniques: a compilation that embeds design into a planning problem, allowing use of off-the-shelf solvers to find a solution, and a heuristic search in the modifications space, for which we present an admissible heuristic. Evaluation shows the feasibility of the approach using standard benchmarks from the probabilistic planning competition and a benchmark we created for a vacuum cleaning robot setting.
Integrating Answer Set Programming with Semantic Dictionaries for Robot Task Planning
Authors: Lu Dongcai , Zhou Yi , Wu Feng , Zhang Zhao , Chen Xiaoping
Published: July 2017

In this paper, we propose a novel integrated task planning system for service robot in domestic domains. Given open-ended high-level user instructions in natural language, robots need to generate a plan, i.e., a sequence of low-level executable actions, to complete the required tasks. To address this, we exploit the knowledge on semantic roles of common verbs defined in semantic dictionaries such as FrameNet and integrate it with Answer Set Programming --- a task planning framework with both representation language and solvers. In the experiments, we evaluated our approach using common benchmarks on service tasks and showed that it can successfully handle much more tasks than the state-of-the-art solution. Notably, we deployed the proposed planning system on our service robot for the annual RoboCup@Home competitions and achieved very encouraging results.
Lossy Compression of Pattern Databases Using Acyclic Random Hypergraphs
Authors: Sadeqi Mehdi , Hamilton Howard J.
Published: July 2017

A domain-independent heuristic function created by an abstraction is usually implemented using a Pattern Database (PDB), which is a lookup table of (abstract state, heuristic value) pairs. PDBs containing high quality heuristic values generally require substantial memory space and therefore need to be compressed. In this paper, we introduce Acyclic Random Hypergraph Compression (ARHC), a domain-independent approach to compressing PDBs using acyclic random r-partite r-uniform hypergraphs. The ARHC algorithm, which comes in Base and Extended versions, provides fast lookup and a high compression rate. ARHC-Extended achieves higher quality heuristics than ARHC-Base by decreasing the heuristic information loss at the cost of some decrease in the compression rate. ARHC shows higher performance than level-by-level Bloom filter PDB compression in all experiments conducted so far.
Efficient, Safe, and Probably Approximately Complete Learning of Action Models
Authors: Stern Roni , Juba Brendan
Published: July 2017

In this paper we explore the theoretical boundaries of planning in a setting where no model of the agent's actions is given. Instead of an action model, a set of successfully executed plans are given and the task is to generate a plan that is safe, i.e., guaranteed to achieve the goal without failing.

To this end, we show how to learn a conservative model of the world

in which actions are guaranteed to be applicable.

This conservative model is then given to an off-the-shelf classical planner,

resulting in a plan that is guaranteed to achieve the goal.

However, this reduction from a model-free planning to a

model-based planning is not complete: in some cases

a plan will not be found even when such exists.

We analyze the relation between the number of observed plans

and the likelihood that our conservative approach will indeed fail to solve a solvable problem. Our analysis show that the number of trajectories needed scales gracefully.
From Qualitative to Quantitative Dominance Pruning for Optimal Planning
Authors: Torralba Álvaro
Published: July 2017

Dominance relations compare states to determine whether one is at least as good as another in terms of their goal distance. We generalize these qualitative yes/no relations to functions that measure by how much a state is better than another. This allows us to distinguish cases where the state is strictly closer to the goal. Moreover, we may obtain a bound on the difference in goal distance between two states even if there is no qualitative dominance.We analyze the multiple advantages that quantitative dominance has, like discovering coarser dominance relations, or trading dominance by g-value. Moreover, quantitative dominance can also be used to prove that an action starts an optimal plan from a given state. We introduce a novel action selection pruning that uses this to prune any other successor. Results show that quantitative dominance pruning greatly reduces the search space, significantly increasing the planners' performance.
Heuristic Online Goal Recognition in Continuous Domains
Authors: Vered Mor , Kaminka Gal A.
Published: July 2017

Goal recognition is the problem of inferring the goal of an agent, based on its observed actions. An inspiring approach—plan recognition by planning

(PRP)—uses off-the-shelf planners to dynamically generate plans for given goals, eliminating the need for the traditional plan library. However, existing PRP formulation is inherently inefficient in online recognition, and cannot be used with motion planners for continuous spaces. In this paper, we utilize a different PRP formulation which allows for online goal recognition, and for application in continuous spaces. We present an online recognition algorithm, where two heuristic decision points may be used to improve run-time significantly over existing work. We specify heuristics for continuous domains, prove guarantees on their use, and empirically evaluate the algorithm over hundreds of experiments in both a 3D navigational environment and a cooperative robotic team task.