bluuebunny/crossref_metadata_2025 huggingface dataset:
Variable-Deletion Backdoors to Planning
Authors: Kronegger Martin , Ordyniak Sebastian , Pfandler Andreas
Published: June 2022

Backdoors are a powerful tool to obtain efficient algorithms for hard problems. Recently, two new notions of backdoors to planning were introduced. However, for one of the new notions (i.e., variable-deletion) only hardness results are known so far. In this work we improve the situation by defining a new type of variable-deletion backdoors based on the extended causal graph of a planning instance. For this notion of backdoors several fixed-parameter tractable algorithms are identified. Furthermore, we explore the capabilities of polynomial time preprocessing, i.e., we check whether there exists a polynomial kernel. Our results also show the close connection between planning and verification problems such as Vector Addition System with States (VASS).
Exploiting Submodular Value Functions for Faster Dynamic Sensor Selection
Authors: Satsangi Yash , Whiteson Shimon , Oliehoek Frans
Published: June 2022

A key challenge in the design of multi-sensor systems is the efficient allocation of scarce resources such as bandwidth, CPU cycles, and energy, leading to the dynamic sensor selection problem in which a subset of the available sensors must be selected at each timestep. While partially observable Markov decision processes (POMDPs) provide a natural decision-theoretic model for this problem, the computational cost of POMDP planning grows exponentially in the number of sensors, making it feasible only for small problems. We propose a new POMDP planning method that uses greedy maximization to greatly improve scalability in the number of sensors. We show that, under certain conditions, the value function of a dynamic sensor selection POMDP is submodular and use this result to bound the error introduced by performing greedy maximization. Experimental results on a real-world dataset from a multi-camera tracking system in a shopping mall show it achieves similar performance to existing methods but incurs only a fraction of the computational cost, leading to much better scalability in the number of cameras.
From Non-Negative to General Operator Cost Partitioning
Authors: Pommerening Florian , Helmert Malte , Röger Gabriele , Seipp Jendrik
Published: June 2022

Operator cost partitioning is a well-known technique to make admissible heuristics additive by distributing the operator costs among individual heuristics. Planning tasks are usually defined with non-negative operator costs and therefore it appears natural to demand the same for the distributed costs. We argue that this requirement is not necessary and demonstrate the benefit of using general cost partitioning. We show that LP heuristics for operator-counting constraints are cost-partitioned heuristics and that the state equation heuristic computes a cost partitioning over atomic projections. We also introduce a new family of potential heuristics and show their relationship to general cost partitioning.
Bayesian Networks Specified Using Propositional and Relational Constructs: Combined, Data, and Domain Complexity
Authors: Cozman Fabio , Maua Denis
Published: June 2022

We examine the inferential complexity of Bayesian networks specified through logical constructs. We first consider simple propositional languages, and then move to relational languages. We examine both the combined complexity of inference (as network size and evidence size are not bounded) and the data complexity of inference (where network size is bounded); we also examine the connection to liftability through domain complexity. Combined and data complexity of several inference problems are presented, ranging from polynomial to exponential classes.
Optimal Cost Almost-Sure Reachability in POMDPs
Authors: Chatterjee Krishnendu , Chmelik Martin , Gupta Raghav , Kanodia Ayush
Published: June 2022

We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objective we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest.
An Improved Lower Bound for Bayesian Network Structure Learning
Authors: Fan Xiannian , Yuan Changhe
Published: June 2022

Several heuristic search algorithms such as A* and breadth-first branch and bound have been developed for learning Bayesian network structures that optimize a scoring function. These algorithms rely on a lower bound function called k-cycle conflict heuristic in guiding the search to explore the most promising search spaces. The heuristic takes as input a partition of the random variables of a data set; the importance of the partition opens up opportunities for further research. This work introduces a new partition method based on information extracted from the potential optimal parent sets (POPS) of the variables. Empirical results show that the new partition can significantly improve the efficiency and scalability of heuristic search-based structure learning algorithms.
Knowledge-Based Probabilistic Logic Learning
Authors: Odom Phillip , Khot Tushar , Porter Reid , Natarajan Sriraam
Published: June 2022

Advice giving has been long explored in artificial intelligence to build robust learning algorithms. We consider advice giving in relational domains where the noise is systematic. The advice is provided as logical statements that are then explicitly considered by the learning algorithm at every update. Our empirical evidence proves that human advice can effectively accelerate learning in noisy structured domains where so far humans have been merely used as labelers or as designers of initial structure of the model.
Stable Model Counting and Its Application in Probabilistic Logic Programming
Authors: Aziz Rehan , Chu Geoffrey , Muise Christian , Stuckey Peter
Published: June 2022

