bluuebunny/crossref_metadata_2025 huggingface dataset:
Transferable Utility Planning Games
Authors: Brafman Ronen , Domshlak Carmel , Engel Yagil , Tennenholtz Moshe
Published: September 2022

Connecting between standard AI planning constructs and a classical cooperative model of transferable-utility coalition games, we introduce the notion of transferable-utility (TU) planning games. The key representational property of these games is that coalitions are valued implicitly based on their ability to carry out efficient joint plans. On the side of the expressiveness, we show that existing succinct representations of monotonic TU games can be efficiently compiled into TU planning games. On the side of computation, TU planning games allow us to provide some of the strongest to date tractability results for core-existence and core-membership queries in succinct TU coalition games.
Facilitating the Evaluation of Automated Negotiators using Peer Designed Agents
Authors: Lin Raz , Kraus Sarit , Oshrat Yinon , Gal Ya'akov (Kobi)
Published: September 2022

Computer agents are increasingly deployed in settings in which they make decisions with people, such as electronic commerce, collaborative interfaces, and cognitive assistants. However, the scientific evaluation of computational strategies for human-computer decision-making is a costly process, involving time, effort and personnel. This paper investigates the use of Peer Designed Agents (PDA) — computer agents developed by human subjects — as a tool for facilitating the evaluation process of automatic negotiators that were developed by researchers. It compared the performance between automatic negotiators that interacted with PDAs to automatic negotiators that interacted with actual people in different domains. The experiments included more than 300 human subjects and 50 PDAs developed by students. Results showed that the automatic negotiators outperformed PDAs in the same situations in which they outperformed people, and that on average, they exhibited the same measure of generosity towards their negotiation partners. These patterns were significant for all types of domains, and for all types of automated negotiators, despite the fact that there were individual differences between the behavior of PDAs and people. The study thus provides an empirical proof that PDAs can alleviate the evaluation process of automatic negotiators, and facilitate their design.
Facial Age Estimation by Learning from Label Distributions
Authors: Geng Xin , Smith-Miles Kate , Zhou Zhi-Hua
Published: September 2022

One of the main difficulties in facial age estimation is the lack of sufficient training data for many ages. Fortunately, the faces at close ages look similar since aging is a slow and smooth process. Inspired by this observation, in this paper, instead of considering each face image as an example with one label (age), we regard each face image as an example associated with a label distribution. The label distribution covers a number of class labels, representing the degree that each label describes the example. Through this way, in addition to the real age, one face image can also contribute to the learning of its adjacent ages. We propose an algorithm named IIS-LLD for learning from the label distributions, which is an iterative optimization process based on the maximum entropy model. Experimental results show the advantages of IIS-LLD over the traditional learning methods based on single-labeled data.
Nonparametric Curve Extraction Based on Ant Colony System
Authors: Tan Qing , He Qing , Shi Zhongzhi
Published: September 2022

Curve extraction is an important and basic technique in image processing and computer vision. Due to the complexity of the images and the limitation of segmentation algorithms, there are always a large number of noisy pixels in the segmented binary images. In this paper, we present an approach based on ant colony system (ACS) to detect nonparametric curves from a binary image containing discontinuous curves and noisy points. Compared with the well-known Hough transform (HT) method, the ACS-based curve extraction approach can deal with both regular and irregular curves without knowing their shapes in advance. The proposed approach has many characteristics such as faster convergence, implicit parallelism and strong ability to deal with highly-noised images. Moreover, our approach can extract multiple curves from an image, which is impossible for the previous genetic algorithm based approach. Experimental results show that the proposed ACS-based approach is effective and efficient.
Discovering Long Range Properties of Social Networks with Multi-Valued Time-Inhomogeneous Models
Authors: Wyatt Danny , Choudhury Tanzeem , Bilmes Jeff
Published: September 2022

The current methods used to mine and analyze temporal social network data make two assumptions: all edges have the same strength, and all parameters are time-homogeneous. We show that those assumptions may not hold for social networks and propose an alternative model with two novel aspects: (1) the modeling of edges as multi-valued variables that can change in intensity, and (2) the use of a curved exponential family framework to capture time-inhomogeneous properties while retaining a parsimonious and interpretable model. We show that our model outperforms traditional models on two real-world social network data sets.
Transductive Learning on Adaptive Graphs
Authors: Zhang Yan-Ming , Zhang Yu , Yeung Dit-Yan , Liu Cheng-Lin , Hou Xinwen
Published: September 2022

