bluuebunny/crossref_metadata_2025 huggingface dataset:
Preference Elicitation in DCOPs for Scheduling Devices in Smart Buildings
Authors: M. Tabakhi Atena
Published: June 2022

Researchers have used Distributed Constraint Optimization Problems (DCOPs) as a powerful approach to model various multi-agent coordination problems, taking into account their preferences and constraints. A core limitation of this model is the assumption that all agents’ preferences are specified a priori. However, in a number of application domains such knowledge become available only after being elicited from users in these domains. In this abstract, we explore the effects of preference elicitation in our motivating application of scheduling smart appliances with the aim of reducing users’ electricity bill cost as well as increasing their comfort.
Rethinking the Link Prediction Problem in Signed Social Networks
Authors: Li Xiaoming , Fang Hui , Zhang Jie
Published: June 2022

We rethink the link prediction problem in signed social networks by also considering "no-relation" as a future status of a node pair, rather than simply distinguishing positive and negative links proposed in the literature. To understand the underlying mechanism of link formation in signed networks, we propose a feature framework on the basis of a thorough exploration of potential features for the newly identified problem. Grounded on the framework, we also design a trinary classification model, and experimental results show that our method outperforms the state-of-the-art approaches.
Extreme Gradient Boosting and Behavioral Biometrics
Authors: Manning Benjamin
Published: June 2022

As insider hacks become more prevalent it is becoming more useful to identify valid users from the inside of a system rather than from the usual external entry points where exploits are used to gain entry. One of the main goals of this study was to ascertain how well Gradient Boosting could be used for prediction or, in this case, classification or identification of a specific user through the learning of HCI-based behavioral biometrics. If applicable, this procedure could be used to verify users after they have gained entry into a protected system using data that is as human-centric as other biometrics, but less invasive. For this study an Extreme Gradient Boosting algorithm was used for training and testing on a dataset containing keystroke dynamics information. This specific algorithm was chosen because the majority of current research utilizes mainstream methods such as KNN and SVM and the hypothesis of this study was centered on the potential applicability of ensemble related decision or model trees. The final predictive model produced an accuracy of 0.941 with a Kappa value of 0.942 demonstrating that HCI-based behavioral biometrics in the form of keystroke dynamics can be used to identify the users of a system.
Bootstrapping with Models: Confidence Intervals for Off-Policy Evaluation
Authors: Hanna Josiah , Stone Peter , Niekum Scott
Published: June 2022

In many reinforcement learning applications, it is desirable to determine confidence interval lower bounds on the performance of any given policy without executing said policy. In this context, we propose two bootstrapping off-policy evaluation methods which use learned MDP transition models in order to estimate lower confidence bounds on policy performance with limited data. We empirically evaluate the proposed methods in a standard policy evaluation tasks.
Machine Learning for Entity Coreference Resolution: A Retrospective Look at Two Decades of Research
Authors: Ng Vincent
Published: June 2022

Though extensively investigated since the 1960s, entity coreference resolution, a core task in natural language understanding, is far from being solved. Nevertheless, significant progress has been made on learning-based coreference research since its inception two decades ago. This paper provides an overview of the major milestones made in learning-based coreference research and discusses a hard entity coreference task, the Winograd Schema Challenge, which has recently received a lot of attention in the AI community.
Reactive Versus Anticipative Decision Making in a Novel Gift-Giving Game
Authors: Fernández Domingos Elias , Burguillo Juan , Lenaerts Tom
Published: June 2022

Evolutionary game theory focuses on the fitness differences between simple discrete or probabilistic strategies to explain the evolution of particular decision-making behavior within strategic situations. Although this approach has provided substantial insights into the presence of fairness or generosity in gift-giving games, it does not fully resolve the question of which cognitive mechanisms are required to produce the choices observed in experiments. One such mechanism that humans have acquired, is the capacity to anticipate. Prior work showed that forward-looking behavior, using a recurrent neural network to model the cognitive mechanism, are essential to produce the actions of human participants in behavioral experiments. In this paper, we evaluate whether this conclusion extends also to gift-giving games, more concretely, to a game that combines the dictator game with a partner selection process. The recurrent neural network model used here for dictators, allows them to reason about a best response to past actions of the receivers (reactive model) or to decide which action will lead to a more successful outcome in the future (anticipatory model). We show for both models the decision dynamics while training, as well as the average behavior. We find that the anticipatory model is the only one capable of accounting for changes in the context of the game, a behavior also observed in experiments, expanding previous conclusions to this more sophisticated game.
When Does Bounded-Optimal Metareasoning Favor Few Cognitive Systems?
Authors: Milli Smitha , Lieder Falk , Griffiths Thomas
Published: June 2022

