25. IJCAI 2016:New York,NY,USA

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016. IJCAI/AAAI Press 【DBLP Link】

Paper Num: 658 || Session Num: 2

Frontmatter 7
Papers 651

【Abstract】: We consider the problem of whether a coalition of agents has a knowledge-based strategy to ensure some outcome under a resource bound. We extend previous work on verification of multi-agent systems where actions of agents produce and consume resources, by adding epistemic pre- and postconditions to actions. This allows us to model scenarios where agents perform both actions which change the world, and actions which change their knowledge about the world, such as observation and communication. To avoid logical omniscience and obtain a compact model of the system, our model of agents' knowledge is syntactic. We define a class of coalition-uniform strategies with respect to any (decidable) notion of coalition knowledge. We show that the model-checking problem for the resulting logic is decidable for any notion of coalition-uniform strategies in these classes.

【Keywords】:

【Paper Link】【Pages】:31-37

【Authors】: Georgios Amanatidis ; Georgios Birmpas ; Evangelos Markakis

【Abstract】: We study a fair division problem with indivisible items, namely the computation of maximin share allocations. Given a set of n players, the maximin share of a single player is the best she can guarantee to herself, if she would partition the items in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find an allocation, so that each player is guaranteed her maximin share. Previous works have studied this problem purely algorithmically, providing constant factor approximation algorithms. In this work, we embark on a mechanism design approach and investigate the existence of truthful mechanisms. We propose three models regarding the information that the mechanism attempts to elicit from the players, based on the cardinal and ordinal representation of preferences. We establish positive and negative (impossibility) results for each model and highlight the limitations imposed by truthfulness on the approximability of the problem. Finally, we pay particular attention to the case of two players, which already leads to challenging questions.

【Keywords】:

13. Modeling and Reasoning about NTU Games via Answer Set Programming.

【Paper Link】【Pages】:38-45

【Authors】: Giovanni Amendola ; Gianluigi Greco ; Nicola Leone ; Pierfrancesco Veltri

【Abstract】: A compact representation for non-transferable utility games founding on answer set programming is proposed. The representation is fully expressive, in that it can capture all games defined over a finite set of alternatives. Moreover, due to the knowledge representation capabilities of answer set programs, it can easily accommodate the definition of games within a wide range of application domains, ranging from scheduling, to routing and planning, just to name a few. The computational complexity of the proposed framework is studied, in particular, by focusing on the core as the prototypical solution concept. A system supporting the basic reasoning tasks arising therein is also made available, and results of experimental activity are discussed.

【Keywords】:

【Abstract】: Vehicle-to-grid (V2G) is a promising approach whereby electric vehicles (EVs) are used to store excess electricity supply (e.g., from renewable sources), which is sold back to the grid in times of scarcity. In this paper we consider the setting of a smart car park, where EVs come and go, and can be used for V2G while parked. We develop novel allocation and payment mechanisms which truthfully elicit the EV owners' preferences and constraints, including arrival, departure, required charge, as well as the costs of discharging due to loss of efficiency of the battery. The car park will schedule the charging and discharging of each EV, ensuring the constraints of the EVs are met, and taking into consideration predictions about future electricity prices. Optimally solving the global problem is intractable, and we present three novel heuristic online scheduling algorithms. We show that, under certain conditions, two of these satisfy monotonicity and are therefore truthful. We furthermore evaluate the algorithms using simulations, and we show that some of our algorithms benefit significantly from V2G, achieving positive benefit for the car park even when agents do not pay for using it.

【Keywords】:

【Paper Link】【Pages】:338-344

【Authors】: Thanasis Lianeas ; Evdokia Nikolova ; Nicolás E. Stier Moses

【Abstract】: We consider a nonatomic selfish routing model with independent stochastic travel times for each edge, represented by mean and variance latency functions that depend on arc flows. This model can apply to traffic in the Internet or in a road network. Variability negatively impacts packets or drivers, by introducing jitter in transmission delays which lowers quality of streaming audio or video, or by making it more difficult to predict the arrival time at destination. The price of risk aversion (PRA) has been defined as the worst-case ratio of the cost of an equilibrium with risk-averse players who seek risk-minimizing paths, and that of an equilibrium with risk-neutral users who minimize the mean travel time of a path [Nikolova and Stier-Moses, 2015]. This inefficiency metric captures the degradation of system performance caused by variability and risk aversion. In this paper, we provide the first lower bounds on the PRA. First, we show a family of structural lower bounds, which grow linearly with the size of the graph and players' risk-aversion. They are tight for graph sizes that are powers of two. We also provide asymptotically tight functional bounds that depend on the allowed latency functions but not on the topology. The functional bounds match the price-of-anarchy bounds for congestion games multiplied by an extra factor that accounts for risk aversion. Finally, we provide a closed-form formula of the PRA for a family of graphs that generalize series-parallel graphs and the Braess graph. This formula also applies to the mean-standard deviation user objective a much more complex model of risk-aversion due to the cost of a path being non-additive over edge costs.

【Keywords】:

【Paper Link】【Pages】:345-351

【Authors】: Hongyao Ma ; Reshef Meir ; David C. Parkes

