bluuebunny/crossref_metadata_2025 huggingface dataset:
Comparing Strategic Secrecy and Stackelberg Commitment in Security Games
Authors: Guo Qingyu , An Bo , Bošanský Branislav , Kiekintveld Christopher
Published: July 2017

The Strong Stackelberg Equilibrium (SSE) has drawn extensive attention recently in several security domains. However, the SSE concept neglects the advantage of defender's strategic revelation of her private information, and overestimates the observation ability of the adversaries. In this paper, we overcome these restrictions and analyze the tradeoff between strategic secrecy and commitment in security games. We propose a Disguised-resource Security Game (DSG) where the defender strategically disguises some of her resources. We compare strategic information revelation with public commitment and formally show that they have different advantages depending the payoff structure. To compute the Perfect Bayesian Equilibrium (PBE), several novel approaches are provided, including a novel algorithm based on support set enumeration, and an approximation algorithm for \epsilon-PBE. Extensive experimental evaluation shows that both strategic secrecy and Stackelberg commitment are critical measures in security domain, and our approaches can efficiently solve PBEs for realistic-sized problems.
Who to Invite Next? Predicting Invitees of Social Groups
Authors: Han Yu , Tang Jie
Published: July 2017

Social instant messaging services (SMS) such as WhatsApp, Snapchat and WeChat, have significantly changed the way people work, live, and communicate, attracting increasing attention from multiple disciplinary including computer science, sociology, psychology, and physics. In SMS, social groups play a very important role in supporting communication among multiple users. An interesting question arises: what are the dynamic mechanisms underlying the group evolution? Or more specifically, in an existing group, who should be invited to join? In this paper, we formalize a novel problem of predicting potential invitees of groups.

Employing WeChat, the largest social messaging service in China, as the source for our experimental data, we develop a probabilistic graph model to capture the fundamental factors that determine the probability of a user to be invited to a specific social group. Our results show that the proposed model indeed lead to statistically significant prediction improvements over several state-of-the-art baseline methods.
Fashion Style Generator
Authors: Jiang Shuhui , Fu Yun
Published: July 2017

In this paper, we focus on a new problem: applying artificial intelligence to automatically generate fashion style images. Given a basic clothing image and a fashion style image (e.g., leopard print), we generate a clothing image with the certain style in real time with a neural fashion style generator. Fashion style generation is related to recent artistic style transfer works, but has its own challenges. The synthetic image should preserve the similar design as the basic clothing, and meanwhile blend the new style pattern on the clothing. Neither existing global nor patch based neural style transfer methods could well solve these challenges. In this paper, we propose an end-to-end feed-forward neural network which consists of a fashion style generator and a discriminator. The global and patch based style and content losses calculated by the discriminator alternatively back-propagate the generator network and optimize it. The global optimization stage preserves the clothing form and design and the local optimization stage preserves the detailed style pattern. Extensive experiments show that our method outperforms the state-of-the-arts.
Tactics of Adversarial Attack on Deep Reinforcement Learning Agents
Authors: Lin Yen-Chen , Hong Zhang-Wei , Liao Yuan-Hong , Shih Meng-Li , Liu Ming-Yu , Sun Min
Published: July 2017

We introduce two tactics, namely the strategically-timed attack and the enchanting attack, to attack reinforcement learning agents trained by deep reinforcement learning algorithms using adversarial examples. In the strategically-timed attack, the adversary aims at minimizing the agent's reward by only attacking the agent at a small subset of time steps in an episode. Limiting the attack activity to this subset helps prevent detection of the attack by the agent. We propose a novel method to determine when an adversarial example should be crafted and applied. In the enchanting attack, the adversary aims at luring the agent to a designated target state. This is achieved by combining a generative model and a planning algorithm: while the generative model predicts the future states, the planning algorithm generates a preferred sequence of actions for luring the agent. A sequence of adversarial examples is then crafted to lure the agent to take the preferred sequence of actions. We apply the proposed tactics to the agents trained by the state-of-the-art deep reinforcement learning algorithm including DQN and A3C. In 5 Atari games, our strategically-timed attack reduces as much reward as the uniform attack (i.e., attacking at every time step) does by attacking the agent 4 times less often. Our enchanting attack lures the agent toward designated target states with a more than 70% success rate. Example videos are available at http://yclin.me/adversarial_attack_RL/.
Staying Ahead of the Game: Adaptive Robust Optimization for Dynamic Allocation of Threat Screening Resources
Authors: Mc Carthy Sara Marie , Vayanos Phebe , Tambe Milind
Published: July 2017

