bluuebunny/crossref_metadata_2025 huggingface dataset:
FACES: Diversity-Aware Entity Summarization Using Incremental Hierarchical Conceptual Clustering
Authors: Gunaratna Kalpa , Thirunarayan Krishnaparasad , Sheth Amit
Published: June 2022

Semantic Web documents that encode facts about entities on the Web have been growing rapidly in size and evolving over time. Creating summaries on lengthy Semantic Web documents for quick identification of the corresponding entity has been of great contemporary interest. In this paper, we explore automatic summarization techniques that characterize and enable identification of an entity and create summaries that are human friendly. Specifically, we highlight the importance of diversified (faceted) summaries by combining three dimensions: diversity, uniqueness, and popularity. Our novel diversity-aware entity summarization approach mimics human conceptual clustering techniques to group facts and picks representative facts from each group to form concise (i.e., short) and comprehensive (i.e., improved coverage through diversity) summaries. We evaluate our approach against the state-of-the-art techniques and show that our work improves both the quality and the efficiency of entity summarization.
Visually Interpreting Names as Demographic Attributes by Exploiting Click-Through Data
Authors: Chen Yan-Ying , Kuo Yin-Hsi , Wu Chun-Che , Hsu Winston
Published: June 2022

Name of an identity is strongly influenced by his/her cultural background such as gender and ethnicity, both vital attributes for user profiling, attribute-based retrieval, etc. Typically, the associations between names and attributes (e.g., people named "Amy" are mostly females) are annotated manually or provided by the census data of governments. We propose to associate a name and its likely demographic attributes by exploiting click-throughs between name queries and images with automatically detected facial attributes. This is the first work attempting to translate an abstract name to demographic attributes in visual-data-driven manner, and it is adaptive to incremental data, more countries and even unseen names (the names out of click-through data) without additional manual labels. In the experiments, the automatic name-attribute associations can help gender inference with competitive accuracy by using manual labeling. It also benefits profiling social media users and keyword-based face image retrieval, especially for contributing 12% relative improvement of accuracy in adapting to unseen names.
Handling Owl:sameAs via Rewriting
Authors: Motik Boris , Nenov Yavor , Piro Robert , Horrocks Ian
Published: June 2022

Rewriting is widely used to optimise owl:sameAs reasoning in materialisation based OWL 2 RL systems. We investigate issues related to both the correctness and efficiency of rewriting, and present an algorithm that guarantees correctness, improves efficiency, and can be effectively parallelised. Our evaluation shows that our approach can reduce reasoning times on practical data sets by orders of magnitude.
An Axiomatic Approach to Link Prediction
Authors: Cohen Sara , Zohar Aviv
Published: June 2022

Link prediction functions are important tools that are used to predict the evolution of a network, to locate hidden or surprising links, and to recommend new connections that should be formed. Multiple link prediction functions have been developed in the past. However, their evaluation has mostly been based onexperimental work, which has shown that the quality of a link prediction function varies significantly depending on the input domain. There is currently very little understanding of why and how a specific link prediction function works well for a particular domain. The underlying foundations of a link prediction function are often left informal---each function contains implicit assumptions about the dynamics of link formation, and about structural properties that result from these dynamics. We draw upon the motivation used in characterizations of ranking algorithms, as well as other celebrated results from social choice, and present an axiomatic basis for link prediction. This approach seeks to deconstruct each function into basic axioms, or properties, that make explicit its underlying assumptions. Our framework uses ``property templates'' that can be considered as general choices made by a function designer, such as what score is assigned to a 2-vertex graph, which vertices are irrelevant to the score, how removing edges or contracting vertices affects the score, and more. Using this framework, we fully characterize four well known link prediction functions and show that they are in fact derived from different variants of a single basic set of property templates.
Estimating Temporal Dynamics of Human Emotions
Authors: Kim Seungyeon , Lee Joonseok , Lebanon Guy , Park Haesun
Published: June 2022

Sentiment analysis predicts a one-dimensional quantity describing the positive or negative emotion of an author. Mood analysis extends the one-dimensional sentiment response to a multi-dimensional quantity, describing a diverse set of human emotions. In this paper, we extend sentiment and mood analysis temporally and model emotions as a function of time based on temporal streams of blog posts authored by a specific author. The model is useful for constructing predictive models and discovering scientific models of human emotions.
Exploring Key Concept Paraphrasing Based on Pivot Language Translation for Question Retrieval
Authors: Zhang Wei-Nan , Ming Zhao-Yan , Zhang Yu , Liu Ting , Chua Tat-Seng
Published: June 2022