【Abstract】: The existence of truthful social choice mechanisms strongly depends on whether monetary transfers are allowed. Without payments there are no truthful, non-dictatorial mechanisms under mild requirements, whereas the VCG mechanism guarantees truthfulness along with welfare maximization when there are payments and utility is quasi-linear in money. In this paper we study mechanisms in which we can use payments but where agents have non quasi-linear utility functions. Our main result extends the Gibbard-Satterthwaite impossibility result by showing that, for two agents, the only truthful mechanism for at least three alternatives under general decreasing utilities remains dictatorial. We then show how to extend the VCG mechanism to work under a more general utility space than quasi-linear (the "parallel domain) and show that the parallel domain is maximal—no mechanism with the VCG properties exists in any larger domain.

【Keywords】:

57. Incentivizing Reliability in Demand-Side Response.

【Paper Link】【Pages】:352-358

【Authors】: Hongyao Ma ; Valentin Robu ; Na Li ; David C. Parkes

【Abstract】: We study the problem of incentivizing reliable demand-response in modern electricity grids. Each agent is uncertain about her future ability to reduce demand and unreliable. Agents who choose to participate in a demand-response scheme may be paid when they respond and penalized otherwise. The goal is to reliably achieve a demand reduction target while selecting a minimal set of agents from those willing to participate. We design incentive-aligned, direct and indirect mechanisms. The direct mechanism elicits both response probabilities and costs, while the indirect mechanism elicits willingness to accept a penalty in the case of non-response. We benchmark against a spot auction, in which demand reduction is purchased from agents when needed. Both the direct and indirect mechanisms achieve the reliability target in a dominant-strategy equilibrium, select a small number of agents to prepare, and do so at low cost and with much lower variance in payments than the spot auction.

【Keywords】:

58. Allocating Indivisible Items in Categorized Domains.

【Paper Link】【Pages】:359-365

【Authors】: Erika Mackin ; Lirong Xia

【Abstract】: We initiate a research agenda of mechanism design for categorized domain allocation problems (CDAPs), where indivisible items from multiple categories are allocated to agents without monetary transfer and each agent gets at least one item per category. We focus on basic CDAPs, where each agent gets exactly one item per category. We first characterize serial dictatorships by a minimal set of three axiomatic properties: strategy-proofness, non-bossiness, and category-wise neutrality. Then, we propose a natural extension of serial dictatorships called categorial sequential allocation mechanisms (CSAMs), which allocate the items in multiple rounds: in each round, the designated agent chooses an item from a designated category. We fully characterize the worst-case rank efficiency of CSAMs for optimistic and pessimistic agents.

【Keywords】:

59. Correlated Voting.

【Paper Link】【Pages】:366-372

【Authors】: Debmalya Mandal ; David C. Parkes

【Abstract】: We study the social choice problem where a group of n voters report their preferences over alternatives and a voting rule is used to select an alternative. We show that when the preferences of voters are positively correlated according to the Kendall-Tau distance, the probability that any scoring rule is not ex post incentive compatible (EPIC) goes to zero exponentially fast with the number of voters, improving over the previously known rate of 1/√n for independent preferences. Motivated by rank-order models from machine learning, we introduce two examples of positively-correlated models, namely Conditional Mallows and Conditional Plackett-Luce. Conditional Mallows satisfies Kendall-Tau correlation and fits our positive result. We also prove that Conditional Plackett-Luce becomes EPIC exponentially quickly.

【Keywords】:

60. Silk: A Simulation Study of Regulating Open Normative Multiagent Systems.

【Paper Link】【Pages】:373-379

【Authors】: Mehdi Mashayekhi ; Hongying Du ; George F. List ; Munindar P. Singh

【Abstract】: In a multiagent system, a (social) norm describes what the agents may expect from each other. Norms promote autonomy (an agent need not comply with a norm) and heterogeneity (a norm describes interactions at a high level independent of implementation details). Researchers have studied norm emergence through social learning where the agents interact repeatedly in a graph structure. In contrast, we consider norm emergence in an open system, where membership can change, and where no predetermined graph structure exists. We propose Silk, a mechanism wherein a generator monitors interactions among member agents and recommends norms to help resolve conflicts. Each member decides on whether to accept or reject a recommended norm. Upon exiting the system, a member passes its experience along to incoming members of the same type. Thus, members develop norms in a hybrid manner to resolve conflicts. We evaluate Silk via simulation in the traffic domain. Our results show that social norms promoting conflict resolution emerge in both moderate and selfish societies via our hybrid mechanism.

【Keywords】:

【Paper Link】【Pages】:787-795

【Authors】: Ruiwei Wang ; Wei Xia ; Roland H. C. Yap ; Zhanshan Li

【Abstract】: Maintaining Generalized Arc Consistency (GAC) during search is considered an efficient way to solve non-binary constraint satisfaction problems. Bit-based representations have been used effectively in Arc Consistency algorithms. We propose STRbit, a GAC algorithm, based on simple tabular reduction (STR) using an efficient bit vector support data structure. STRbit is extended to deal with compression of the underlying constraint with c-tuples. Experimental evaluation show our algorithms are faster than many algorithms (STR2, STR2-C, STR3, STR3-C and MDDc) across a variety of benchmarks except for problems with small tables where complex data structures do not payoff.

【Keywords】:

【Authors】: Tristan Charrier ; Bastien Maubert ; François Schwarzentruber

【Abstract】: Epistemic planning is a variant of automated planning in the framework of dynamic epistemic logic. In recent works, the epistemic planning problem has been proved to be undecidable when preconditions of events can be epistemic formulas of arbitrary complexity, and in particular arbitrary modal depth. It is known however that when preconditions are propositional (and there are no postconditions), the problem is between PSPACE and EXPSPACE. In this work we bring two new pieces to the picture. First, we prove that the epistemic planning problem with propositional preconditions and without postconditions is in PSPACE, and is thus PSPACE-complete. Second, we prove that very simple epistemic preconditions are enough to make the epistemic planning problem undecidable: preconditions of modal depth at most two suffice.

【Keywords】:

151. Imperfect-Information Games and Generalized Planning.

【Paper Link】【Pages】:1037-1043

【Authors】: Giuseppe De Giacomo ; Aniello Murano ; Sasha Rubin ; Antonio Di Stasio

【Abstract】: We study a generalized form of planning under partial observability, in which we have multiple, possibly infinitely many, planning domains with the same actions and observations, and goals expressed over observations, which are possibly temporally extended. By building on work on two-player (non-probabilistic) games with imperfect information in the Formal Methods literature, we devise a general technique, generalizing the belief-state construction, to remove partial observability. This reduces the planning problem to a game of perfect information with a tight correspondence between plans and strategies. Then we instantiate the technique and solve some generalized-planning problems.

【Keywords】:

152. LTLf and LDLf Synthesis under Partial Observability.

【Paper Link】【Pages】:1044-1050

【Authors】: Giuseppe De Giacomo ; Moshe Y. Vardi

【Abstract】: In this paper, we study synthesis under partial observability for logical specifications over finite traces expressed in LTLf/LDLf. This form of synthesis can be seen as a generalization of planning under partial observability in nondeterministic domains, which is known to be 2EXPTIME-complete. We start by showing that the usual "belief-state construction" used in planning under partial observability works also for general LTLf/LDLf synthesis, though with a jump in computational complexity from 2EXPTIME to 3EXPTIME. Then we show that the belief-state construction can be avoided in favor of a direct automata construction which exploits projection to hide unobservable propositions. This allow us to prove that the problem remains 2EXPTIME-complete. The new synthesis technique proposed is effective and readily implementable.

【Keywords】:

153. Investigating the Relationship between Argumentation Semantics via Signatures.

【Paper Link】【Pages】:1051-1057

【Authors】: Paul E. Dunne ; Christof Spanring ; Thomas Linsbichler ; Stefan Woltran

【Abstract】: Understanding the relation between different semantics in abstract argumentation is an important issue, not least since such semantics capture the basic ingredients of different approaches to nonmonotonic reasoning. The question we are interested in relates two semantics as follows: What are the necessary and sufficient conditions, such that we can decide, for any two sets of extensions, whether there exists an argumentation framework which has exactly the first extension set under one semantics, and the second extension set under the other semantics. We investigate in total nine argumentation semantics and give a nearly complete landscape of exact characterizations. As we shall argue, such results not only give an account on the independency between semantics, but might also prove useful in argumentation systems by providing guidelines for how to prune the search space.

【Keywords】:

154. Exploiting Partial Assignments for Efficient Evaluation of Answer Set Programs with External Source Access.

【Paper Link】【Pages】:1058-1065

【Authors】: Thomas Eiter ; Tobias Kaminski ; Christoph Redl ; Antonius Weinzierl

【Abstract】: Answer Set Programming (ASP) is a well-known problem solving approach based on nonmonotonic logic programs and efficient solvers. HEX-programs extend ASP with external atoms for access to arbitrary external information. In this work, we extend the evaluation principles of external atoms to partial assignments, lift nogood learning to this setting, and introduce a variant of nogood minimization. This enables external sources to guide the search for answer sets akin to theory propagation. Our benchmark experiments demonstrate a clear improvement in efficiency over the state-of-the-art HEX-solver.

【Keywords】:

【Keywords】:

250. Learning to Detect Concepts from Webly-Labeled Video Data.

【Paper Link】【Pages】:1746-1752

【Authors】: Junwei Liang ; Lu Jiang ; Deyu Meng ; Alexander G. Hauptmann

【Abstract】: Learning detectors that can recognize concepts, such as people actions, objects, etc., in video content is an interesting but challenging problem. In this paper, we study the problem of automatically learning detectors from the big video data on the web without any additional manual annotations. The contextual information available on the web provides noisy labels to the video content. To leverage the noisy web labels, we propose a novel method called WEbly-Labeled Learning (WELL). It is established on two theories called curriculum learning and self-paced learning and exhibits useful properties that can be theoretically verified. We provide compelling insights on the latent non-convex robust loss that is being minimized on the noisy data. In addition, we propose two novel techniques that not only enable WELL to be applied to big data but also lead to more accurate results. The efficacy and the scalability of WELL have been extensively demonstrated on two public benchmarks, including the largest multimedia dataset and the largest manually-labeled video set. Experimental results show that WELL significantly outperforms the state-of-the-art methods. To the best of our knowledge, WELL achieves by far the best reported performance on these two webly-labeled big video datasets.

【Keywords】:

251. Towards Convolutional Neural Networks Compression via Global Error Reconstruction.

【Paper Link】【Pages】:1753-1759

【Authors】: Shaohui Lin ; Rongrong Ji ; Xiaowei Guo ; Xuelong Li

【Abstract】: In recent years, convolutional neural networks (CNNs) have achieved remarkable success in various applications such as image classification, object detection, object parsing and face alignment. Such CNN models are extremely powerful to deal with massive amounts of training data by using millions and billions of parameters. However, these models are typically deficient due to the heavy cost in model storage, which prohibits their usage on resource-limited applications like mobile or embedded devices. In this paper, we target at compressing CNN models to an extreme without significantly losing their discriminability. Our main idea is to explicitly model the output reconstruction error between the original and compressed CNNs, which error is minimized to pursuit a satisfactory rate-distortion after compression. In particular, a global error reconstruction method termed GER is presented, which firstly leverages an SVD-based low-rank approximation to coarsely compress the parameters in the fully connected layers in a layer-wise manner. Subsequently, such layer-wise initial compressions are jointly optimized in a global perspective via back-propagation. The proposed GER method is evaluated on the ILSVRC2012 image classification benchmark, with implementations on two widely-adopted convolutional neural networks, i.e. the AlexNet and VGGNet-19. Comparing to several state-of-the-art and alternative methods of CNN compression, the proposed scheme has demonstrated the best rate-distortion performance on both networks.

【Keywords】:

252. Efficient k-Support-Norm Regularized Minimization via Fully Corrective Frank-Wolfe Method.

【Paper Link】【Pages】:1760-1766

【Authors】: Bo Liu ; Xiao-Tong Yuan ; Shaoting Zhang ; Qingshan Liu ; Dimitris N. Metaxas

【Abstract】: The k-support-norm regularized minimization has recently been applied with success to sparse prediction problems. The proximal gradient method is conventionally used to minimize this composite model. However it tends to suffer from expensive iteration cost as the proximity operator associated with k-support-norm needs exhaustive searching operations and thus could be time consuming in large scale settings. In this paper, we reformulate the k-support-norm regularized formulation into an identical constrained formulation and propose a fully corrective Frank-Wolfe algorithm to minimize the constrained model. Our method is inspired by an interesting observation that the convex hull structure of the k-support-norm ball allows the application of Frank-Wolfe-type algorithms with low iteration complexity. The convergence behavior of the proposed algorithm is analyzed. Extensive numerical results in learning tasks including logistic regression and matrix pursuit demonstrate the substantially improved computational efficiency of our algorithm over the state-of-the-art proximal gradient algorithms.

【Keywords】:

253. Supervised Matrix Factorization for Cross-Modality Hashing.

【Paper Link】【Pages】:1767-1773

【Authors】: Hong Liu ; Rongrong Ji ; Yongjian Wu ; Gang Hua

【Abstract】: Matrix factorization has been recently utilized for the task of multi-modal hashing for cross-modality visual search, where basis functions are learned to map data from different modalities to the same Hamming embedding. In this paper, we propose a novel cross-modality hashing algorithm termed Supervised Matrix Factorization Hashing (SMFH) which tackles the multi-modal hashing problem with a collective non-negative matrix factorization across the different modalities. In particular, SMFH employs a well-designed binary code learning algorithm to preserve the similarities among multi-modal original features through a graph regularization. At the same time, semantic labels, when available, are incorporated into the learning procedure.We conjecture that all these would facilitate to preserve the most relevant information during the binary quantization process, and hence improve the retrieval accuracy. We demonstrate the superior performance of SMFH on three cross-modality visual search benchmarks, i.e., the PASCAL-Sentence, Wiki, and NUS-WIDE, with quantitative comparison to various state-of-the-art methods.

【Keywords】:

【Paper Link】【Pages】:1816-1822

【Authors】: Weizhi Ma ; Min Zhang ; Yiqun Liu ; Shaoping Ma

【Abstract】: Large-scale customer service call records include lots of valuable information for business intelligence. However, the analysis of those records has not utilized in the big data era before. There are two fundamental problems before mining and analyses: 1) The telephone conversation is mixed with words of agents and users which have to be recognized before analysis; 2) The speakers in conversation are not in a pre-defined set. These problems are new challenges which have not been well studied in the previous work. In this paper, we propose a four-phase framework for role labeling in real customer service telephone conversation, with the benefit of integrating multi-modality features, i.e., both low-level acoustic features and semantic-level textual features. Firstly, we conduct ΔBayesian Information Criterion (ΔBIC) based speaker diarization to get two segments clusters from an audio stream. Secondly, the segments are transferred into text in an Automatic Speech Recognition (ASR) phase with a deep learning model DNN-HMM. Thirdly, by integrating acoustic and textual features, dialog level role labeling is proposed to map the two clusters into the agent and the user. Finally, sentence level role correction is designed in order to label results correctly in a fine-grained notion, which reduces the errors made in previous phases. The proposed framework is tested on two real datasets: mobile and bank customer service calls datasets. The precision of dialog level labeling is over 99.0%. On the sentence level, the accuracy of labeling reaches 90.4%, greatly outperforming traditional acoustic features based method which achieves only 78.5% in accuracy.