We consider the problem of dynamically allocating screening resources of different efficacies (e.g., magnetic or X-ray imaging) at checkpoints (e.g., at airports or ports) to successfully avert an attack by one of the screenees. Previously, the Threat Screening Game model was introduced to address this problem under the assumption that screenee arrival times are perfectly known. In reality, arrival times are uncertain, which severely impedes the implementability and performance of this approach. We thus propose a novel framework for dynamic allocation of threat screening resources that explicitly accounts for uncertainty in the screenee arrival times. We model the problem as a multistage robust optimization problem and propose a tractable solution approach using compact linear decision rules combined with robust reformulation and constraint randomization. We perform extensive numerical experiments which showcase that our approach outperforms (a) exact solution methods in terms of tractability, while incurring only a very minor loss in optimality, and (b) methods that ignore uncertainty in terms of both feasibility and optimality.
Thwarting Vote Buying Through Decoy Ballots
Authors: Parkes David C. , Tylkin Paul , Xia Lirong
Published: July 2017

There is increasing interest in promoting participatory democracy, in particular by allowing voting by mail or internet and through random-sample elections. A pernicious concern, though, is that of vote buying, which occurs when a bad actor seeks to buy ballots, paying someone to vote against their own intent. This becomes possible whenever a voter is able to sell evidence of which way she voted. We show how to thwart vote buying through decoy ballots, which are not counted but are indistinguishable from real ballots to a buyer. We show that an Election Authority can significantly reduce the power of vote buying through a small number of optimally distributed decoys, and model societal processes by which decoys could be distributed.
Interactive Narrative Personalization with Deep Reinforcement Learning
Authors: Wang Pengcheng , Rowe Jonathan , Min Wookhee , Mott Bradford , Lester James
Published: July 2017

Data-driven techniques for interactive narrative generation are the subject of growing interest. Reinforcement learning (RL) offers significant potential for devising data-driven interactive narrative generators that tailor players’ story experiences by inducing policies from player interaction logs. A key open question in RL-based interactive narrative generation is how to model complex player interaction patterns to learn effective policies. In this paper we present a deep RL-based interactive narrative generation framework that leverages synthetic data produced by a bipartite simulated player model. Specifically, the framework involves training a set of Q-networks to control adaptable narrative event sequences with long short-term memory network-based simulated players. We investigate the deep RL framework’s performance with an educational interactive narrative, Crystal Island. Results suggest that the deep RL-based narrative generation framework yields effective personalized interactive narratives.
Predicting the Quality of Short Narratives from Social Media
Authors: Wang Tong , Chen Ping , Li Boyang
Published: July 2017

An important and difficult challenge in building computational models for narratives is the automatic evaluation of narrative quality. Quality evaluation connects narrative understanding and generation as generation systems need to evaluate their own products. To circumvent difficulties in acquiring annotations, we employ upvotes in social media as an approximate measure for story quality. We collected 54,484 answers from a crowd-powered question-and-answer website, Quora, and then used active learning to build a classifier that labeled 28,320 answers as stories. To predict the number of upvotes without the use of social network features, we create neural networks that model textual regions and the interdependence among regions, which serve as strong benchmarks for future research. To our best knowledge, this is the first large-scale study for automatic evaluation of narrative quality.
Efficient Private ERM for Smooth Objectives
Authors: Zhang Jiaqi , Zheng Kai , Mou Wenlong , Wang Liwei
Published: July 2017

In this paper, we consider efficient differentially private empirical risk minimization from the viewpoint of optimization algorithms. For strongly convex and smooth objectives, we prove that gradient descent with output perturbation not only achieves nearly optimal utility, but also significantly improves the running time of previous state-of-the-art private optimization algorithms, for both $\epsilon$-DP and $(\epsilon, \delta)$-DP. For non-convex but smooth objectives, we propose an RRPSGD (Random Round Private Stochastic Gradient Descent) algorithm, which provably converges to a stationary point with privacy guarantee. Besides the expected utility bounds, we also provide guarantees in high probability form. Experiments demonstrate that our algorithm consistently outperforms existing method in both utility and running time.
Efficient Label Contamination Attacks Against Black-Box Learning Models
Authors: Zhao Mengchen , An Bo , Gao Wei , Zhang Teng
Published: July 2017

Label contamination attack (LCA) is an important type of data poisoning attack where an attacker manipulates the labels of training data to make the learned model beneficial to him. Existing work on LCA assumes that the attacker has full knowledge of the victim learning model, whereas the victim model is usually a black-box to the attacker. In this paper, we develop a Projected Gradient Ascent (PGA) algorithm to compute LCAs on a family of empirical risk minimizations and show that an attack on one victim model can also be effective on other victim models. This makes it possible that the attacker designs an attack against a substitute model and transfers it to a black-box victim model. Based on the observation of the transferability, we develop a defense algorithm to identify the data points that are most likely to be attacked. Empirical studies show that PGA significantly outperforms existing baselines and linear learning models are better substitute models than nonlinear ones.
A Group-Based Personalized Model for Image Privacy Classification and Labeling
Authors: Zhong Haoti , Squicciarini Anna , Miller David , Caragea Cornelia
Published: July 2017