Model counting is the problem of computing the number of models that satisfy a given propositional theory. It has recently been applied to solving inference tasks in probabilistic logic programming, where the goal is to compute the probability of given queries being true provided a set of mutually independent random variables, a model (a logic program) and some evidence. The core of solving this inference task involves translating the logic program to a propositional theory and using a model counter. In this paper, we show that for some problems that involve inductive definitions like reachability in a graph, the translation of logic programs to SAT can be expensive for the purpose of solving inference tasks. For such problems, direct implementation of stable model semantics allows for more efficient solving. We present two implementation techniques, based on unfounded set detection, that extend a propositional model counter to a stable model counter. Our experiments show that for particular problems, our approach can outperform a state-of-the-art probabilistic logic programming solver by several orders of magnitude in terms of running time and space requirements, and can solve instances of significantly larger sizes on which the current solver runs out of time or memory.
Chance-Constrained Scheduling via Conflict-Directed Risk Allocation
Authors: Wang Andrew , Williams Brian
Published: June 2022

Temporal uncertainty in large-scale logistics forces one to trade off between lost efficiency through built-in slack and costly replanning when deadlines are missed. Due to the difficulty of reasoning about such likelihoods and consequences, a computational framework is needed to quantify and bound the risk of violating scheduling requirements. This work addresses the chance-constrained scheduling problem, where actions' durations are modeled probabilistically. Our solution method uses conflict-directed risk allocation to efficiently compute a scheduling policy. The key insight, compared to previous work in probabilistic scheduling, is to decouple the reasoning about temporal and risk constraints. This decomposes the problem into a separate master and subproblem, which can be iteratively solved much quicker. Through a set of simulated car-sharing scenarios, it is empirically shown that conflict-directed risk allocation computes solutions nearly an order of magnitude faster than prior art, which considers all constraints in a single lump-sum optimization.
Better Be Lucky than Good: Exceeding Expectations in MDP Evaluation
Authors: Keller Thomas , Geißer Florian
Published: June 2022

We introduce the MDP-Evaluation Stopping Problem, the optimization problem faced by participants of the International Probabilistic Planning Competition 2014 that focus on their own performance. It can be constructed as a meta-MDP where actions correspond to the application of a policy on a base-MDP, which is intractable in practice. Our theoretical analysis reveals that there are tractable special cases where the problem can be reduced to an optimal stopping problem. We derive approximate strategies of high quality by relaxing the general problem to an optimal stopping problem, and show both theoretically and experimentally that it not only pays off to pursue luck in the execution of the optimal policy, but that there are even cases where it is better to be lucky than good as the execution of a suboptimal base policy is part of an optimal strategy in the meta-MDP.
Coupled Collaborative Filtering for Context-aware Recommendation
Authors: Jiang Xinxin , Liu Wei , Cao Longbing , Long Guodong
Published: June 2022

Context-aware features have been widely recognized as important factors in recommender systems. However, as a major technique in recommender systems, traditional Collaborative Filtering (CF) does not provide a straight-forward way of integrating the context-aware information into personal recommendation. We propose a Coupled Collaborative Filtering (CCF) model to measure the contextual information and use it to improve recommendations. In the proposed approach, coupled similarity computation is designed to be calculated by interitem, intra-context and inter-context interactions among item, user and context-ware factors. Experiments based on different types of CF models demonstrate the effectiveness of our design.
Combining Ontology Class Expression Generation with Mathematical Modeling for Ontology Learning
Authors: Potoniec Jedrzej , Ławrynowicz Agnieszka
Published: June 2022

We present an idea of using mathematicall modelling to guide a process of mining a set of patterns in an RDF graph and further exploiting these patterns to build expressive OWL class hierarchies.
Self-Organized Collective Decision-Making in a 100-Robot Swarm
Authors: Valentini Gabriele , Hamann Heiko , Dorigo Marco
Published: June 2022

We study a self-organized collective decision-making strategy to solve a site-selection problem using a swarm of simple robots. Robots can only move forward or turn in place; sense the intensity of the ambient light; and exchange 3-byte messages with peers in a limited range. The goal of the swarm is to collectively decide which of the sites available in the environment is the best candidate site. We define a distributed and iterative decision-making strategy: robots explore the available options, determine the options' qualities, decide autonomously which option to take, and communicate their decision to neighboring robots. We study the effectiveness and robustness of the proposed strategy using a swarm of 100 Kilobots and we focus on the impact of the neighborhood size over the dynamics of the system.
"Is It Rectangular?" Using I Spy as an Interactive, Game-Based Approach to Multimodal Robot Learning
Authors: Parde Natalie , Papakostas Michalis , Tsiakas Konstantinos , Nielsen Rodney
Published: June 2022

