bluuebunny/crossref_metadata_2025 huggingface dataset:
Double Configuration Checking in Stochastic Local Search for Satisfiability
Authors: Luo Chuan , Cai Shaowei , Wu Wei , Su Kaile
Published: June 2022

Stochastic local search (SLS) algorithms have shown effectiveness on satisfiable instances of the Boolean satisfiability (SAT) problem. However, their performance is still unsatisfactory on random k-SAT at the phase transition, which is of significance and is one of the empirically hardest distributions of SAT instances. In this paper, we propose a new heuristic called DCCA, which combines two configuration checking (CC) strategies with different definitions of configuration in a novel way. We use the DCCA heuristic to design an efficient SLS solver for SAT dubbed DCCASat. The experiments show that the DCCASat solver significantly outperforms a number of state-of-the-art solvers on extensive random k-SAT benchmarks at the phase transition. Moreover, DCCASat shows good performance on structured benchmarks, and a combination of DCCASat with a complete solver achieves state-of-the-art performance on structured benchmarks.
Boosting SBDS for Partial Symmetry Breaking in Constraint Programming
Authors: Lee Jimmy , Zhu Zichen
Published: June 2022

The paper proposes a dynamic method, Recursive SBDS(ReSBDS), for efficient partial symmetry breaking. Wefirst demonstrate how (partial) Symmetry BreakingDuring Search (SBDS) misses important pruning opportunitieswhen given only a subset of symmetries tobreak. The investigation pinpoints the culprit and in turnsuggests rectification. The main idea is to add extra conditionalconstraints during search recursively to prunealso symmetric nodes of some pruned subtrees. Thus,ReSBDS can break extra symmetry compositions, butis carefully designed to break only the ones that areeasy to identify and inexpensive to break. We presenttheorems to guarantee the soundness and terminationof our approach, and compare our method with popularstatic and dynamic methods. When the variable (value)heuristic is static, ReSBDS is also complete in eliminatingall interchangeable variables (values) given only thegenerator symmetries. Extensive experimentations confirmthe efficiency of ReSBDS, when compared againststate of the art methods.
An Experimentally Efficient Method for (MSS,CoMSS) Partitioning
Authors: Grégoire Eric , Lagniez Jean-Marie , Mazure Bertrand
Published: June 2022

The concepts of MSS (Maximal Satisfiable Subset) andCoMSS (also called Minimal Correction Subset) playa key role in many A.I. approaches and techniques. Inthis paper, a novel algorithm for partitioning a BooleanCNF formula into one MSS and the correspondingCoMSS is introduced. Extensive empirical evaluationshows that it is more robust and more efficient on mostinstances than currently available techniques.
Non-Restarting SAT Solvers with Simple Preprocessing Can Efficiently Simulate Resolution
Authors: Beame Paul , Sabharwal Ashish
Published: June 2022

Propositional satisfiability (SAT) solvers based on conflict directed clause learning (CDCL) implicitly produce resolution refutations of unsatisfiable formulas. The precise class of formulas for which they can produce polynomial size refutations has been the subject of several studies, with special focus on the clause learning aspect of these solvers. The results, however, assume the use of non-standard and non-asserting learning schemes, or rely on polynomially many restarts for simulating individual steps of a resolution refutation, or work with a theoretical model that significantly deviates from certain key aspects of all modern CDCL solvers such as learning only one asserting clause from each conflict and other techniques such as conflict guided backjumping and phase saving. We study non-restarting CDCL solvers that learn only one asserting clause per conflict and show that, with simple preprocessing that depends only on the number of variables of the input formula, such solvers can polynomially simulate resolution. We show, moreover, that this preprocessing allows one to convert any CDCL solver to one that is non-restarting.
Cached Iterative Weakening for Optimal Multi-Way Number Partitioning
Authors: Schreiber Ethan , Korf Richard
Published: June 2022

The NP-hard number-partitioning problem is to separate a multiset S of n positive integers into k subsets, such that the largest sum of the integers assigned to any subset is minimized. The classic application is scheduling a set of n jobs with different run times onto k identical machines such that the makespan, the time to complete the schedule, is minimized. We present a new algorithm, cached iterative weakening (CIW), for solving this problem optimally. It incorporates three ideas distinct from the previous state of the art: it explores the search space using iterative weakening instead of branch and bound; generates feasible subsets once and caches them instead of at each node of the search tree; and explores subsets in cardinality order instead of an arbitrary order. The previous state of the art is represented by three different algorithms depending on the values of n and k. We provide one algorithm which outperforms all previous algorithms for k >= 4. Our run times are up to two orders of magnitude faster.
Avoiding Plagiarism in Markov Sequence Generation
Authors: Papadopoulos Alexandre , Roy Pierre , Pachet François
Published: June 2022