We address machine prediction of an individual's label (private or public) for a given image. This problem is difficult due to user subjectivity and inadequate labeled examples to train individual, personalized models. It is also time and space consuming to train a classifier for each user.

We propose a Group-Based Personalized Model for image privacy classification in online social media sites, which learns a set of archetypical privacy models (groups), and associates a given user with one of these groups. Our system can be used to provide accurate ``early warnings'' with respect to a user's privacy awareness level.
Effective Deep Memory Networks for Distant Supervised Relation Extraction
Authors: Feng Xiaocheng , Guo Jiang , Qin Bing , Liu Ting , Liu Yongjie
Published: July 2017

Distant supervised relation extraction (RE) has been an effective way of finding novel relational facts from text without labeled training data. Typically it can be formalized as a multi-instance multi-label problem.In this paper, we introduce a novel neural approach for distant supervised (RE) with specific focus on attention mechanisms.Unlike the feature-based logistic regression model and compositional neural models such as CNN, our approach includes two major attention-based memory components, which is capable of explicitly capturing the importance of each context word for modeling the representation of the entity pair, as well as the intrinsic dependencies between relations.Such importance degree and dependency relationship are calculated with multiple computational layers, each of which is a neural attention model over an external memory. Experiment on real-world datasets shows that our approach performs significantly and consistently better than various baselines.
Understanding and Exploiting Language Diversity
Authors: Giunchiglia Fausto , Batsuren Khuyagbaatar , Bella Gabor
Published: July 2017

The main goal of this paper is to describe a general approach to the problem of understanding linguistic phenomena, as they appear in lexical semantics, through the analysis of large scale resources, while exploiting these results to improve the quality of the resources themselves. The main contributions are: the approach itself, a formal quantitative measure of language diversity; a set of formal quantitative measures of resource incompleteness and a large scale resource, called the Universal Knowledge Core (UKC) built following the methodology proposed. As a concrete example of an application, we provide an algorithm for distinguishing polysemes from homonyms, as stored in the UKC.
How Unlabeled Web Videos Help Complex Event Detection?
Authors: Liu Huan , Zheng Qinghua , Luo Minnan , Zhang Dingwen , Chang Xiaojun , Deng Cheng
Published: July 2017

The lack of labeled exemplars is an important factor that makes the task of multimedia event detection (MED) complicated and challenging. Utilizing artificially picked and labeled external sources is an effective way to enhance the performance of MED. However, building these data usually requires professional human annotators, and the procedure is too time-consuming and costly to scale. In this paper, we propose a new robust dictionary learning framework for complex event detection, which is able to handle both labeled and easy-to-get unlabeled web videos by sharing the same dictionary. By employing the lq-norm based loss jointly with the structured sparsity based regularization, our model shows strong robustness against the substantial noisy and outlier videos from open source. We exploit an effective optimization algorithm to solve the proposed highly non-smooth and non-convex problem. Extensive experiment results over standard datasets of TRECVID MEDTest 2013 and TRECVID MEDTest 2014 demonstrate the effectiveness and superiority of the proposed framework on complex event detection.
Adaptive Semantic Compositionality for Sentence Modelling
Authors: Liu Pengfei , Qiu Xipeng , Huang Xuanjing
Published: July 2017

Representing a sentence with a fixed vector has shown its effectiveness in various NLP tasks. Most of the existing methods are based on neural network, which recursively apply different composition functions to a sequence of word vectors thereby obtaining a sentence vector.A hypothesis behind these approaches is that the meaning of any phrase can be composed of the meanings of its constituents.However, many phrases, such as idioms, are apparently non-compositional.To address this problem, we introduce a parameterized compositional switch, which outputs a scalar to adaptively determine whether the meaning of a phrase should be composed of its two constituents.We evaluate our model on five datasets of sentiment classification and demonstrate its efficacy with qualitative and quantitative experimental analysis .
A Variational Autoencoding Approach for Inducing Cross-lingual Word Embeddings
Authors: Wei Liangchen , Deng Zhi-Hong
Published: July 2017

Cross-language learning allows one to use training data from one language to build models for another language. Many traditional approaches require word-level alignment sentences from parallel corpora, in this paper we define a general bilingual training objective function requiring sentence level parallel corpus only. We propose a variational autoencoding approach for training bilingual word embeddings. The variational model introduces a continuous latent variable to explicitly model the underlying semantics of the parallel sentence pairs and to guide the generation of the sentence pairs. Our model restricts the bilingual word embeddings to represent words in exactly the same continuous vector space. Empirical results on the task of cross lingual document classification has shown that our method is effective.
Lexical Sememe Prediction via Word Embeddings and Matrix Factorization
Authors: Xie Ruobing , Yuan Xingchi , Liu Zhiyuan , Sun Maosong
Published: July 2017