Training robots about the objects in their environment requires a multimodal correlation of features extracted from visual and linguistic sources.  This work abstracts the task of collecting multimodal training data for object and feature learning by encapsulating it in an interactive game, I Spy, played between human players and robots.  It introduces the concept of the game, briefly describes its methodology, and finally presents an evaluation of the game's performance and its appeal to human players.
A Multi-Pass Sieve for Name Normalization
Authors: D'Souza Jennifer
Published: June 2022

We propose a simple multi-pass sieve framework that applies tiers of deterministic normalization modules one at a time from highest to lowest precision for the task of normalizing names. While a sieve based architecture has been shown effective in coreference resolution, it has not yet been applied to the normalization task. We find that even in this task, the approach retains its characteristic features of being simple, and highly modular. In addition, it also proves robust when evaluated on two different kinds of data: clinical notes and biomedical text, by demonstrating high accuracy in normalizing disorder names found in both datasets.
A Goal-Based Model of Personality for Planning-Based Narrative Generation
Authors: Bahamon Julio , Barot Camille , Young R. Michael
Published: June 2022

We present an approach to incorporate interesting and compelling characters in planning-based narrative generation. The approach is based on a computational model that utilizes character actions to portray these as having distinct and well-defined personalities.
What Is the Longest River in the USA? Semantic Parsing for Aggregation Questions
Authors: Xu Kun , Zhang Sheng , Feng Yansong , Huang Songfang , Zhao Dongyan
Published: June 2022

Answering natural language questions against structured knowledge bases (KB) has been attracting increasing attention in both IR and NLP communities. The task involves two main challenges: recognizing the questions' meanings, which are then grounded to a given KB. Targeting simple factoid questions, many existing open domain semantic parsers jointly solve these two subtasks, but are usually expensive in complexity and resources.In this paper, we propose a simple pipeline framework to efficiently answer more complicated questions, especially those implying aggregation operations, e.g., argmax, argmin.We first develop a transition-based parsing model to recognize the KB-independent meaning representation of the user's intention inherent in the question. Secondly, we apply a probabilistic model to map the meaning representation, including those aggregation functions, to a structured query.The experimental results showed that our method can better understand aggregation questions, outperforming the state-of-the-art methods on the Free917 dataset while still maintaining promising performance on a more challenging dataset, WebQuestions, without extra training.
Planning with Numeric Timed Initial Fluents
Authors: Piacentini Chiara , Fox Maria , Long Derek
Published: June 2022

Numeric Timed Initial Fluents represent a new feature in PDDL that extends the concept of Timed Initial Literals to numeric fluents. They are particularly useful to model independent functions that change through time and influence the actions to be applied. Although they are very useful to model real world problems, they are not systematically defined in the family of PDDL languages and they are not implemented in any generic PDDL planner, except for POPF2 and UPMurphi. In this paper we present an extension of the planner POPF2 (POPF-TIF) to handle problems with numeric Timed Initial Fluents. We propose and evaluate two contributions: the first is based on improvements of the heuristic evaluation, while the second considers alternative search algorithms based on a mixture of Enforced Hill Climbing and Best First Search.
Active Learning for Informative Projection Retrieval
Authors: Fiterau Madalina , Dubrawski Artur
Published: June 2022

We introduce an active learning framework designed to train classification models which use informative projections. Our approach works with the obtained low-dimensional models in finding unlabeled data for annotation by experts. The advantage of our approach is that the labeling effort is expended mainly on samples which benefit models from the considered hypothesis class. This results in an improved learning rate over standard selection criteria for data from the clinical domain.
Representation Discovery for MDPs Using Bisimulation Metrics
Authors: Ruan Sherry , Comanici Gheorghe , Panangaden Prakash , Precup Doina
Published: June 2022

We provide a novel, flexible, iterative refinement algorithm to automatically construct an approximate statespace representation for Markov Decision Processes (MDPs). Our approach leverages bisimulation metrics, which have been used in prior work to generate features to represent the state space of MDPs.We address a drawback of this approach, which is the expensive computation of the bisimulation metrics. We propose an algorithm to generate an iteratively improving sequence of state space partitions. Partial metric computations guide the representation search and provide much lower space and computational complexity, while maintaining strong convergence properties. We provide theoretical results guaranteeing convergence as well as experimental illustrations of the accuracy and savings (in time and memory usage) of the new algorithm, compared to traditional bisimulation metric computation.
SAT-Based Strategy Extraction in Reachability Games
Authors: Een Niklas , Legg Alexander , Narodytska Nina , Ryzhyk Leonid
Published: June 2022