Markov processes are widely used to generate sequences that imitate a given style, using random walk. Random walk generates sequences by iteratively concatenating states to prefixes of length equal or less than the given Markov order}. However, at higher orders, Markov chains tend to replicate chunks of the corpus with a size possibly higher than the order, a primary form of plagiarism. The Markov order defines a maximum length for training but not for generation. In the framework of constraint satisfaction (CSP), we introduce MaxOrder. This global constraint ensures that generated sequences do not include chunks larger than a given maximum order. We exhibit an automaton that recognises the solution set, with a size linear in the size of the corpus. We propose a linear-time procedure to generate this automaton from a corpus and a given max order. We then use this automaton to achieve generalised arc consistency for the MaxOrder constraint, holding on a sequence of size n, in O(n.T) time, where T is the size of the automaton. We illustrate our approach by generating text sequences from text corpora with a maximum order guarantee, effectively controlling plagiarism.
Semantic Segmentation Using Multiple Graphs with Block-Diagonal Constraints
Authors: Zhang Ke , Zhang Wei , Zeng Sheng , Xue Xiangyang
Published: June 2022

In this paper we propose a novel method for image semantic segmentation using multiple graphs. The multiview affinity graph is constructed by leveraging the consistency between semantic space and multiple visualspaces. With block-diagonal constraints, we enforce the affinity matrix to be sparse such that the pairwise potential for dissimilar superpixels is close to zero. By a divide-and-conquer strategy, the optimizationfor learning affinity matrix is decomposed into several subproblems that can be solved in parallel. Using the neighborhood relationship between superpixels and the consistency between affinity matrix and labelconfidencematrix, we infer the semantic label for each superpixel of unlabeled images by minimizing an objective whose closed form solution can be easily obtained. Experimental results on two real-world image datasetsdemonstrate the effectiveness of our method.
The Quest Draft: an Automated Course Allocation Algorithm
Authors: Hoshino Richard , Raible-Clark Caleb
Published: June 2022

Course allocation is one of the most complex issues facing any university, due to the sensitive nature of deciding which subset of students should be granted seats in highly-popular (market-scarce) courses. In recent years, researchers have proposed numerous solutions, using techniques in integer programming, combinatorial auction design, and matching theory. In this paper, we present a four-part AI-based course allocation algorithm that was conceived by an undergraduate student, and recently implemented at a small Canadian liberal arts university. This new allocation process, which builds upon the Harvard Business School Draft, has received overwhelming support from students and faculty for its transparency, impartiality, and effectiveness.
Pattern Discovery in Protein Networks Reveals High-Confidence Predictions of Novel Interactions
Authors: Hazem Radwan Ahmed Hazem Radwan Ahmed , Glasgow Janice
Published: June 2022

Pattern discovery in protein interaction networks can reveal crucial biological knowledge on the inner workings of cellular machinery. Although far from complete, extracting meaningful patterns from proteomic networks is a nontrivial task due to their size-complexity. This paper proposes a computational framework to efficiently discover topologically-similar patterns from large proteomic networks using Particle Swarm Optimization (PSO). PSO is a robust and low-cost optimization technique that demonstrated to work effectively on the complex, mostly sparse proteomic networks. The resulting topologicallysimilar patterns of close proximity are utilized to systematically predict new high-confidence protein-protein interactions (PPIs). The proposed PSO-based PPI prediction method (3PI) managed to predict high-confidence PPIs, validated by more than one computational/experimental source, through a proposed PPI knowledge transfer process between topologically-similar interaction patterns of close proximity. In three case studies, over 50% of the predicted interactions for EFGR, ERBB2, ERBB3, GRB2 and UBC are overlapped with publically available interaction databases, ~80% of the predictions are found among the Top 1% results of another PPI prediction method and their genes are significantly co-expressed across different tissues. Moreover, the only single prediction example that did not overlap with any of our validation sources was recently experimentally supported by two PubMed publications.
DOROTHY: Enhancing Bidirectional Communication between a 3D Programming Interface and Mobile Robots
Authors: Featherston Emilie , Sridharan Mohan , Urban Susan , Urban Joseph
Published: June 2022

Dorothy is an integrated 3D/robotics educational tool created by augmenting the Alice programming environment for teaching core computing skills to students without prior programming experience. The tool provides a drag and drop interface to create graphical routines in virtual worlds; these routines are automatically translated into code to provide a real-time or offline enactment on mobile robots in the real world. This paper summarizes the key capabilities of Dorothy, and describes the contributions made to: (a) enhance the bidirectional communication between the virtual interface and robots; and (b) support multirobot collaboration. Specifically, we describe the ability to automatically revise the virtual world based on sensor data obtained from robots, creating or deleting objects in the virtual world based on their observed presence or absence in the real world. Furthermore, we describe the use of visually observed behavior of teammates for collaboration between robots when they cannot communicate with each other. Dorothy thus helps illustrate sophisticated algorithms for fundamental challenges in robotics and AI to teach advanced computing concepts, and to emphasize the importance of computing in real world applications, to beginning programmers.
Teaching With Watson
Authors: Wollowski Michael
Published: June 2022