While optimal metareasoning is notoriously intractable, humans are nonetheless able to adaptively allocate their computational resources. A possible approximation that humans may use to do this is to only metareason over a finite set of cognitive systems that perform variable amounts of computation. The highly influential "dual-process" accounts of human cognition, which postulate the coexistence of a slow accurate system with a fast error-prone system, can be seen as a special case of this approximation. This raises two questions: how many cognitive systems should a bounded optimal agent be equipped with and what characteristics should those systems have? We investigate these questions in two settings: a one-shot decision between two alternatives, and planning under uncertainty in a Markov decision process. We find that the optimal number of systems depends on the variability of the environment and the costliness of metareasoning. Consistent with dual-process theories, we also find that when having two systems is optimal, then the first system is fast but error-prone and the second system is slow but accurate.
Inductive Reasoning about Ontologies Using Conceptual Spaces
Authors: Bouraoui Zied , Jameel Shoaib , Schockaert Steven
Published: June 2022

Structured knowledge about concepts plays an increasingly important role in areas such as information retrieval. The available ontologies and knowledge graphs that encode such conceptual knowledge, however, are inevitably incomplete. This observation has led to a number of methods that aim to automatically complete existing knowledge bases. Unfortunately, most existing approaches rely on black box models, e.g. formulated as global optimization problems, which makes it difficult to support the underlying reasoning process with intuitive explanations. In this paper, we propose a new method for knowledge base completion, which uses interpretable conceptual space representations and an explicit model for inductive inference that is closer to human forms of commonsense reasoning. Moreover, by separating the task of representation learning from inductive reasoning, our method is easier to apply in a wider variety of contexts. Finally, unlike optimization based approaches, our method can naturally be applied in settings where various logical constraints between the extensions of concepts need to be taken into account.
Boosting Complementary Hash Tables for Fast Nearest Neighbor Search
Authors: Liu Xianglong , Deng Cheng , Mu Yadong , Li Zhujin
Published: June 2022

Hashing has been proven a promising technique for fast nearest neighbor search over massive databases. In many practical tasks it usually builds multiple hash tables for a desired level of recall performance. However, existing multi-table hashing methods suffer from the heavy table redundancy, without strong table complementarity and effective hash code learning. To address the problem, this paper proposes a multi-table learning method which pursues a specified number of complementary and informative hash tables from a perspective of ensemble learning. By regarding each hash table as a neighbor prediction model, the multi-table search procedure boils down to a linear assembly of predictions stemming from multiple tables. Therefore, a sequential updating and learning framework is naturally established in a boosting mechanism, theoretically guaranteeing the table complementarity and algorithmic convergence. Furthermore, each boosting round pursues the discriminative hash functions for each table by a discrete optimization in the binary code space. Extensive experiments carried out on two popular tasks including Euclidean and semantic nearest neighbor search demonstrate that the proposed boosted complementary hash-tables method enjoys the strong table complementarity and significantly outperforms the state-of-the-arts.
VINet: Visual-Inertial Odometry as a Sequence-to-Sequence Learning Problem
Authors: Clark Ronald , Wang Sen , Wen Hongkai , Markham Andrew , Trigoni Niki
Published: June 2022

In this paper we present an on-manifold sequence-to-sequence learning approach to motion estimation using visual and inertial sensors. It is to the best of our knowledge the first end-to-end trainable method for visual-inertial odometry which performs fusion of the data at an intermediate feature-representation level. Our method has numerous advantages over traditional approaches. Specifically, it eliminates the need for tedious manual synchronization of the camera and IMU as well as eliminating the need for manual calibration between the IMU and camera. A further advantage is that our model naturally and elegantly incorporates domain specific information which significantly mitigates drift. We show that our approach is competitive with state-of-the-art traditional methods when accurate calibration data is available and can be trained to outperform them in the presence of calibration and synchronization errors.
Video Recovery via Learning Variation and Consistency of Images
Authors: Huo Zhouyuan , Gao Shangqian , Cai Weidong , Huang Heng
Published: June 2022

Matrix completion algorithms have been popularly used to recover images with missing entries, and they are proved to be very effective. Recent works utilized tensor completion models in video recovery assuming that all video frames are homogeneous and correlated. However, real videos are made up of different episodes or scenes, i.e. heterogeneous. Therefore, a video recovery model which utilizes both video spatiotemporal consistency and variation is necessary. To solve this problem, we propose a new video recovery method Sectional Trace Norm with Variation and Consistency Constraints (STN-VCC). In our model, capped L1-norm regularization is utilized to learn the spatial-temporal consistency and variation between consecutive frames in video clips. Meanwhile, we introduce a new low-rank model to capture the low-rank structure in video frames with a better approximation of rank minimization than traditional trace norm. An efficient optimization algorithm is proposed, and we also provide a proof of convergence in the paper. We evaluate the proposed method via several video recovery tasks and experiment results show that our new method consistently outperforms other related approaches.
Cross-Lingual Entity Linking for Web Tables
Authors: Luo Xusheng , Luo Kangqi , Chen Xianyang , Zhu Kenny
Published: June 2022