Sememes are defined as the minimum semantic units of human languages. People have manually annotated lexical sememes for words and form linguistic knowledge bases. However, manual construction is time-consuming and labor-intensive, with significant annotation inconsistency and noise. In this paper, we for the first time explore to automatically predict lexical sememes based on semantic meanings of words encoded by word embeddings. Moreover, we apply matrix factorization to learn semantic relations between sememes and words. In experiments, we take a real-world sememe knowledge base HowNet for training and evaluation, and the results reveal the effectiveness of our method for lexical sememe prediction. Our method will be of great use for annotation verification of existing noisy sememe knowledge bases and annotation suggestion of new words and phrases.
Entity Suggestion with Conceptual Expanation
Authors: Zhang Yi , Xiao Yanghua , Hwang Seung-won , Wang Haixun , Wang X. Sean , Wang Wei
Published: July 2017

Entity Suggestion with Conceptual Explanation (ESC) refers to a type of entity acquisition query in which a user provides a set of example entities as the query and obtains in return not only some related entities but also concepts which can best explain the query and the result. ESC is useful in many applications such as related-entity recommendation and query expansion. Many example based entity suggestion solutions are available in existing literatures. However, they are generally not aware of the concepts of query entities thus cannot be used for conceptual explanation. In this paper, we propose two probabilistic entity suggestion models and their computation solutions. Our models and solutions fully take advantage of the large scale taxonomies which consist of isA relations between entities and concepts. With our models and solutions, we can not only find the best entities to suggest but also derive the best concepts to explain the suggestion. Extensive evaluations on real data sets justify the accuracy of our models and the efficiency of our solutions.
Maximum Expected Likelihood Estimation for Zero-resource Neural Machine Translation
Authors: Zheng Hao , Cheng Yong , Liu Yang
Published: July 2017

While neural machine translation (NMT) has made remarkable progress in translating a handful of high-resource language pairs recently, parallel corpora are not always available for many zero-resource language pairs. To deal with this problem, we propose an approach to zero-resource NMT via maximum expected likelihood estimation. The basic idea is to maximize the expectation with respect to a pivot-to-source translation model for the intended source-to-target model on a pivot-target parallel corpus. To approximate the expectation, we propose two methods to connect the pivot-to-source and source-to-target models. Experiments on two zero-resource language pairs show that the proposed approach yields substantial gains over baseline methods. We also observe that when trained jointly with the source-to-target model, the pivot-to-source translation model also obtains improvements over independent training.
On the Power and Limitations of Deception in Multi-Robot Adversarial Patrolling
Authors: Talmor Noga , Agmon Noa
Published: July 2017

Multi-robot adversarial patrolling is a well studied problem, investigating how defenders can optimally use all given resources for maximizing the probability of detecting penetrations, that are controlled by an adversary. It is commonly assumed that the adversary in this problem is rational, thus uses the knowledge it has on the patrolling robots (namely, the number of robots, their location, characteristics and strategy) to optimize its own chances to penetrate successfully. In this paper we present a novel defending approach which manipulates the adversarial (possibly partial) knowledge on the patrolling robots, so that it will believe the robots have more power than they actually have. We describe two different ways of deceiving the adversary: Window Deception, in which it is assumed that the adversary has partial observability of the perimeter, and Scarecrow Deception, in which some of the patrolling robots only appear as real robots, though they have no ability to actually detect the adversary. We analyze the limitations of both models, and suggest a random-based approach for optimally deceiving the adversary that considers both the resources of the defenders, and the adversarial knowledge.
Deceptive Path-Planning
Authors: Masters Peta , Sardina Sebastian
Published: July 2017

Deceptive path-planning involves finding a path such that the probability of an observer identifying the path's final destination - before it has been reached - is minimised. This paper formalises deception as it applies to path-planning and introduces the notion of a last deceptive point (LDP) which, when measured in terms of 'path completion', can be used to rank paths by their potential to deceive. Building on recent developments in probabilistic goal-recognition, we propose a formula to calculate an optimal LDP and present strategies for the generation of deceptive paths by both simulation ('showing the false') and dissimulation ('hiding the real').
Fast Preprocessing for Robust Face Sketch Synthesis
Authors: Song Yibing , Zhang Jiawei , Bao Linchao , Yang Qingxiong
Published: July 2017

Exemplar-based face sketch synthesis methods usually meet the challenging problem that input photos are captured in different lighting conditions from training photos. The critical step causing the failure is the search of similar patch candidates for an input photo patch. Conventional illumination invariant patch distances are adopted rather than directly relying on pixel intensity difference, but they will fail when local contrast within a patch changes. In this paper, we propose a fast preprocessing method named Bidirectional Luminance Remapping (BLR), which interactively adjust the lighting of training and input photos. Our method can be directly integrated into state-of-the-art exemplar-based methods to improve their robustness with ignorable computational cost
Fair and Efficient Social Choice in Dynamic Settings
Authors: Freeman Rupert , Zahedi Seyed Majid , Conitzer Vincent
Published: July 2017