Graph-based semi-supervised learning methods are based on some smoothness assumption about the data. As a discrete approximation of the data manifold, the graph plays a crucial role in the success of such graph-based methods. In most existing methods, graph construction makes use of a predefined weighting function without utilizing label information even when it is available. In this work, by incorporating label information, we seek to enhance the performance of graph-based semi-supervised learning by learning the graph and label inference simultaneously. In particular, we consider a particular setting of semi-supervised learning called transductive learning. Using the LogDet divergence to define the objective function, we propose an iterative algorithm to solve the optimization problem which has closed-form solution in each step. We perform experiments on both synthetic and real data to demonstrate improvement in the graph and in terms of classification accuracy.
Efficient Spectral Feature Selection with Minimum Redundancy
Authors: Zhao Zheng , Wang Lei , Liu Huan
Published: September 2022

Spectral feature selection identifies relevant features by measuring their capability of preserving sample similarity. It provides a powerful framework for both supervised and unsupervised feature selection, and has been proven to be effective in many real-world applications. One common drawback associated with most existing spectral feature selection algorithms is that they evaluate features individually and cannot identify redundant features. Since redundant features can have significant adverse effect on learning performance, it is necessary to address this limitation for spectral feature selection. To this end, we propose a novel spectral feature selection algorithm to handle feature redundancy, adopting an embedded model. The algorithm is derived from a formulation based on a sparse multi-output regression with a L2,1-norm constraint. We conduct theoretical analysis on the properties of its optimal solutions, paving the way for designing an efficient path-following solver. Extensive experiments show that the proposed algorithm can do well in both selecting relevant features and removing redundancy.
The Induction and Transfer of Declarative Bias
Authors: Bridewell Will , Todorovski Ljupco
Published: September 2022

People constantly apply acquired knowledge to new learning tasks, but machines almost never do. Research on transfer learning attempts to address this dissimilarity. Working within this area, we report on a procedure that learns and transfers constraints in the context of inductive process modeling, which we review. After discussing the role of constraints in model induction, we describe the learning method, MISC, and introduce our metrics for assessing the cost and benefit of transferred knowledge. The reported results suggest that cross-domain transfer is beneficial in the scenarios that we investigated, lending further evidence that this strategy is a broadly effective means for increasing the efficiency of learning systems. We conclude by discussing the aspects of inductive process modeling that encourage effective transfer, by reviewing related strategies, and by describing future research plans for constraint induction and transfer learning.
The Genetic Algorithm as a General Diffusion Model for Social Networks
Authors: Lahiri Mayank , Cebrian Manuel
Published: September 2022

Diffusion processes taking place in social networks are used to model a number of phenomena, such as the spread of human or computer viruses, and the adoption of products in viral marketing campaigns. It is generally difficult to obtain accurate information about how such spreads actually occur, so a variety of stochastic diffusion models are used to simulate spreading processes in networks instead. We show that a canonical genetic algorithm with a spatially distributed population, when paired with specific forms of Holland's synthetic hyperplane-defined objective functions, can simulate a large and rich class of diffusion models for social networks. These include standard diffusion models, such as the Independent Cascade and Competing Processes models. In addition, our Genetic Algorithm Diffusion Model (GADM) can also model complex phenomena such as information diffusion. We demonstrate an application of the GADM to modeling information flow in a large, dynamic social network derived from e-mail headers.
Non-Metric Locality-Sensitive Hashing
Authors: Mu Yadong , Yan Shuicheng
Published: September 2022

Non-metric distances are often more reasonable compared with metric ones in terms of consistency with human perceptions. However, existing locality-sensitive hashing (LSH) algorithms can only support data which are gauged with metrics. In this paper we propose a novel locality-sensitive hashing algorithm targeting such non-metric data. Data in original feature space are embedded into an implicit reproducing kernel Krein space and then hashed to obtain binary bits. Here we utilize the norm-keeping property of p-stable functions to ensure that two data's collision probability reflects their non-metric distance in original feature space. We investigate various concrete examples to validate the proposed algorithm. Extensive empirical evaluations well illustrate its effectiveness in terms of accuracy and retrieval speedup.
A Topic Model for Linked Documents and Update Rules for its Estimation
Authors: Guo Zhen , Zhu Shenghuo , Zhang Zhongfei , Chi Yun , Gong Yihong
Published: September 2022

The latent topic model plays an important role in the unsupervised learning from a corpus, which provides a probabilistic interpretation of the corpus in terms of the latent topic space. An underpinning assumption which most of the topic models are based on is that the documents are assumed to be independent of each other. However, this assumption does not hold true in reality and the relations among the documents are available in different ways, such as the citation relations among the research papers. To address this limitation, in this paper we present a Bernoulli Process Topic (BPT) model, where the interdependence among the documents is modeled by a random Bernoulli process. In the BPT model a document is modeled as a distribution over topics that is a mixture of the distributions associated with the related documents. Although BPT aims at obtaining a better document modeling by incorporating the relations among the documents, it could also be applied to many applications including detecting the topics from corpora and clustering the documents. We apply the BPT model to several document collections and the experimental comparisons against several state-of-the-art approaches demonstrate the promising performance.
Interactive Learning Using Manifold Geometry
Authors: Eaton Eric , Holness Gary , McFarlane Daniel
Published: September 2022