Question retrieval in current community-based question answering (CQA) services does not, in general, work well for long and complex queries. One of the main difficulties lies in the word mismatch between queries and candidate questions. Existing solutions try to expand the queries at word level, but they usually fail to consider concept level enrichment. In this paper, we explore a pivot language translation based approach to derive the paraphrases of key concepts. We further propose a unified question retrieval model which integrates the keyconcepts and their paraphrases for the query question. Experimental results demonstrate that the paraphrase enhanced retrieval model significantly outperforms the state-of-the-art models in question retrieval.
Mining User Intents in Twitter: A Semi-Supervised Approach to Inferring Intent Categories for Tweets
Authors: Wang Jinpeng , Cong Gao , Zhao Xin , Li Xiaoming
Published: June 2022

In this paper, we propose to study the problem of identifying and classifying tweets into intent categories. For example, a tweet “I wanna buy a new car” indicates the user’s intent for buying a car. Identifying such intent tweets will have great commercial value among others. In particular, it is important that we can distinguish different types of intent tweets. We propose to classify intent tweets into six categories, namely Food & Drink, Travel, Career & Education, Goods & Services, Event and Activities and Trifle. We propose a semisupervised learning approach to categorizing intent tweets into the six categories.We construct a test collection by using a bootstrap method. Our experimental results show that our approach is effective in inferring intent categories for tweets.
DynaDiffuse: A Dynamic Diffusion Model for Continuous Time Constrained Influence Maximization
Authors: Xie Miao , Yang Qiusong , Wang Qing , Cong Gao , Melo Gerard
Published: June 2022

Studying the spread of phenomena in social networks is critical but still not fully solved. Existing influence maximization models assume a static network, disregarding its evolution over time. We introduce the continuous time constrained influence maximization problem for dynamic diffusion networks, based on a novel diffusion model called DynaDiffuse. Although the problem is NP-hard, the influence spread functions are monotonic and submodular, enabling fast approximations on top of an innovative stochastic model checking approach. Experiments on real social network data show that our model finds higher quality solutions and our algorithm outperforms state-of-art alternatives.
Using Matched Samples to Estimate the Effects of Exercise on Mental Health via Twitter
Authors: Landeiro Dos Reis Virgile , Culotta Aron
Published: June 2022

Recent work has demonstrated the value of social media monitoring for health surveillance (e.g., tracking influenza or depression rates). It is an open question whether such data can be used to make causal inferences (e.g., determining which activities lead to increased depression rates). Even in traditional, restricted domains, estimating causal effects from observational data is highly susceptible to confounding bias. In this work, we estimate the effect of exercise on mental health from Twitter, relying on statistical matching methods to reduce confounding bias. We train a text classifier to estimate the volume of a user's tweets expressing anxiety, depression, or anger, then compare two groups: those who exercise regularly (identified by their use of physical activity trackers like Nike+), and a matched control group. We find that those who exercise regularly have significantly fewer tweets expressing depression or anxiety; there is no significant difference in rates of tweets expressing anger. We additionally perform a sensitivity analysis to investigate how the many experimental design choices in such a study impact the final conclusions, including the quality of the classifier and the construction of the control group.
Incorporating Assortativity and Degree Dependence into Scalable Network Models
Authors: Mussmann Stephen , Moore John , Pfeiffer Joseph , Neville Jennifer
Published: June 2022

Due to the recent availability of large complex networks, considerable analysis has focused on understanding and characterizing the properties of these networks. Scalable generative graph models focus on modeling distributions of graphs that match real world network properties and scale to large datasets. Much work has focused on modeling networks with a power law degree distribution, clustering, and small diameter. In network analysis, the assortativity statistic is defined as the correlation between the degrees of linked nodes in the network. The assortativity measure can distinguish between types of networks---social networks commonly exhibit positive assortativity, in contrast to biological or technological networks that are typically disassortative. Despite this, little work has focused on scalable graph models that capture assortativity in networks. The contributions of our work are twofold. First, we prove that an unbounded number of pairs of networks exist with the same degree distribution and assortativity, yet different joint degree distributions. Thus, assortativity as a network measure cannot distinguish between graphs with complex (non-linear) dependence in their joint degree distributions. Motivated by this finding, we introduce a generative graph model that explicitly estimates and models the joint degree distribution. Our Binned Chung Lu method accurately captures both the joint degree distribution and assortativity, while still matching characteristics such as the degree distribution and clustering coefficients. Further, our method has subquadratic learning and sampling methods that enable scaling to large, real world networks. We evaluate performance compared to other scalable graph models on six real world networks, including a citation network with over 14 million edges.
Kickback Cuts Backprop's Red-Tape: Biologically Plausible Credit Assignment in Neural Networks
Authors: Balduzzi David , Vanchinathan Hastagiri , Buhmann Joachim
Published: June 2022

Error backpropagation is an extremely effective algorithm for assigning credit in artificial neural networks. However, weight updates under Backprop depend on lengthy recursive computations and require separate output and error messages — features not shared by biological neurons, that are perhaps unnecessary. In this paper, we revisit Backprop and the credit assignment problem. We first decompose Backprop into a collection of interacting learning algorithms; provide regret bounds on the performance of these sub-algorithms; and factorize Backprop's error signals. Using these results, we derive a new credit assignment algorithm for nonparametric regression, Kickback, that is significantly simpler than Backprop. Finally, we provide a sufficient condition for Kickback to follow error gradients, and show that Kickback matches Backprop's performance on real-world regression benchmarks.
An Entorhinal-Hippocampal Model for Simultaneous Cognitive Map Building
Authors: Yuan Miaolong , Tian Bo , Shim Vui Ann , Tang Huajin , Li Haizhou
Published: June 2022