We study a dynamic social choice problem in which an alternative is chosen at each round according to the reported valuations of a set of agents. In the interests of obtaining a solution that is both efficient and fair, we aim to maximize the long-term Nash social welfare, which is the product of all agents' utilities. We present and analyze two greedy algorithms for this problem, including the classic Proportional Fair (PF) algorithm. We analyze several versions of the algorithms and how they relate, and provide an axiomatization of PF. Finally, we evaluate the algorithms on data gathered from a computer systems application.
Incremental Decision Making Under Risk with the Weighted Expected Utility Model
Authors: Gilbert Hugo , Benabbou Nawal , Perny Patrice , Spanjaard Olivier , Viappiani Paolo
Published: July 2017

This paper deals with decision making under risk with the Weighted Expected Utility (WEU) model, which is a model generalizing expected utility and providing stronger descriptive possibilities. We address the problem of identifying, within a given set of lotteries, a (near-)optimal solution for a given decision maker consistent with the WEU theory. The WEU model is parameterized by two real-valued functions. We propose here a new incremental elicitation procedure to progressively reduce the imprecision about these functions until a robust decision can be made. We also give experimental results showing the practical efficiency of our method.
Order Statistics for Probabilistic Graphical Models
Authors: Smith David , Rouhani Sara , Gogate Vibhav
Published: July 2017

We consider the problem of computing r-th order statistics, namely finding an assignment having rank r in a probabilistic graphical model. We show that the problem is NP-hard even when the graphical model has no edges (zero-treewidth models) via a reduction from the partition problem. We use this reduction, specifically a pseudo-polynomial time algorithm for number partitioning to yield a pseudo-polynomial time approximation algorithm for solving the r-th order statistics problem in zero- treewidth models. We then extend this algorithm to arbitrary graphical models by generalizing it to tree decompositions, and demonstrate via experimental evaluation on various datasets that our proposed algorithm is more accurate than sampling algorithms.
Approximating Discrete Probability Distribution of Image Emotions by Multi-Modal Features Fusion
Authors: Zhao Sicheng , Ding Guiguang , Gao Yue , Han Jungong
Published: July 2017

Existing works on image emotion recognition mainly assigned the dominant emotion category or average dimension values to an image based on the assumption that viewers can reach a consensus on the emotion of images. However, the image emotions perceived by viewers are subjective by nature and highly related to the personal and situational factors. On the other hand, image emotions can be conveyed by different features, such as semantics and aesthetics. In this paper, we propose a novel machine learning approach that formulates the categorical image emotions as a discrete probability distribution (DPD). To associate emotions with the extracted visual features, we present a weighted multi-modal shared sparse leaning to learn the combination coefficients, with which the DPD of an unseen image can be predicted by linearly integrating the DPDs of the training images. The representation abilities of different modalities are jointly explored and the optimal weight of each modality is automatically learned. Extensive experiments on three datasets verify the superiority of the proposed method, as compared to the state-of-the-art.
Plato's Cave in the Dempster-Shafer land--the Link between Pignistic and Plausibility Transformations
Authors: Zhou Chunlai , Qin Biao , Du Xiaoyong
Published: July 2017

In reasoning under uncertainty in AI, there are (at least) two useful and different ways of understanding beliefs: the first is as absolute belief or degree of belief in propositions and the second is as belief update or measure of change in belief. Pignistic and plausibility transformations are two well-known probability transformations that map belief functions to probability functions in the Dempster-Shafer theory of evidence. In this paper, we establish the link between pignistic and plausibility transformations by devising a belief-update framework for belief functions where plausibility transformation works on belief update while pignistic transformation operates on absolute belief. In this framework, we define a new belief-update operator connecting the two transformations, and interpret the framework in a belief-function model of parametric statistical inference. As a metaphor, these two transformations projecting the belief-update framework for belief functions to that for probabilities are likened to the fire projecting reality into shadows on the wall in Plato's cave.
Context-Based Reasoning on Privacy in Internet of Things
Authors: Kokciyan Nadin , Yolum Pinar
Published: July 2017

More and more, devices around us are being connected to each other in the realm of Internet of Things (IoT). Their communication and especially collaboration promises useful services to be provided to end users. However, the same communication channels pose important privacy concerns to be raised. It is not clear which information will be shared with whom, for which intents, under which conditions. Existing approaches to privacy advocate policies to be in place to regulate privacy. However, the scale and heterogeneity of the IoT entities make it infeasible to maintain policies among each and every entity in the system. Conversely, it is best if each entity can reason on the privacy using norms and context autonomously. Accordingly, this paper proposes an approach where each entity finds out which contexts it is in based on information it gathers from other entities in the system. The proposed approach uses argumentation to enable IoT entities to reason about their context and decide to reveal information based on it. We demonstrate the applicability of the approach over an IoT scenario.
Concrete Problems for Autonomous Vehicle Safety: Advantages of Bayesian Deep Learning
Authors: McAllister Rowan , Gal Yarin , Kendall Alex , van der Wilk Mark , Shah Amar , Cipolla Roberto , Weller Adrian
Published: July 2017