Reachability games are a useful formalism for the synthesis of reactive systems. Solving a reachability game involves (1) determining the winning player and (2) computing a winning strategy that determines the winning player's action in each state of the game. Recently, a new family of game solvers has been proposed, which rely on counterexample-guided search to compute winning sequences of actions represented as an abstract game tree. While these solvers have demonstrated promising performance in solving the winning determination problem, they currently do not support strategy extraction. We present the first strategy extraction algorithm for abstract game tree-based game solvers. Our algorithm performs SAT encoding of the game abstraction produced by the winner determination algorithm and uses interpolation to compute the strategy. Our experimental results show that our approach performs well on a number of software synthesis benchmarks.
Semantic Representation
Authors: Schubert Lenhart
Published: June 2022

In recent years, there has been renewed interest in the NLP community in genuine language understanding and dialogue. Thus the long-standing issue of how the semantic content of language should be represented is reentering the communal discussion. This paper provides a brief "opinionated survey" of broad-coverage semantic representation (SR). It suggests multiple desiderata for such representations, and then outlines more than a dozen approaches to SR — some long-standing, and some more recent, providing quick characterizations, pros, cons, and some comments on implementations.
Impact of Modeling Languages on the Theory and Practice in Planning Research
Authors: Rintanen Jussi
Published: June 2022

We propose revisions to the research agenda in Automated Planning. The proposal is based on a review of the role of the Planning Domain Definition Language (PDDL) in the activities of the AI planning community and the impact of PDDL on parts of its research agenda. We specifically show how specific properties of PDDL have impacted research on planning, by putting emphasis on certain research topics and complicating others. We argue that the development of more advanced modeling languages would be — analogously to the impact PDDL has had — a low overhead and smooth route for the ICAPS community shift its research focus to increasingly promising and relevant research topics.
Emerging Architectures for Global System Science
Authors: Milano Michela , Van Hentenryck Pascal
Published: June 2022

Our society is organized around a number of (interdependent) global systems. Logistic and supply chains, health services, energy networks, financial markets, computer networks, and cities are just a few examples of such global, complex systems. These global systems are socio-technical and involve interactions between complex infrastructures, man-made processes, natural phenomena, multiple stakeholders, and human behavior. For the first time in the history of manking, we have access to data sets of unprecedented scale and accuracy about these infrastructures, processes, natural phenomena, and human behaviors. In addition, progress in high-performancing computing, data mining, machine learning, and decision support opens the possibility of looking at these problems more holistically, capturing many of these aspects simultaneously. This paper addresses emergent architectures enabling controlling, predicting and reaoning on these systems.
Explaining Watson: Polymath Style
Authors: Zadrozny Wlodek , De Paiva Valeria , Moss Lawrence
Published: June 2022

Our paper is actually two contributions in one. First, we argue that IBM's Jeopardy! playing machine needs a formal semantics. We present several arguments as we discuss the system. We also situate the work in the broader context of contemporary AI. Our second point is that the work in this area might well be done as a broad collaborative project. Hence our "Blue Sky'' contribution is a proposal to organize a polymath-style effort aimed at developing formal tools for the study of state of the art question-answer systems, and other large scale NLP efforts whose architectures and algorithms lack a theoretical foundation.
Cerebella: Automatic Generation of Nonverbal Behavior for Virtual Humans
Authors: Lhommet Margot , Xu Yuyu , Marsella Stacy
Published: June 2022

Our method automatically generates realistic nonverbal performances for virtual characters to accompany spo- ken utterances. It analyses the acoustic, syntactic, se- mantic and rhetorical properties of the utterance text and audio signal to generate nonverbal behavior such as such as head movements, eye saccades, and novel gesture animations based on co-articulation.
LOL — Laugh Out Loud
Authors: Pecune Florian , Biancardi Beatrice , Ding Yu , Pelachaud Catherine , Mancini Maurizio , Varni Giovanna , Camurri Antonio , Volpe Gualtiero
Published: June 2022

In our demo, LoL, a user interacts with a virtual agentable to copy and to adapt its laughing and expressive behaviorson-the-fly. Our aim is to study copying capabilitiesparticipate in enhancing user’s experience in the interaction.User listens to funny audio stimuli in the presenceof a laughing agent: when funniness of audio increases, theagent laughs and the quality of its body movement (directionand amplitude of laughter movements) is modulated on-theflyby user’s body features.
Metric Learning Driven Multi-Task Structured Output Optimization for Robust Keypoint Tracking
Authors: Zhao Liming , Li Xi , Xiao Jun , Wu Fei , Zhuang Yueting
Published: June 2022

As an important and challenging problem in computer vision and graphics, keypoint-based object tracking is typically formulated in a spatio-temporal statistical learning framework. However, most existing keypoint trackers are incapable of effectively modeling and balancing the following three aspects in a simultaneous manner: temporal model coherence across frames, spatial model consistency within frames, and discriminative feature construction. To address this issue, we propose a robust keypoint tracker based on spatio-temporal multi-task structured output optimization driven by discriminative metric learning. Consequently, temporal model coherence is characterized by multi-task structured keypoint model learning over several adjacent frames, while spatial model consistency is modeled by solving a geometric verification based structured learning problem. Discriminative feature construction is enabled by metric learning to ensure the intra-class compactness and inter-class separability. Finally, the above three modules are simultaneously optimized in a joint learning scheme. Experimental results have demonstrated the effectiveness of our tracker.
A Local Sparse Model for Matching Problem
Authors: Jiang Bo , Tang Jin , Ding Chris , Luo Bin
Published: June 2022