In this paper, we describe how we integrated the materials from the 2013 IBM The Great Minds Challenge (TGMC) - Watson Technical Edition into our Introductory Artificial Intelligence course. We describe the variety of materials made available by IBM, as well as the nature of the competition and the datasets that are at the heart of it. We detail how, where and in what form we integrated the materials into our course. We describe assignments that are based on the materials from the competition as well as additional materials we incorporated into our course. We finish by evaluating our experience in teaching with the materials as well as summarize relevant student feedback. We make recommendations for those who wish to adopt the materials.
A Stochastic Model for Detecting Heterogeneous Link Communities in Complex Networks
Authors: He Dongxiao , Liu Dayou , Jin Di , Zhang Weixiong
Published: June 2022

Discovery of communities in networks is a fundamental data analysis problem. Most of the existing approaches have focused on discovering communities of nodes, while recent studies have shown great advantages and utilities of the knowledge of communities of links. Stochastic models provides a promising class of techniques for the identification of modular structures, but most stochastic models mainly focus on the detection of node communities rather than link communities. We propose a stochastic model, which not only describes the structure of link communities, but also considers the heterogeneous distribution of community sizes, a property which is often ignored by other models. We then learn the model parameters using a method of maximum likelihood based on an expectation-maximization algorithm. To deal with large complex real networks, we extend the method by a strategy of iterative bipartition. The extended method is not only efficient, but is also able to determine the number of communities for a given network. We test our approach on both synthetic benchmarks and real-world networks including an application to a large biological network, and also compare it with two existing methods. The results demonstrate the superior performance of our approach over the competing methods for detecting link communities.
On the Scalable Learning of Stochastic Blockmodel
Authors: Yang Bo , Zhao Xuehua
Published: June 2022

Stochastic blockmodel (SBM) enables us to decompose and analyze an exploratory network without a priori knowledge about its intrinsic structure. However, the task of effectively and efficiently learning a SBM from a large-scale network is still challenging due to the high computational cost of its model selection and parameter estimation. To address this issue, we present a novel SBM learning algorithm referred to as BLOS (BLOckwise Sbm learning). Distinct from the literature, the model selection and parameter estimation of SBM are concurrently, rather than alternately, executed in BLOS by embedding the minimum message length criterion into a block-wise EM algorithm, which greatly reduces the time complexity of SBM learning without losing learning accuracy and modeling flexibility. Its effectiveness and efficiency have been tested through rigorous comparisons with the state-of-the-art methods on both synthetic and real-world networks.
Recommending Positive Links in Signed Social Networks by Optimizing a Generalized AUC
Authors: Song Dongjin , Meyer David
Published: June 2022

With the rapid development of signed social networks in which therelationships between two nodes can be either positive (indicatingrelations such as like) or negative (indicating relations such asdislike), producing a personalized ranking list with positive linkson the top and negative links at the bottom is becoming anincreasingly important task. To accomplish it, we propose ageneralized AUC (GAUC) to quantify the ranking performance ofpotential links (including positive, negative, and unknown statuslinks) in partially observed signed social networks. In addition, wedevelop a novel link recommendation algorithm by directly optimizingthe GAUC loss. We conduct experimental studies based upon Wikipedia,MovieLens, and Slashdot; our results demonstrate the effectivenessand the efficiency of the proposed approach.
Using Description Logics for RDF Constraint Checking and Closed-World Recognition
Authors: Patel-Schneider Peter
Published: June 2022

RDF and Description Logics work in an open-world setting where absence of information is not information about absence. Nevertheless, Description Logic axioms can be interpreted in a closed-world setting and in this setting they can be used for both constraint checking and closed-world recognition against information sources. When the information sources are expressed in well-behaved RDF or RDFS (i.e., RDF graphs interpreted in the RDF or RDFS semantics) this constraint checking and closed-world recognition is simple to describe. Further this constraint checking can be implemented as SPARQL querying and thus effectively performed.
Cross-Modal Image Clustering via Canonical Correlation Analysis
Authors: Jin Cheng , Mao Wenhui , Zhang Ruiqi , Zhang Yuejie , Xue Xiangyang
Published: June 2022

A new algorithm via Canonical Correlation Analysis (CCA) is developed in this paper to support more effective cross-modal image clustering for large-scale annotated image collections. It can be treated as a bi-media multimodal mapping problem and modeled as a correlation distribution over multimodal feature representations. It integrates the multimodal feature generation with the Locality Linear Coding (LLC) and co-occurrence association network, multimodal feature fusion with CCA, and accelerated hierarchical k-means clustering, which aims to characterize the correlations between the inter-related visual features in images and semantic features in captions, and measure their association degree more precisely. Very positive results were obtained in our experiments using a large quantity of public data.
On Information Coverage for Location Category Based Point-of-Interest Recommendation
Authors: Chen Xuefeng , Zeng Yifeng , Cong Gao , Qin Shengchao , Xiang Yanping , Dai Yuanshun
Published: June 2022