【Keywords】:

【Paper Link】【Pages】:2039-2045

【Authors】: Sanatan Sukhija ; Narayanan Chatapuram Krishnan ; Gurkanwal Singh

【Abstract】: Heterogeneity of features and lack of correspondence between data points of different domains are the two primary challenges while performing feature transfer. In this paper, we present a novel supervised domain adaptation algorithm (SHDA-RF) that learns the mapping between heterogeneous features of different dimensions. Our algorithm uses the shared label distributions present across the domains as pivots for learning a sparse feature transformation. The shared label distributions and the relationship between the feature spaces and the label distributions are estimated in a supervised manner using random forests. We conduct extensive experiments on three diverse datasets of varying dimensions and sparsity to verify the superiority of the proposed approach over other baseline and state of the art transfer approaches.

【Keywords】:

【Paper Link】【Pages】:2273-2279

【Authors】: Yang Yang ; Fumin Shen ; Zi Huang ; Heng Tao Shen

【Abstract】: Spectral clustering has been playing a vital role in various research areas. Most traditional spectral clustering algorithms comprise two independent stages (i.e., first learning continuous labels and then rounding the learned labels into discrete ones), which may lead to severe information loss and performance degradation. In this work, we study how to achieve discrete clustering as well as reliably generalize to unseen data. We propose a unified spectral clustering scheme which jointly learns discrete clustering labels and robust out-of-sample prediction functions. Specifically, we explicitly enforce a discrete transformation on the intermediate continuous labels, which leads to a tractable optimization problem with a discrete solution. Moreover, to further compensate the unreliability of the learned labels, we integrate an adaptive robust module with ℓ2,p loss to learn prediction function for unseen data. Extensive experiments conducted on various data sets have demonstrated the superiority of our proposal as compared to existing clustering approaches.