Autonomous vehicle (AV) software is typically composed of a pipeline of individual components, linking sensor inputs to motor outputs. Erroneous component outputs propagate downstream, hence safe AV software must consider the ultimate effect of each component’s errors. Further, improving safety alone is not sufficient. Passengers must also feel safe to trust and use AV systems. To address such concerns, we investigate three under-explored themes for AV research: safety, interpretability, and compliance. Safety can be improved by quantifying the uncertainties of component outputs and propagating them forward through the pipeline. Interpretability is concerned with explaining what the AV observes and why it makes the decisions it does, building reassurance with the passenger. Compliance refers to maintaining some control for the passenger. We discuss open challenges for research within these themes. We highlight the need for concrete evaluation metrics, propose example problems, and highlight possible solutions.
Should Robots be Obedient?
Authors: Milli Smitha , Hadfield-Menell Dylan , Dragan Anca , Russell Stuart
Published: July 2017

Intuitively, obedience -- following the order that a human gives -- seems like a good property for a robot to have. But, we humans are not perfect and we may give orders that are not best aligned to our preferences. We show that when a human is not perfectly rational then a robot that tries to infer and act according to the human's underlying preferences can always perform better than a robot that simply follows the human's literal order. Thus, there is a tradeoff between the obedience of a robot and the value it can attain for its owner. We investigate how this tradeoff is impacted by the way the robot infers the human's preferences, showing that some methods err more on the side of obedience than others. We then analyze how performance degrades when the robot has a misspecified model of the features that the human cares about or the level of rationality of the human. Finally, we study how robots can start detecting such model misspecification. Overall, our work suggests that there might be a middle ground in which robots intelligently decide when to obey human orders, but err on the side of obedience.
Unsatisfiable Core Shrinking for Anytime Answer Set Optimization
Authors: Alviano Mario , Dodaro Carmine
Published: July 2017

Efficient algorithms for the computation of optimum stable models are based on unsatisfiable core analysis. However, these algorithms essentially run to completion, providing few or even no suboptimal stable models. This drawback can be circumvented by shrinking unsatisfiable cores. Interestingly, the resulting anytime algorithm can solve more instances than the original algorithm.
A Verified SAT Solver Framework with Learn, Forget, Restart, and Incrementality
Authors: Blanchette Jasmin Christian , Fleury Mathias , Weidenbach Christoph
Published: July 2017

We developed a formal framework for SAT solving using the Isabelle/HOL proof assistant. Through a chain of refinements, an abstract CDCL (conflict-driven clause learning) calculus is connected to a SAT solver that always terminates with correct answers. The framework offers a convenient way to prove theorems about the SAT solver and experiment with variants of the calculus. Compared with earlier verifications, the main novelties are the inclusion of the CDCL rules for forget, restart, and incremental solving and the use of refinement.
Blockedness in Propositional Logic: Are You Satisfied With Your Neighborhood?
Authors: Kiesl Benjamin , Seidl Martina , Tompits Hans , Biere Armin
Published: July 2017

Clause-elimination techniques that simplify formulas by removing redundant clauses play an important role in modern SAT solving. Among the types of redundant clauses, blocked clauses are particularly popular. For checking whether a clause C is blocked in a formula F, one only needs to consider the so-called resolution neighborhood of C, i.e., the set of clauses that can be resolved with C. Because of this, blocked clauses are referred to as being locally redundant. In this paper, we discuss powerful generalizations of blocked clauses that are still locally redundant, viz. set-blocked clauses and super-blocked clauses. We furthermore present complexity results for deciding whether a clause is set-blocked or super-blocked.
Grounding Abstract Spatial Concepts for Language Interaction with Robots
Authors: Paul Rohan , Arkin Jacob , Roy Nicholas , Howard Thomas M.
Published: July 2017

Our goal is to develop models that allow a robot to understand or ``ground" natural language instructionsin the context of its world model. Contemporary approaches estimate correspondences between an instruction and possible candidate groundings such as objects, regions and goals for a robot's action. However, these approaches are unable to reason about abstract or hierarchical concepts such as rows, columns and groups that are relevant in a manipulation domain. We introduce a probabilistic model that incorporates an expressive space of abstract spatial concepts as well as notions of cardinality and ordinality. Abstract concepts are introduced as explicit hierarchical symbols correlated with concrete groundings. Crucially, the abstract groundings form a Markov boundary over concrete groundings, effectively de-correlating them from the remaining variables in the graph which reduces the complexity of training and inference in the model. Empirical evaluation demonstrates accurate grounding of abstract concepts embedded in complex natural language instructions commanding a robot manipulator. The proposed inference method leads to significant efficiency gains compared to the baseline, with minimal trade-off in accuracy.
Maximizing Awareness about HIV in Social Networks of Homeless Youth with Limited Information
Authors: Yadav Amulya , Chan Hau , Xin Jiang Albert , Xu Haifeng , Rice Eric , Tambe Milind
Published: July 2017