Hippocampal place cells and entorhinal grid cells have been hypothesized to be able to form map-like spatial representation of the environment, namely cognitive map. In most prior approaches, either neural network methods or only hippocampal models are used for building cognitive maps, lacking biological fidelity to the entorhinal-hippocampal system. This paper presents a novel computational model to build cognitive maps of real environments using both place cells and grid cells. The proposed model includes two major components: (1) A competitive Hebbian learning algorithm is used to select velocity-coupled grid cell population activities, which path-integrate self-motion signals to determine computation of place cell population activities; (2) Visual cues of environments are used to correct the accumulative errors intrinsically associated with the path integration process. Experiments performed on a mobile robot show that cognitive maps of the real environment can be efficiently built. The proposed model would provide an alternative neuro-inspired approach for robotic mapping, navigation and localization.
Extending Analogical Generalization with Near-Misses
Authors: McLure Matthew , Friedman Scott , Forbus Kenneth
Published: June 2022

Concept learning is a central problem for cognitive systems. Generalization techniques can help organize examples by their commonalities, but comparisons with non-examples, near-misses, can provide discrimination. Early work on near-misses required hand-selected examples by a teacher who understood the learner’s internal representations. This paper introduces Analogical Learning by Integrating Generalization and Near-misses (ALIGN) and describes three key advances. First, domain-general cognitive models of analogical processes are used to handle a wider range of examples. Second, ALIGN’s analogical generalization process constructs multiple probabilistic representations per concept via clustering, and hence can learn disjunctive concepts. Finally, ALIGN uses unsupervised analogical retrieval to find its own near-miss examples. We show that ALIGN out-performs analogical generalization on two perceptual data sets: (1) hand-drawn sketches; and (2) geospatial concepts from strategy-game maps.
AffectiveSpace 2: Enabling Affective Intuition for Concept-Level Sentiment Analysis
Authors: Cambria Erik , Fu Jie , Bisio Federica , Poria Soujanya
Published: June 2022

Predicting the affective valence of unknown multi-word expressions is key for concept-level sentiment analysis. AffectiveSpace 2 is a vector space model, built by means of random projection, that allows for reasoning by analogy on natural language con- cepts. By reducing the dimensionality of affec- tive common-sense knowledge, the model allows semantic features associated with concepts to be generalized and, hence, allows concepts to be intu- itively clustered according to their semantic and affective relatedness. Such an affective intuition (so called because it does not rely on explicit fea- tures, but rather on implicit analogies) enables the inference of emotions and polarity conveyed by multi-word expressions, thus achieving efficient concept-level sentiment analysis.
Pattern Decomposition with Complex Combinatorial Constraints: Application to Materials Discovery
Authors: Ermon Stefano , Le Bras Ronan , Suram Santosh , Gregoire John , Gomes Carla , Selman Bart , Van Dover Robert
Published: June 2022

Identifying important components or factors in large amounts of noisy data is a key problem in machine learning and data mining. Motivated by a pattern decomposition problem in materials discovery, aimed at discovering new materials for renewable energy, e.g. for fuel and solar cells, we introduce CombiFD, a framework for factor based pattern decomposition that allows the incorporation of a-priori knowledge as constraints, including complex combinatorial constraints. In addition, we propose a new pattern decomposition algorithm, called AMIQO, based on solving a sequence of (mixed-integer) quadratic programs. Our approach considerably outperforms the state of the art on the materials discovery problem, scaling to larger datasets and recovering more precise and physically meaningful decompositions. We also show the effectiveness of our approach for enforcing background knowledge on other application domains.
Best-Response Planning of Thermostatically Controlled Loads under Power Constraints
Authors: De Nijs Frits , Spaan Matthijs , De Weerdt Mathijs
Published: June 2022

Renewable power sources such as wind and solar are inflexible in their energy production, which requires demand to rapidly follow supply in order to maintain energy balance. Promising controllable demands are air-conditioners and heat pumps which use electric energy to maintain a temperature at a setpoint. Such Thermostatically Controlled Loads (TCLs) have been shown to be able to follow a power curve using reactive control. In this paper we investigate the use of planning under uncertainty to pro-actively control an aggregation of TCLs to overcome temporary grid imbalance. We present a formal definition of the planning problem under consideration, which we model using the Multi-Agent Markov Decision Process (MMDP) framework. Since we are dealing with hundreds of agents, solving the resulting MMDPs directly is intractable. Instead, we propose to decompose the problem by decoupling the interactions through arbitrage. Decomposition of the problem means relaxing the joint power consumption constraint, which means that joining the plans together can cause overconsumption. Arbitrage acts as a conflict resolution mechanism during policy execution, using the future expected value of policies to determine which TCLs should receive the available energy. We experimentally compare several methods to plan with arbitrage, and conclude that a best response-like mechanism is a scalable approach that returns near-optimal solutions.
Learning Large-Scale Dynamic Discrete Choice Models of Spatio-Temporal Preferences with Application to Migratory Pastoralism in East Africa
Authors: Ermon Stefano , Xue Yexiang , Toth Russell , Dilkina Bistra , Bernstein Richard , Damoulas Theodoros , Clark Patrick , DeGloria Steve , Mude Andrew , Barrett Christopher , Gomes Carla
Published: June 2022