【Keywords】:

【Paper Link】【Pages】:2280-2286

【Authors】: Yang Yang ; De-Chuan Zhan ; Yuan Jiang

【Abstract】: Complex objects are usually with multiple modal features. In multi-modal learning, modalities closely related to the target tasks are known as strong modalities. While collecting strong modalities of all instances is often expensive, and current multi-modal learning techniques hardly take the strong modal feature extraction expenses into consideration. On the other hand, active learning is proposed to reduce the labeling expenses by querying the ground truths for specific selected instances. In this paper, we propose a training strategy, ACQUEST (ACtive QUErying STrong modalities), which exploits strong modal information by actively querying the strong modal feature values of "selected" instances rather than their corresponding ground truths. In ACQUEST, only the informative instances are selected for strong modal feature acquisition. An inverse prediction technique is also proposed to make the ACQUEST a unified optimization form. Experiments on image datasets show that ACQUEST achieves better classification performance than conventional active learning and multi-modal learning methods with less feature acquisition costs and labeling expenses.

【Keywords】:

【Paper Link】【Pages】:2385-2391

【Authors】: Feipeng Zhao ; Min Xiao ; Yuhong Guo

【Abstract】: Recommender systems have been widely studied in the literature as they have real world impacts in many E-commerce platforms and social networks. Most previous systems are based on the user-item recommendation matrix, which contains users' history recommendation activities on items. In this paper, we propose a novel predictive collaborative filtering approach that exploits both the partially observed user-item recommendation matrix and the item-based side information to produce top-N recommender systems. The proposed approach automatically identifies the most interesting items for each user from his or her non-recommended item pool by aggregating over his or her recommended items via a low-rank coefficient matrix. Moreover, it also simultaneously builds linear regression models from the item-based side information such as item reviews to predict the item recommendation scores for the users. The proposed approach is formulated as a rank constrained joint minimization problem with integrated least squares losses, for which an efficient analytical solution can be derived. To evaluate the proposed learning technique, empirical evaluations on five recommendation tasks are conducted. The experimental results demonstrate the efficacy of the proposed approach comparing to the competing methods.