This paper presents HEALER, a software agent that recommends sequential intervention plans for use by homeless shelters, who organize these interventions to raise awareness about HIV among homeless youth. HEALER's sequential plans (built using knowledge of social networks of homeless youth) choose intervention participants strategically to maximize influence spread, while reasoning about uncertainties in the network. While previous work presents influence maximizing techniques to choose intervention participants, they do not address two real-world issues: (i) they completely fail to scale up to real-world sizes; and (ii) they do not handle deviations in execution of intervention plans. HEALER handles these issues via two major contributions: (i) HEALER casts this influence maximization problem as a POMDP and solves it using a novel planner which scales up to previously unsolvable real-world sizes; and (ii) HEALER allows shelter officials to modify its recommendations, and updates its future plans in a deviation-tolerant manner. HEALER was deployed in the real world in Spring 2016 with considerable success.
Robust Multilingual Named Entity Recognition with Shallow Semi-supervised Features (Extended Abstract)
Authors: Agerri Rodrigo , Rigau German
Published: July 2017

We present a multilingual Named Entity Recognition approach based on a robust and general set of features across languages and datasets. Our system combines shallow local information with clustering semi-supervised features induced on large amounts of unlabeled text. Understanding via empiricalexperimentation how to effectively combine various types of clustering features allows us to seamlessly export our system to other datasets and languages. The result is a simple but highly competitive system which obtains state of the art results across five languages and twelve datasets. The results are reported on standard shared task evaluation data such as CoNLL for English, Spanish and Dutch. Furthermore, and despite the lack of linguistically motivated features, we also report best results for languages such as Basque and German. In addition, we demonstrate that our method also obtains very competitive results even when the amount of supervised data is cut by half, alleviating the dependency on manually annotated data. Finally, the results show that our emphasis on clustering features is crucial to develop robust out-of-domain models. The system and models are freely available to facilitate its use and guarantee the reproducibility of results.
A New Semantics for Overriding in Description Logics (Extended Abstract)
Authors: Bonatti Piero , Faella Marco , Petrova Iliana M. , Sauro Luigi
Published: July 2017

Nonmonotonic inferences are not yet supported by Description Logic

technology, although their potential usefulness is widely recognized. Lack of

support to nonmonotonic reasoning is due to a number of issues related

to expressiveness, computational complexity, and optimizations. This

work contributes to the practical support of nonmonotonic reasoning

in description logics by introducing a new semantics designed to

address knowledge engineering needs. The formalism is validated

through extensive comparison with the other nonmonotonic DLs, and

systematic scalability tests.
A Random Model for Argumentation Framework: Phase Transitions, Empirical Hardness, and Heuristics
Authors: Gao Yong
Published: July 2017

We propose and study, theoretically and empirically, a new random model for the abstract argumentation framework (AF). Our model overcomes some intrinsic difficulties of the only random model of directed graphs in the literature that is relevant to AFs, and makes it possible to study the typical-case complexity of AF instances in terms of threshold behaviours and phase transitions. We proved that the probability for a random AF instance to have a stable/preferred extension goes through a sudden change (from 1 to 0) at the

threshold of the parameters of the new model D(n, p, q), satisfying the equation 4q/((1 + q)(1+q)) = p. We showed, empirically, that in this new model, there is a clear easy-hard-easy pattern of hardness (for a typical backtracking-style exact solvers) associated with the phase transition. Our empirical studies indicated that instances from the new model at phase transitions are much harder than those from an Erdos-Renyi-style model with equal edge density. In addition to being an analytically tractable model for understanding the interplay between problems structures and effectiveness of (branching) heuristics used in practical argumentation solvers, the model can also be used to generate, in a systematic way, non-trivial AF instances with controlled features to evaluate the performance of other AF solvers.
Evaluating Epistemic Negation in Answer Set Programming (Extended Abstract)
Authors: Shen Yi-Dong , Eiter Thomas
Published: July 2017

Epistemic negation 'not' along with default negation 'neg' plays a key role in knowledge representation and nonmonotonic reasoning. However, the existing approaches behave not satisfactorily in that they suffer from the problems of unintended world views due to recursion through the epistemic modal operator K or M ( K F and M F are shorthands for (neg not F) and (not neg F), respectively). In this paper we present a general approach to epistemic negation which is free of unintended world views and thus offers a solution to the long-standing problem of epistemic specifications which were introduced by Gelfond 1991 over two decades ago.
Some Properties of Batch Value of Information in the Selection Problem (Extended Abstract)
Authors: Shperberg Shahaf S. , Shimony Solomon Eyal
Published: July 2017

