bluuebunny/crossref_metadata_2025 huggingface dataset:
Veto-Consensus Multiple Kernel Learning
Authors: Zhou Yuxun , Hu Ninghang , Spanos Costas
Published: June 2022

We propose Veto-Consensus Multiple Kernel Learning (VCMKL), a novel way of combining multiple kernels such that one class of samples is described by the logical intersection (consensus) of base kernelized decision rules, whereas the other classes by the union (veto) of their complements. The proposed configuration is a natural fit for domain description and learning with hidden subgroups. We first provide generalization risk bound in terms of the Rademacher complexity of the classifier, and then a large margin multi-ν learning objective with tunable training error bound is formulated. Seeing that the corresponding optimization is non-convex and existing methods severely suffer from local minima, we establish a new algorithm, namely Parametric Dual Descent Procedure (PDDP) that can approach global optimum with guarantees. The bases of PDDP are two theorems that reveal the global convexity and local explicitness of the parameterized dual optimum, for which a series of new techniques for parametric program have been developed. The proposed method is evaluated on extensive set of experiments, and the results show significant improvement over the state-of-the-art approaches.
Knowledge Transfer with Interactive Learning of Semantic Relationships
Authors: Choi Jonghyun , Hwang Sung Ju , Sigal Leonid , Davis Larry
Published: June 2022

We propose a novel learning framework for object categorization with interactive semantic feedback. In this framework, a discriminative categorization model improves through human-guided iterative semantic feedbacks. Specifically, the model identifies the most helpful relational semantic queries to discriminatively refine the model. The user feedback on whether the relationship is semantically valid or not is incorporated back into the model, in the form of regularization, and the process iterates. We validate the proposed model in a few-shot multi-class classification scenario, where we measure classification performance on a set of ‘target’ classes, with few training instances, by leveraging and transferring knowledge from ‘anchor’ classes, that contain larger set of labeled instances.
Conservativeness of Untied Auto-Encoders
Authors: Im Daniel , Belghazi Mohamed , Memisevic Roland
Published: June 2022