This paper studies the problem of linking string mentions from web tables in one language to the corresponding named entities in a knowledge base written in another language, which we call the cross-lingual table linking task. We present a joint statistical model to simultaneously link all mentions that appear in one table. The framework is based on neural networks, aiming to bridge the language gap by vector space transformation and a coherence feature that captures the correlations between entities in one table. Experimental results report that our approach improves the accuracy of cross-lingual table linking by a relative gain of 12.1%. Detailed analysis of our approach also shows a positive and important gain brought by the joint framework and coherence feature.
A Multi-Task Learning Approach for Improving Product Title Compression with User Search Log Data
Authors: Wang Jingang , Tian Junfeng , Qiu Long , Li Sheng , Lang Jun , Si Luo , Lan Man
Published: June 2022

It is a challenging and practical research problem to obtain effective compression of lengthy product titles for E-commerce. This is particularly important as more and more users browse mobile E-commerce apps and more merchants make the original product titles redundant and lengthy for Search Engine Optimization. Traditional text summarization approaches often require a large amount of preprocessing costs and do not capture the important issue of conversion rate in E-commerce. This paper proposes a novel multi-task learning approach for improving product title compression with user search log data. In particular, a pointer network-based sequence-to-sequence approach is utilized for title compression with an attentive mechanism as an extractive method and an attentive encoder-decoder approach is utilized for generating user search queries. The encoding parameters (i.e., semantic embedding of original titles) are shared among the two tasks and the attention distributions are jointly optimized. An extensive set of experiments with both human annotated data and online deployment demonstrate the advantage of the proposed research for both compression qualities and online business values.
Predicting Aesthetic Score Distribution Through Cumulative Jensen-Shannon Divergence
Authors: Jin Xin , Wu Le , Li Xiaodong , Chen Siyu , Peng Siwei , Chi Jingying , Ge Shiming , Song Chenggen , Zhao Geng
Published: June 2022

Aesthetic quality prediction is a challenging task in the computer vision community because of the complex interplay with semantic contents and photographic technologies. Recent studies on the powerful deep learning based aesthetic quality assessment usually use a binary high-low label or a numerical score to represent the aesthetic quality. However the scalar representation cannot describe well the underlying varieties of the human perception of aesthetics. In this work, we propose to predict the aesthetic score distribution (i.e., a score distribution vector of the ordinal basic human ratings) using Deep Convolutional Neural Network (DCNN). Conventional DCNNs which aim to minimize the difference between the predicted scalar numbers or vectors and the ground truth cannot be directly used for the ordinal basic rating distribution. Thus, a novel CNN based on the Cumulative distribution with Jensen-Shannon divergence (CJS-CNN) is presented to predict the aesthetic score distribution of human ratings, with a new reliability-sensitive learning method based on the kurtosis of the score distribution, which eliminates the requirement of the original full data of human ratings (without normalization). Experimental results on large scale aesthetic dataset demonstrate the effectiveness of our introduced CJS-CNN in this task.
Ranking Users in Social Networks With Higher-Order Structures
Authors: Zhao Huan , Xu Xiaogang , Song Yangqiu , Lee Dik Lun , Chen Zhao , Gao Han
Published: June 2022

PageRank has been widely used to measure the authority or the influence of a user in social networks. However, conventional PageRank only makes use of edge-based relations, ignoring higher-order structures captured by motifs, subgraphs consisting of a small number of nodes in complex networks. In this paper, we propose a novel framework, motif-based PageRank (MPR), to incorporate higher-order structures into conventional PageRank computation. We conduct extensive experiments in three real-world networks, i.e., DBLP, Epinions, and Ciao, to show that MPR can significantly improve the effectiveness of PageRank for ranking users in social networks. In addition to numerical results, we also provide detailed analysis for MPR to show how and why incorporating higher-order information works better than PageRank in ranking users in social networks.
Automated Segmentation of Overlapping Cytoplasm in Cervical Smear Images via Contour Fragments
Authors: Song Youyi , Qin Jing , Lei Baiying , Choi Kup-Sze
Published: June 2022