Point-of-interest(POI) recommendation becomes a valuable service in location-based social networks. Based on the norm that similar users are likely to have similar preference of POIs, the current recommendation techniques mainly focus on users' preference to provide accurate recommendation results. This tends to generate a list of homogeneous POIs that are clustered into a narrow band of location categories(like food, museum, etc.) in a city. However, users are more interested to taste a wide range of flavors that are exposed in a global set of location categories in the city.In this paper, we formulate a new POI recommendation problem, namely top-K location category based POI recommendation, by introducing information coverage to encode the location categories of POIs in a city.The problem is NP-hard. We develop a greedy algorithm and further optimization to solve this challenging problem. The experimental results on two real-world datasets demonstrate the utility of new POI recommendations and the superior performance of the proposed algorithms.
Lower and Upper Bounds for SPARQL Queries over OWL Ontologies
Authors: Glimm Birte , Kazakov Yevgeny , Kollia Ilianna , Stamou Giorgos
Published: June 2022

The paper presents an approach for optimizing the evaluation of SPARQL queries over OWL ontologies using SPARQL's OWL Direct Semantics entailment regime. The approach is based on the computation of lower and upper bounds, but we allow for much more expressive queries than related approaches. In order to optimize the evaluation of possible query answers in the upper but not in the lower bound, we present a query extension approach that uses schema knowledge from the queried ontology to extend the query with additional parts. We show that the resulting query is equivalent to the original one and we use the additional parts that are simple to evaluate for restricting the bounds of subqueries of the initial query. In an empirical evaluation we show that the proposed query extension approach can lead to a significant decrease in the query execution time of up to four orders of magnitude.
An EBMC-Based Approach to Selecting Types for Entity Filtering
Authors: Ding Jiwei , Ding Wentao , Hu Wei , Qu Yuzhong
Published: June 2022

The quantity of entities in the Linked Data is increasing rapidly. For entity search and browsing systems, filtering is very useful for users to find entities that they are interested in. Type is a kind of widely-used facet and can be easily obtained from knowledge bases, which enables to create filters by selecting at most K types of an entity collection. However, existing approaches often fail to select high-quality type filters due to complex overlap between types. In this paper, we propose a novel type selection approach based upon Budgeted Maximum Coverage (BMC), which can achieve integral optimization for the coverage quality of type filters. Furthermore, we define a new optimization problem called Extended Budgeted Maximum Coverage (EBMC) and propose an EBMC-based approach, which enhances the BMC-based approach by incorporating the relevance between entities and types, so as to create sensible type filters. Our experimental results show that the EBMC-based approach performs best comparing with several representative approaches.
Predicting the Demographics of Twitter Users from Website Traffic Data
Authors: Culotta Aron , Kumar Nirmal , Cutler Jennifer
Published: June 2022