We examine theoretical properties of value of information (VOI) in the selection problem, and identify cases of submodularity and supermodularity. We use these properties to compute approximately optimal measurement batch policies, implemented on a “wine selection problem” example.
Robots in Retirement Homes: Applying Off-the-Shelf Planning and Scheduling to a Team of Assistive Robots (Extended Abstract)
Authors: Tran Tony T. , Vaquero Tiago , Nejat Goldie , Beck J. Christopher
Published: July 2017

We investigate Constraint Programming and Planning Domain Definition Language-based technologies for planning and scheduling multiple robots in a retirement home environment to assist elderly residents. Our robotics problem and investigation into proposed solution approaches provide a real world application of planning and scheduling, while highlighting the different modeling assumptions required to solve such a problem. This information is valuable to the planning and scheduling community as it provides insight into potential application avenues, in particular for robotics problems. Based on empirical results, we conclude that a constraint-based scheduling approach, specifically a decomposition using constraint programming, provides the most promising results for our application.
POPPONENT: Highly accurate, individually and socially efficient opponent preference model in bilateral multi issue negotiations (Extended Abstract)
Authors: Zafari Farhad , Nassiri-Mofakham Faria
Published: July 2017

In automated bilateral multi issue negotiations, two intelligent automated agents negotiate on behalf of their owners over many issues in order to reach an agreement. Modeling the opponent can excessively boost the performance of the agents and increase the quality of the negotiation outcome. State of the art models accomplish this by considering some assumptions about the opponent which restricts their applicability in real scenarios. In this paper, a less restricted technique where perceptron units (POPPONENT) are applied in modelling the preferences of the opponent is proposed. This model adopts a Multi Bipartite version of the Standard Gradient Descent search algorithm (MBGD) to find the best hypothesis, which is the best preference profile. In order to evaluate the accuracy and performance of this proposed opponent model, it is compared with the state of the art models available in the Genius repository. This results in the devised setting which approves the higher accuracy of POPPONENT compared to the most accurate state of the art model. Evaluating the model in the real world negotiation scenarios in the Genius framework also confirms its high accuracy in relation to the state of the art models in estimating the utility of offers. The findings here indicate that the proposed model is individually and socially efficient. This proposed MBGD method could also be adopted in similar practical areas of Artificial Intelligence.
Robotic Strategic Behavior in Adversarial Environments
Authors: Agmon Noa
Published: July 2017

The presence of robots in areas containing threats is becoming more prevalent, due to their ability to perform missions accurately, efficiently, and with little risk to humans. Having the robots handle adversarial forces in missions such as search and rescue, intelligence gathering, border protection and humanitarian assistance, raises many new, exciting research challenges. This paper describes recent research achievements in areas related to robotic mission planning in adversarial environments, including multi-robot patrolling, robotic coverage, multi-robot formation, and navigation, and suggests possible future research directions.
The Mixing of Markov Chains on Linear Extensions in Practice
Authors: Talvitie Topi , Niinimäki Teppo , Koivisto Mikko
Published: July 2017

We investigate almost uniform sampling from the set of linear extensions of a given partial order. The most efficient schemes stem from Markov chains whose mixing time bounds are polynomial, yet impractically large. We show that, on instances one encounters in practice, the actual mixing times can be much smaller than the worst-case bounds, and particularly so for a novel Markov chain we put forward. We circumvent the inherent hardness of estimating standard mixing times by introducing a refined notion, which admits estimation for moderate-size partial orders. Our empirical results suggest that the Markov chain approach to sample linear extensions can be made to scale well in practice, provided that the actual mixing times can be realized by instance-sensitive upper bounds or termination rules. Examples of the latter include existing perfect simulation algorithms, whose running times in our experiments follow the actual mixing times of certain chains, albeit with significant overhead.
Improving Group Decision-Making by Artificial Intelligence
Authors: Xia Lirong
Published: July 2017

We summarize some of our recent work on using AI to improve group decision-making by taking a unified approach from statistics, economics, and computation. We then discuss a few ongoing and future directions.
Securing and scaling cryptocurrencies
Authors: Zohar Aviv
Published: July 2017

Bitcoin, a protocol for a new permissionless decentralized digital currency hailed the arrival of a new application domain for computer science. Following Bitcoin's arrival, a series of innovations derived from the state of the art in several fields has been applied to cryptocurrencies, and has been slowly reshaping monetary and financial instruments on public distributed ledgers. It was soon clear however that Bitcoin and similar cryptocurrencies still require additional improvements. This challenging domain presents researchers in the field with new and exciting questions. I provide examples from two main research threads, related to the scalability of the protocol and to its underlying incentives.