We present an interactive learning method that enables a user to iteratively refine a regression model. The user examines the output of the model, visualized as the vertical axis of a 2D scatterplot, and provides corrections by repositioning individual data instances to the correct output level. Each repositioned data instance acts as a control point for altering the learned model, using the geometry underlying the data. We capture the underlying structure of the data as a manifold, on which we compute a set of basis functions as the foundation for learning. Our results show that manifold-based interactive learning improves performance monotonically with each correction, outperforming alternative approaches.
Gaussian Process Latent Random Field
Authors: Zhong Guoqiang , Li Wu-Jun , Yeung Dit-Yan , Hou Xinwen , Liu Cheng-Lin
Published: September 2022

In this paper, we propose a novel supervised extension of GPLVM, called Gaussian process latent random field (GPLRF), by enforcing the latent variables to be a Gaussian Markov random field with respect to a graph constructed from the supervisory information.
Multi-Label Learning with Weak Label
Authors: Sun Yu-Yin , Zhang Yin , Zhou Zhi-Hua
Published: September 2022

Multi-label learning deals with data associated with multiple labels simultaneously. Previous work on multi-label learning assumes that for each instance, the “full” label set associated with each training instance is given by users. In many applications, however, to get the full label set for each instance is difficult and only a “partial” set of labels is available. In such cases, the appearance of a label means that the instance is associated with this label, while the absence of a label does not imply that this label is not proper for the instance. We call this kind of problem “weak label” problem. In this paper, we propose the WELL (WEak Label Learning) method to solve the weak label problem. We consider that the classification boundary for each label should go across low density regions, and that each label generally has much smaller number of positive examples than negative examples. The objective is formulated as a convex optimization problem which can be solved efficiently. Moreover, we exploit the correlation between labels by assuming that there is a group of low-rank base similarities, and the appropriate similarities between instances for different labels can be derived from these base similarities. Experiments validate the performance of WELL.
Computationally Feasible Automated Mechanism Design: General Approach and Case Studies
Authors: Guo Mingyu , Conitzer Vincent
Published: September 2022

In many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the decision that work in spite of such strategic behavior, usually by making untruthful behavior suboptimal. In automated mechanism design, the idea is to computationally search through the space of feasible mechanisms, rather than to design them analytically by hand. Unfortunately, the most straightforward approach to automated mechanism design does not scale to large instances, because it requires searching over a very large space of possible functions. In this paper, we describe an approach to automated mechanism design that is computationally feasible. Instead of optimizing over all feasible mechanisms, we carefully choose a parameterized subfamily of mechanisms. Then we optimize over mechanisms within this family, and analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily. We demonstrate the usefulness of our approach with two case studies.
What Is an Opinion About? Exploring Political Standpoints Using Opinion Scoring Model
Authors: Chen Bi , Zhu Leilei , Kifer Daniel , Lee Dongwon
Published: September 2022

In this paper, we propose a generative model to automatically discover the hidden associations between topics words and opinion words. By applying those discovered hidden associations, we construct the opinion scoring models to extract statements which best express opinionists’ standpoints on certain topics. For experiments, we apply our model to the political area. First, we visualize the similarities and dissimilarities between Republican and Democratic senators with respect to various topics. Second, we compare the performance of the opinion scoring models with 14 kinds of methods to find the best ones. We find that sentences extracted by our opinion scoring models can effectively express opinionists’ standpoints.
Relative Entropy Policy Search
Authors: Peters Jan , Mulling Katharina , Altun Yasemin
Published: September 2022

Policy search is a successful approach to reinforcement learning. However, policy improvements often result in the loss of information. Hence, it has been marred by premature convergence and implausible solutions. As first suggested in the context of covariant policy gradients, many of these problems may be addressed by constraining the information loss. In this paper, we continue this path of reasoning and suggest the Relative Entropy Policy Search (REPS) method. The resulting method differs significantly from previous policy gradient approaches and yields an exact update step. It can be shown to work well on typical reinforcement learning benchmark problems.
g-Planner: Real-time Motion Planning and Global Navigation using GPUs
Authors: Pan Jia , Lauterbach Christian , Manocha Dinesh
Published: September 2022