Understanding spatio-temporal resource preferences is paramount in the design of policies for sustainable development. Unfortunately, resource preferences are often unknown to policy-makers and have to be inferred from data. In this paper we consider the problem of inferring agents' preferences from observed movement trajectories, and formulate it as an Inverse Reinforcement Learning (IRL) problem . With the goal of informing policy-making, we take a probabilistic approach and consider generative models that can be used to simulate behavior under new circumstances such as changes in resource availability, access policies, or climate. We study the Dynamic Discrete Choice (DDC) models from econometrics and prove that they generalize the Max-Entropy IRL model, a widely used probabilistic approach from the machine learning literature. Furthermore, we develop SPL-GD, a new learning algorithm for DDC models that is considerably faster than the state of the art and scales to very large datasets. We consider an application in the context of pastoralism in the arid and semi-arid regions of Africa, where migratory pastoralists face regular risks due to resource availability, droughts, and resource degradation from climate change and development. We show how our approach based on satellite and survey data can accurately model migratory pastoralism in East Africa and that it considerably outperforms other approaches on a large-scale real-world dataset of pastoralists' movements in Ethiopia collected over 3 years.
Probabilistic Planning with Risk-Sensitive Criterion
Authors: Hou Ping
Published: June 2022

While probabilistic planning models have been extensively used by AI and Decision Theoretic communities for planning under uncertainty, the objective to minimize the expected cumulative cost is inappropriate for high-stake planning problems. With this motivation in mind, we revisit the Risk-Sensitive criterion (RS-criterion), where the objective is to find a policy that maximizes the probability that the cumulative cost is within some user-defined cost threshold. The overall scope of this research is to develop efficient and scalable algorithms to optimize the RS-criterion in probabilistic planning problems. In our recent paper (Hou, Yeoh, and Varakantham 2014), we formally defined Risk-Sensitive MDPs (RS-MDPs) and introduced new algorithms for RS-MDPs with non-negative costs. Next, my plan is to develop algorithm for RS-MDPs with negative cost cycles and for Risk-Sensitive POMDPs (RS-POMDPs).
Scaling-Up Inference in Markov Logic
Authors: Venugopal Deepak
Published: June 2022

Markov logic networks (MLNs) combine the power of first-order logic and probabilistic graphical models and as a result are ideally suited for solving large, complex problems in application domains that have both rich relational structure and large amount of uncertainty. However, inference in these rich, relational representations is quite challenging. The aim of this thesis is to advance the state-of-the-art in MLN inference, enabling it to solve much harder and more complex tasks than is possible today. To this end, I will develop techniques that exploit logical structures and symmetries that are either explicitly or implicitly encoded in the MLN representation and demonstrate their usefulness by using them to solve hard real-world problems in the field of natural language understanding.
CrowdMR: Integrating Crowdsourcing with MapReduce for AI-Hard Problems
Authors: Chen Jun , Wang Chaokun , Bai Yiyuan
Published: June 2022

Large-scale distributed computing has made available the resources necessary to solve "AI-hard" problems. As a result, it becomes feasible to automate the processing of such problems, but accuracy is not very high due to the conceptual difficulty of these problems. In this paper, we integrated crowdsourcing with MapReduce to provide a scalable innovative human-machine solution to AI-hard problems, which is called CrowdMR. In CrowdMR, the majority of problem instances are automatically processed by machine while the troublesome instances are redirected to human via crowdsourcing. The results returned from crowdsourcing are validated in the form of CAPTCHA (Completely Automated Public Turing test to Tell Computers and Humans Apart) before adding to the output. An incremental scheduling method was brought forward to combine the results from machine and human in a "pay-as-you-go" way.
Bottom-Up Demand Response by Following Local Energy Generation Voluntarily
Authors: Linnenberg Tobias , Fay Alexander , Kaisers Michael
Published: June 2022

We present an open-source low-budget hardware and software prototype of a smart plug, and the principles behind its capability to align power demand with a ref- erence signal, e.g. from local renewable energy genera- tion. We envision its use in conjunction with a platform that combines social-media and gamification elements with energy networks.
Cognitive Master Teacher
Authors: Krishnapuram Raghu , Lastras Luis , Nitta Satya
Published: June 2022