Understanding the demographics of users of online social networks has important applications for health, marketing, and public messaging. In this paper, we predict the demographics of Twitter users based on whom they follow. Whereas most prior approaches rely on a supervised learning approach, in which individual users are labeled with demographics, we instead create a distantly labeled dataset by collecting audience measurement data for 1,500 websites (e.g., 50% of visitors to gizmodo.com are estimated to have a bachelor's degree). We then fit a regression model to predict these demographics using information about the followers of each website on Twitter. The resulting average held-out correlation is .77 across six different variables (gender, age, ethnicity, education, income, and child status). We additionally validate the model on a smaller set of Twitter users labeled individually for ethnicity and gender, finding performance that is surprisingly competitive with a fully supervised approach.
Embedded Unsupervised Feature Selection
Authors: Wang Suhang , Tang Jiliang , Liu Huan
Published: June 2022

Sparse learning has been proven to be a powerful techniquein supervised feature selection, which allows toembed feature selection into the classification (or regression)problem. In recent years, increasing attentionhas been on applying spare learning in unsupervisedfeature selection. Due to the lack of label information,the vast majority of these algorithms usually generatecluster labels via clustering algorithms and then formulateunsupervised feature selection as sparse learningbased supervised feature selection with these generatedcluster labels. In this paper, we propose a novel unsupervisedfeature selection algorithm EUFS, which directlyembeds feature selection into a clustering algorithm viasparse learning without the transformation. The AlternatingDirection Method of Multipliers is used to addressthe optimization problem of EUFS. Experimentalresults on various benchmark datasets demonstrate theeffectiveness of the proposed framework EUFS.
Person Identification Using Anthropometric and Gait Data from Kinect Sensor
Authors: Andersson Virginia , Araujo Ricardo
Published: June 2022

Uniquely identifying individuals using anthropometric and gait data allows for passive biometric systems, where cooperation from the subjects being identified is not required. In this paper, we report on experiments using a novel data set composed of 140 individuals walking in front of a Microsoft Kinect sensor. We provide a methodology to extract anthropometric and gait features from this data and show results of applying different machine learning algorithms on subject identification tasks. Focusing on KNN classifiers, we discuss how accuracy varies in different settings, including number of individuals in a gallery, types of attributes used and number of considered neighbors. Finally, we compare the obtained results with other results in the literature, showing that our approach has comparable accuracy for large galleries.
Learning User-Specific Latent Influence and Susceptibility from Information Cascades
Authors: Wang Yongqing , Shen Huawei , Liu Shenghua , Cheng Xueqi
Published: June 2022

Predicting cascade dynamics has important implications for understanding information propagation and launching viral marketing. Previous works mainly adopt a pair-wise manner, modeling the propagation probability between pairs of users using n2 independent parameters for n users. Consequently, these models suffer from severe overfitting problem, especially for pairs of users without direct interactions, limiting their prediction accuracy. Here we propose to model the cascade dynamics by learning two low-dimensional user-specific vectors from observed cascades, capturing their influence and susceptibility respectively. This model requires much less parameters and thus could combat overfitting problem. Moreover, this model could naturally model context-dependent factors like cumulative effect in information propagation. Extensive experiments on synthetic dataset and a large-scale microblogging dataset demonstrate that this model outperforms the existing pair-wise models at predicting cascade dynamics, cascade size, and "who will be retweeted."
Personalized Tag Recommendation through Nonlinear Tensor Factorization Using Gaussian Kernel
Authors: Fang Xiaomin , Pan Rong , Cao Guoxiang , He Xiuqiang , Dai Wenyuan
Published: June 2022

Personalized tag recommendation systems recommend a list of tags to a user when he is about to annotate an item. It exploits the individual preference and the characteristic of the items. Tensor factorization tech- niques have been applied to many applications, such as tag recommendation. Models based on Tucker Decomposition can achieve good performance but require a lot of computation power. On the other hand, mod- els based on Canonical Decomposition can run in linear time and are more feasible for online recommendation. In this paper, we propose a novel method for personalized tag recommendation, which can be considered as a nonlinear extension of Canonical Decomposition. Different from linear tensor factorization, we exploit Gaussian radial basis function to increase the model’s capacity. The experimental results show that our proposed method outperforms the state-of-the-art methods for tag recommendation on real datasets and perform well even with a small number of features, which verifies that our models can make better use of features.
Learning Plausible Inferences from Semantic Web Knowledge by Combining Analogical Generalization with Structured Logistic Regression
Authors: Liang Chen , Forbus Kenneth
Published: June 2022

Fast and efficient learning over large bodies of commonsense knowledge is a key requirement for cognitive systems. Semantic web knowledge bases provide an important new resource of ground facts from which plausible inferences can be learned. This paper applies structured logistic regression with analogical generalization (SLogAn) to make use of structural as well as statistical information to achieve rapid and robust learning. SLogAn achieves state-of-the-art performance in a standard triplet classification task on two data sets and, in addition, can provide understandable explanations for its answers.
Automated Construction of Visual-Linguistic Knowledge via Concept Learning from Cartoon Videos
Authors: Ha Jung-Woo , Kim Kyung-Min , Zhang Byoung-Tak
Published: June 2022

Learning mutually-grounded vision-language knowledge is a foundational task for cognitive systems and human-level artificial intelligence. Most of knowledge-learning techniques are focused on single modal representations in a static environment with a fixed set of data. Here, we explore an ecologically more-plausible setting by using a stream of cartoon videos to build vision-language concept hierarchies continuously. This approach is motivated by the literature on cognitive development in early childhood. We present the model of deep concept hierarchy (DCH) that enables the progressive abstraction of concept knowledge in multiple levels. We develop a stochastic method for graph construction, i.e. a graph Monte Carlo algorithm, to search efficiently the huge compositional space of the vision-language concepts. The concept hierarchies are built incrementally and can handle concept drift, allowing for being deployed in lifelong learning environments. Using a series of approximately 200 episodes of educational cartoon videos we demonstrate the emergence and evolution of the concept hierarchies as the video stories unfold. We also present the application of the deep concept hierarchies for context-dependent translation between vision and language, i.e. the transcription of a visual scene into text and the generation of visual imagery from text.
Real-Time Predictive Optimization for Energy Management in a Hybrid Electric Vehicle
Authors: Styler Alexander , Nourbakhsh Illah
Published: June 2022

With increasing numbers of electric and hybrid vehicles on the road, transportation presents a unique opportunity to leverage data-driven intelligence to realize large scale impact in energy use and emissions. Energy management in these vehicles is highly sensitive to upcoming power load on the vehicle, which is not considered in conventional reactive policies calculated at design time. Advancements in cheap sensing and computation have enabled on-board upcoming load predictions which can be used to optimize energy management. In this work, we propose and evaluate a novel, real-time optimization strategy that leverages predictions from prior data in a simulated hybrid battery-supercapacitor energy management task. We demonstrate a complete adaptive system that improves over the lifetime of the vehicle as more data is collected and prediction accuracy improves. Using thousands of miles of real-world data collected from both petrol and electric vehicles, we evaluate the performance of our optimization strategy with respect to our cost function. The system achieves performance within 10% of the optimal upper bound calculated using a priori knowledge of the upcoming loads. This performance implies improved battery thermal stability, efficiency, and longevity. Our strategy can be applied to optimize energy use in gas-electric hybrids, battery cooling in electric vehicles, and many other load-sensitive tasks in transportation.
HVAC-Aware Occupancy Scheduling
Authors: Lim BoonPing , Van den Briel Menkes , Thiebaux Sylvie , Backhaus Scott , Bent Russell
Published: June 2022

Energy consumption in commercial and educational buildings is impacted by group activities such as meetings, workshops, classes and exams, and can be reduced by scheduling these activities to take place at times and locations that are favorable from an energy standpoint. This paper improves on the effectiveness of energy-aware room-booking and occupancy scheduling approaches, by allowing the scheduling decisions to rely on an explicit model of the building's occupancy-based HVAC control. The core component of our approach is a mixed-integer linear programming (MILP) model which optimally solves the joint occupancy scheduling and occupancy-based HVAC control problem. To scale up to realistic problem sizes, we embed this MILP model into a large neighbourhood search (LNS). We obtain substantial energy reduction in comparison with occupancy-based HVAC control using arbitrary schedules or using schedules obtained by existing heuristic energy-aware scheduling approaches.
A Simulator of Human Emergency Mobility Following Disasters: Knowledge Transfer from Big Disaster Data
Authors: Song Xuan , Zhang Quanshi , Sekimoto Yoshihide , Shibasaki Ryosuke , Yuan Nicholas Jing , Xie Xing
Published: June 2022

The frequency and intensity of natural disasters has significantly increased over the past decades and this trend is predicted to continue. Facing these possible and unexpected disasters, understanding and simulating of human emergency mobility following disasters will becomethe critical issue for planning effective humanitarian relief, disaster management, and long-term societal reconstruction. However, due to the uniquenessof various disasters and the unavailability of reliable and large scale human mobility data, such kind of research is very difficult to be performed. Hence, in this paper,we collect big and heterogeneous data (e.g. 1.6 million users' GPS records in three years, 17520 times of Japan earthquake data in four years, news reporting data, transportation network data and etc.) to capture and analyze human emergency mobility following different disasters. By mining these big data, we aim to understand what basic laws govern human mobility following disasters, and develop a general model of human emergency mobility for generating and simulating large amount of human emergency movements. The experimental results and validations demonstrate the efficiency of our simulation model, and suggest that human mobility following disasters may be significantly morepredictable and can be easier simulated than previously thought.
Aggregating Electric Cars to Sustainable Virtual Power Plants: The Value of Flexibility in Future Electricity Markets
Authors: Kahlen Micha , Ketter Wolfgang
Published: June 2022

Electric vehicles will play a crucial role in balancing the future electrical grid, which is complicated by many intermittent renewable energy sources. We developed an algorithm that determines for a fleet of electric vehicles, which EV at what price and location to commit to the operating reserve market to either absorb excess capacity or provide electricity during shortages (vehicle-2-grid). The algorithm takes the value of immobility into account by using carsharing fees as a reference point. A virtual power plant autonomously replaces cars that are committed to the operating reserves and are then rented out, with other idle cars to pool the risks of uncertainty. We validate our model with data from a free float carsharing fleet of 500 electric vehicles. An analysis of expected future developments (2015, 2018, and 2022) in operating reserve demand and battery costs yields that the gross profits for a carsharing operator increase between 7-12% with a negligible decrease in car availability (<0.01%).
Scalable Agent Modeling for Large Multiagent Systems
Authors: Rebhuhn Carrie
Published: June 2022

In a heterogeneous multiagent system it can be useful to have knowledge about the different types of agents in the system. Agent modeling develops agent models based on interactions between agents, then predicts agent actions. This approach is effective in small domains but does not scale well. We develop an approach where an agent can learn using an abstract model identification or stereotype rather than an explicit and unique model for each agent. We associate each agent with a stereotype and learn a policy incorporating this knowledge. The benefits of this approach are that it is simple, scalable, and degrades gracefully with misidentification.
DeepTutor: An Effective, Online Intelligent Tutoring System That Promotes Deep Learning
Authors: Rus Vasile , Niraula Nobal , Banjade Rajendra
Published: June 2022

We present in this paper an innovative solution to the challenge of building effective educational technologies that offer tailored instruction to each individual learner. The proposed solution in the form of a conversational intelligent tutoring system, called DeepTutor, has been developed as a web application that is accessible 24/7 through a browser from any device connected to the Internet. The success of several large scale experiments with high-school students using DeepTutor is a solid proof that conversational intelligent tutoring at scale over the web is possible.
Inferring Latent User Properties from Texts Published in Social Media
Authors: Volkova Svitlana , Bachrach Yoram , Armstrong Michael , Sharma Vijay
Published: June 2022

We demonstrate an approach to predict latent personal attributes including user demographics, online personality, emotions and sentiments from texts published on Twitter. We rely on machine learning and natural language processing techniques to learn models from user communications. We first examine individual tweets to detect emotions and opinions emanating from them, and then analyze all the tweets published by a user to infer latent traits of that individual. We consider various user properties including age, gender, income, education, relationship status, optimism and life satisfaction. We focus on Ekman’s six emotions: anger, joy, surprise, fear, disgust and sadness. Our work can help social network users to understand how others may perceive them based on how they communicate in social media, in addition to its evident applications in online sales and marketing, targeted advertising, large scale polling and healthcare analytics.
On Correcting Misspelled Queries in Email Search
Authors: Bhole Abhijit , Udupa Raghavendra
Published: June 2022

We consider the problem of providing spelling corrections for misspelled queries in Email Search using user’s own mail data. A popular strategy for general query spelling correction is to generate corrections from query logs. However, this strategy is not effective in Email Search for two reasons: 1) query log of any sin- gle user is typically not rich enough to provide potential corrections for a new query 2) corrections generated us- ing query logs of other users are not particularly useful since the mail data as well as search intent are highly specific to the user. We address the challenge of design- ing an effective spelling correction algorithm for Email Search in the absence of query logs. We propose SpEQ, a Machine Learning based approach that generates cor- rections for misspelled queries directly from the user’s own mail data.
Voting Rules As Error-Correcting Codes
Authors: Procaccia Ariel , Shah Nisarg , Zick Yair
Published: June 2022