We discuss necessary and sufficient conditions for an auto-encoder to define a conservative vector field, in which case it is associated with anenergy function akin to the unnormalized log-probability of the data.We show that the conditions for conservativeness are more general than for encoder and decoder weights to be the same ("tied weights''), and thatthey also depend on the form of the hidden unit activation functions.Moreover, we show that contractive training criteria, such as denoising, enforces these conditions locally.Based on these observations, we show how we can use auto-encoders to extract the conservative component of a vector field.
Marginalized Continuous Time Bayesian Networks for Network Reconstruction from Incomplete Observations
Authors: Studer Lukas , Paulevé Loic , Zechner Christoph , Reumann Matthias , Rodríguez Martínez María , Koeppl Heinz
Published: June 2022

Continuous Time Bayesian Networks (CTBNs) provide a powerful means to model complex network dynamics. How- ever, their inference is computationally demanding — especially if one considers incomplete and noisy time-series data. The latter gives rise to a joint state- and parameter estimation problem, which can only be solved numerically. Yet, finding the exact parameterization of the CTBN has often only secondary importance in practical scenarios. We therefore focus on the structure learning problem and present a way to analytically marginalize the Markov chain underlying the CTBN model with respect its parameters. Since the resulting stochastic process is parameter-free, its inference reduces to an optimal filtering problem. We solve the latter using an efficient parallel implementation of a sequential Monte Carlo scheme. Our framework enables CTBN inference to be applied to incomplete noisy time-series data frequently found in molecular biology and other disciplines.
Compressed Conditional Mean Embeddings for Model-Based Reinforcement Learning
Authors: Lever Guy , Shawe-Taylor John , Stafford Ronnie , Szepesvari Csaba
Published: June 2022

We present a model-based approach to solving Markov decision processes (MDPs) in which the system dynamics are learned using conditional mean embeddings (CMEs). This class of methods comes with strong performance guarantees, and enables planning to be performed in an induced finite (pseudo-)MDP, which approximates the MDP, but can be solved exactly using dynamic programming. Two drawbacks of existing methods exist: firstly, the size of the induced finite (pseudo-)MDP scales quadratically with the amount of data used to learn the model, costing much memory and time when planning with the learned model; secondly, learning the CME itself using powerful kernel least-squares is costly – a second computational bottleneck. We present an algorithm which maintains a rich kernelized CME model class, but solves both problems: firstly we demonstrate that the loss function for the CME model suggests a principled approach to compressing the induced (pseudo-)MDP, leading to faster planning, while maintaining guarantees; secondly we propose to learn the CME model itself using fast sparse-greedy kernel regression well-suited to the RL context. We demonstrate superior performance to existing methods in this class of modelbased approaches on a range of MDPs.
Five Dimensions of Reasoning in the Wild
Authors: Perlis Don
Published: June 2022

Reasoning does not work well when done in isolation from its significance, both to the needs and interests of an agent and with respect to the wider world. Moreover, those issues may best be handled with a new sort of data structure that goes beyond the knowledge base and incorporates aspects of perceptual knowledge and even more, in which a kind of anticipatory action may be key.
Embedding Ethical Principles in Collective Decision Support Systems
Authors: Greene Joshua , Rossi Francesca , Tasioulas John , Venable Kristen , Williams Brian
Published: June 2022

The future will see autonomous machines acting in the same environment as humans, in areas as diverse as driving, assistive technology, and health care. Think of self-driving cars, companion robots, and medical diagnosis support systems. We also believe that humans and machines will often need to work together and agree on common decisions. Thus hybrid collective decision making systems will be in great need. In this scenario, both machines and collective decision making systems should follow some form of moral values and ethical principles (appropriate to where they will act but always aligned to humans'), as well as safety constraints. In fact, humans would accept and trust more machines that behave as ethically as other humans in the same environment. Also, these principles would make it easier for machines to determine their actions and explain their behavior in terms understandable by humans. Moreover, often machines and humans will need to make decisions together, either through consensus or by reaching a compromise. This would be facilitated by shared moral values and ethical principles.
Robust Classification under Covariate Shift with Application to Active Learning
Authors: Liu Anqi
Published: June 2022

In supervised machine learning, model performance can decrease significantly when the distribution generating the new data varies from the distribution that generated the training data. One of the situations is covariate shift which happens a lot when labeled training data is missing, hard to get access to or very expensive to uniformly collect. All (probabilistic) classifiers will suffer from covariate shift. This motivates our research. Generally, we try to answer this question: how can we deal with covariate shift and generate predictions that are robust and reliable? We propose to develop a general framework for classification under covariate shift that is robust, flexible and accurate.
Architectural Mechanisms for Situated Natural Language Understanding in Uncertain and Open Worlds
Authors: Williams Tom
Published: June 2022

As natural language capable robots and other agents become more commonplace, the ability for these agents to understand truly natural human speech is becoming increasingly important. What is more, these agents must be able to understand truly natural human speech in realistic scenarios, in which an agent may not have full certainty in its knowledge of its environment, and in which an agent may not have full knowledge of the entities contained in its environment. As such, I am interested in developing architectural mechanisms which will allow robots to understand natural language in uncertain and open-worlds. My work towards this goal has primarily focused on two problems: (1) reference resolution, and (2) pragmatic reasoning.
Interactive Learning and Analogical Chaining for Moral and Commonsense Reasoning
Authors: Blass Joseph
Published: June 2022

Autonomous systems must consider the moral ramifications of their actions. Moral norms vary among people and depend on common sense, posing a challenge for encoding them explicitly in a system. I propose to develop a model of repeated analogical chaining and analogical reasoning to enable autonomous agents to interactively learn to apply common sense and model an individual’s moral norms.
Machine Learning for Computational Psychology
Authors: Brown Sarah
Published: June 2022

Advances in sensing and imaging have provided psychology researchers new tools to understand how the brain creates the mind and simultaneously revealed the need for a new paradigm of mind-brain correspondence-- a set of basic theoretical tenets and an overhauled methodology. I develop machine learning methods to overcome three initial technical barriers to application of the new paradigm. I assess candidate solutions to these problems using two test datasets representing different areas of psychology: the first aiming to build more objective Post-Traumatic Stress Disorder(PTSD) diagnostic tools using virtual reality and peripheral physiology, the second aiming to verify theoretical tenets of the new paradigm in a study of basic affect using functional Magnetic Resonance Imaging(fMRI). Specifically I address three technical challenges: assessing performance in small, real datasets through stability; learning from labels of varying quality; and probabilistic representations of dynamical systems.
EKNOT: Event Knowledge from News and Opinions in Twitter
Authors: Li Min , Wang Jingjing , Tong Wenzhu , Yu Hongkun , Ma Xiuli , Chen Yucheng , Cai Haoyan , Han Jiawei
Published: June 2022

We present the EKNOT system that automatically discovers major events from online news articles, connects each event to its discussion in Twitter, and provides a comprehensive summary of the events from both news media and social media's point of view. EKNOT takes a time period as input and outputs a complete picture of the events within the given time range along with the public opinions. For each event, EKNOT provides multi-dimensional summaries: a) a summary from news for an objective description; b) a summary from tweets containing opinions/sentiments; c) an entity graph which illustrates the major players involved and their correlations; d) the time span of the event; and e) an opinion (sentiment) distribution. Also, if a user is interested in a particular event, he/she can zoom into this event to investigate its aspects (sub-events) summarized in the same manner. EKNOT is built on real-time crawled news articles and tweets, allowing users to explore the dynamics of major events with minimal delays.
Modeling and Experimentation Framework for Fuzzy Cognitive Maps
Authors: Leon Espinosa Maikel , Napoles Ruiz Gonzalo
Published: June 2022

Many papers describe the use of Fuzzy Cognitive Maps as a modeling/representation technique for real-life scenarios’ simulation or prediction. However, not many real software implementations are described neither found. In this proposal the authors describe a modeling and experimentation framework where realistic problems can be recreated using Fuzzy Cognitive Maps as a knowledge representation form. Design elements, and descriptions of the algorithms that have been incorporated into the software, and hybridized with Fuzzy Cognitive Maps, are presented in this paper. Case studies were conducted and are illustrated with the intention of demonstrating the success and practical value of the general approach together with the implementation tool.
Predicting Gaming Related Properties from Twitter Accounts
Authors: Gorinova Maria , Lewenberg Yoad , Bachrach Yoram , Kalaitzis Alfredo , Fagan Michael , Carignan Dean , Gautam Nitin
Published: June 2022

We demonstrate a system for predicting gaming related properties from Twitter accounts. Our system predicts various traits of users based on the tweets publicly available in their profiles. Such inferred traits include degrees of tech-savviness and knowledge on computer games, actual gaming performance, preferred platform, degree of originality, humor and influence on others. Our system is based on machine learning models trained on crowd-sourced data. It allows people to select Twitter accounts of their fellow gamers, examine the trait predictions made by our system, and the main drivers of these predictions. We present empirical results on the performance of our system based on its accuracy on our crowd-sourced dataset.
EDDIE: An Embodied AI System for Research and Intervention for Individuals with ASD
Authors: Selkowitz Robert , Rodgers Jonathan , Moskal P. , Mrowczynski Jon , Colson Christine
Published: June 2022

We report on the ongoing development of EDDIE (Emotion Demonstration, Decoding, Interpretation, and Encoding), an interactive embodied AI to be deployed as an intervention system for children diagnosed with High-Functioning Autism Spectrum Disorders (HFASD). EDDIE presents the subject with interactive requests to decode facial expressions presented through an avatar, encode requested expressions, or do both in a single session. Facial tracking software interprets the subject’s response, and allows for immediate feedback. The system fills a need in research and intervention for children with HFASD by providing an engaging platform for presentation of exemplar expressions consistent with mechanical systems of facial action measurement integrated with an automatic system for interpreting and giving feedback to the subject’s expressions. Both live interaction with EDDIE and video recordings of human-EDDIE interaction will be demonstrated.
An Image Analysis Environment for Species Identification of Food Contaminating Beetles
Authors: Martin Daniel , Ding Hongjian , Wu Leihong , Semey Howard , Barnes Amy , Langley Darryl , Park Su Inn , Liu Zhichao , Tong Weida , Xu Joshua
Published: June 2022

Food safety is vital to the well-being of society; therefore, it is important to inspect food products to ensure minimal health risks are present. The presence of certain species of insects, especially storage beetles, is a reliable indicator of possible contamination during storage and food processing. However, the current approach of identifying species by visual examination of insect fragments is rather subjective and time-consuming. To aid this inspection process, we have developed in collaboration with FDA food analysts some image analysis-based machine intelligence to achieve species identification with up to 90% accuracy. The current project is a continuation of this development effort. Here we present an image analysis environment that allows practical deployment of the machine intelligence on computers with limited processing power and memory. Using this environment, users can prepare input sets by selecting images for analysis, and inspect these images through the integrated panning and zooming capabilities. After species analysis, the results panel allows the user to compare the analyzed images with reference images of the proposed species. Further additions to this environment should include a log of previously analyzed images, and eventually extend to interaction with a central cloud repository of images through a web-based interface.
The Turing Test in the Classroom
Authors: Torrey Lisa , Johnson Karen , Sondergard Sid , Ponce Pedro , Desmond Laura
Published: June 2022

This paper discusses the Turing Test as an educational activity for undergraduate students. It describes in detail an experiment that we conducted in a first-year non-CS course. We also suggest other pedagogical purposes that the Turing Test could serve.
BeeMo, a Monte Carlo Simulation Agent for Playing Parameterized Poker Squares
Authors: Castro-Wunsch Karo , Maga William , Anton Calin
Published: June 2022

We investigated Parameterized Poker Squares to approximate an optimal game playing agent. We organized our inquiry along three dimensions: partial hand representation, search algorithms, and partial hand utility learning. For each dimension we implemented and evaluated several designs, among which we selected the best strategies to use for BeeMo, our final product. BeeMo uses a parallel flat Monte-Carlo search. The search is guided by a heuristic based on hand patterns utilities, which are learned through an iterative improvement method involving Monte-Carlo simulations and optimized greedy search.
Using Declarative Programming in an Introductory Computer Science Course for High School Students
Authors: Reyes Maritza , Perez Cynthia , Upchurch Rocky , Yuen Timothy , Zhang Yuanlin
Published: June 2022

This paper discusses the design of an introductory computer science course for high school students using declarative programming. Though not often taught at the K-12 level, declarative programming is a viable paradigm for teaching computer science due to its importance in artificial intelligence and in helping student explore and understand problem spaces. This paper describes the authors' implementation of a declarative programming course for high school students during a 4-week summer session.
What’s Hot in Human Language Technology: Highlights from NAACL HLT 2015
Authors: Chai Joyce , Sarkar Anoop , Mihalcea Rada
Published: June 2022

This paper shows a few examples to highlight the trends observed at the NAACL HLT 2015 conference.
Unsupervised Lexical Simplification for Non-Native Speakers
Authors: Paetzold Gustavo , Specia Lucia
Published: June 2022

Lexical Simplification is the task of replacing complex words with simpler alternatives. We propose a novel, unsupervised approach for the task. It relies on two resources: a corpus of subtitles and a new type of word embeddings model that accounts for the ambiguity of words. We compare the performance of our approach and many others over a new evaluation dataset, which accounts for the simplification needs of 400 non-native English speakers. The experiments show that our approach outperforms state-of-the-art work in Lexical Simplification.
Supervised Hashing via Uncorrelated Component Analysis
Authors: Sohn SungRyull , Kim Hyunwoo , Kim Junmo
Published: June 2022

The Approximate Nearest Neighbor (ANN) search problem is important in applications such as information retrieval. Several hashing-based search methods that provide effective solutions to the ANN search problem have been proposed. However, most of these focus on similarity preservation and coding error minimization, and pay little attention to optimizing the precision-recall curve or receiver operating characteristic curve. In this paper, we propose a novel projection-based hashing method that attempts to maximize the precision and recall. We first introduce an uncorrelated component analysis (UCA) by examining the precision and recall, and then propose a UCA-based hashing method. The proposed method is evaluated with a variety of datasets. The results show that UCA-based hashing outperforms state-of-the-art methods, and has computationally efficient training and encoding processes.
Identifying Sentiment Words Using an Optimization Model with L1 Regularization
Authors: Deng Zhi-Hong , Yu Hongliang , Yang Yunlun
Published: June 2022

Sentiment word identification is a fundamental work in numerous applications of sentiment analysis and opinion mining, such as review mining, opinion holder finding, and twitter classification. In this paper, we propose an optimization model with L1 regularization, called ISOMER, for identifying the sentiment words from the corpus. Our model can employ both seed words and documents with sentiment labels, different from most existing researches adopting seed words only. The L1 penalty in the objective function yields a sparse solution since most candidate words have no sentiment. The experiments on the real datasets show that ISOMER outperforms the classic approaches, and that the lexicon learned by ISOMER can be effectively adapted to document-level sentiment analysis.
Phrase-Based Presentation Slides Generation for Academic Papers
Authors: Wang Sida , Wan Xiaojun , Du Shikang
Published: June 2022

Automatic generation of presentation slides for academic papers is a very challenging task. Previous methods for addressing this task are mainly based on document summarization techniques and they extract document sentences to form presentation slides, which are not well-structured and concise. In this study, we propose a phrase-based approach to generate well-structured and concise presentation slides for academic papers. Our approach first extracts phrases from the given paper, and then learns both the saliency of each phrase and the hierarchical relationship between a pair of phrases. Finally a greedy algorithm is used to select and align the salient phrases in order to form the well-structured presentation slides. Evaluation results on a real dataset verify the efficacy of our proposed approach.
Semantic Proximity Search on Heterogeneous Graph by Proximity Embedding
Authors: Liu Zemin , Zheng Vincent W. , Zhao Zhou , Zhu Fanwei , Chang Kevin Chen-Chuan , Wu Minghui , Ying Jing
Published: June 2022

Many real-world networks have a rich collection of objects. The semantics of these objects allows us to capture different classes of proximities, thus enabling an important task of semantic proximity search. As the core of semantic proximity search, we have to measure the proximity on a heterogeneous graph, whose nodes are various types of objects. Most of the existing methods rely on engineering features about the graph structure between two nodes to measure their proximity. With recent development on graph embedding, we see a good chance to avoid feature engineering for semantic proximity search. There is very little work on using graph embedding for semantic proximity search. We also observe that graph embedding methods typically focus on embedding nodes, which is an "indirect'' approach to learn the proximity. Thus, we introduce a new concept of proximity embedding, which directly embeds the network structure between two possibly distant nodes. We also design our proximity embedding, so as to flexibly support both symmetric and asymmetric proximities. Based on the proximity embedding, we can easily estimate the proximity score between two nodes and enable search on the graph. We evaluate our proximity embedding method on three real-world public data sets, and show it outperforms the state-of-the-art baselines.
Random-Radius Ball Method for Estimating Closeness Centrality
Authors: Inariba Wataru , Akiba Takuya , Yoshida Yuichi
Published: June 2022

In the analysis of real-world complex networks, identifying important vertices is one of the most fundamental operations. A variety of centrality measures have been proposed and extensively studied in various research areas. Many of distance-based centrality measures embrace some issues in treating disconnected networks, which are resolved by the recently emerged harmonic centrality. This paper focuses on a family of centrality measures including the harmonic centrality and its variants, and addresses their computational difficulty on very large graphs by presenting a new estimation algorithm named the random-radius ball (RRB) method. The RRB method is easy to implement, and a theoretical analysis, which includes the time complexity and error bounds, is also provided. The effectiveness of the RRB method over existing algorithms is demonstrated through experiments on real-world networks.
A Leukocyte Detection Technique in Blood Smear Images Using Plant Growth Simulation Algorithm
Authors: Bhattacharjee Deblina , Paul Anand
Published: June 2022

For quite some time, the analysis of leukocyte images has drawn significant attention from the fields of medicine and computer vision alike where various techniques have been used to automate the manual analysis and classification of such images. Analysing such samples manually for detecting leukocytes is time-consuming and prone to error as the cells have different morphological features. Therefore, in order to automate and optimize the process, the nature-inspired Plant Growth Simulation Algorithm (PGSA) has been applied in this paper. An automated detection technique of white blood cells embedded in obscured, stained and smeared images of blood samples has been presented in this paper which is based on a random bionic algorithm and makes use of a fitness function that measures the similarity of the generated candidate solution to an actual leukocyte. As the proposed algorithm proceeds the set of candidate solutions evolves, guaranteeing their fit with the actual leukocytes outlined in the edge map of the image. The experimental results of the stained images and the empirical results reported validate the higher precision and sensitivity of the proposed method than the existing methods. Further, the proposed method reduces the feasible sets of candidate points in each iteration, thereby decreasing the required run time of load flow, objective function evaluation, thus reaching the goal state in minimum time and within the desired constraints.
SnapNETS: Automatic Segmentation of Network Sequences with Node Labels
Authors: Amiri Sorour , Chen Liangzhe , Prakash B.
Published: June 2022

Given a sequence of snapshots of flu propagating over a population network, can we find a segmentation when the patterns of the disease spread change, possibly due to interventions? In this paper, we study the problem of segmenting graph sequences with labeled nodes. Memes on the Twitter network, diseases over a contact network, movie-cascades over a social network, etc. are all graph sequences with labeled nodes. Most related work is on plain graphs (and hence ignore the label dynamics) or fix parameters or require much feature engineering. Instead, we propose SnapNETS, to automatically find segmentations of such graph sequences, with different characteristics of nodes of each label in adjacent segments. It satisfies all the desired properties (being parameter-free, comprehensive and scalable) by leveraging a principled, multi-level, flexible framework which maps the problem to a path optimization problem over a weighted DAG. Extensive experiments on several diverse real datasets show that it finds cut points matching ground-truth or meaningful external signals outperforming non-trivial baselines. We also show that SnapNETS scales near-linearly with the size of the input.
Accelerating Multiagent Reinforcement Learning through Transfer Learning
Authors: Da Silva Felipe , Costa Anna
Published: June 2022

Reinforcement Learning (RL) is a widely used solution for sequential decision-making problems and has been used in many complex domains. However, RL algorithms suffer from scalability issues, especially when multiple agents are acting in a shared environment. This research intends to accelerate learning in multiagent sequential decision-making tasks by reusing previous knowledge, both from past solutions and advising between agents. We intend to contribute a Transfer Learning framework focused on Multiagent RL, requiring as few domain-specific hand-coded parameters as possible.
Scalable Nonparametric Tensor Analysis
Authors: Zhe Shandian
Published: June 2022

Multiway data, described by tensors, are common in real-world applications. For example, online advertising click logs can be represented by a three-mode tensor (user, advertisement, context). The analysis of tensors is closely related to many important applications, such as click-through-rate (CTR) prediction, anomaly detection and product recommendation. Despite the success of existing tensor analysis approaches, such as Tucker, CANDECOMP/PARAFAC and infinite Tucker decompositions, they are either not enough powerful to capture complex hidden relationships in data, or not scalable to handle real-world large data. In addition, they may suffer from the extreme sparsity in real data, i.e., when the portion of nonzero entries is extremely low; they lack of principled ways to discover other patterns — such as an unknown number of latent clusters — which are critical for data mining tasks such as anomaly detection and market targeting. To address these challenges, I used nonparametric Bayesian techniques, such as Gaussian processes (GP) and Dirichlet processes (DP), to model highly nonlinear interactions and to extract hidden patterns in tensors; I derived tractable variational evidence lower bounds, based on which I developed scalable, distributed or online approximate inference algorithms. Experiments on both simulation and real-world large data have demonstrated the effect of my propoaed approaches.
Cornhole: A Widely-Accessible AI Robotics Task
Authors: Derbinsky Nate , Frasca Tyler
Published: June 2022

In this paper we present the game of cornhole as a compelling, accessible, and adaptable AI robotics task. Cornhole is a fun and social game with simple rules, but involves strategy and physical training for humans to play competitively; thus, developing a robot that can play at the level of even the average human player presents a multitude of opportunities for curricular integration at a variety of levels. We characterize the AI tasks involved with the game, and present results and resources gained from preliminary offerings.
A Monte Carlo Localization Assignment Using a Neato Vacuum with ROS
Authors: Yang Zuozhi , Neller Todd
Published: June 2022

Monte Carlo Localization (MCL) is a sampling-based algorithm for mobile robot localization. In this paper we describe an MCL assignment and its required hardware and software. The Neato vacuum robot and a Raspberry Pi serve as the core of the robot model. The Robot Operating System (ROS) is used as the robot programming environment. Students are expected to learn the localization problem, implement the MCL algorithm, and better understand the kidnapped robot problem and the limitations of MCL by observing the performance of the algorithm in real-time application.
Optimal Personalized Defense Strategy Against Man-In-The-Middle Attack
Authors: Li Xiaohong , Li Shuxin , Hao Jianye , Feng Zhiyong , An Bo
Published: June 2022

The Man-In-The-Middle (MITM) attack is one of the most common attacks employed in the network hacking. MITM attackers can successfully invoke attacks such as denial of service (DoS) and port stealing, and lead to surprisingly harmful consequences for users in terms of both financial loss and security issues. The conventional defense approaches mainly consider how to detect and eliminate those attacks or how to prevent those attacks from being launched in the first place. This paper proposes a game-theoretic defense strategy from a different perspective, which aims at minimizing the loss that the whole system sustains given that the MITM attacks are inevitable. We model the interaction between the attacker and the defender as a Stackelberg security game and adopt the Strong Stackelberg Equilibrium (SSE) as the defender's strategy. Since the defender's strategy space is infinite in our model, we employ a novel method to reduce the searching space of computing the optimal defense strategy. Finally, we empirically evaluate our optimal defense strategy by comparing it with non-strategic defense strategies. The results indicate that our game-theoretic defense strategy significantly outperforms other non-strategic defense strategies in terms of decreasing the total losses against MITM attacks.
The Dollar Auction with Spiteful Players
Authors: Waniek Marcin , Tran-Thanh Long , Michalak Tomasz , Jennings Nicholas
Published: June 2022

The dollar auction is an auction model used to analyse the dynamics of conflict escalation. In this paper, we analyse the course of an auction when participating players are spiteful, i.e., they are motivated not only by their own profit, but also by the desire to hurt the opponent. We investigate this model for the complete information setting, both for the standard scenario and for the situation where auction starts with non-zero bids. Our results give us insight into the possible effects of meanness onto conflict escalation.
Selfish Knapsack
Authors: Feigenbaum Itai , Johnson Matthew
Published: June 2022

We consider a strategic variant of the knapsack problem: the items are owned by agents, and agents can misrepresent their sets of items---either by hiding items (understating), or by reporting fake ones (overstating). Each agent's utility equals the total value of her items included in the knapsack. We wish to maximize social welfare, and attempt to design mechanisms that lead to small worst-case approximation ratios at equilibrium. We provide a randomized mechanism with attractive strategic properties: it has a price of anarchy of 2 for Bayes-Nash and coarse correlated equilibria. For overstating-only agents, it becomes strategyproof, and has a matching lower bound. For the case of two understating-only agents, we provide a specialized randomized strategyproof 1.522-approximate mechanism, and a lower bound of 1.09. When all agents but one are honest, we provide a deterministic strategyproof 1.618-approximate mechanism with a matching lower bound. The latter two mechanisms are also useful in problems beyond the one in consideration.
Axiomatic Characterization of Game-Theoretic Network Centralities
Authors: Skibski Oskar , Michalak Tomasz , Rahwan Talal
Published: June 2022

One of the fundamental research challenges in network science is the centrality analysis, i.e., identifying the nodes that play the most important roles in the network. In this paper, we focus on the game-theoretic approach to centrality analysis. While various centrality indices have been proposed based on this approach, it is still unknown what distinguishes this family of indices from the more classical ones. In this paper, we answer this question by providing the first axiomatic characterization of game-theoretic centralities. Specifically, we show that every centrality can be obtained following the game-theoretic approach, and show that two natural classes of game-theoretic centrality can be characterized by two intuitive properties pertaining to Myerson's notion of Fairness.
Faster and Simpler Algorithm for Optimal Strategies of Blotto Game
Authors: Behnezhad Soheil , Dehghani Sina , Derakhshan Mahsa , Hajiaghayi MohammadTaghi , Seddighin Saeed
Published: June 2022

In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battleﬁelds.The winner of each battleﬁeld is determined independently by a winner-take-all rule. The ultimate payoff of each colonel is the number of battleﬁelds he wins. This game is commonly used for analyzing a wide range of applications such as the U.S presidential election, innovative technology competitions, advertisements, etc. There have been persistent efforts for ﬁnding the optimal strategies for the Colonel Blotto game. After almost a century Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin provided a poly-time algorithm for ﬁnding the optimal strategies. They ﬁrst model the problem by a Linear Program (LP) with exponential number of constraints and use Ellipsoid method to solve it. However, despite the theoretical importance of their algorithm, it ishighly impractical. In general, even Simplex method (despite its exponential running-time) performs better than Ellipsoid method in practice. In this paper, we provide the ﬁrst polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game. We use linear extension techniques. Roughly speaking, we project the strategy space polytope to a higher dimensional space, which results in a lower number of facets for the polytope.We use this polynomial-size LP to provide a novel, simpler and signiﬁcantly faster algorithm for ﬁnding the optimal strategies for the Colonel Blotto game. We further show this representation is asymptotically tight in terms of the number of constraints. We also extend our approach to multi-dimensional Colonel Blotto games, and implement our algorithm to observe interesting properties of Colonel Blotto; for example, we observe the behavior of players in the discrete model is very similar to the previously studied continuous model.
SAT Competition 2016: Recent Developments
Authors: Balyo Tomas , Heule Marijn , Jarvisalo Matti
Published: June 2022

We give an overview of SAT Competition 2016, the 2016 edition of thefamous competition for Boolean satisfiability (SAT) solvers with over 20 years of history. A key aim is to point out ``what's hot'' in SAT competitions in 2016, i.e., new developments in thecompetition series, including new competition tracks and new solver techniquesimplemented in some of the award-winning solvers.
Going Beyond Primal Treewidth for (M)ILP
Authors: Ganian Robert , Ordyniak Sebastian , Ramanujan M.
Published: June 2022

Integer Linear Programming (ILP) and its mixed variant (MILP) are archetypical examples of NP-complete optimization problems which have a wide range of applications in various areas of artificial intelligence. However, we still lack a thorough understanding of which structural restrictions make these problems tractable. Here we focus on structure captured via so-called decompositional parameters, which have been highly successful in fields such as boolean satisfiability and constraint satisfaction but have not yet reached their full potential in the ILP setting. In particular, primal treewidth (an established decompositional parameter) can only be algorithmically exploited to solve ILP under restricted circumstances. Our main contribution is the introduction and algorithmic exploitation of two new decompositional parameters for ILP and MILP. The first, torso-width, is specifically tailored to the linear programming setting and is the first decompositional parameter which can also be used for MILP. The latter, incidence treewidth, is a concept which originates from boolean satisfiability but has not yet been used in the ILP setting; here we obtain a full complexity landscape mapping the precise conditions under which incidence treewidth can be used to obtain efficient algorithms. Both of these parameters overcome previous shortcomings of primal treewidth for ILP in unique ways, and consequently push the frontiers of tractability for these important problems.
Efficient Stochastic Optimization for Low-Rank Distance Metric Learning
Authors: Zhang Jie , Zhang Lijun
Published: June 2022

Although distance metric learning has been successfully applied to many real-world applications, learning a distance metric from large-scale and high-dimensional data remains a challenging problem. Due to the PSD constraint, the computational complexity of previous algorithms per iteration is at least O(d2) where d is the dimensionality of the data.In this paper, we develop an efficient stochastic algorithm  for a class of distance metric learning problems with nuclear norm regularization, referred to as low-rank DML. By utilizing the low-rank structure of the intermediate solutions and stochastic gradients, the complexity of our algorithm has a linear dependence on the dimensionality d. The key idea is to maintain all the iterates  in factorized representations  and construct  stochastic gradients that are low-rank. In this way, the projection onto the PSD cone can be implemented efficiently by incremental SVD. Experimental results on several data sets validate the effectiveness and efficiency of our method.
Embedded Bandits for Large-Scale Black-Box Optimization
Authors: Al-Dujaili Abdullah , Suresh S.
Published: June 2022

Random embedding has been applied with empirical success to large-scale black-box optimization problems with low effective dimensions. This paper proposes the EmbeddedHunter algorithm, which incorporates the technique in a hierarchical stochastic bandit setting, following the optimism in the face of uncertainty principle and breaking away from the multiple-run framework in which random embedding has been conventionally applied similar to stochastic black-box optimization solvers. Our proposition is motivated by the bounded mean variation in the objective value for a low-dimensional point projected randomly into the decision space of Lipschitz-continuous problems. In essence, the EmbeddedHunter algorithm expands optimistically a partitioning tree over a low-dimensional — equal to the effective dimension of the problem —search space based on a bounded number of random embeddings of sampled points from the low-dimensional space. In contrast to the probabilistic theoretical guarantees of multiple-run random-embedding algorithms, the finite-time analysis of the proposed algorithm presents a theoretical upper bound on the regret as a function of the algorithm's number of iterations. Furthermore, numerical experiments were conducted to validate its performance. The results show a clear performance gain over recently proposed random embedding methods for large-scale problems, provided the intrinsic dimensionality is low.
Parallel Asynchronous Stochastic Variance Reduction for Nonconvex Optimization
Authors: Fang Cong , Lin Zhouchen
Published: June 2022

Nowadays, asynchronous parallel algorithms have received much attention in the optimization field due to the crucial demands for modern large-scale optimization problems. However, most asynchronous algorithms focus on convex problems. Analysis on nonconvex problems is lacking. For the Asynchronous Stochastic Descent (ASGD) algorithm, the best result from (Lian et al., 2015) can only achieve an asymptotic O(\frac{1}{\epsilon^2}) rate (convergence to the stationary points) on nonconvex problems. In this paper, we study Stochastic Variance Reduced Gradient (SVRG) in the asynchronous setting. We propose the Asynchronous Stochastic Variance Reduced Gradient (ASVRG) algorithm for nonconvex finite-sum problems. We develop two schemes for ASVRG, depending on whether the parameters are updated as an atom or not. We prove that both of the two schemes can achieve linear speed up (a non-asymptotic O(\frac{n^\frac{2}{3}}{\epsilon}) rate to the stationary points) for nonconvex problems when the delay parameter \tau\leq n^{\frac{1}{3}}, where n is the number of training samples. We also establish a non-asymptotic O(\frac{n^\frac{2}{3}\tau^\frac{1}{3}}{\epsilon}) rate (convergence to the stationary points) for our algorithm without assumptions on \tau. This further demonstrates that even with asynchronous updating, SVRG has less number of Incremental First-order Oracles (IFOs) compared with Stochastic Gradient Descent and Gradient Descent. We also experiment on a shared memory multi-core system to demonstrate the efficiency of our algorithm.
Reactive Dialectic Search Portfolios for MaxSAT
Authors: Ansótegui Carlos , Pon Josep , Sellmann Meinolf , Tierney Kevin
Published: June 2022

Metaheuristics have been developed to provide general purpose approaches for solving hard combinatorial problems. While these frameworks often serve as the starting point for the development of problem-specific search procedures, they very rarely work efficiently in their default state. We combine the ideas of reactive search, which adjusts key parameters during search, and algorithm configuration, which fine-tunes algorithm parameters for a given set of problem instances, for the automatic compilation of a portfolio of highly reactive dialectic search heuristics for MaxSAT. Even though the dialectic search metaheuristic knows nothing more about MaxSAT than how to evaluate the cost of a truth assignment, our automatically generated solver defines a new state of the art for random weighted partial MaxSAT instances. Moreover, when combined with an industrial MaxSAT solver, the self-assembled reactive portfolio was able to win four out of nine gold medals at the recent 2016 MaxSAT Evaluation on random, crafted, and industrial partial and weighted-partial MaxSAT instances.
New Lower Bound for the Minimum Sum Coloring Problem
Authors: Lecat Clément , Lucet Corinne , Li Chu-Min
Published: June 2022

The Minimum Sum Coloring Problem (MSCP) is an NP-Hard problem derived from the graph coloring problem (GCP) and has practical applications in different domains such as VLSI design, distributed resource allocation, and scheduling. There exist few exact solutions for MSCP, probably due to its search space much more elusive than that of GCP. On the contrary, much effort is spent in the literature to develop upper and lower bounds for MSCP. In this paper, we borrow a notion called motif, that was used in a recent work for upper bounding the minimum number of colors in an optimal solution of MSCP, to develop a new algebraic lower bound called for MSCP. Experiments on standard benchmarks for MSCP and GCP show that this new lower bound is substantially better than the existing lower bounds for several families of graphs.
Ontology Materialization by Abstraction Refinement in Horn SHOIF
Authors: Glimm Birte , Kazakov Yevgeny , Tran Trung-Kien
Published: June 2022

Abstraction refinement is a recently introduced technique using which reasoning over large ABoxes is reduced to reasoning over small abstract ABoxes. Although the approach is sound for any classical Description Logic such as SROIQ, it is complete only for Horn ALCHOI. In this paper, we propose an extension of this method that is now complete for Horn SHOIF and also handles role- and equality-materialization. To show completeness, we use a tailored set of materialization rules that loosely decouple the ABox from the TBox. An empirical evaluation demonstrates that, despite the new features, the abstractions are still significantly smaller than the original ontologies and the materialization can be computed efficiently.