Feature matching problem that incorporates pairwise constraints is usually formulated as a quadratic assignment problem (QAP). Since it is NP-hard, relaxation models are required. In this paper, we first formulate the QAP from the match selection point of view; and then propose a local sparse model for matching problem. Our local sparse matching (LSM) method has the following advantages: (1) It is parameter-free; (2) It generates a local sparse solution which is closer to a discrete matrix than most other continuous relaxation methods for the matching problem. (3) The one-to-one matching constraints are better maintained in LSM solution. Promising experimental results show the effectiveness of the Proposed LSM method.
Learning Predictable and Discriminative Attributes for Visual Recognition
Authors: Guo Yuchen , Ding Guiguang , Jin Xiaoming , Wang Jianmin
Published: June 2022

Utilizing attributes for visual recognition has attracted increasingly interest because attributes can effectively bridge the semantic gap between low-level visual features and high-level semantic labels. In this paper, we propose a novel method for learning predictable and discriminative attributes. Specifically, we require the learned attributes can be reliably predicted from visual features, and discover the inherent discriminative structure of data. In addition, we propose to exploit the intra-category locality of data to overcome the intra-category variance in visual data. We conduct extensive experiments on Animals with Attributes (AwA) and Caltech256 datasets, and the results demonstrate that the proposed method achieves state-of-the-art performance.
A Bayesian Approach to Perceptual 3D Object-Part Decomposition Using Skeleton-Based Representations
Authors: El-Gaaly Tarek , Froyen Vicky , Elgammal Ahmed , Feldman Jacob , Singh Manish
Published: June 2022

We present a probabilistic approach to shape decomposition that creates a skeleton-based shape representation of a 3D object while simultaneously decomposing it into constituent parts. Our approach probabilistically combines two prominent threads from the shape literature: skeleton-based (medial axis) representations of shape, and part-based representations of shape, in which shapes are combinations of primitive parts. Our approach recasts skeleton-based shape representation as a mixture estimation problem, allowing us to apply probabilistic estimation techniques to the problem of 3D shape decomposition, extending earlier work on the 2D case. The estimated 3D shape decompositions approximate human shape decomposition judgments. We present a tractable implementation of the framework, which begins by over-segmenting objects at concavities, and then probabilistically merges them to create a distribution over possible decompositions. This results in a hierarchy of decompositions at different structural scales, again closely matching known properties of human shape representation. The probabilistic estimation procedures that arise naturally in the model allow effective prediction of missing parts. We present results on shapes from a standard database illustrating the effectiveness of the approach.
Robust System for Identifying Procurement Fraud
Authors: Dhurandhar Amit , Ravi Rajesh , Graves Bruce , Maniachari Gopi , Ettl Markus
Published: June 2022

An accredited biennial 2012 study by the Association of Certified Fraud Examiners claims that on average 5% of a company’s revenue is lost because of unchecked fraud every year. The reason for such heavy losses are that it takes around 18 months for a fraud to be caught and audits catch only 3% of the actual fraud. This begs the need for better tools and processes to be able to quickly and cheaply identify potential malefactors. In this paper, we describe a robust tool to identify procurement related fraud/risk, though the general design and the analytical components could be adapted to detecting fraud in other domains. Besides analyzing standard transactional data, our solution analyzes multiple public and private data sources leading to wider coverage of fraud types than what generally exists in the marketplace. Moreover, our approach is more principled in the sense that the learning component, which is based on investigation feedback has formal guarantees. Though such a tool is ever evolving, an initial deployment of this tool over the past 6 months has found many interesting cases from compliance risk and fraud point of view, increasing the number of true positives found by over 80% compared with other state-of-the-art tools that the domain experts were previously using.
HACKAR: Helpful Advice for Code Knowledge and Attack Resilience
Authors: Kuter Ugur , Burstein Mark , Benton J. , Bryce Daniel , Thayer Jordan , McCoy Steve
Published: June 2022