We present the first model of optimal voting under adversarial noise. From this viewpoint, voting rules are seen as error-correcting codes: their goal is to correct errors in the input rankings and recover a ranking that is close to the ground truth. We derive worst-case bounds on the relation between the average accuracy of the input votes, and the accuracy of the output ranking. Empirical results from real data show that our approach produces significantly more accurate rankings than alternative approaches.
Optimal Machine Strategies to Commit to in Two-Person Repeated Games
Authors: Zuo Song , Tang Pingzhong
Published: June 2022

The problem of computing optimal strategy to commit to in various games has attracted intense research interests and has important real-world applications such as security (attacker-defender) games. In this paper, we consider the problem of computing optimal leader’s machine to commit to in two-person repeated game, where the follower also plays a machine strategy. Machine strategy is the generalized notion of automaton strategy, where the number of states in the automaton can be possibly infinite. We begin with the simple case where both players are confined to automata strategies, and then extend to general (possibly randomized) machine strategies. We first give a concise linear program to compute the optimal leader’s strategy and give two efficient implementations of the linear program: one via enumeration of a convex hull and the other via randomization. We then investigate the case where two machines have different levels of intelligence in the sense that one machine is able to record more history information than the other. We show that an intellectually superior leader, sometimes considered being exploited by the follower, can figure out the follower’s machine by brute-force and exploit the follower in return.
Stable Invitations
Authors: Lee Hooyeon , Shoham Yoav
Published: June 2022