The “Cognitive Master Teacher” is a result of discussions with teachers, members of educational institutions, government bodies and other thought leaders in the United States who have helped us shape its the requirements. It is conceived as a cloud-based and mobile-accessible personal agent that is readily available for teachers to use at anytime and assist them with various issues related to day-to-day teaching activities as well as professional development.
Salient Object Detection via Objectness Proposals
Authors: Nguyen Tam
Published: June 2022

Salient object detection has gradually become a popular topic in robotics and computer vision research. This paper presents a real-time system that detects salient object by integrating objectness, foreground and compactness measures. Our algorithm consists of four basic steps. First, our method generates the objectness map via object proposals. Based on the objectness map, we estimate the background margin and compute the corresponding foreground map which prefers the foreground objects. From the objectness map and the foreground map, the compactness map is formed to favor the compact objects. We then integrate those cues to form a pixel-accurate saliency map which covers the salient objects and consistently separates fore- and background.
Multi-Agent Dynamic Coupling for Cooperative Vehicles Modeling
Authors: Guériau Maxime , Billot Romain , El Faouzi Nour-Eddin , Hassas Salima , Armetta Frédéric
Published: June 2022

Cooperative Intelligent Transportation Systems (C-ITS) are complex systems well-suited to a multi-agent modeling. We propose a multi-agent based modeling of a C-ITS, that couples 3 dynamics (physical, informational and control dynamics) in order to ensure a smooth cooperation between non cooperative and cooperative vehicles, that communicate with each other (V2V communication) and the infrastructure (I2V and V2I communication). We present our multi-agent model, tested through simulations using real traffic data and integrated into our extension of the Multi-model Open-source Vehicular-traffic SIMulator (MovSim).
VecLP: A Realtime Video Recommendation System for Live TV Programs
Authors: Gao Sheng , Zhang Dai , Zhang Honggang , Huang Chao , Zhang Yongsheng , Liao Jianxin , Guo Jun
Published: June 2022

We propose VecLP, a novel Internet Video recommendation system working for Live TV Programs in this paper. Given little information on the live TV programs, our proposed VecLP system can effectively collect necessary information on both the programs and the subscribers as well as a large volume of related online videos, and then recommend the relevant Internet videos to the subscribers. For that, the key frames are firstly detected from the live TV programs, and then visual and textual features are extracted from these frames to enhance the understanding of the TV broadcasts. Furthermore, by utilizing the subscribers' profiles and their social relationships, a user preference model is constructed, which greatly improves the diversity of the recommendations in our system. The subscriber's browsing history is also recorded and used to make a further personalized recommendation. This work also illustrates how our proposed VecLP system makes it happen. Finally, we dispose some sort of new recommendation strategies in use at the system to meet special needs from diverse live TV programs and throw light upon how to fuse these strategies.
A Faster Core Constraint Generation Algorithm for Combinatorial Auctions
Authors: Bünz Benedikt , Seuken Sven , Lubin Benjamin
Published: June 2022

Computing prices in core-selecting combinatorial auctions is a computationally hard problem. Auctions with many bids can only be solved using a recently proposed core constraint generation (CCG) algorithm, which may still take days on hard instances. In this paper, we present a new algorithm that significantly outperforms the current state of the art. Towards this end, we first provide an alternative definition of the set of core constraints, where each constraint is weakly stronger, and prove that together these constraints define the identical polytope to the previous definition. Using these new theoretical insights we develop two new algorithmic techniques which generate additional constraints in each iteration of the CCG algorithm by 1) exploiting separability in allocative conflicts between participants in the auction, and 2) by leveraging non-optimal solutions. We show experimentally that our new algorithm leads to significant speed-ups on a variety of large combinatorial auction problems. Our work provides new insights into the structure of core constraints and advances the state of the art in fast algorithms for computing core prices in large combinatorial auctions.
Cooperative Game Solution Concepts that Maximize Stability under Noise
Authors: Li Yuqian , Conitzer Vincent
Published: June 2022

In cooperative game theory, it is typically assumed that the value of each coalition is known. We depart from this, assuming that v(S) is only a noisy estimate of the true value V (S), which is not yet known. In this context, we investigate which solution concepts maximize the probability of ex-post stability (after the true values are revealed). We show how various conditions on the noise characterize the least core and the nucleolus as optimal. Modifying some aspects of these conditions to (arguably) make them more realistic, we obtain characterizations of new solution concepts as being optimal, including the partial nucleolus, the multiplicative least core, and the multiplicative nucleolus.
Truthful Mechanisms without Money for Non-Utilitarian Heterogeneous Facility Location
Authors: Serafino Paolo , Ventre Carmine
Published: June 2022