We present novel randomized algorithms for solving global motion planning problems that exploit the computational capabilities of many-core GPUs. Our approach uses thread and data parallelism to achieve high performance for all components of sample-based algorithms, including random sampling, nearest neighbor computation, local planning, collision queries and graph search. The approach can efficiently solve both the multi-query and single-query versions of the problem and obtain considerable speedups over prior CPU-based algorithms. We demonstrate the efficiency of our algorithms by applying them to a number of 6DOF planning benchmarks in 3D environments. Overall, this is the first algorithm that can perform real-time motion planning and global navigation using commodity hardware.
Using Closed Captions as Supervision for Video Activity Recognition
Authors: Gupta Sonal , Mooney Raymond
Published: September 2022

Recognizing activities in real-world videos is a difficult problem exacerbated by background clutter, changes in camera angle & zoom, and rapid camera movements. Large corpora of labeled videos can be used to train automated activity recognition systems, but this requires expensive human labor and time. This paper explores how closed captions that naturally accompany many videos can act as weak supervision that allows automatically collecting "labeled" data for activity recognition. We show that such an approach can improve activity retrieval in soccer videos. Our system requires no manual labeling of video clips and needs minimal human supervision. We also present a novel caption classifier that uses additional linguistic information to determine whether a specific comment refers to an ongoing activity. We demonstrate that combining linguistic analysis and automatically trained activity recognizers can significantly improve the precision of video retrieval.
Relational Partially Observable MDPs
Authors: Wang Chenggang , Khardon Roni
Published: September 2022

Relational Markov Decision Processes (MDP) are a useful abstraction for stochastic planning problems since one can develop abstract solutions for them that are independent of domain size or instantiation. While there has been an increased interest in developing relational fully observable MDPs, there has been very little work on relational partially observable MDPs (POMDP), which deal with uncertainty in problem states in addition to stochastic action effects. This paper provides a concrete formalization of relational POMDPs making several technical contributions toward their solution. First, we show that to maintain correctness one must distinguish between quantification over states and quantification over belief states; this implies that solutions based on value iteration are inherently limited to the finite horizon case. Second, we provide a symbolic dynamic programing algorithm for finite horizon relational POMDPs, solving them at an abstract level, by lifting the propositional incremental pruning algorithm. Third, we show that this algorithm can be implemented using first order decision diagrams, a compact representation for functions over relational structures, that has been recently used to solve relational MDPs.
Structured Parameter Elicitation
Authors: Ko Li Ling , Hsu David , Lee Wee Sun , Ong Sylvie
Published: September 2022

The behavior of a complex system often depends on parameters whose values are unknown in advance. To operate effectively, an autonomous agent must actively gather information on the parameter values while progressing towards its goal. We call this problem parameter elicitation. Partially observable Markov decision processes (POMDPs) provide a principled framework for such uncertainty planning tasks, but they suffer from high computational complexity. However, POMDPs for parameter elicitation often possess special structural properties, specifically, factorization and symmetry. This work identifies these properties and exploits them for efficient solution through a factored belief representation. The experimental results show that our new POMDP solvers outperform SARSOP and MOMDP, two of the fastest general-purpose POMDP solvers available, and can handle significantly larger problems.
Probabilistic Plan Recognition Using Off-the-Shelf Classical Planners
Authors: Ramírez Miguel , Geffner Hector
Published: September 2022

Plan recognition is the problem of inferring the goals and plans of an agent after observing its behavior. Recently, it has been shown that this problem can be solved efficiently, without the need of a plan library, using slightly modified planning algorithms. In this work, we extend this approach to the more general problem of probabilistic plan recognition where a probability distribution over the set of goals is sought under the assumptions that actions have deterministic effects and both agent and observer have complete information about the initial state. We show that this problem can be solved efficiently using classical planners provided that the probability of a partially observed execution given a goal is defined in terms of the cost difference of achieving the goal under two conditions: complying with the observations, and not complying with them. This cost, and hence the posterior goal probabilities, are computed by means of two calls to a classical planner that no longer has to be modified in any way. A number of examples is considered to illustrate the quality, flexibility, and scalability of the approach.
Using Bisimulation for Policy Transfer in MDPs
Authors: Castro Pablo , Precup Doina
Published: September 2022

Knowledge transfer has been suggested as a useful approach for solving large Markov Decision Processes. The main idea is to compute a decision-making policy in one environment and use it in a different environment, provided the two are ”close enough”. In this paper, we use bisimulation-style metrics (Ferns et al., 2004) to guide knowledge transfer. We propose algorithms that decide what actions to transfer from the policy computed on a small MDP task to a large task, given the bisimulation distance between states in the two tasks. We demonstrate the inherent ”pessimism” of bisimulation metrics and present variants of this metric aimed to overcome this pessimism, leading to improved action transfer. We also show that using this approach for transferring temporally extended actions (Sutton et al., 1999) is more successful than using it exclusively with primitive actions. We present theoretical guarantees on the quality of the transferred policy, as well as promising empirical results.
Planning in Dynamic Environments: Extending HTNs with Nonlinear Continuous Effects
Authors: Molineaux Matthew , Klenk Matthew , Aha David
Published: September 2022