【Keywords】:

【Paper Link】【Pages】:2449-2457

【Authors】: Xiaojin Zhu ; Ara Vartanian ; Manish Bansal ; Duy Nguyen ; Luke Brandl

【Abstract】: We introduce a new topological feature representation for point cloud objects. Specifically, we construct a Stochastic Multiresolution Persistent Homology (SMURPH) kernel which represents an object's persistent homology at different resolutions. Under the SMURPH kernel two objects are similar if they have similar number and sizes of "holes" at these resolutions. Our multiresolution kernel can capture both global topology and fine-grained topological texture in the data. Importantly, on large point clouds the SMURPH kernel is more computationally tractable compared to existing topological data analysis methods. We demonstrate SMURPH's potential for clustering and classification on several applications, including eye disease classification and human activity recognition.

【Keywords】:

【Paper Link】【Pages】:3014-3021

【Authors】: Deyu Zhou ; Haiyang Xu ; Xin-Yu Dai ; Yulan He

【Abstract】: Storyline extraction from news streams aims to extract events under a certain news topic and reveal how those events evolve over time. It requires algorithms capable of accurately extracting events from news articles published in different time periods and linking these extracted events into coherent stories. The two tasks are often solved separately, which might suffer from the problem of error propagation. Existing unified approaches often consider events as topics, ignoring their structured representations. In this paper, we propose a non-parametric generative model to extract structured representations and evolution patterns of storylines simultaneously. In the model, each storyline is modelled as a joint distribution over some locations, organizations, persons, keywords and a set of topics. We further combine this model with the Chinese restaurant process so that the number of storylines can be determined automatically without human intervention. Moreover, per-token Metropolis-Hastings sampler based on light latent Dirichlet allocation is employed to reduce sampling complexity. The proposed model has been evaluated on three news corpora and the experimental results show that it outperforms several baseline approaches.

【Keywords】:

【Abstract】: We analyze how complex a heuristic function must be to directly guide a state-space search algorithm towards the goal. As a case study, we examine functions that evaluate states with a weighted sum of state features. We measure the complexity of a domain by the complexity of the required features. We analyze conditions under which the search algorithm runs in polynomial time and show complexity results for several classical planning domains.

【Keywords】:

【Authors】: Tianmin Shu ; Michael S. Ryoo ; Song-Chun Zhu

【Abstract】: In this paper, we present an approach for robot learning of social affordance from human activity videos. We consider the problem in the context of human-robot interaction: our approach learns structural representations of human-human (and human-object-human) interactions, describing how body-parts of each agent move with respect to each other and what spatial relations they should maintain to complete each sub-event (i.e., sub-goal). This enables the robot to infer its own movement in reaction to the human body motion, allowing it to naturally replicate such interactions.

【Keywords】:

489. Learning to Order Objects Using Haptic and Proprioceptive Exploratory Behaviors.

【Paper Link】【Pages】:3462-3468

【Authors】: Jivko Sinapov ; Priyanka Khante ; Maxwell Svetlik ; Peter Stone

【Abstract】: This paper proposes a novel framework that enables a robot to learn ordinal object relations. While most related work focuses on classifying objects into discrete categories, such approaches cannot learn object properties (e.g., weight, height, size, etc.) that are context-specific and relative to other objects. To address this problem, we propose that a robot should learn to order objects based on ordinal object relations. In our experiments, the robot explored a set of 32 objects that can be ordered by three properties: height, weight, and width. Next, the robot used unsupervised learning to discover multiple ways that the objects can be ordered based on the haptic and proprioceptive perceptions detected while exploring the objects. Following, the robot's model was presented with labeled object series, allowing it to ground the three ordinal relations in terms of how similar they are to the orders discovered during the unsupervised stage. Finally, the grounded models were used to recognize whether new object series were ordered by any of the three properties as well as to correctly insert additional objects into an existing series.