In this paper, we consider the facility location problem un- der a novel model recently proposed in the literature, which combines the no-money constraint (i.e. the impossibility to employ monetary transfers between the mechanism and the agents) with the presence of heterogeneous facilities, i.e. facilities serving different purposes. Agents thus have a significantly different cost model w.r.t. the classical model with homogeneous facilities studied in literature. We initiate the study of non-utilitarian optimization functions under this novel model. In particular, we consider the case where the optimization goal consists of minimizing the maximum connection cost of the agents. In this setting, we investigate both deterministic and randomized algorithms and derive both lower and upper bounds regarding the approximability of strate- gyproof mechanisms.
Envy-Free Cake-Cutting in Two Dimensions
Authors: Segal-Halevi Erel , Hassidim Avinatan , Aumann Yonatan
Published: June 2022

We consider the problem of fair division of a two dimensional heterogeneous good among several agents. Applications include division of land as well as ad space in print and electronic media. Classical cake cutting protocols either consider a one-dimensional resource, or allocate each agent several disconnected pieces. In practice, however, the two dimensional shape of the allotted piece is of crucial importance in many applications, e.g., squares or bounded aspect-ratio rectangles are most useful for building houses as well as advertisements. We thus introduce and study the problem of envy-free two-dimensional division wherein the utility of the agents depends on the geometric shape of the allocated pieces (as well as the location and size). In addition to envy-freeness, we require that the fraction allocated to each agent be at least a certain constant that depends only on the shape of the cake and the number of agents. We focus on the case where the allotted pieces must be square and the cakes are either squares or the unbounded plane. We provide algorithms for the problem for settings with two and three agents.
Fair Information Sharing for Treasure Hunting
Authors: Chen Yiling , Nissim Kobbi , Waggoner Bo
Published: June 2022

In a search task, a group of agents compete to be the first to find the solution. Each agent has different private information to incorporate into its search. This problem is inspired by settings such as scientific research, Bitcoin hash inversion, or hunting for some buried treasure. A social planner such as a funding agency, mining pool, or pirate captain might like to convince the agents to collaborate, share their information, and greatly reduce the cost of searching. However, this cooperation is in tension with the individuals' competitive desire to each be the first to win the search. The planner's proposal should incentivize truthful information sharing, reduce the total cost of searching, and satisfy fairness properties that preserve the spirit of the competition. We design contract-based mechanisms for information sharing without money. The planner solicits the agents' information and assigns search locations to the agents, who may then search only within their assignments. Truthful reporting of information to the mechanism maximizes an agent's chance to win the search. Epsilon-voluntary participation is satisfied for large search spaces. In order to formalize the planner's goals of fairness and reduced search cost, we propose a simplified, simulated game as a benchmark and quantify fairness and search cost relative to this benchmark scenario. The game is also used to implement our mechanisms. Finally, we extend to the case where coalitions of agents may participate in the mechanism, forming larger coalitions recursively.
Crowdsourcing Complex Workflows under Budget Constraints
Authors: Tran-Thanh Long , Huynh Trung Dong , Rosenfeld Avi , Ramchurn Sarvapali , Jennings Nicholas
Published: June 2022

We consider the problem of task allocation in crowdsourcing systems with multiple complex workflows, each of which consists of a set of inter-dependent micro-tasks.We propose Budgeteer, an algorithm to solve this problem under a budget constraint. In particular, our algorithm first calculates an efficient way to allocate budget to each workflow. It then determines the number of inter-dependent micro-tasks and the price to pay for each task within each workflow, given the corresponding budget constraints. We empirically evaluate it on a well-known crowdsourcing-based text correction workflow using Amazon Mechanical Turk, and show that Budgeteer can achieve similar levels of accuracy to current benchmarks, but is on average 45 % cheaper.
Knowledge Representation and Reasoning: What’s Hot
Authors: Baral Chitta , De Giacomo Giuseppe
Published: June 2022

This is an extended abstract about what is  hot in the field of Knowledge Representation and Reasoning.
What Is Hot in CHI
Authors: Li Wei
Published: June 2022

As the premier international forumon human-computer interaction, "ACM Conference on Human Factors in ComputingSystems" (CHI), has continued to grow and broaden its range of topics and contributing disciplines. CHI 2014 received over 2000 submissions. Those papers and notes were from diversified research domains — psychologists and computer scientists began to meet new visions from sociology, engineering and manufacturing, communication sciences, design and arts, among others. Here, I would like to introduce progress in HCI research which will bring new opportunities and challenges to AI community.
RoboCup@Home — Benchmarking Domestic Service Robots
Authors: Wachsmuth Sven , Holz Dirk , Rudinac Maja , Ruiz-del-Solar Javier
Published: June 2022

The RoboCup@Home league has been founded in 2006with the idea to drive research in AI and related fieldstowards autonomous and interactive robots that copewith real life tasks in supporting humans in everday life.The yearly competition format establishes benchmarkingas a continuous process with yearly changes insteadof a single challenge. We discuss the current state andfuture perspectives of this endeavor.
Initializing Bayesian Hyperparameter Optimization via Meta-Learning
Authors: Feurer Matthias , Springenberg Jost , Hutter Frank
Published: June 2022