Planning in dynamic continuous environments requires reasoning about nonlinear continuous effects, which previous Hierarchical Task Network (HTN) planners do not support. In this paper, we extend an existing HTN planner with a new state projection algorithm. To our knowledge, this is the first HTN planner that can reason about nonlinear continuous effects. We use a wait action to instruct this planner to consider continuous effects in a given state. We also introduce a new planning domain to demonstrate the benefits of planning with nonlinear continuous effects. We compare our approach with a linear continuous effects planner and a discrete effects HTN planner on a benchmark domain, which reveals that its additional costs are largely mitigated by domain knowledge. Finally, we present an initial application of this algorithm in a practical domain, a Navy training simulation, illustrating the utility of this approach for planning in dynamic continuous environments.
DTProbLog: A Decision-Theoretic Probabilistic Prolog
Authors: Van den Broeck Guy , Thon Ingo , Van Otterlo Martijn , De Raedt Luc
Published: September 2022

We introduce DTProbLog, a decision-theoretic extension of Prolog and its probabilistic variant ProbLog. DTProbLog is a simple but expressive probabilistic programming language that allows the modeling of a wide variety of domains, such as viral marketing. In DTProbLog, the utility of a strategy (a particular choice of actions) is defined as the expected reward for its execution in the presence of probabilistic effects. The key contribution of this paper is the introduction of exact, as well as approximate, solvers to compute the optimal strategy for a DTProbLog program and the decision problem it represents, by making use of binary and algebraic decision diagrams.  We also report on experimental results that show the effectiveness and the practical usefulness of the approach.
On the Use of Prime Implicates in Conformant Planning
Authors: To Son , Son Tran , Pontelli Enrico
Published: September 2022

The paper presents an investigation of the use of two alternative forms of CNF formulae—prime implicates and minimal CNF—to compactly represent belief states in the context of conformant planning. For each representation, we define a transition function for computing the successor belief state resulting from the execution of an action in a belief state; results concerning soundness and completeness are provided. The paper describes a system (PIP) which dynamically selects either of these two forms to represent belief states, and an experimental evaluation of PIP against state-of-the-art conformant planners. The results show that PIP has the potential of scaling up better than other planners in problems rich in disjunctive information about the initial state.
The Model-Based Approach to Autonomous Behavior: A Personal View
Authors: Geffner Hector
Published: September 2022

The selection of the action to do next is one of the central problems faced by autonomous agents. In AI, three approaches have been used to address this problem: the programming-based approach, where the agent controller is given by the programmer, the learning-based approach, where the controller is induced from experience via a learning algorithm, and the model-based approach, where the controller is derived from a model of the problem. Planning in AI is best conceived as the model-based approach to action selection. The models represent the initial situation, actions, sensors, and goals. The main challenge in planning is computational, as all the models, whether accommodating feedback and uncertainty or not, are intractable in the worst case. In this article, I review some of the models considered in current planning research, the progress achieved in solving these models, and some of the open problems.
A Phrase-Based Method for Hierarchical Clustering of Web Snippets
Authors: Li Zhao , Wu Xindong
Published: September 2022

Document clustering has been applied in web information retrieval, which facilitates users’ quick browsing by organizing retrieved results into different groups. Meanwhile, a tree-like hierarchical structure is wellsuited for organizing the retrieved results in favor of web users. In this regard, we introduce a new method for hierarchical clustering of web snippets by exploiting a phrase-based document index. In our method, a hierarchy of web snippets is built based on phrases instead of all snippets, and the snippets are then assigned to the corresponding clusters consisting of phrases. We show that, as opposed to the traditional hierarchical clustering, our method not only presents meaningful cluster labels but also improves clustering performance.
Relational Reinforcement Learning in Infinite Mario
Authors: Mohan Shiwali , Laird John
Published: September 2022

Relational representations in reinforcement learning allow for the use of structural information like the presence of objects and relationships between them in the description of value functions. Through this paper, we show that such representations allow for the inclusion of background knowledge that qualitatively describes a state and can be used to design agents that demonstrate learning behavior in domains with large state and actions spaces such as computer games.
Genome Rearrangement: A Planning Approach
Authors: Uras Tansel , Erdem Esra
Published: September 2022