This paper describes a novel combination of Java program analysis and automated learning and planning architecture to the domain of Java vulnerability analysis. The key feature of our “HACKAR: Helpful Advice for Code Knowledge and Attack Resilience” system is its ability to analyze Java programs at development-time, identifying vulnerabilities and ways to avoid them. HACKAR uses an improved version of NASA’s Java PathFinder (JPF) to execute Java programs and identify vulnerabilities. The system features new Hierarchical Task Network (HTN) learning algorithms that (1) advance stateof-theart HTN learners with reasoning about numeric constraints, failures, and more general cases of recursion, and (2) contribute to problem-solving by learning a hierarchical dataflow representation of the program from the inputs of the program. Empirical evaluation demonstrates that HACKAR was able to suggest fixes for all of our test program suites. It also shows that HACKAR can analyze programs with string inputs that original JPF implementation cannot.
SKILL: A System for Skill Identification and Normalization
Authors: Zhao Meng , Javed Faizan , Jacob Ferosh , McNair Matt
Published: June 2022

Named Entity Recognition (NER) and Named Entity Normalization (NEN) refer to the recognition and normalization of raw texts to known entities. From the perspective of recruitment innovation, professional skill characterization and normalization render human capital data more meaningful both commercially and socially. Accurate and detailed normalization of skills is the key for the predictive analysis of labor market dynamics. Such analytics help bridge the skills gap between employers and candidate workers by matching the right talent for the right job and identifying in-demand skills for workforce training programs. This can also work towards the social goal of providing more job opportunities to the community. In this paper we propose an automated approach for skill entity recognition and optimal normalization. The proposed system has two components: 1) Skills taxonomy generation, which employs vocational skill related sections of resumes and Wikipedia categories to define and develop a taxonomy of professional skills; 2) Skills tagging, which leverages properties of semantic word vectors to recognize and normalize relevant skills in input text. By sampling based end-user evaluation, the current system attains 91% accuracy on the taxonomy generation and 82% accuracy on the skills tagging tasks. The beta version of the system is currently applied in various big data and business intelligence applications for workforce analytics and career track projections at CareerBuilder.
Time-Varying Clusters in Large-Scale Flow Cytometry
Authors: Hyrkas Jeremy , Halperin Daniel , Howe Bill
Published: June 2022

Flow cytometers measure the optical properties of particles to classify microbes. Recent innovations have allowed oceanographers to collect flow cytometry data continuously during research cruises, leading to an explosion of data and new challenges for the classification task. The massive scale, time-varying underlying populations, and noisy measurements motivate the development of new classification methods. We describe the problem, the data, and some preliminary results demonstrating the difficulty with conventional methods.
Combining Retrieval, Statistics, and Inference to Answer Elementary Science Questions
Authors: Clark Peter , Etzioni Oren , Khot Tushar , Sabharwal Ashish , Tafjord Oyvind , Turney Peter , Khashabi Daniel
Published: June 2022

What capabilities are required for an AI system to pass standard 4th Grade Science Tests? Previous work has examined the use of Markov Logic Networks (MLNs) to represent the requisite background knowledge and interpret test questions, but did not improve upon an information retrieval (IR) baseline. In this paper, we describe an alternative approach that operates at three levels of representation and reasoning: information retrieval, corpus statistics, and simple inference over a semi-automatically constructed knowledge base, to achieve substantially improved results. We evaluate the methods on six years of unseen, unedited exam questions from the NY Regents Science Exam (using only non-diagram, multiple choice questions), and show that our overall system’s score is 71.3%, an improvement of 23.8% (absolute) over the MLN-based method described in previous work. We conclude with a detailed analysis, illustrating the complementary strengths of each method in the ensemble. Our datasets are being released to enable further research.
Inside Out: Two Jointly Predictive Models for Word Representations and Phrase Representations
Authors: Sun Fei , Guo Jiafeng , Lan Yanyan , Xu Jun , Cheng Xueqi
Published: June 2022

Distributional hypothesis lies in the root of most existing word representation models by inferring word meaning from its external contexts. However, distributional models cannot handle rare and morphologically complex words very well and fail to identify some fine-grained linguistic regularity as they are ignoring the word forms. On the contrary, morphology points out that words are built from some basic units, i.e., morphemes. Therefore, the meaning and function of such rare words can be inferred from the words sharing the same morphemes, and many syntactic relations can be directly identified based on the word forms. However, the limitation of morphology is that it cannot infer the relationship between two words that do not share any morphemes. Considering the advantages and limitations of both approaches, we propose two novel models to build better word representations by modeling both external contexts and internal morphemes in a jointly predictive way, called BEING and SEING. These two models can also be extended to learn phrase representations according to the distributed morphology theory. We evaluate the proposed models on similarity tasks and analogy tasks. The results demonstrate that the proposed models can outperform state-of-the-art models significantly on both word and phrase representation learning.
Evaluation of Semantic Dependency Labeling Across Domains
Authors: Stoyanchev Svetlana , Stent Amanda , Bangalore Srinivas
Published: June 2022