【Keywords】:

490. Crowd Scene Understanding with Coherent Recurrent Neural Networks.

【Paper Link】【Pages】:3469-3476

【Authors】: Hang Su ; Yinpeng Dong ; Jun Zhu ; Haibin Ling ; Bo Zhang

【Abstract】: Exploring crowd dynamics is essential in understanding crowd scenes, which still remains as a challenging task due to the nonlinear characteristics and coherent spatio-temporal motion patterns in crowd behaviors. To address these issues, we present a Coherent Long Short Term Memory (cLSTM) network to capture the nonlinear crowd dynamics by learning an informative representation of crowd motions, which facilitates the critical tasks in crowd scene analysis. By describing the crowd motion patterns with a cloud of keypoint tracklets, we explore the nonlinear crowd dynamics embedded in the tracklets with a stacked LSTM model, which is further improved to capture the collective properties by introducing a coherent regularization term; and finally, we adopt an unsupervised encoder-decoder framework to learn a hidden feature for each input tracklet that embeds its inherent dynamics. With the learnt features properly harnessed, crowd scene understanding is conducted effectively in predicting the future paths of agents, estimating group states, and classifying crowd events. Extensive experiments on hundreds of public crowd videos demonstrate that our method is state-of-the-art performance by exploring the coherent spatio-temporal structures in crowd behaviors.

【Keywords】:

【Authors】: Qing Bao ; William K. Cheung ; Jiming Liu

【Abstract】: Existing diffusion models for social networks often assume that the activation of a node depends independently on their parents' activations. Some recent work showed that incorporating the structural and behavioral dependency among the parent nodes allows more accurate diffusion models to be inferred. In this paper, we postulate that the latent temporal activation patterns (or motifs) of nodes of different social roles form the underlying information diffusion mechanisms generating the information cascades observed over a social network. We formulate the inference of the temporal activation motifs and a corresponding motif-based diffusion model under a unified probabilistic framework. A two-level EM algorithm is derived so as to infer the diffusion-specific motifs and the diffusion probabilities simultaneously. We applied the proposed model to several real-world datasets with significant improvement on modelling accuracy. We also illustrate how the inferred motifs can be interpreted as the underlying mechanisms causing the diffusion process to happen in different social networks.

【Keywords】:

518. Non-Objection Inference for Inconsistency-Tolerant Query Answering.

【Paper Link】【Pages】:3684-3690

【Authors】: Salem Benferhat ; Zied Bouraoui ; Madalina Croitoru ; Odile Papini ; Karim Tabia

【Abstract】: Repair based techniques are a standard way of dealing with inconsistency in the context of ontology based data access. We propose a novel non-objection inference relation (along with its variants) where a query is considered as valid if it follows from at least one repair and it is consistent with all the repairs. These inferences are strictly more productive than universal inference while preserving the consistency of its set of conclusions. We study the productivity and properties of the new inferences. We also give experimental results of the proposed non-objection inference.

【Keywords】:

519. Multi-Source Iterative Adaptation for Cross-Domain Classification.

【Paper Link】【Pages】:3691-3697

【Authors】: Himanshu S. Bhatt ; Arun Rajkumar ; Shourya Roy

【Abstract】: Owing to the tremendous increase in the volume and variety of user generated content, train-once-apply-forever models are insufficient for supervised learning tasks. Thus, developing algorithms that adapt across domains by leveraging data from multiple domains is critical. However, existing adaptation algorithms often fail to identify the right sources to use for adaptation. In this work, we present a novel multi-source iterative domain adaptation algorithm (MSIDA) that leverages knowledge from selective sources to improve the performance in a target domain. The algorithm first chooses the best K sources from possibly numerous existing domains taking into account both similarity and complementarity properties of the domains. Then it learns target specific features in an iterative manner building on the common shared representations from the source domains. We give theoretical justifications for our source selection procedure and also give mistake bounds for the MSIDA algorithm. Experimental results justify the theory as MSIDA significantly outperforms existing cross-domain classification approaches on the real world and benchmark datasets.

【Keywords】:

【Paper Link】【Pages】:3768-3774

【Authors】: Sheng Li ; Nikos Vlassis ; Jaya Kawale ; Yun Fu

【Abstract】: A widely used method for estimating counterfactuals and causal treatment effects from observational data is nearest-neighbor matching. This typically involves pairing each treated unit with its nearest-in-covariates control unit, and then estimating an average treatment effect from the set of matched pairs. Although straightforward to implement, this estimator is known to suffer from a bias that increases with the dimensionality of the covariate space, which can be undesirable in applications that involve high-dimensional data. To address this problem, we propose a novel estimator that first projects the data to a number of random linear subspaces, and it then estimates the median treatment effect by nearest-neighbor matching in each subspace. We empirically compute the mean square error of the proposed estimator using semi-synthetic data, and we demonstrate the method on real-world digital marketing campaign data. The results show marked improvement over baseline methods.

【Keywords】:

【Authors】: Zheng Wang ; Chaokun Wang ; Jisheng Pei ; Xiaojun Ye ; Philip S. Yu