Evolutionary trees of species can be reconstructed by pairwise comparison of their entire genomes. Such a comparison can be quantified by determining the number of events that change the order of genes in a genome. Earlier Erdem and Tillier formulated the pairwise comparison of entire genomes as the problem of planning rearrangement events that transform one genome to the other. We reformulate this problem as a planning problem to extend its applicability to genomes with multiple copies of genes and with unequal gene content, and illustrate its applicability and effectiveness on three real datasets: mitochondrial genomes of Metazoa, chloroplast genomes of Campanulaceae, chloroplast genomes of various land plants and green algae.
Policy Gradient Planning for Environmental Decision Making with Existing Simulators
Authors: Crowley Mark , Poole David
Published: September 2022

In environmental and natural resource planning domains actions are taken at a large number of locations over multiple time periods. These problems have enormous state and action spaces, spatial correlation between actions, uncertainty and complex utility models. We present an approach for modeling these planning problems as factored Markov decision processes. The reward model can contain local and global components as well as spatial constraints between locations. The transition dynamics can be provided by existing simulators developed by domain experts. We propose a landscape policy defined as the equilibrium distribution of a Markov chain built from many locally-parameterized policies. This policy is optimized using a policy gradient algorithm. Experiments using a forestry simulator demonstrate the algorithm's ability to devise policies for sustainable harvest planning of a forest.
Green Driver: AI in a Microcosm
Authors: Apple Jim , Chang Paul , Clauson Aran , Dixon Heidi , Fakhoury Hiba , Ginsberg Matthew , Keenan Erin , Leighton Alex , Scavezze Kevin , Smith Bryan
Published: September 2022

The Green Driver app is a dynamic routing application for GPS-enabled smartphones. Green Driver combines client GPS data with real-time traffic light information provided by cities to determine optimal routes in response to driver route requests. Routes are optimized with respect to travel time, with the intention of saving the driver both time and fuel, and rerouting can occur if warranted. During a routing session, client phones communicate with a centralized server that both collects GPS data and processes route requests. All relevant data are anonymized and saved to databases for analysis; statistics are calculated from the aggregate data and fed back to the routing engine to improve future routing. Analyses can also be performed to discern driver trends: where do drivers tend to go, how long do they stay, when and where does traffic congestion occur, and so on. The system uses a number of techniques from the field of artificial intelligence. We apply a variant of A* search for solving the stochastic shortest path problem in order to find optimal driving routes through a network of roads given light-status information. We also use dynamic programming and hidden Markov models to determine the progress of a driver through a network of roads from GPS data and light-status data. The Green Driver system is currently deployed for testing in Eugene, Oregon, and is scheduled for large-scale deployment in Portland, Oregon, in Spring 2011.
Verifying Intervention Policies to Counter Infection Propagation over Networks: A Model Checking Approach
Authors: Santhanam Ganesh Ram , Suvorov Yuly , Basu Samik , Honavar Vasant
Published: September 2022

Spread of infections (diseases, ideas, etc.) in a networkcan be modeled as the evolution of states of nodes ina graph as a function of the states of their neighbors.Given an initial configuration of a network in which asubset of the nodes have been infected, and an infectionpropagation function that specifies how the states ofthe nodes evolve over time, we show how to use modelchecking to identify, verify, and evaluate the effectivenessof intervention policies for containing the propagationof infection over such networks.
Enforcing Liveness in Autonomous Traffic Management
Authors: Au Tsz-Chiu , Shahidi Neda , Stone Peter
Published: September 2022

Looking ahead to the time when autonomous cars will be common, Dresner and Stone proposed a multiagent systems-based intersection control protocol called Autonomous Intersection Management (AIM). They showed that by leveraging the capacities of autonomous vehicles it is possible to dramatically reduce the time wasted in traffic, and therefore also fuel consumption and air pollution. The proposed protocol, however, handles reservation requests one at a time and does not prioritize reservations according to their relative priorities and waiting times, causing potentially large inequalities in granting reservations. For example, at an intersection between a main street and an alley, vehicles from the alley can take an excessively long time to get reservations to enter the intersection, causing a waste of time and fuel. The same is true in a network of intersections, in which gridlock may occur and cause traffic congestion. In this paper, we introduce the batch processing of reservations in AIM to enforce liveness properties in intersections and analyze the conditions under which no vehicle will get stuck in traffic. Our experimental results show that our prioritizing schemes outperform previous intersection control protocols in unbalanced traffic.
Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models
Authors: Kask Kalev , Gelfand Andrew , Otten Lars , Dechter Rina
Published: September 2022