We consider the situation in which an organizer is trying to convenean event, and needs to choose whom out of a given set of agents to invite.Agents have preferences over how many attendees should be at the eventand possibly also who the attendees should be.This induces a stability requirement: All invited agents should preferattending to not attending, and all the other agents should not regretbeing not invited.The organizer's objective is to find an invitation of maximum size,subject to the stability requirement. We investigate the computational complexity of finding such an invitation when agents are truthful, as well as the mechanism design problem when agents act strategically.
Hedonic Coalition Formation in Networks
Authors: Hoefer Martin , Vaz Daniel , Wagner Lisa
Published: June 2022

Coalition formation is a fundamental problem in the organization of many multi-agent systems. In large populations, the formation of coalitions is often restricted by structural visibility and locality constraints under which agents can reorganize. We capture and study this aspect using a novel network-based model for dynamic locality within the popular framework of hedonic coalition formation games. We analyze the effects of network-based visibility and structure on the convergence of coalition formation processes to stable states. Our main result is a tight characterization of the structures based on which dynamic coalition formation can stabilize quickly. Maybe surprisingly, polynomial-time convergence can be achieved if and only if coalition formation is based on complete or star graphs.
Approximating Optimal Social Choice under Metric Preferences
Authors: Anshelevich Elliot , Bhardwaj Onkar , Postl John
Published: June 2022