【Abstract】: In social network sites (SNS), propagation histories which record the information diffusion process can be used to explain to users what happened in their networks. However, these histories easily grow in size and complexity, limiting their intuitive understanding by users. To reduce this information overload, in this paper, we present the problem of propagation history ranking. The goal is to rank participant edges/nodes by their contribution to the diffusion. Firstly, we discuss and adapt Difference of Causal Effects (DCE) as the ranking criterion. Then, to avoid the complex calculation of DCE, we propose a resp-cap ranking strategy by adopting two indicators. The first is responsibility which captures the necessary face of causal effects. We further give an approximate algorithm for this indicator. The second is capability which is defined to capture the sufficient face of causal effects. Finally, promising experimental results are presented to verify the feasibility of our method.

【Keywords】:

552. Learning Defining Features for Categories.

【Paper Link】【Pages】:3924-3930

【Authors】: Bo Xu ; Chenhao Xie ; Yi Zhang ; Yanghua Xiao ; Haixun Wang ; Wei Wang

【Abstract】: Categories play a fundamental role in human cognition. Defining features (short for DFs) are the key elements to define a category, which enables machines to categorize objects. Categories enriched with their DFs significantly improve the machine's ability of categorization and benefit many applications built upon categorization. However, defining features can rarely be found for categories in current knowledge bases. Traditional efforts such as manual construction by domain experts are not practical to find defining features for millions of categories. In this paper, we make the first attempt to automatically find defining features for millions of categories in the real world. We formalize the defining feature learning problem and propose a bootstrapping solution to learn defining features from the features of entities belonging to a category. Experimental results show the effectiveness and efficiency of our method. Finally, we find defining features for overall 60,247 categories with acceptable accuracy.

【Keywords】:

553. Deep Semantic-Preserving and Ranking-Based Hashing for Image Retrieval.

【Paper Link】【Pages】:3931-3937

【Authors】: Ting Yao ; Fuchen Long ; Tao Mei ; Yong Rui

【Abstract】: Hashing techniques have been intensively investigated for large scale vision applications. Recent research has shown that leveraging supervised information can lead to high quality hashing. However, most existing supervised hashing methods only construct similarity-preserving hash codes. Observing that semantic structures carry complementary information, we propose the idea of co-training for hashing, by jointly learning projections from image representations to hash codes and classification. Specifically, a novel deep semantic-preserving and ranking-based hashing (DSRH) architecture is presented, which consists of three components: a deep CNN for learning image representations, a hash stream of a binary mapping layer by evenly dividing the learnt representations into multiple bags and encoding each bag into one hash bit, and a classification stream. Meanwhile, our model is learnt under two constraints at the top loss layer of hash stream: a triplet ranking loss and orthogonality constraint. The former aims to preserve the relative similarity ordering in the triplets, while the latter makes different hash bit as independent as possible. We have conducted experiments on CIFAR-10 and NUS-WIDE image benchmarks, demonstrating that our approach can provide superior image search accuracy than other state-of-the-art hashing techniques.

【Keywords】:

554. Modeling the Homophily Effect between Links and Communities for Overlapping Community Detection.

【Paper Link】【Pages】:3938-3944

【Authors】: Hongyi Zhang ; Tong Zhao ; Irwin King ; Michael R. Lyu

【Abstract】: Overlapping community detection has drawn much attention recently since it allows nodes in a network to have multiple community memberships. A standard framework to deal with overlapping community detection is Matrix Factorization (MF). Although all existing MF-based approaches use links as input to identify communities, the relationship between links and communities is still under-investigated. Most of the approaches only view links as consequences of communities (community-to-link) but fail to explore how nodes' community memberships can be represented by their linked neighbors (link-to-community). In this paper, we propose a Homophily-based Nonnegative Matrix Factorization (HNMF) to model both-sided relationships between links and communities. From the community-to-link perspective, we apply a preference-based pairwise function by assuming that nodes with common communities have a higher probability to build links than those without common communities. From the link-to-community perspective, we propose a new community representation learning with network embedding by assuming that linked nodes have similar community representations. We conduct experiments on several real-world networks and the results show that our HNMF model is able to find communities with better quality compared with state-of-the-art baselines.

【Keywords】:

555. Matrix Factorization+ for Movie Recommendation.

【Paper Link】【Pages】:3945-3951

【Authors】: Lili Zhao ; Zhongqi Lu ; Sinno Jialin Pan ; Qiang Yang

【Abstract】: We present a novel model for movie recommendations using additional visual features extracted from pictorial data like posters and still frames, to better understand movies. In particular, several context-based methods for recommendation are shown to be special cases of our proposed framework. Unlike existing context-based approaches, our method can be used to incorporate visual features — features that are lacking in existing context-based approaches for movie recommendations. In reality, movie posters and still frames provide us with rich knowledge for understanding movies, users' preferences as well. For instance, user may want to watch a movie at the minute when she/he finds some released posters or still frames attractive. Unfortunately, such unique features cannot be revealed from rating data or other form of context that being used in most of existing methods. In this paper, we take a step in this direction and investigate both low-level and high-level visual features from the movie posters and still frames for further improvement of recommendation methods. A comprehensive set of experiments on real world datasets shows that our approach leads to significant improvement over the state-of-the-art methods.

【Keywords】:

【Abstract】: Short-texts accentuate the challenges posed by the high feature space dimensionality of text learning tasks. The linked nature of social data causes new dimensions to be added to the feature space, which, also becomes sparser. Thus, efficient and scalable online feature selection becomes a crucial requirement of numerous large-scale social applications. This thesis proposes an online feature selection technique for high-dimensional data based on both social and content-based information for the real-time classification of short-text streams coming from social media. The main objective of this thesis is to define and evaluate a new intelligent text mining technique for enhancing the process of knowledge discovery in social-media. This technique would help in the development of new and more effective models for personalisation and recommendation of content in social environments.