We study iterative randomized greedy algorithms for generating (elimination) orderings with small induced width and state space size — two parameters known to bound the complexity of inference in graphical models. We propose and implement the Iterative Greedy Variable Ordering (IGVO) algorithm, a new variant within this algorithm class. An empirical evaluation using different ranking functions and conditions of randomness, demonstrates that IGVO finds significantly better orderings than standard greedy ordering implementations when evaluated within an anytime framework. Additional order of magnitude improvements are demonstrated on a multi-core system, thus further expanding the set of solvable graphical models. The experiments also confirm the superiority of the MinFill heuristic within the iterative scheme.
Spectrum-Based Sequential Diagnosis
Authors: Gonzalez-Sanchez Alberto , Abreu Rui , Gross Hans-Gerhard , Van Gemund Arjan J. C.
Published: September 2022

We present a spectrum-based, sequential software debugging approach coined Sequoia, that greedily selects tests out of a suite of tests to narrow down the set of diagnostic candidates with a minimum number of tests. Sequoia handles multiple faults, that can be intermittent, at polynomial time and space complexity, due to a novel, approximate diagnostic entropy estimation approach, which considers the subset of diagnoses that cover almost all Bayesian posterior probability mass. Synthetic experiments show that Sequoia achieves much better diagnostic uncertainty reduction compared to random test sequencing.Real programs, taken from the Software Infrastructure Repository, confirm Sequoia's better performance, with a test reduction up to 80% compared to random test sequences.
A Semantical Account of Progression in the Presence of Uncertainty
Authors: Belle Vaishak , Lakemeyer Gerhard
Published: September 2022

Building on a general theory of action by Reiter and his colleagues, Bacchus et al. give an account for formalizing degrees of belief and noisy actions in the situation calculus. Unfortunately, there is no clear solution to the projection problem for the formalism. And, while the model has epistemic features, it is not obvious what the agent's knowledge base should look like. Also, reasoning about uncertainty essentially resorts to second-order logic. In recent work, Gabaldon and Lakemeyer remedy these shortcomings somewhat, but here too the utility seems to be restricted to queries (with action operators) about the initial theory. In this paper, we propose a fresh amalgamation of a modal fragment of the situation calculus and uncertainty, where the idea will be to update the initial knowledge base, containing both ordinary and (certain kinds of) probabilistic beliefs, when noisy actions are performed. We show that the new semantics has the right properties, and study a special case where updating probabilistic beliefs is computable. Our ideas are closely related to the Lin and Reiter notion of progression.
Risk-Averse Strategies for Security Games with Execution and Observational Uncertainty
Authors: Yin Zhengyu , Jain Manish , Tambe Milind , Ordóñez Fernando
Published: September 2022

Attacker-defender Stackelberg games have become a popular game-theoretic approach for security with deployments for LAX Police, the FAMS and the TSA. Unfortunately, most of the existing solution approaches do not model two key uncertainties of the real-world: there may be noise in the defender's execution of the suggested mixed strategy and/or the observations made by an attacker can be noisy. In this paper, we provide a framework to model these uncertainties, and demonstrate that previous strategies perform poorly in such uncertain settings. We also provide RECON, a novel algorithm that computes strategies for the defender that are robust to such uncertainties, and provide heuristics that further improve RECON's efficiency.
A Kernel-Based Iterative Combinatorial Auction
Authors: Lahaie Sebastien
Published: September 2022

This paper describes an iterative combinatorial auction for single-minded bidders that offers modularity in the choice of price structure, drawing on ideas from kernel methods and the primal-dual paradigm of auction design. In our implementation, the auction is able to automatically detect, as the rounds progress, whether price expressiveness must be increased to clear the market. The auction also features a configurable step size which can be tuned to trade-off between monotonicity in prices and the number of bidding rounds, with no impact on efficiency. An empirical evaluation against a state of the art ascending-price auction demonstrates the performance gains that can be obtained in efficiency, revenue, and rounds to convergence through various configurations of our design.
Dominating Manipulations in Voting with Partial Information
Authors: Conitzer Vincent , Walsh Toby , Xia Lirong
Published: September 2022

We consider manipulation problems when the manipulator only has partial information about the votes of the non-manipulators. Such partial information is described by an {\em information set}, which is the set of profiles of the non-manipulators that are indistinguishable to the manipulator. Given such an information set, a {\em dominating manipulation} is a non-truthful vote that the manipulator can cast which makes the winner at least as preferable (and sometimes more preferable) as the winner when the manipulator votes truthfully. When the manipulator has full information, computing whether or not there exists a dominating manipulation is in P for many common voting rules (by known results). We show that when the manipulator has no information, there is no dominating manipulation for many common voting rules. When the manipulator's information is represented by partial orders and only a small portion of the preferences are unknown, computing a dominating manipulation is NP-hard for many common voting rules. Our results thus throw light on whether we can prevent strategic behavior by limiting information about the votes of other voters.
VCG Redistribution with Gross Substitutes
Authors: Guo Mingyu
Published: September 2022