We present a novel method for automated segmentation of overlapping cytoplasm in cervical smear images based on contour fragments. We formulate the segmentation problem as a graphical model, and employ the contour fragments generated from cytoplasm clump to construct the graph. Compared with traditional methods that are based on pixels, our contour fragment-based solution can take more geometric information into account and hence generate more accurate prediction of the overlapping boundaries. We further design a novel energy function for the graph, and by minimizing the energy function, fragments that come from the same cytoplasm are selected into the same set. To construct the energy function, our fragments-based data term and pairwise term are measured from the spatial relation and shape prior, which offer more geometric information for the occluded boundary inference. Afterwards, occluded boundaries are inferred using the minimal path model, in which shape of each individual cytoplasm is reconstructed on the selected fragments set. Constructed shape is used as a constraint to locate the searching area, and curvature regulation is enforced to promote the smoothness of inference result. The inference result, in turn, is used as the shape prior to construct a high-level shape regulation energy term of the built graph, and then graph energy is updated. In other words, fragments selection and occluded boundary inference are iterative processed; this interaction makes more potential shape information accessible. Using two cervical smear datasets, the performance of our method is extensively evaluated and compared with that of the state-of-the-art approaches; the results show the superiority of the proposed method.
Norm Conflict Resolution in Stochastic Domains
Authors: Kasenberg Daniel , Scheutz Matthias
Published: June 2022

Artificial agents will need to be aware of human moral and social norms, and able to use them in decision-making. In particular, artificial agents will need a principled approach to managing conflicting norms, which are common in human social interactions. Existing logic-based approaches suffer from normative explosion and are typically designed for deterministic environments; reward-based approaches lack principled ways of determining which normative alternatives exist in a given environment. We propose a hybrid approach, using Linear Temporal Logic (LTL) representations in Markov Decision Processes (MDPs), that manages norm conflicts in a systematic manner while accommodating domain stochasticity. We provide a proof-of-concept implementation in a simulated vacuum cleaning domain.
Uplink Communication Efficient Differentially Private Sparse Optimization With Feature-Wise Distributed Data
Authors: Lou Jian , Cheung Yiu-ming
Published: June 2022

Preserving differential privacy during empirical risk minimization model training has been extensively studied under centralized and sample-wise distributed dataset settings. This paper considers a nearly unexplored context with features partitioned among different parties under privacy restriction. Motivated by the nearly optimal utility guarantee achieved by centralized private Frank-Wolfe algorithm (Talwar, Thakurta, and Zhang 2015), we develop a distributed variant with guaranteed privacy, utility and uplink communication complexity. To obtain these guarantees, we provide a much generalized convergence analysis for block-coordinate Frank-Wolfe under arbitrary sampling, which greatly extends known convergence results that are only applicable to two specific block sampling distributions. We also design an active feature sharing scheme by utilizing private Johnson-Lindenstrauss transform, which is the key to updating local partial gradients in a differentially private and communication efficient manner.
Thinking in PolAR Pictures: Using Rotation-Friendly Mental Images to Solve Leiter-R Form Completion
Authors: Palmer Joshua , Kunda Maithilee
Published: June 2022

The Leiter International Performance Scale-Revised (Leiter-R) is a standardized cognitive test that seeks to "provide a nonverbal measure of general intelligence by sampling a wide variety of functions from memory to nonverbal reasoning." Understanding the computational building blocks of nonverbal cognition, as measured by the Leiter-R, is an important step towards understanding human nonverbal cognition, especially with respect to typical and atypical trajectories of child development. One subtest of the Leiter-R, Form Completion, involves synthesizing and localizing a visual figure from its constituent slices. Form Completion poses an interesting nonverbal problem that seems to combine several aspects of visual memory, mental rotation, and visual search. We describe a new computational cognitive model that addresses Form Completion using a novel, mental-rotation-friendly image representation that we call the Polar Augmented Resolution (PolAR) Picture, which enables high-fidelity mental rotation operations. We present preliminary results using actual Leiter-R test items and discuss directions for future work.
Reading With Robots: Towards a Human-Robot Book Discussion System for Elderly Adults
Authors: Parde Natalie
Published: June 2022

As people age, it is critical that they maintain not only their physical health, but also their cognitive health―for instance, by engaging in cognitive exercise. Recent advancements in AI have uncovered novel ways through which to facilitate such exercise. In this thesis, I propose the first human-robot dialogue system designed specifically to promote cognitive exercise in elderly adults, through discussions about interesting metaphors in books. I describe my work to date, including the development of a new, large corpus and an approach for automatically scoring metaphor novelty. Finally, I outline my plans for incorporating this work into the proposed system.
Guaranteed Plans for Multi-Robot Systems via Optimization Modulo Theories
Authors: Leofante Francesco
Published: June 2022