【Keywords】:

【Abstract】: In recent years, many different types of intelligent mobile robots have been developed in research and industrial labs. Although there are significant differences in both hardware and software over these robots, many of them share a common set of AI capabilities, e.g., planning, learning, vision and natural language processing. At the same time, almost all of them are equipped with traditional robotic capabilities such as mapping, localization, and navigation. However, to date it has been difficult to compare and contrast their capabilities in any controlled way. The main goal of the Robot Scavenger Hunt is to provide a standardized framework that includes a set of standardized tasks for evaluating the AI and robotic capabilities of medium-sized intelligent mobile robots. Compared to existing benchmarks, e.g., RoboCup@Home, Robot Scavenger Hunt aims at evaluations in larger spaces (multi-floor buildings vs. rooms) over longer periods of time (hours vs.minutes) while interacting with real human residents.

【Keywords】:

25. IJCAI 2016:New York,NY,USA

Paper Num: 658 || Session Num: 2

Frontmatter 7

1. Preface.

2. Conference Organization.

3. Program Committee.

4. Conference Organizers and Sponsors.

5. Awards and Distinguished Papers.

6. IJCAI Organization.

7. Past IJCAI Conferences.

Papers 651

8. Interdependent Scheduling Games.

9. Scalable Greedy Algorithms for Task/Resource Constrained Multi-Agent Stochastic Planning.

10. Coco: Runtime Reasoning about Conflicting Commitments.

11. Verifying Existence of Resource-Bounded Coalition Uniform Strategies.

12. On Truthful Mechanisms for Maximin Share Allocations.

13. Modeling and Reasoning about NTU Games via Answer Set Programming.

14. Randomized Social Choice Functions under Metric Preferences.

15. Generalized Discrete Preference Games.

16. Computing Pareto Optimal Committees.

17. Control of Fair Division.

18. A Characterization of Voting Power for Discrete Weight Distributions.

19. Misrepresentation in District Voting.

20. Conditional and Sequential Approval Voting on Combinatorial Domains.

21. On Logics of Strategic Ability Based on Propositional Control.

22. Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels.

23. The Complexity of Playing Durak.

24. Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving.

25. To Give or Not to Give: Fair Division for Single Minded Valuations.

26. Pairwise Diffusion of Preference Rankings in Social Networks.

27. Facility Location with Minimax Envy.

28. Achieving Proportional Representation in Conference Programs.

29. Subset Selection via Implicit Utilitarian Voting.

30. Trading on a Rigged Game: Outcome Manipulation in Prediction Markets.

31. Congestion Games with Polytopal Strategy Spaces.

32. Robust Draws in Balanced Knockout Tournaments.

33. Verifying Pushdown Multi-Agent Systems against Strategy Logics.

34. Truthfulness of a Proportional Sharing Mechanism in Resource Exchange.

35. Better Strategyproof Mechanisms without Payments or Prior - An Analytic Approach.

36. Approximating Value Equivalence in Interactive Dynamic Influence Diagrams Using Behavioral Coverage.

37. Selective Norm Monitoring.

38. Elicitation for Preferences Single Peaked on Trees.

39. Preference Elicitation for Single Crossing Domain.

40. Complexity of Manipulation with Partial Information in Voting.

41. Strategic Voting with Incomplete Information.

42. Voting-Based Group Formation.

43. Committee Scoring Rules: Axiomatic Classification and Hierarchy.

44. How Hard Is It for a Party to Nominate an Election Winner?.

45. Digital Good Exchange.

46. Parallel Behavior Composition for Manufacturing.

47. Opinion Dynamics with Local Interactions.

48. Online Mechanism Design for Vehicle-to-Grid Car Parks.

49. Moving in a Crowd: Safe and Efficient Navigation among Heterogeneous Agents.

50. A Network-Based Rating System and Its Resistance to Bribery.

51. Three Strategies to Success: Learning Adversary Models in Security Games.

52. Reconfigurability in Reactive Multiagent Systems.

53. Probabilistic Matrix Inspection and Group Scheduling.

54. Catcher-Evader Games.

55. Asymptotically Tight Bounds for Inefficiency in Risk-Averse Selfish Routing.

56. Social Choice for Agents with General Utilities.

57. Incentivizing Reliability in Demand-Side Response.

58. Allocating Indivisible Items in Categorized Domains.

59. Correlated Voting.

60. Silk: A Simulation Study of Regulating Open Normative Multiagent Systems.

61. Incentivizing Intelligent Customer Behavior in Smart-Grids: A Risk-Sharing Tariff & Optimal Strategies.

62. Dynamic Auctions with Bank Accounts.

63. SLIM: Semi-Lazy Inference Mechanism for Plan Recognition.

64. Sequential Plan Recognition.

65. Distributed Decoupling of Multiagent Simple Temporal Problems.

66. Role Assignment for Game-Theoretic Cooperation.

67. Core-Selecting Payment Rules for Combinatorial Auctions with Uncertain Availability of Goods.

68. Automated Mechanism Design without Money via Machine Learning.

69. Trembling Hand Equilibria of Plurality Voting.

70. Distributed Breakout: Beyond Satisfaction.

71. Mission Oriented Robust Multi-Team Formation and Its Application to Robot Rescue Simulation.

72. Controlling Growing Tasks with Heterogeneous Agents.

73. Using Message-Passing DCOP Algorithms to Solve Energy-Efficient Smart Environment Configuration Problems.

74. An Online Mechanism for Ridesharing in Autonomous Mobility-on-Demand Systems.

75. Efficient Local Search in Coordination Games on Graphs.

76. Assigning a Small Agreeable Set of Indivisible Items to Multiple Players.