Model selection and hyperparameter optimization is crucial in applying machine learning to a novel dataset. Recently, a subcommunity of machine learning has focused on solving this problem with Sequential Model-based Bayesian Optimization (SMBO), demonstrating substantial successes in many applications. However, for computationally expensive algorithms the overhead of hyperparameter optimization can still be prohibitive. In this paper we mimic a strategy human domain experts use: speed up optimization by starting from promising configurations that performed well on similar datasets. The resulting initialization technique integrates naturally into the generic SMBO framework and can be trivially applied to any SMBO method. To validate our approach, we perform extensive experiments with two established SMBO frameworks (Spearmint and SMAC) with complementary strengths; optimizing two machine learning frameworks on 57 datasets. Our initialization procedure yields mild improvements for low-dimensional hyperparameter optimization and substantially improves the state of the art for the more complex combined algorithm selection and hyperparameter optimization problem.
Value-Directed Compression of Large-Scale Assignment Problems
Authors: Lu Tyler , Boutilier Craig
Published: June 2022

Data-driven analytics — in areas ranging from consumer marketing to public policy — often allow behavior prediction at the level of individuals rather than population segments, offering the opportunity to improve decisions that impact large populations. Modeling such (generalized) assignment problems as linear programs, we propose a general value-directed compression technique for solving such problems at scale. We dynamically segment the population into cells using a form of column generation, constructing groups of individuals who can provably be treated identically in the optimal solution. This compression allows problems, unsolvable using standard LP techniques, to be solved effectively. Indeed, once a compressed LP is constructed, problems can solved in milliseconds. We provide a theoretical analysis of themethods, outline the distributed implementation of the requisite data processing, and show how a single compressed LP can be used to solve multiple variants of the original LP near-optimally in real-time (e.g., tosupport scenario analysis). We also show how the method can be leveraged in integer programming models.  Experimental results on marketing contact optimization and political legislature problems validate the performance of our technique.
Massively Parallel A* Search on a GPU
Authors: Zhou Yichao , Zeng Jianyang
Published: June 2022

A* search is a fundamental topic in artificial intelligence. Recently, the general purpose computation on graphics processing units (GPGPU) has been widely used to accelerate numerous computational tasks. In this paper, we propose the first parallel variant of the A* search algorithm such that the search process of an agent can be accelerated by a single GPU processor in a massively parallel fashion. Our experiments have demonstrated that the GPU-accelerated A* search is efficient in solving multiple real-world search tasks, including combinatorial optimization problems, pathfinding and game solving. Compared to the traditional sequential CPU-based A* implementation, our GPU-based A* algorithm can achieve a significant speedup by up to 45x on large-scale search problems.
Limitations of Front-To-End Bidirectional Heuristic Search
Authors: Barker Joseph , Korf Richard
Published: June 2022

We present an intuitive explanation for the limited effectiveness of front-to-end bidirectional heuristic search, supported with extensive evidence from many commonly-studied domains. While previous work has proved the limitations of specific algorithms, we show that any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search. We also demonstrate a pathological case where bidirectional heuristic search is the dominant algorithm, so a stronger claim cannot be made. Finally, we show that on the four-peg Towers Of Hanoi with arbitrary start and goal states, bidirectional brute-force search outperforms unidirectional heuristic search using pattern-database heuristics.
Answering Conjunctive Queries over EL Knowledge Bases with Transitive and Reflexive Roles
Authors: Stefanoni Giorgio , Motik Boris
Published: June 2022

Answering conjunctive queries (CQs) over EL knowledge bases (KBs) with complex role inclusions is PSPACE-hard and in PSPACE in certain cases; however, if complex role inclusions are restricted to role transitivity, a tight upper complexity bound has so far been unknown. Furthermore, the existing algorithms cannot handle reflexive roles, and they are not practicable. Finally, the problem is tractable for acyclic CQs and ELH, and NP-complete for unrestricted CQs and ELHO KBs. In this paper we complete the complexity landscape of CQ answering for several important cases. In particular, we present a practicable NP algorithm for answering CQs over ELHOs KBs—a logic containing all of OWL 2 EL, but with complex role inclusions restricted to role transitivity. Our preliminary evaluation suggests that the algorithm can be suitable for practical use. Moreover, we show that, even for a restricted class of so-called arborescent acyclic queries, CQ answering over EL KBs becomes NP-hard in the presence of either transitive or reflexive roles. Finally, we show that answering arborescent CQs over ELHO KBs is tractable, whereas answering acyclic CQs is NP-hard.
The Relative Expressiveness of Abstract Argumentation and Logic Programming
Authors: Strass Hannes
Published: June 2022

We analyze the relative expressiveness of the two-valued semantics of abstract argumentation frameworks, normal logic programs and abstract dialectical frameworks. By expressiveness we mean the ability to encode a desired set of two-valued interpretations over a given propositional vocabulary A using only atoms from A. While the computational complexity of the two-valued model existence problem for all these languages is (almost) the same, we show that the languages form a neat hierarchy with respect to their expressiveness. We then demonstrate that this hierarchy collapses once we allow to introduce a linear number of new vocabulary elements.
Projection in the Epistemic Situation Calculus with Belief Conditionals
Authors: Schwering Christoph , Lakemeyer Gerhard
Published: June 2022