One of the key concerns in computational semantics is to construct a domain independent semantic representation which captures the richness of natural language, yet can be quickly customized to a specific domain for practical applications. We propose to use generic semantic frames defined in FrameNet, a domain-independent semantic resource, as an intermediate semantic representation for language understanding in dialog systems. In this paper we: (a) outline a novel method for FrameNet-style semantic dependency labeling that builds on a syntactic dependency parse; and (b) compare the accuracy of domain-adapted and generic approaches to semantic parsing for dialog tasks, using a frame-annotated corpus of human-computer dialogs in an airline reservation domain.
Non-Linear Similarity Learning for Compositionality
Authors: Tsubaki Masashi , Duh Kevin , Shimbo Masashi , Matsumoto Yuji
Published: June 2022

Many NLP applications rely on the existence ofsimilarity measures over text data.Although word vector space modelsprovide good similarity measures between words,phrasal and sentential similarities derived from compositionof individual words remain as a difficult problem.In this paper, we propose a new method of ofnon-linear similarity learning for semantic compositionality.In this method, word representations are learnedthrough the similarity learning of sentencesin a high-dimensional space with kernel functions.On the task of predicting the semantic similarity oftwo sentences (SemEval 2014, Task 1),our method outperforms linear baselines,feature engineering approaches,recursive neural networks,and achieve competitive results with long short-term memory models.
TGSum: Build Tweet Guided Multi-Document Summarization Dataset
Authors: Cao Ziqiang , Chen Chengyao , Li Wenjie , Li Sujian , Wei Furu , Zhou Ming
Published: June 2022

The development of summarization research has been significantly hampered by the costly acquisition of reference summaries. This paper proposes an effective way to automatically collect large scales of news-related multi-document summaries with reference to social media's reactions. We utilize two types of social labels in tweets, i.e., hashtags and hyper-links. Hashtags are used to cluster documents into different topic sets. Also, a tweet with a hyper-link often highlights certain key points of the corresponding document. We synthesize a linked document cluster to form a reference summary which can cover most key points. To this aim, we adopt the ROUGE metrics to measure the coverage ratio, and develop an Integer Linear Programming solution to discover the sentence set reaching the upper bound of ROUGE. Since we allow summary sentences to be selected from both documents and high-quality tweets, the generated reference summaries could be abstractive. Both informativeness and readability of the collected summaries are verified by manual judgment. In addition, we train a Support Vector Regression summarizer on DUC generic multi-document summarization benchmarks. With the collected data as extra training resource, the performance of the summarizer improves a lot on all the test sets. We release this dataset for further research.
Truncated Approximate Dynamic Programming with Task-Dependent Terminal Value
Authors: Farahmand Amir-massoud , Nikovski Daniel , Igarashi Yuji , Konaka Hiroki
Published: June 2022

We propose a new class of computationally fast algorithms to find close to optimal policy for Markov Decision Processes (MDP) with large finite horizon T.The main idea is that instead of planning until the time horizon T, we plan only up to a truncated horizon H << T and use an estimate of the true optimal value function as the terminal value. Our approach of finding the terminal value function is to learn a mapping from an MDP to its value function by solving many similar MDPs during a training phase and fit a regression estimator. We analyze the method by providing an error propagation theorem that shows the effect of various sources of errors to the quality of the solution. We also empirically validate this approach in a real-world application of designing an energy management system for Hybrid Electric Vehicles with promising results.
Randomised Procedures for Initialising and Switching Actions in Policy Iteration
Authors: Kalyanakrishnan Shivaram , Misra Neeldhara , Gopalan Aditya
Published: June 2022

Policy Iteration (PI) (Howard 1960) is a classical method for computing an optimal policy for a finite Markov Decision Problem (MDP). The method is conceptually simple: starting from some initial policy, “policy improvement” is repeatedly performed to obtain progressively dominating policies, until eventually, an optimal policy is reached. Being remarkably efficient in practice, PI is often favoured over alternative approaches such as Value Iteration and Linear Programming. Unfortunately, even after several decades of study, theoretical bounds on the complexity of PI remain unsatisfactory. For an MDP with n states and k actions, Mansour and Singh (1999) bound the number of iterations taken by Howard’s PI, the canonical variant of the method, by O(kn / n). This bound merely improves upon the trivial bound of kn by a linear factor. However, a randomised variant of PI introduced by Mansour and Singh (1999) does yield an exponential improvement, with its expected number of iterations bounded by O(((1 + 2/log2(k)) k / 2)n).With the objective of furnishing improved upper bounds for PI, we introduce two randomised procedures in this paper. Our first contribution is a routine to find a good initial policy for PI. After evaluating a number of randomly generated policies, this procedure applies a novel criterion to pick one to initialise PI. When PI is subsequently applied, we show that the expected number of policy evaluations—including both the initialisation and the improvement stages—remains bounded in expectation by O(kn/2). The key construction employed in this routine is a total order on the set of policies. Our second contribution is a randomised action-switching rule for PI, which admits a bound of O((2 + ln(k – 1))n) on the expected number of iterations. To the best of our knowledge, this is the tightest complexity bound known for PI when k >= 3.
Approximate Probabilistic Inference via Word-Level Counting
Authors: Chakraborty Supratik , Meel Kuldeep , Mistry Rakesh , Vardi Moshe
Published: June 2022