Industries are on the brink of widely accepting a new paradigm for organizing production by having autonomous robots manage in-factory processes. This transition from static process chains towards more automation and autonomy poses new challenges in terms of, e.g., efficiency of production processes. The RoboCup Logistics League (RCLL) has been proposed as a realistic testbed to study the above mentioned problem at a manageable scale. In RCLL, teams of robots manage and optimize the material flow according to dynamic orders in a simplified factory environment. In particular, robots have to transport workpieces among several machines scattered around the factory shop floor. Each machine performs a specific processing step, orders that denote the products which must be assembled with these operations are posted at run-time and require quick planning and scheduling. Orders also come with a delivery time window, therefore introducing a temporal component into the problem. Though there exist successful heuristic approaches to solve the underlying planning and scheduling problems, a disadvantage of these methods is that they provide no guarantees about the quality of the solution. A promising solution to this problem is offered by the recently emerging field of Optimization Modulo Theories (OMT), where Satisfiability Modulo Theories (SMT) solving is extended with optimization functionalities. In this paper, we present an approach that combines bounded model checking and optimization to generate optimal controllers for multi-robot systems. In particular, using the RoboCup Logistics League as a testbed, we build formal models for robot motions, production processes, and for order schedules, deadlines and rewards. We then encode the synthesis problem as a linear mixed-integer problem and employ Optimization Modulo Theories to synthesize controllers with optimality guarantees.
Complexity of Optimally Defending and Attacking a Network
Authors: Najeebullah Kamran
Published: June 2022

We consider single-agent, two-agent turn-taking and cooperative security games with Inverse Geodesic Length (IGL) as utility metric. We focus on the single-agent vertex deletion problem corresponding to IGL called MinIGL. Specifically, given a graph G, a budget k and a target inverse geodesic length T, does there exist a subset of vertices S of size k such that by deleting S the graph induced on the remaining vertices in G has IGL at most T. We cite our recently published work to report the results on the computational and parameterized complexity of MinIGL. Furthermore, we briefly state the problems we are interested to study in future.
Sequential Decision Making in Artificial Musical Intelligence
Authors: Liebman Elad
Published: June 2022

My main research motivation is to develop complete autonomous agents that interact with people socially. For an agent to be social with respect to humans, it needs to be able to parse and process the multitude of aspects that comprise the human cultural experience. That in itself gives rise to many fascinating learning problems. I am interested in tackling these fundamental problems from an empirical as well as a theoretical perspective. Music, as a general target domain, serves as an excellent testbed for these research ideas. Musical skills---playing music (alone or in a group), analyzing music or composing it---all involve extremely advanced knowledge representation and problem solving tools. Creating "musical agents"---agents that can interact richly with people in the music domain---is a challenge that holds the potential of advancing social agents research, and contributing important and broadly applicable AI knowledge. This belief is fueled not just by my background in computer science and artificial intelligence, but also by my deep passion for music as well as my extensive musical training. One key aspect of musical intelligence which hasn’t been sufficiently studied is that of sequential decision-making. My thesis strives to answer the following question: How can a sequential decision making perspective guide us in the creation of better music agents, and social agents in general? More specifically, this thesis focuses on two aspects of musical intelligence: music recommendation and multiagent interaction in the context of music.
Reasonableness Monitors
Authors: Gilpin Leilani
Published: June 2022

As we move towards autonomous machines responsible for making decisions previously entrusted to humans, there is an immediate need for machines to be able to explain their behavior and defend the reasonableness of their actions. To implement this vision, each part of a machine should be aware of the behavior of the other parts that they cooperate with. Each part must be able to explain the observed behavior of those neighbors in the context of the shared goal for the local community. If such an explanation cannot be made, it is evidence that either a part has failed (or was subverted) or the communication has failed. The development of reasonableness monitors is work towards generalizing that vision, with the intention of developing a system-construction methodology that enhances both robustness and security, at runtime (not static compile time), by dynamic checking and explaining of the behaviors of parts and subsystems for reasonableness in context.
Interactive Machine Learning at Scale With CHISSL
Authors: Arendt Dustin , Grace Emily , Volkova Svitlana
Published: June 2022

We demonstrate CHISSL a scalable client-server system for real-time interactive machine learning. Our system is capable of incorporating user feedback incrementally and immediately without a pre-defined prediction task. Computation is partitioned between a lightweight web-client and a heavyweight server. The server relies on representation learning and off-the-shelf agglomerative clustering to find a dendrogram, which we use to quickly approximate distances in the representation space. The client, using only this dendrogram, incorporates user feedback via transduction. Distances and predictions for each unlabeled instance are updated incrementally and deterministically, with O(n) space and time complexity. Our algorithm is implemented in a functional prototype, designed to be easy to use by non-experts. The prototype organizes the large amounts of data into recommendations. This allows the user to interact with actual instances by dragging and dropping to provide feedback in an intuitive manner. We applied CHISSL to several domains including cyber, social media, and geo-temporal analysis.
PegasusN: A Scalable and Versatile Graph Mining System
Authors: Park Ha-Myung , Park Chiwan , Kang U
Published: June 2022