A fundamental task in reasoning about action and change is projection, which refers to determining what holds after a number of actions have occurred. A powerful method for solving the projection problem is regression, which reduces reasoning about the future to reasoning about the initial state. In particular, regression has played an important role in the situation calculus and its epistemic extensions. Recently, a modal variant of the situation calculus was proposed, which allows an agent to revise its beliefs based on so-called belief conditionals as part of its knowledge base. In this paper, we show how regression can be extended to reduce beliefs about the future to initial beliefs in the presence of belief conditionals. Moreover, we show how any remaining belief operators can be eliminated as well, thus reducing the belief projection problem to ordinary first-order entailments.
Partial Meet Revision and Contraction in Logic Programs
Authors: Binnewies Sebastian , Zhuang Zhiqiang , Wang Kewen
Published: June 2022

The recent years have seen several proposals aimed at placing the revision of logic programs within the belief change frameworks established for classical logic. A crucial challenge of this task lies in the nonmonotonicity of standard logic programming semantics. Existing approaches have thus used the monotonic characterisation via SE-models to develop semantic revision operators, which however neglect any syntactic information, or reverted to a syntax-oriented belief base approach altogether. In this paper, we bridge the gap between semantic and syntactic techniques by adapting the idea of a partial meet construction from classical belief change. This type of construction allows us to define new model-based operators for revising as well as contracting logic programs that preserve the syntactic structure of the programs involved. We demonstrate the rationality of our operators by testing them against the classic AGM or alternative belief change postulates adapted to the logic programming setting. We further present an algorithm that reduces the partial meet revision or contraction of a logic program to performing revision or contraction only on the relevant subsets of that program.
From Classical to Consistent Query Answering under Existential Rules
Authors: Lukasiewicz Thomas , Martinez Maria Vanina , Pieris Andreas , Simari Gerardo
Published: June 2022

Querying inconsistent ontologies is an intriguing new problem that gave rise to a flourishing research activity in the description logic (DL) community. The computational complexity of consistent query answering under the main DLs is rather well understood; however, little is known about existential rules. The goal of the current work is to perform an in-depth analysis of the complexity of consistent query answering under the main decidable classes of existential rules enriched with negative constraints. Our investigation focuses on one of the most prominent inconsistency-tolerant semantics, namely, the AR semantics. We establish a generic complexity result, which demonstrates the tight connection between classical and consistent query answering. This result allows us to obtain in a uniform way a relatively complete picture of the complexity of our problem.
A Comparison of Qualitative and Metric Spatial Relation Models for Scene Understanding
Authors: Thippur Akshaya , Burbridge Chris , Kunze Lars , Alberti Marina , Folkesson John , Jensfelt Patric , Hawes Nick
Published: June 2022

Object recognition systems can be unreliable when run in isolation depending on only image based features, but their performance can be improved when taking scene context into account. In this paper, we present techniques to model and infer object labels in real scenes based on a variety of spatial relations — geometric features which capture how objects co-occur — and compare their efficacy in the context of augmenting perception based object classification in real-world table-top scenes. We utilise a long-term dataset of office table-tops for qualitatively comparing the performances of these techniques. On this dataset, we show that more intricate techniques, have a superior performance but do not generalise well on small training data. We also show that techniques using coarser information perform crudely but sufficiently well in standalone scenarios and generalise well on small training data. We conclude the paper, expanding on the insights we have gained through these comparisons and comment on a few fundamental topics with respect to long-term autonomous robots.
Generalization Analysis for Game-Theoretic Machine Learning
Authors: Li Haifang , Tian Fei , Chen Wei , Qin Tao , Ma Zhi-Ming , Liu Tie-Yan
Published: June 2022

For Internet applications like sponsored search, cautions need to be taken when using machine learning to optimize their mechanisms (e.g., auction) since self-interested agents in these applications may change their behaviors (and thus the data distribution) in response to the mechanisms. To tackle this problem, a framework called game-theoretic machine learning (GTML) was recently proposed, which first learns a Markov behavior model to characterize agents' behaviors, and then learns the optimal mechanism by simulating agents' behavior changes in response to the mechanism. While GTML has demonstrated practical success, its generalization analysis is challenging because the behavior data are non-i.i.d. and dependent on the mechanism. To address this challenge, first, we decompose the generalization error for GTML into the behavior learning error and the mechanism learning error; second, for the behavior learning error, we obtain novel non-asymptotic error bounds for both parametric and non-parametric behavior learning methods; third, for the mechanism learning error, we derive a uniform convergence bound based on a new concept called \emph{nested covering number} of the mechanism space and the generalization analysis techniques developed for mixing sequences.