For the problem of allocating resources among multiple strategic agents, the well-known Vickrey-Clarke-Groves (VCG) mechanism is efficient, strategy-proof, and it never incurs a deficit. However, in general, under the VCG mechanism, payments flow out of the system of agents, which reduces the agents' utilities. VCG redistribution mechanisms aim to return as much of the VCG payments as possible back to the agents, without affecting the desirable properties of the VCG mechanism. Most previous research on VCG redistribution mechanisms has focused on settings with homogeneous items and/or settings with unit-demand agents. In this paper, we study VCG redistribution mechanisms in the more general setting of combinatorial auctions. We show that when the gross substitutes condition holds, we are able to design mechanisms that guarantee to redistribute a large fraction of the VCG payments.
Size Adaptive Selection of Most Informative Features
Authors: Liu Si , Liu Hairong , Latecki Longin Jan , Yan Shuicheng , Xu Changsheng , Lu Hanqing
Published: September 2022

In this paper, we propose a novel method to select the most informativesubset of features, which has little redundancy andvery strong discriminating power. Our proposed approach automaticallydetermines the optimal number of features and selectsthe best subset accordingly by maximizing the averagepairwise informativeness, thus has obvious advantage overtraditional filter methods. By relaxing the essential combinatorialoptimization problem into the standard quadratic programmingproblem, the most informative feature subset canbe obtained efficiently, and a strategy to dynamically computethe redundancy between feature pairs further greatly acceleratesour method through avoiding unnecessary computationsof mutual information. As shown by the extensive experiments,the proposed method can successfully select the mostinformative subset of features, and the obtained classificationresults significantly outperform the state-of-the-art results onmost test datasets.
OASIS: Online Active Semi-Supervised Learning
Authors: Goldberg Andrew , Zhu Xiaojin , Furger Alex , Xu Jun-Ming
Published: September 2022

We consider a learning setting of importance to large scale machine learning: potentially unlimited data arrives sequentially, but only a small fraction of it is labeled. The learner cannot store the data; it should learn from both labeled and unlabeled data, and it may also request labels for some of the unlabeled items. This setting is frequently encountered in real-world applications and has the characteristics of online, semi-supervised, and active learning. Yet previous learning models fail to consider these characteristics jointly. We present OASIS, a Bayesian model for this learning setting. The main contributions of the model include the novel integration of a semi-supervised likelihood function, a sequential Monte Carlo scheme for efficient online Bayesian updating, and a posterior-reduction criterion for active learning. Encouraging results on both synthetic and real-world optical character recognition data demonstrate the synergy of these characteristics in OASIS.
Localized K-Flats
Authors: Wang Yong , Jiang Yuan , Wu Yi , Zhou Zhi-Hua
Published: September 2022

K-flats is a model-based linear manifold clustering algorithm which has been successfully applied in many real-world scenarios. Though some previous works have shown that K-flats doesn’t always provide good performance, little effort has been devoted to analyze its inherent deficiency. In this paper, we address this challenge by showing that the deteriorative performance of K-flats can be attributed to the usual reconstruction error measure and the infinitely extending representations of linear models. Then we propose Localized K-flats algorithm (LKF), which introduces localized representations of linear models and a new distortion measure, to remove confusion among different clusters. Experiments on both synthetic and real-world data sets demonstrate the efficiency of the proposed algorithm. Moreover, preliminary experiments show that LKF has the potential to group manifolds with nonlinear structure.
Transfer Latent Semantic Learning: Microblog Mining with Less Supervision
Authors: Zhang Dan , Liu Yan , Lawrence Richard , Chenthamarakshan Vijil
Published: September 2022

The increasing volume of information generated on micro-blogging sites such as Twitter raises several challenges to traditional text mining techniques. First, most texts from those sites are abbreviated due to the constraints of limited characters in one post; second, the input usually comes in streams of large-volumes. Therefore, it is of significant importance to develop effective and efficient representations of abbreviated texts for better filtering and mining. In this paper, we introduce a novel transfer learning approach, namely transfer latent semantic learning, that utilizes a large number of related tagged documents with rich information from other sources (source domain) to help build a robust latent semantic space for the abbreviated texts (target domain). This is achieved by simultaneously minimizing the document reconstruction error and the classification error of the labeled examples from the source domain by building a classifier with hinge loss in the latent semantic space. We demonstrate the effectiveness of our method by applying them to the task of classifying and tagging abbreviated texts. Experimental results on both synthetic datasets and real application datasets, including Reuters-21578 and Twitter data, suggest substantial improvements using our approach over existing ones.