How can we find patterns and anomalies in peta-scale graphs? Even recently proposed graph mining systems fail in processing peta-scale graphs. In this work, we propose PegasusN, a scalable and versatile graph mining system that runs on Hadoop and Spark. To handle enormous graphs, PegasusN provides and seamlessly integrates efficient algorithms for various graph mining operations: graph structure analyses, subgraph enumeration, graph generation, and graph visualization. PegasusN quickly processes extra-large graphs that other systems cannot handle.
Water Advisor - A Data-Driven, Multi-Modal, Contextual Assistant to Help With Water Usage Decisions
Authors: Ellis Jason , Srivastava Biplav , Bellamy Rachel , Aaron Andy
Published: June 2022

We demonstrate Water Advisor, a multi-modal assistant to help non-experts make sense of complex water quality data and apply it to their specific needs. A user can chat with the tool about water quality and activities of interest, and the system tries to advise using available water data for a location, applicable water regulations and relevant parameters using AI methods.
A Unified Implicit Dialog Framework for Conversational Commerce
Authors: Feng Song , Gunasekara R. Chulaka , Shashidhara Sunil , Fadnis Kshitij , Polymenakos Lazaros
Published: June 2022

We propose a unified Implicit Dialog framework for goal-oriented, information seeking tasks of Conversational Commerce applications. It aims to enable the dialog interactions with domain data without replying on the explicitly encoded rules but utilizing the underlying data representation to build the components required for the interactions, which we refer as Implicit Dialog in this work. The proposed framework consists of a pipeline of End-to-End trainable modules. It generates a centralized knowledge representation to semantically ground multiple sub-modules. The framework is also integrated with an associated set of tools to gather end users' input for continuous improvement of the system. This framework is designed to facilitate fast development of conversational systems by identifying the components and the data that can be adapted and reused across many end-user applications. We demonstrate our approach by creating conversational agents for several independent domains.
Predictive Modeling of Learning Continuation in Preschool Education Using Temporal Patterns of Development Tests
Authors: Naito Junpei , Baba Yukino , Kashima Hisashi , Takaki Takenori , Funo Takuya
Published: June 2022

Learning analytics applies data analysis techniques to learning data in order to support students’ learning processes and to improve the quality of education. Despite the increasing attention to learning analytics for higher education, it has not been fully addressed in primary and preschool education. In this research, we apply learning analytics to preschool education to predict the continuation of learning of preschool children. Based on our hypothesis that temporal patterns in the assessment scores of development tests are effective features for prediction, we extract the temporal patterns using time-series clustering, and use them as the features of prediction models. The experimental results using a real preschool education dataset show that the use of the temporal patterns improves the predictive accuracy of future continuation of study.
Investigating Active Learning for Concept Prerequisite Learning
Authors: Liang Chen , Ye Jianbo , Wang Shuting , Pursel Bart , Giles C. Lee
Published: June 2022

Concept prerequisite learning focuses on machine learning methods for measuring the prerequisite relation among concepts. With the importance of prerequisites for education, it has recently become a promising research direction. A major obstacle to extracting prerequisites at scale is the lack of large-scale labels which will enable effective data-driven solutions. We investigate the applicability of active learning to concept prerequisite learning.We propose a novel set of features tailored for prerequisite classification and compare the effectiveness of four widely used query strategies. Experimental results for domains including data mining, geometry, physics, and precalculus show that active learning can be used to reduce the amount of training data required. Given the proposed features, the query-by-committee strategy outperforms other compared query strategies.
Asymmetric Action Abstractions for Multi-Unit Control in Adversarial Real-Time Games
Authors: Moraes Rubens , Lelis Levi
Published: June 2022

Action abstractions restrict the number of legal actions available during search in multi-unit real-time adversarial games, thus allowing algorithms to focus their search on a set of promising actions. Optimal strategies derived from un-abstracted spaces are guaranteed to be no worse than optimal strategies derived from action-abstracted spaces. In practice, however, due to real-time constraints and the state space size, one is only able to derive good strategies in un-abstracted spaces in small-scale games. In this paper we introduce search algorithms that use an action abstraction scheme we call asymmetric abstraction. Asymmetric abstractions retain the un-abstracted spaces' theoretical advantage over regularly abstracted spaces while still allowing the search algorithms to derive effective strategies, even in large-scale games. Empirical results on combat scenarios that arise in a real-time strategy game show that our search algorithms are able to substantially outperform state-of-the-art approaches.
On Social Envy-Freeness in Multi-Unit Markets
Authors: Flammini Michele , Mauro Manuel , Tonelli Matteo
Published: June 2022