We examine the quality of social choice mechanisms using a utilitarian view, in which all of the agents have costs for each of the possible alternatives. While these underlying costs determine what the optimal alternative is, they may be unknown to the social choice mechanism; instead the mechanism must decide on a good alternative based only on the ordinal preferences of the agents which are induced by the underlying costs. Due to its limited information, such a social choice mechanism cannot simply select the alternative that minimizes the total social cost (or minimizes some other objective function). Thus, we seek to bound the distortion: the worst-case ratio between the social cost of the alternative selected and the optimal alternative. Distortion measures how good a mechanism is at approximating the alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that the agent costs form a metric space, which is a natural assumption in many settings. We quantify the distortion of many well-known social choice mechanisms. We show that for both total social cost and median agent cost, many positional scoring rules have large distortion, while on the other hand Copeland and similar mechanisms perform optimally or near-optimally, always obtaining a distortion of at most 5. We also give lower bounds on the distortion that could be obtained by any deterministic social choice mechanism, and extend our results on median agent cost to more general objective functions.
A Unifying Hierarchy of Valuations with Complements and Substitutes
Authors: Feige Uriel , Feldman Michal , Immorlica Nicole , Izsak Rani , Lucier Brendan , Syrgkanis Vasilis
Published: June 2022

We introduce a new hierarchy over monotone set functions, that we refer to as MPH (Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. The highest level of the hierarchy, MPH-m (where m is the total number of items) captures all monotone functions. The lowest level, MPH-1, captures all monotone submodular functions, and more generally, the class of functions known as XOS. Every monotone function that has a positive hypergraph representation of rank k (in the sense defined by Abraham, Babaioff, Dughmi and Roughgarden [EC 2012]) is in MPH-k. Every monotone function that has supermodular degree k (in the sense defined by Feige and Izsak [ITCS 2013]) is in MPH-(k+1). In both cases, the converse direction does not hold, even in an approximate sense. We present additional results that demonstrate the expressiveness power of MPH-k.One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the MPH hierarchy. We present two such applications. One shows that the maximum welfare problem can be approximated within a ratio of k+1 if all players hold valuation functions in MPH-k. The other is an upper bound of 2k on the price of anarchy of simultaneous first price auctions.
A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences
Authors: Fujita Etsushi , Lesca Julien , Sonoda Akihisa , Todo Taiki , Yokoo Makoto
Published: June 2022

Core-selection is a crucial property of social choice functions, or rules, in social choice literature. It is also desirable to address the incentive of agents to cheat by misreporting their preferences. This paper investigates an exchange problem where each agent may have multiple indivisible goods, agents' preferences over sets of goods are assumed to be lexicographic, and side payments are not allowed. We propose an exchange rule called augmented top-trading-cycles (ATTC) procedure based on the original TTC procedure. We first show that the ATTC procedure is core-selecting. We then show that finding a beneficial misreport under the ATTC procedure is NP-hard. Under the ATTC procedure, we finally clarify the relationship between preference misreport and splitting, which is a different type of manipulation.
Combining Compact Representation and Incremental Generation in Large Games with Sequential Strategies
Authors: Bosansky Branislav , Jiang Albert Xin , Tambe Milind , Kiekintveld Christopher
Published: June 2022

Many search and security games played on a graph can be modeled as normal-form zero-sum games with strategies consisting of sequences of actions. The size of the strategy space provides a computational challenge when solving these games. This complexity is tackled either by using the compact representation of sequential strategies and linear programming, or by incremental strategy generation of iterative double-oracle methods. In this paper, we present novel hybrid of these two approaches: compact-strategy double-oracle (CS-DO) algorithm that combines the advantages of the compact representation with incremental strategy generation. We experimentally compare CS-DO with the standard approaches and analyze the impact of the size of the support on the performance of the algorithms. Results show that CS-DO dramatically improves the convergence rate in games with non-trivial support
Matching with Dynamic Ordinal Preferences
Authors: Hosseini Hadi , Larson Kate , Cohen Robin
Published: June 2022

We consider the problem of repeatedly matching a set of alternatives to a set of agents with dynamic ordinal preferences. Despite a recent focus on designing one-shot matching mechanisms in the absence of monetary transfers, little study has been done on strategic behavior of agents in sequential assignment problems. We formulate a generic dynamic matching problem via a sequential stochastic matching process. We design a mechanism based on random serial dictatorship (RSD) that, given any history of preferences and matching decisions, guarantees global stochastic strategyproofness while satisfying desirable local properties. We further investigate the notion of envyfreeness in such sequential settings.