Hashing-based model counting has emerged as a promising approach for large-scale probabilistic inference on graphical models. A key component of these techniques is the use of xor-based 2-universal hash functions that operate over Boolean domains. Many counting problems arising in probabilistic inference are, however, naturally encoded over finite discrete domains. Techniques based on bit-level (or Boolean) hash functions require these problems to be propositionalized, making it impossible to leverage the remarkable progress made in SMT (Satisfiability Modulo Theory) solvers that can reason directly over words (or bit-vectors). In this work, we present the first approximate model counter that uses word-level hashing functions, and can directly leverage the power of sophisticated SMT solvers. Empirical evaluation over an extensive suite of benchmarks demonstrates the promise of the approach.
Scaling Relational Inference Using Proofs and Refutations
Authors: Mangal Ravi , Zhang Xin , Kamath Aditya , Nori Aditya , Naik Mayur
Published: June 2022

Many inference problems are naturally formulated using hard and soft constraints over relational domains: the desired solution must satisfy the hard constraints, while optimizing the objectives expressed by the soft constraints. Existing techniques for solving such constraints rely on efficiently grounding a sufficient subset of constraints that is tractable to solve. We present an eager-lazy grounding algorithm that eagerly exploits proofs and lazily refutes counterexamples. We show that our algorithm achieves significant speedup over existing approaches without sacrificing soundness for real-world applications from information retrieval and program analysis.
Closing the Gap Between Short and Long XORs for Model Counting
Authors: Zhao Shengjia , Chaturapruek Sorathan , Sabharwal Ashish , Ermon Stefano
Published: June 2022

Many recent algorithms for approximate model counting are based on a reduction to combinatorial searches over random subsets of the space defined by parity or XOR constraints. Long parity constraints (involving many variables) provide strong theoretical guarantees but are computationally difficult. Short parity constraints are easier to solve but have weaker statistical properties. It is currently not known how long these parity constraints need to be. We close the gap by providing matching necessary and sufficient conditions on the required asymptotic length of the parity constraints. Further, we provide a new family of lower bounds and the first non-trivial upper bounds on the model count that are valid for arbitrarily short XORs. We empirically demonstrate the effectiveness of these bounds on model counting benchmarks and in a Satisfiability Modulo Theory (SMT) application motivated by the analysis of contingency tables in statistics.
Breaking More Composition Symmetries Using Search Heuristics
Authors: Lee Jimmy , Zhu Zichen
Published: June 2022

The pruning power of partial symmetry breaking depends on the given subset of symmetries to break as well as the interactions among symmetry breaking constraints. In the context of Partial Symmetry Breaking During Search (ParSBDS), the search order determines the set of symmetry breaking constraints to add and thus also makes an impact on node and solution pruning. In this paper, we give the first formal characterization of the pruning behavior of ParSBDS and its improved variants. Introducing the notion of Dominance-Completeness (DC-ness), we show that ParSBDS and variants eliminate the symmetry group of the given subset of symmetries if the resultant search tree is DC, and give an example scenario. Unfortunately, building a DC tree is not always possible. We propose two search heuristics with the aim of having more nodes dominated and thus also pruned during search. Extensive experimentation demonstrates how the proposed heuristics and their combination can drastically reduce the solution set size, search space and runtime when compared against the state-of-the-art static and dynamic symmetry breaking methods.
Domain-Constraint Transfer Coding for Imbalanced Unsupervised Domain Adaptation
Authors: Tsai Yao-Hung Hubert , Hou Cheng-An , Chen Wei-Yu , Yeh Yi-Ren , Wang Yu-Chiang Frank
Published: June 2022

Unsupervised domain adaptation (UDA) deals with the task that labeled training and unlabeled test data collected from source and target domains, respectively. In this paper, we particularly address the practical and challenging scenario of imbalanced cross-domain data. That is, we do not assume the label numbers across domains to be the same, and we also allow the data in each domain to be collected from multiple datasets/sub-domains. To solve the above task of imbalanced domain adaptation, we propose a novel algorithm of Domain-constraint Transfer Coding (DcTC). Our DcTC is able to exploit latent subdomains within and across data domains, and learns a common feature space for joint adaptation and classification purposes. Without assuming balanced cross-domain data as most existing UDA approaches do, we show that our method performs favorably against state-of-the-art methods on multiple cross-domain visual classification tasks.