We consider a market setting in which buyers are individuals of a population, whose relationships are represented by an underlying social graph. Given buyers valuations for the items being sold, an outcome consists of a pricing of the objects and an allocation of bundles to the buyers. An outcome is social envy-free if no buyer strictly prefers the bundles of her neighbors in the social graph. We focus on the revenue maximization problem in multi-unit markets, in which there are multiple copies of a same item being sold and each buyer is assigned a set of identical items. We consider the four different cases arising by considering different buyers valuations, i.e., single-minded or general, and by adopting different forms of pricing, that is item- or bundle-pricing. For all the above cases we show the hardness of the revenue maximization problem and give corresponding approximation results. All our approximation bounds are optimal or nearly optimal. Moreover, we provide an optimal allocation algorithm for general valuations with item-pricing, under the assumption of social graphs of bounded treewidth. Finally, we determine optimal bounds on the corresponding price of envy-freeness, that is on the worst case ratio between the maximum revenue that can be achieved without envy-freeness constraints, and the one obtainable in case of social relationships. Some of our results close hardness open questions or improve already known ones in the literature concerning the classical setting without sociality.
Average-Case Approximation Ratio of Scheduling Without Payments
Authors: Zhang Jie
Published: June 2022

Apart from the principles and methodologies inherited from Economics and Game Theory, the studies in Algorithmic Mechanism Design typically employ the worst-case analysis and approximation schemes of Theoretical Computer Science. For instance, the approximation ratio, which is the canonical measure of evaluating how well an incentive-compatible mechanism approximately optimizes the objective, is defined in the worst-case sense. It compares the performance of the optimal mechanism against the performance of a truthful mechanism, for all possible inputs. In this paper, we take the average-case analysis approach, and tackle one of the primary motivating problems in Algorithmic Mechanism Design -- the scheduling problem [Nisan and Ronen 1999]. One version of this problem which includes a verification component is studied by [Koutsoupias 2014]. It was shown that the problem has a tight approximation ratio bound of (n+1)/2 for the single-task setting, where n is the number of machines. We show, however, when the costs of the machines to executing the task follow any independent and identical distribution, the average-case approximation ratio of the mechanism given in [Koutsoupias 2014] is upper bounded by a constant. This positive result asymptotically separates the average-case ratio from the worst-case ratio, and indicates that the optimal mechanism for the problem actually works well on average, although in the worst-case the expected cost of the mechanism is Theta(n) times that of the optimal cost.
Disarmament Games With Resource
Authors: Deng Yuan , Conitzer Vincent
Published: June 2022

A paper by Deng and Conitzer in AAAI'17 introduces disarmament games, in which players alternatingly commit not to play certain pure strategies. However, in practice, disarmament usually does not consist in removing a strategy, but rather in removing a resource (and doing so rules out all the strategies in which that resource is used simultaneously). In this paper, we introduce a model of disarmament games in which resources, rather than strategies, are removed. We prove NP-completeness of several formulations of the problem of achieving desirable outcomes via disarmament. We then study the case where resources can be fractionally removed, and prove a result analogous to the folk theorem that all desirable outcomes can be achieved. We show that we can approximately achieve any desirable outcome in a polynomial number of rounds, though determining whether a given outcome can be obtained in a given number of rounds remains NP-complete.
Computing the Strategy to Commit to in Polymatrix Games
Authors: De Nittis Giuseppe , Marchesi Alberto , Gatti Nicola
Published: June 2022

Leadership games provide a powerful paradigm to model many real-world settings. Most literature focuses on games with a single follower who acts optimistically, breaking ties in favour of the leader. Unfortunately, for real-world applications, this is unlikely. In this paper, we look for efficiently solvable games with multiple followers who play either optimistically or pessimistically, i.e., breaking ties in favour or against the leader. We study the computational complexity of finding or approximating an optimistic or pessimistic leader-follower equilibrium in specific classes of succinct games—polymatrix like—which are equivalent to 2-player Bayesian games with uncertainty over the follower, with interdependent or independent types. Furthermore, we provide an exact algorithm to find a pessimistic equilibrium for those game classes. Finally, we show that in general polymatrix games the computation is harder even when players are forced to play pure strategies.
Approximating Bribery in Scoring Rules
Authors: Keller Orgad , Hassidim Avinatan , Hazon Noam
Published: June 2022

The classic bribery problem is to find a minimal subset of voters who need to change their vote to make some preferred candidate win.We find an approximate solution for this problem for a broad family of scoring rules (which includes Borda and t-approval), in the following sense: if there is a strategy which requires bribing k voters, we efficiently find a strategy which requires bribing at most k + Õ(√k) voters. Our algorithm is based on a randomized reduction from bribery to coalitional manipulation (UCM). To solve the UCM problem, we apply the Birkhoff-von Neumann (BvN) decomposition to a fractional manipulation matrix. This allows us to limit the size of the possible ballot search space reducing it from exponential to polynomial, while still obtaining good approximation guarantees. Finding the optimal solution in the truncated search space yields a new algorithm for UCM, which is of independent interest.
Committee Selection with Intraclass and Interclass Synergies
Authors: Izsak Rani , Talmon Nimrod , Woeginger Gerhard
Published: June 2022

Voting is almost never done in void, as usually there are some relations between the alternatives on which the voters vote on. These relations shall be taken into consideration when selecting a winning committee of some given multiwinner election. As taking into account all possible relations between the alternatives is generally computationally intractable, in this paper we consider classes of alternatives; intuitively, the number of classes is significantly smaller than the number of alternatives, and thus there is some hope in reaching computational tractability. We model both intraclass relations and interclass relations by functions, which we refer to as synergy functions, and study the computational complexity of identifying the best committee, taking into account those synergy functions. Our model accommodates both positive and negative relations between alternatives; further, our efficient algorithms can also deal with a rich class of diversity wishes, which we show how to model using synergy functions.
A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems
Authors: Hemmi David , Tack Guido , Wallace Mark
Published: June 2022

Stochastic programming is concerned with decision making under uncertainty, seeking an optimal policy with respect to a set of possible future scenarios. This paper looks at multistage decision problems where the uncertainty is revealed over time. First, decisions are made with respect to all possible future scenarios. Secondly, after observing the random variables, a set of scenario specific decisions is taken. Our goal is to develop algorithms that can be used as a back-end solver for high-level modeling languages. In this paper we propose a scenario decomposition method to solve multistage stochastic combinatorial decision problems recursively. Our approach is applicable to general problem structures, utilizes standard solving technology and is highly parallelizable. We provide experimental results to show how it efficiently solves benchmarks with hundreds of scenarios.
Memory-Augmented Monte Carlo Tree Search
Authors: Xiao Chenjun , Mei Jincheng , Müller Martin
Published: June 2022

This paper proposes and evaluates Memory-Augmented Monte Carlo Tree Search (M-MCTS), which provides a new approach to exploit generalization in online real-time search. The key idea of M-MCTS is to incorporate MCTS with a memory structure, where each entry contains information of a particular state. This memory is used to generate an approximate value estimation by combining the estimations of similar states. We show that the memory based value approximation is better than the vanilla Monte Carlo estimation with high probability under mild conditions. We evaluate M-MCTS in the game of Go. Experimental results show that M-MCTS outperforms the original MCTS with the same number of simulations.
Avoiding Dead Ends in Real-Time Heuristic Search
Authors: Cserna Bence , Doyle William , Ramsdell Jordan , Ruml Wheeler
Published: June 2022

Many systems, such as mobile robots, need to be controlled in real time. Real-time heuristic search is a popular on-line planning paradigm that supports concurrent planning and execution. However,existing methods do not incorporate a notion of safety and we show that they can perform poorly in domains that contain dead-end states from which a goal cannot be reached. We introduce new real-time heuristic search methods that can guarantee safety if the domain obeys certain properties. We test these new methods on two different simulated domains that contain dead ends, one that obeys the properties and one that does not. We find that empirically the new methods provide good performance. We hope this work encourages further efforts to widen the applicability of real-time planning.
Measuring Strong Inconsistency
Authors: Ulbricht Markus , Thimm Matthias , Brewka Gerhard
Published: June 2022

We address the issue of quantitatively assessing the severity of inconsistencies in nonmonotonic frameworks. While measuring inconsistency in classical logics has been investigated for some time now, taking the nonmonotonicity into account poses new challenges. In order to tackle them, we focus on the structure of minimal strongly kb-inconsistent subsets of a knowledge base kb---a generalization of minimal inconsistency to arbitrary, possibly nonmonotonic, frameworks. We propose measures based on this notion and investigate their behavior in a nonmonotonic setting by revisiting existing rationality postulates, analyzing the compliance of the proposed measures with these postulates, and by investigating their computational complexity.
Optimised Maintenance of Datalog Materialisations
Authors: Hu Pan , Motik Boris , Horrocks Ian
Published: June 2022

To efficiently answer queries, datalog systems often materialise all consequences of a datalog program, so the materialisation must be updated whenever the input facts change. Several solutions to the materialisation update problem have been proposed. The Delete/Rederive (DRed) and the Backward/Forward (B/F) algorithms solve this problem for general datalog, but both contain steps that evaluate rules "backwards" by matching their heads to a fact and evaluating the partially instantiated rule bodies as queries. We show that this can be a considerable source of overhead even on very small updates. In contrast, the Counting algorithm does not evaluate the rules "backwards," but it can handle only nonrecursive rules. We present two hybrid approaches that combine DRed and B/F with Counting so as to reduce or even eliminate "backward" rule evaluation while still handling arbitrary datalog programs. We show empirically that our hybrid algorithms are usually significantly faster than existing approaches, sometimes by orders of magnitude.