bluuebunny/crossref_metadata_2025 huggingface dataset:
Structural Deep Embedding for Hyper-Networks
Authors: Tu Ke , Cui Peng , Wang Xiao , Wang Fei , Zhu Wenwu
Published: June 2022

Network embedding has recently attracted lots of attentions in data mining. Existing network embedding methods mainly focus on networks with pairwise relationships. In real world, however, the relationships among data points could go beyond pairwise, i.e., three or more objects are involved in each relationship represented by a hyperedge, thus forming hyper-networks. These hyper-networks pose great challenges to existing network embedding methods when the hyperedges are indecomposable, that is to say, any subset of nodes in a hyperedge cannot form another hyperedge. These indecomposable hyperedges are especially common in heterogeneous networks. In this paper, we propose a novel Deep Hyper-Network Embedding (DHNE) model to embed hyper-networks with indecomposable hyperedges. More specifically, we theoretically prove that any linear similarity metric in embedding space commonly used in existing methods cannot maintain the indecomposibility property in hyper-networks, and thus propose a new deep model to realize a non-linear tuplewise similarity function while preserving both local and global proximities in the formed embedding space. We conduct extensive experiments on four different types of hyper-networks, including a GPS network, an online social network, a drug network and a semantic network. The empirical results demonstrate that our method can significantly and consistently outperform the state-of-the-art algorithms.
Community Detection in Attributed Graphs: An Embedding Approach
Authors: Li Ye , Sha Chaofeng , Huang Xin , Zhang Yanchun
Published: June 2022

Community detection is a fundamental and widely-studied problem that finds all densely-connected groups of nodes and well separates them from others in graphs. With the proliferation of rich information available for entities in real-world networks, it is useful to discover communities in attributed graphs where nodes tend to have attributes. However, most existing attributed community detection methods directly utilize the original network topology leading to poor results due to ignoring inherent community structures. In this paper, we propose a novel embedding based model to discover communities in attributed graphs. Specifically, based on the observation of densely-connected structures in communities, we develop a novel community structure embedding method to encode inherent community structures via underlying community memberships. Based on node attributes and community structure embedding, we formulate the attributed community detection as a nonnegative matrix factorization optimization problem. Moreover, we carefully design iterative updating rules to make sure of finding a converging solution. Extensive experiments conducted on 19 attributed graph datasets with overlapping and non-overlapping ground-truth communities show that our proposed model CDE can accurately identify attributed communities and significantly outperform 7 state-of-the-art methods.
Inferring Emotion from Conversational Voice Data: A Semi-Supervised Multi-Path Generative Neural Network Approach
Authors: Zhou Suping , Jia Jia , Wang Qi , Dong Yufei , Yin Yufeng , Lei Kehua
Published: June 2022

To give a more humanized response in Voice Dialogue Applications (VDAs), inferring emotion states from users’ queries may play an important role. However, in VDAs, we have tremendous amount of VDA users and massive scale of unlabeled data with high dimension features from multimodal information, which challenge the traditional speech emotion recognition methods. In this paper, to better infer emotion from conversational voice data, we proposed a semi-supervised multi-path generative neural network. Specifically, first, we build a novel supervised multi-path deep neural network framework. To avoid high dimensional input, raw features are trained by groups in local classifiers. Then high-level features of each local classifiers are concatenated as input of a global classifier. These two kinds classifiers are trained simultaneously through a single objective function to achieve a more effective and discriminative emotion inferring. To further solve the labeled-data-scarcity problem, we extend the multi-path deep neural network to a generative model based on semi-supervised variational autoencoder (semi-VAE), which is able to train the labeled and unlabeled data simultaneously. Experiment based on a 24,000 real-world dataset collected from Sogou Voice Assistant (SVAD13) and a benchmark dataset IEMOCAP show that our method significantly outperforms the existing state-of-the-art results.
Mitigating Overexposure in Viral Marketing
Authors: Abebe Rediet , Adamic Lada , Kleinberg Jon
Published: June 2022

In traditional models for word-of-mouth recommendations and viral marketing, the objective function has generally been based on reaching as many people as possible. However, a number of studies have shown that the indiscriminate spread of a product by word-of-mouth can result in overexposure, reaching people who evaluate it negatively. This can lead to an effect in which the over-promotion of a product can produce negative reputational effects, by reaching a part of the audience that is not receptive to it. How should one make use of social influence when there is a risk of overexposure? In this paper, we develop and analyze a theoretical model for this process; we show how it captures a number of the qualitative phenomena associated with overexposure, and for the main formulation of our model, we provide a polynomial-time algorithm to find the optimal marketing strategy. We also present simulations of the model on real network topologies, quantifying the extent to which our optimal strategies outperform natural baselines.
Catching Captain Jack: Efficient Time and Space Dependent Patrols to Combat Oil-Siphoning in International Waters
Authors: Wang Xinrun , An Bo , Strobel Martin , Kong Fookwai
Published: June 2022

Pirate syndicates capturing tankers to siphon oil, causing an estimated cost of $5 billion a year, has become a serious security issue for maritime traffic. In response to the threat, coast guards and navies deploy patrol boats to protect international oil trade. However, given the vast area of the sea and the highly time and space dependent behaviors of both players, it remains a significant challenge to find efficient ways to deploy patrol resources. In this paper, we address the research challenges and provide four key contributions. First, we construct a Stackelberg model of the oil-siphoning problem based on incident reports of actual attacks; Second, we propose a compact formulation and a constraint generation algorithm, which tackle the exponentially growth of the defender’s and attacker’s strategy spaces, respectively, to compute efficient strategies of security agencies; Third, to further improve the scalability, we propose an abstraction method, which exploits the intrinsic similarity of defender’s strategy space, to solve extremely large-scale games; Finally, we evaluate our approaches through extensive simulations and a detailed case study with real ship traffic data. The results demonstrate that our approach achieves a dramatic improvement of scalability with modest influence on the solution quality and can scale up to realistic-sized problems.
TIMERS: Error-Bounded SVD Restart on Dynamic Networks
Authors: Zhang Ziwei , Cui Peng , Pei Jian , Wang Xiao , Zhu Wenwu
Published: June 2022

Singular Value Decomposition (SVD) is a popular approach in various network applications, such as link prediction and network parameter characterization. Incremental SVD approaches are proposed to process newly changed nodes and edges in dynamic networks. However, incremental SVD approaches suffer from serious error accumulation inevitably due to approximation on incremental updates. SVD restart is an effective approach to reset the aggregated error, but when to restart SVD for dynamic networks is not addressed in literature. In this paper, we propose TIMERS, Theoretically Instructed Maximum-Error-bounded Restart of SVD, a novel approach which optimally sets the restart time in order to reduce error accumulation in time. Specifically, we monitor the margin between reconstruction loss of incremental updates and the minimum loss in SVD model. To reduce the complexity of monitoring, we theoretically develop a lower bound of SVD minimum loss for dynamic networks and use the bound to replace the minimum loss in monitoring. By setting a maximum tolerated error as a threshold, we can trigger SVD restart automatically when the margin exceeds this threshold. We prove that the time complexity of our method is linear with respect to the number of local dynamic changes, and our method is general across different types of dynamic networks. We conduct extensive experiments on several synthetic and real dynamic networks. The experimental results demonstrate that our proposed method significantly outperforms the existing methods by reducing 27% to 42% in terms of the maximum error for dynamic network reconstruction when fixing the number of restarts. Our method reduces the number of restarts by 25% to 50% when fixing the maximum error tolerated.
CD-CNN: A Partially Supervised Cross-Domain Deep Learning Model for Urban Resident Recognition
Authors: Wang Jingyuan , He Xu , Wang Ze , Wu Junjie , Yuan Nicholas Jing , Xie Xing , Xiong Zhang
Published: June 2022

Driven by the wave of urbanization in recent decades, the research topic about migrant behavior analysis draws great attention from both academia and the government. Nevertheless, subject to the cost of data collection and the lack of modeling methods, most of existing studies use only questionnaire surveys with sparse samples and non-individual level statistical data to achieve coarse-grained studies of migrant behaviors. In this paper, a partially supervised cross-domain deep learning model named CD-CNN is proposed for migrant/native recognition using mobile phone signaling data as behavioral features and questionnaire survey data as incomplete labels. Specifically, CD-CNN features in decomposing the mobile data into location domain and communication domain, and adopts a joint learning framework that combines two convolutional neural networks with a feature balancing scheme. Moreover, CD-CNN employs a three-step algorithm for training, in which the co-training step is of great value to partially supervised cross-domain learning. Comparative experiments on the city Wuxi demonstrate the high predictive power of CD-CNN. Two interesting applications further highlight the ability of CD-CNN for in-depth migrant behavioral analysis.
MuseGAN: Multi-track Sequential Generative Adversarial Networks for Symbolic Music Generation and Accompaniment
Authors: Dong Hao-Wen , Hsiao Wen-Yi , Yang Li-Chia , Yang Yi-Hsuan
Published: June 2022

Generating music has a few notable differences from generating images and videos. First, music is an art of time, necessitating a temporal model. Second, music is usually composed of multiple instruments/tracks with their own temporal dynamics, but collectively they unfold over time interdependently. Lastly, musical notes are often grouped into chords, arpeggios or melodies in polyphonic music, and thereby introducing a chronological ordering of notes is not naturally suitable. In this paper, we propose three models for symbolic multi-track music generation under the framework of generative adversarial networks (GANs). The three models, which differ in the underlying assumptions and accordingly the network architectures, are referred to as the jamming model, the composer model and the hybrid model. We trained the proposed models on a dataset of over one hundred thousand bars of rock music and applied them to generate piano-rolls of five tracks: bass, drums, guitar, piano and strings. A few intra-track and inter-track objective metrics are also proposed to evaluate the generative results, in addition to a subjective user study. We show that our models can generate coherent music of four bars right from scratch (i.e. without human inputs). We also extend our models to human-AI cooperative music generation: given a specific track composed by human, we can generate four additional tracks to accompany it. All code, the dataset and the rendered audio samples are available at https://salu133445.github.io/musegan/.
Picasso, Matisse, or a Fake? Automated Analysis of Drawings at the Stroke Level for Attribution and Authentication
Authors: Elgammal Ahmed , Kang Yan , Den Leeuw Milko
Published: June 2022

This paper proposes a computational approach for analysis of strokes in line drawings by artists. We aim at developing an AI methodology that facilitates attribution of drawings of unknown authors in a way that is not easy to be deceived by forged art. The methodology used is based on quantifying the characteristics of individual strokes in drawings. We propose a novel algorithm for segmenting individual strokes. We propose an approach that combines different hand-crafted and learned features for the task of quantifying stroke characteristics. We experimented with a dataset of 300 digitized drawings with over 80 thousands strokes. The collection mainly consisted of drawings of Pablo Picasso, Henry Matisse, and Egon Schiele, besides a small number of representative works of other artists. The experiments shows that the proposed methodology can classify individual strokes with accuracy 70%-90%, and aggregate over drawings with accuracy above 80%, while being robust to be deceived by fakes.
HAN: Hierarchical Association Network for Computing Semantic Relatedness
Authors: Gong Xiaolong , Xu Hao , Huang Linpeng
Published: June 2022

Measuring semantic relatedness between two words is a significant problem in many areas such as natural language processing. Existing approaches to the semantic relatedness problem mainly adopt the co-occurrence principle and regard two words as highly related if they appear in the same sentence frequently. However, such solutions suffer from low coverage and low precision because i) the two highly related words may not appear close to each other in the sentences, e.g., the synonyms; and ii) the co-occurrence of words may happen by chance rather than implying the closeness in their semantics. In this paper, we explore the latent semantics (i.e., concepts) of the words to identify highly related word pairs. We propose a hierarchical association network to specify the complex relationships among the words and the concepts, and quantify each relationship with appropriate measurements. Extensive experiments are conducted on real datasets and the results show that our proposed method improves correlation precision compared with the state-of-the-art approaches.
Learning From Unannotated QA Pairs to Analogically Disambiguate and Answer Questions
Authors: Crouse Maxwell , McFate Clifton , Forbus Kenneth
Published: June 2022

Creating systems that can learn to answer natural language questions has been a longstanding challenge for artificial intelligence. Most prior approaches focused on producing a specialized language system for a particular domain and dataset, and they required training on a large corpus manually annotated with logical forms. This paper introduces an analogy-based approach that instead adapts an existing general purpose semantic parser to answer questions in a novel domain by jointly learning disambiguation heuristics and query construction templates from purely textual question-answer pairs. Our technique uses possible semantic interpretations of the natural language questions and answers to constrain a query-generation procedure, producing cases during training that are subsequently reused via analogical retrieval and composed to answer test questions. Bootstrapping an existing semantic parser in this way significantly reduces the number of training examples needed to accurately answer questions. We demonstrate the efficacy of our technique using the Geoquery corpus, on which it approaches state of the art performance using 10-fold cross validation, shows little decrease in performance with 2-folds, and achieves above 50% accuracy with as few as 10 examples.
Style Transfer in Text: Exploration and Evaluation
Authors: Fu Zhenxin , Tan Xiaoye , Peng Nanyun , Zhao Dongyan , Yan Rui
Published: June 2022

The ability to transfer styles of texts or images, is an important measurement of the advancement of artificial intelligence (AI). However, the progress in language style transfer is lagged behind other domains, such as computer vision, mainly because of the lack of parallel data and reliable evaluation metrics. In response to the challenge of lacking parallel data, we explore learning style transfer from non-parallel data. We propose two models to achieve this goal. The key idea behind the proposed models is to learn separate content representations and style representations using adversarial networks. Considering the problem of lacking principle evaluation metrics, we propose two novel evaluation metrics that measure two aspects of style transfer: transfer strength and content preservation. We benchmark our models and the evaluation metrics on two style transfer tasks: paper-news title transfer, and positive-negative review transfer. Results show that the proposed content preservation metric is highly correlate to human judgments, and the proposed models are able to generate sentences with similar content preservation score but higher style transfer strength comparing to auto-encoder.
Cross-Lingual Learning With Distributed Representations
Authors: Pikuliak Matúš
Published: June 2022

Cross-lingual Learning can help to bring state-of-the-art deep learning solutions to smaller languages. These languages in general lack resource for training advanced neural networks. With transfer of knowledge across languages we can improve the results for various NLP tasks.
Decomposition-Based Solving Approaches for Stochastic Constraint Optimisation
Authors: Hemmi David
Published: June 2022

Combinatorial optimisation problems often contain uncertainty that has to be taken into account to produce realistic solutions. A common way to describe the uncertainty is by means of scenarios, where each scenario describes different potential sets of problem parameters based on random distributions or historical data. While efficient algorithmic techniques exist for specific problem classes such as linear programs, there are very few approaches that can handle general Constraint Programming formulations subject to uncertainty. The goal of my PhD is to develop generic methods for solving stochastic combinatorial optimisation problems formulated in a Constraint Programming framework.
Building More Explainable Artificial Intelligence With Argumentation
Authors: Zeng Zhiwei , Miao Chunyan , Leung Cyril , Chin Jing Jih
Published: June 2022

Currently, much of machine learning is opaque, just like a "black box." However, in order for humans to understand, trust and effectively manage the emerging AI systems, an AI needs to be able to explain its decisions and conclusions. In this paper, I propose an argumentation-based approach to explainable AI, which has the potential to generate more comprehensive explanations than existing approaches.
Identifying Private Content for Online Image Sharing
Authors: Tonge Ashwini
Published: June 2022

I present the outline of my dissertation work, Identifying Private Content for Online Image Sharing. Particularly, in my dissertation, I explore learning models to predict appropriate binary privacy settings (i.e., private, public) for images, before they are shared online. Specifically, I investigate textual features (user-annotated tags and automatically derived tags), and visual semantic features that are transferred from various layers of deep Convolutional Neural Network (CNN). Experimental results show that the learning models based on the proposed features outperform strong baseline models for this task on the Flickr dataset of thousands of images.
Adaptive and Dynamic Team Formation for Strategic and Tactical Planning
Authors: Mc Carthy Sara Marie
Published: June 2022

Past work in security games has mainly focused on the problem static resource allocation; how to optimally deploy a given fixed team of resources. My research aims to address the challenge of integrating operational planning into security games, where resources are heterogeneous and the defender is tasked with optimizing over both the investment into these resources, as well as their deployment in the field. This allows the defender to design more adaptive strategies, reason about the efficiency of their use of these resources as well as their effectiveness in their deployment. This thesis explores the challenges in integrating these two optimization problems in both the single stage and multi-stage setting and provides a formal model of this problem, which we refer to as the Simultaneous Optimization of Resource Teams and Tactics (SORT) as a new fundamental research problem in security games that combines strategic and tactical decision making. The main contributions of this work are solution methods to the SORT problem under various settings as well as exploring various types of tradeoffs that can arise in these settings. These include managing budget for investment in resources as well as capacity constraints on use of resources. My work addresses scenarios when the tactical decision problem (optimal deployment) is difficult, and thus evaluating the performance of any given team is difficult. Additionally, I address domains where we are tasked with making repeated strategic level decision and where, due to changing domain features, fluctuations in time dependent processes or the realization of uncertain parameters in the problem, it becomes necessary to re-evaluate and adapt to new information.
Efficiency and Safety in Autonomous Vehicles Through Planning With Uncertainty
Authors: Sunberg Zachary
Published: June 2022

Autonomous vehicles are quickly becoming an important part of human society for transportation, monitoring, agriculture, and other applications. In these applications, there is a fundamental tradeoff between safety and efficiency that is especially salient when the autonomous vehicles interact directly with humans. A key to maintaining safety without sacrificing efficiency is dealing with uncertainty properly so that robots can be assertive when it is appropriate and careful in dangerous situations. The research that will be presented in my thesis uses the partially observable Markov decision process framework to approach this challenge, exploring several applications and proposing a new solution approach that is able to handle continuous action and observation spaces, a qualitative improvement over current methods.
Perception-Action-Learning System for Mobile Social-Service Robots Using Deep Learning
Authors: Lee Beom-Jin , Choi Jinyoung , Lee Chung-Yeon , Park Kyung-Wha , Choi Sungjun , Han Cheolho , Han Dong-Sig , Baek Christina , Emaase Patrick , Zhang Byoung-Tak
Published: June 2022

We introduce a novel perception-action-learning system for mobile social-service robots. The state-of-the-art deep learning techniques were incorporated into each module which significantly improves the performance in solving social service tasks. The system not only demonstrated fast and robust performance in a homelike environment but also achieved the highest score in the RoboCup2017@Home Social Standard Platform League (SSPL) held in Nagoya, Japan.
Learning an Image-based Obstacle Detector With Automatic Acquisition of Training Data
Authors: Toniolo Stefano , Guzzi Jérôme , Gambardella Luca , Giusti Alessandro
Published: June 2022

We detect and localize obstacles in front of a mobile robot by means of a deep neural network that maps images acquired from a forward-looking camera to the outputs of five proximity sensors. The robot autonomously acquires training data in multiple environments; once trained, the network can detect obstacles and their position also in unseen scenarios, and can be used on different robots, not equipped with proximity sensors. We demonstrate both the training and deployment phases on a small modified Thymio robot.
A Cognitive Assistant for Visualizing and Analyzing Exoplanets
Authors: Kephart Jeffrey , Dibia Victor , Ellis Jason , Srivastava Biplav , Talamadupula Kartik , Dholakia Mishal
Published: June 2022

We demonstrate an embodied cognitive agent that helps scientists visualize and analyze exo-planets and their host stars. The prototype is situated in a room equipped with a large display, microphones, cameras, speakers, and pointing devices. Users communicate with the agent via speech, gestures, and combinations thereof, and it responds by displaying content and generating synthesized speech. Extensive use of context facilitates natural interaction with the agent.
Lookine: Let the Blind Hear a Smile
Authors: Bu Yaohua , Jia Jia , Tang Yuhan , Zang Xuan , Gao Tianyu
Published: June 2022

It is believed that nonverbal visual information including facial expressions, facial micro-actions and head movements plays a significant role in fundamental social communication. Unfortunately it is regretful that the blind can not achieve such necessary information. Therefore, we propose a social assistant system, Lookine, to help them to go beyond this limitation. For Lookine, we apply the novel techniques including facial expression recognition, facial action recognition and head pose estimation, and obey barrier-free principles in our design. In experiments, the algorithm evaluation and user study prove that our system has promising accuracy, good real-time performance, and great user experience.
An Automated Employee Timetabling System for Small Businesses
Authors: Hoshino Richard , Slobodin Aaron , Bernoudy William
Published: June 2022

Employee scheduling is one of the most difficult challenges facing any small business owner. The problem becomes more complex when employees with different levels of seniority indicate preferences for specific roles in certain shifts and request flexible work hours outside of the standard eight-hour block. Many business owners and managers, who cannot afford (or choose not to use) commercially-available timetabling apps, spend numerous hours creating sub-optimal schedules by hand, leading to low staff morale. In this paper, we explain how two undergraduate students generalized the Nurse Scheduling Problem to take into account multiple roles and flexible work hours, and implemented a user-friendly automated timetabler based on a four-dimensional integer linear program. This system has been successfully deployed at two businesses in our community, each with 20+ employees: a coffee shop and a health clinic.
Secure and Automated Enterprise Revenue Forecasting
Authors: Barker Jocelyn , Gajewar Amita , Golyaev Konstantin , Bansal Gagan , Conners Matt
Published: June 2022

Revenue forecasting is required by most enterprises for strategic business planning and for providing expected future results to investors. However, revenue forecasting processes in most companies are time-consuming and error-prone as they are performed manually by hundreds of financial analysts. In this paper, we present a novel machine learning based revenue forecasting solution that we developed to forecast 100% of Microsoft's revenue (around $85 Billion in 2016), and is now deployed into production as an end-to-end automated and secure pipeline in Azure. Our solution combines historical trend and seasonal patterns with additional information, e.g., sales pipeline data, within a unified modeling framework. In this paper, we describe our framework including the features, method for hyperparameters tuning of ML models using time series cross-validation, and generation of prediction intervals. We also describe how we architected an end-to-end secure and automated revenue forecasting solution on Azure using Cortana Intelligence Suite. Over consecutive quarters, our machine learning models have continuously produced forecasts with an average accuracy of 98-99 percent for various divisions within Microsoft's Finance organization. As a result, our models have been widely adopted by them and are now an integral part of Microsoft's most important forecasting processes, from providing Wall Street guidance to managing global sales performance.
Sentient Ascend: AI-Based Massively Multivariate Conversion Rate Optimization
Authors: Miikkulainen Risto , Iscoe Neil , Shagrin Aaron , Rapp Ryan , Nazari Sam , McGrath Patrick , Schoolland Cory , Achkar Elyas , Brundage Myles , Miller Jeremy , Epstein Jonathan , Lamba Gurmeet
Published: June 2022

Conversion rate optimization (CRO) means designing an e-commerce web interface so that as many users as possible take a desired action such as registering for an account, requesting a contact, or making a purchase. Such design is usually done by hand, evaluating one change at a time through A/B testing, or evaluating all combinations of two or three variables through multivariate testing. Traditional CRO is thus limited to a small fraction of the design space only. This paper describes Sentient Ascend, an automatic CRO system that uses evolutionary search to discover effective web interfaces given a human-designed search space. Design candidates are evaluated in parallel on line with real users, making it possible to discover and utilize interactions between the design elements that are difficult to identify otherwise. A commercial product since September 2016, Ascend has been applied to numerous web interfaces across industries and search space sizes, with up to four-fold improvements over human design. Ascend can therefore be seen as massively multivariate CRO made possible by AI.
Horizontal Scaling With a Framework for Providing AI Solutions Within a Game Company
Authors: Kolen John , Sardari Mohsen , Mattar Marwan , Peterson Nick , Wu Meng
Published: June 2022

Games have been a major focus of AI since the field formed seventy years ago. Recently, video games have replaced chess and go as the current "Mt. Everest Problem." This paper looks beyond the video games themselves to the application of AI techniques within the ecosystems that produce them. Electronic Arts (EA) must deal with AI at scale across many game studios as it develops many AAA games each year, and not a single, AI-based, flagship application. EA has adopted a horizontal scaling strategy in response to this challenge and built a platform for delivering AI artifacts anywhere within EA's software universe. By combining a data warehouse for player history, an Agent Store for capturing processes acquired through machine learning, and a recommendation engine as an action layer, EA has been delivering a wide range of AI solutions throughout the company during the last two years. These solutions, such as dynamic difficulty adjustment, in-game content and activity recommendations, matchmaking, and game balancing, have had major impact on engagement, revenue, and development resources within EA.
Diagnosing University Student Subject Proficiency and Predicting Degree Completion in Vector Space
Authors: Luo Yuetian , Pardos Zachary
Published: June 2022

We investigate the issues of undergraduate on-time graduation with respect to subject proficiencies through the lens of representation learning, training a student vector embeddings from a dataset of 8 years of course enrollments. We compare the per-semester student representations of a cohort of undergraduate Integrative Biology majors to those of graduated students in subject areas involved in their degree requirements. The result is an embedding rich in information about the relationships between majors and pathways taken by students which encoded enough information to improve prediction accuracy of on-time graduation to 95%, up from a baseline of 87.3%. Challenges to preparation of the data for student vectorization and sourcing of validation sets for optimization are discussed.
Introducing Machine Learning Concepts by Training a Neural Network to Recognize Hand Gestures
Authors: Giusti Alessandro , Huber David , Gambardella Luca
Published: June 2022

We present an interactive guided activity to introduce supervised learning by training a deep neural network (treated as a black box) to recognize "rock paper scissors" hand gestures from unconstrained images. The audience is actively involved in acquiring a varied and representative dataset, on which the rest of the activity is based. Covered concepts include the training/evaluation split, classifier evaluation, baseline accuracy, overfitting, generalization, data augmentation.
Addressing the Technical, Philosophical, and Ethical Issues of Artificial Intelligence Through Active Learning Class Assignments
Authors: Fink Pamela
Published: June 2022

Artificial intelligence (AI) is an extremely large and complex field technically, while at the same time it captures our imagination and prompts us to explore major philosophical and ethical questions concerning humanity and human intelligence. Teaching a course that does justice to all these aspects of the field is a big challenge. However, due to the increase in computational capability with a commensurate decrease in cost, a wealth of products and materials are available that can be used to provide students with rich, meaningful, and memorable experiences within the context of a primarily technical course in AI. Toys, articles, and movies can all be used to foster student exploration of key questions in the technical, philosophical, and ethical issues of AI.
Introducing AI to Undergraduate Students via Computer Vision Projects
Authors: Zeng Kaiman , Li Yancheng , Xu Yida , Wu Di , Wu Nansong
Published: June 2022

Computer vision, as a subfield in the general artificial intelligence (AI), is a technology can be visualized and easily found in a large number of state-of-art applications. In this project, undergraduate students performed research on a landmark recognition task using computer vision techniques. The project focused on analyzing, designing, configuring, and testing the two core components in landmark recognition: feature detection and description. The project modeled the landmark recognition system as a tour guide for visitors to the campus and evaluated the performance in the real world circumstances. By analyzing real-world data and solving problems, student’s cognitive skills and critical thinking skills were sharpened. Their knowledge and understanding in mathematical modeling and data processing were also enhanced.
Policy Learning for Continuous Space Security Games Using Neural Networks
Authors: Kamra Nitin , Gupta Umang , Fang Fei , Liu Yan , Tambe Milind
Published: June 2022

A wealth of algorithms centered around (integer) linear programming have been proposed to compute equilibrium strategies in security games with discrete states and actions. However, in practice many domains possess continuous state and action spaces. In this paper, we consider a continuous space security game model with infinite-size action sets for players and present a novel deep learning based approach to extend the existing toolkit for solving security games. Specifically, we present (i) OptGradFP, a novel and general algorithm that searches for the optimal defender strategy in a parameterized continuous search space, and can also be used to learn policies over multiple game states simultaneously; (ii) OptGradFP-NN, a convolutional neural network based implementation of OptGradFP for continuous space security games. We demonstrate the potential to predict good defender strategies via experiments and analysis of OptGradFP and OptGradFP-NN on discrete and continuous game settings.
It Takes (Only) Two: Adversarial Generator-Encoder Networks
Authors: Ulyanov Dmitry , Vedaldi Andrea , Lempitsky Victor
Published: June 2022

We present a new autoencoder-type architecture that is trainable in an unsupervised mode, sustains both generation and inference, and has the quality of conditional and unconditional samples boosted by adversarial learning. Unlike previous hybrids of autoencoders and adversarial networks, the adversarial game in our approach is set up directly between the encoder and the generator, and no external mappings are trained in the process of learning.The game objective compares the divergences of each of the real and the generated data distributions with the prior distribution in the latent space. We show that direct generator-vs-encoder game leads to a tight coupling of the two components, resulting in samples and reconstructions of a comparable quality to some recently-proposed more complex architectures.
MUDA: A Truthful Multi-Unit Double-Auction Mechanism
Authors: Segal-Halevi Erel , Hassidim Avinatan , Aumann Yonatan
Published: June 2022

In a seminal paper, McAfee (1992) presented a truthful mechanism for double auctions, attaining asymptotically-optimal gain-from-trade without any prior information on the valuations of the traders. McAfee's mechanism handles single-parametric agents, allowing each seller to sell a single unit and each buyer to buy a single unit. This paper presents a double-auction mechanism that handles multi-parametric agents and allows multiple units per trader, as long as the valuation functions of all traders have decreasing marginal returns. The mechanism is prior-free, ex-post individually-rational, dominant-strategy truthful and strongly-budget-balanced. Its gain-from-trade approaches the optimum when the market size is sufficiently large.
Coalition Manipulation of Gale-Shapley Algorithm
Authors: Shen Weiran , Tang Pingzhong , Deng Yuan
Published: June 2022

It is well-known that the Gale-Shapley algorithm is not truthful for all agents. Previous studies in this category concentrate on manipulations using incomplete preference lists by a single woman and by the set of all women. Little is known about manipulations by a subset of women. In this paper, we consider manipulations by any subset of women with arbitrary preferences. We show that a strong Nash equilibrium of the induced manipulation game always exists among the manipulators and the equilibrium outcome is unique and Pareto-dominant. In addition, the set of matchings achievable by manipulations has a lattice structure. We also examine the super-strong Nash equilibrium in the end.
Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure
Authors: Wilder Bryan
Published: June 2022

We define a class of zero-sum games with combinatorial structure, where the best response problem of one player is to maximize a submodular function. For example, this class includes security games played on networks, as well as the problem of robustly optimizing a submodular function over the worst case from a set of scenarios. The challenge in computing equilibria is that both players' strategy spaces can be exponentially large. Accordingly, previous algorithms have worst-case exponential runtime and indeed fail to scale up on practical instances. We provide a pseudopolynomial-time algorithm which obtains a guaranteed (1 - 1/e)^2-approximate mixed strategy for the maximizing player. Our algorithm only requires access to a weakened version of a best response oracle for the minimizing player which runs in polynomial time. Experimental results for network security games and a robust budget allocation problem confirm that our algorithm delivers near-optimal solutions and scales to much larger instances than was previously possible.
On Recognising Nearly Single-Crossing Preferences
Authors: Jaeckle Florian , Peters Dominik , Elkind Edith
Published: June 2022

If voters' preferences are one-dimensional, many hard problems in computational social choice become tractable. A preference profile can be classified as one-dimensional if it has the single-crossing property, which requires that the voters can be ordered from left to right so that their preferences are consistent with this order. In practice, preferences may exhibit some one-dimensional structure, despite not being single-crossing in the formal sense. Hence, we ask whether one can identify preference profiles that are close to being single-crossing. We consider three distance measures, which are based on partitioning voters or candidates or performing a small number of swaps in each vote. We prove that it can be efficiently decided if voters can be split into two single-crossing groups. Also, for every fixed k >= 1 we can decide in polynomial time if a profile can be made single-crossing by performing at most k candidate swaps per vote. In contrast, for each k >= 3 it is NP-complete to decide whether candidates can be partitioned into k sets so that the restriction of the input profile to each set is single-crossing.
Groupwise Maximin Fair Allocation of Indivisible Goods
Authors: Barman Siddharth , Biswas Arpita , Krishnamurthy Sanath , Narahari Yadati
Published: June 2022

We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Specifically, maximin share is defined as the minimum utility that an agent can guarantee for herself when asked to partition the set of goods into n bundles such that the remaining (n-1) agents pick their bundles adversarially. An allocation is deemed to be fair if every agent gets a bundle whose valuation is at least her maximin share. Even though maximin shares provide a natural benchmark for fairness, it has its own drawbacks and, in particular, it is not sufficient to rule out unsatisfactory allocations. Motivated by these considerations, in this work we define a stronger notion of fairness, called groupwise maximin share guarantee (GMMS). In GMMS, we require that the maximin share guarantee is achieved not just with respect to the grand bundle, but also among all the subgroups of agents. Hence, this solution concept strengthens MMS and provides an ex-post fairness guarantee. We show that in specific settings, GMMS allocations always exist. We also establish the existence of approximate GMMS allocations under additive valuations, and develop a polynomial-time algorithm to find such allocations. Moreover, we establish a scale of fairness wherein we show that GMMS implies approximate envy freeness. Finally, we empirically demonstrate the existence of GMMS allocations in a large set of randomly generated instances. For the same set of instances, we additionally show that our algorithm achieves an approximation factor better than the established, worst-case bound.
Incentivizing High Quality User Contributions: New Arm Generation in Bandit Learning
Authors: Liu Yang , Ho Chien-Ju
Published: June 2022

We study the problem of incentivizing high quality contributions in user generated content platforms, in which users arrive sequentially with unknown quality. We are interested in designing a content displaying strategy which decides which content should be chosen to show to users, with the goal of maximizing user experience (i.e., the likelihood of users liking the content).This goal naturally leads to a joint problem of incentivizing high quality contributions and learning the unknown content quality. To address the incentive issue, we consider a model in which users are strategic in deciding whether to contribute and are motivated by exposure, i.e., they aim to maximize the number of times their contributions are viewed. For the learning perspective, we model the content quality as the probability of obtaining positive feedback (e.g., like or upvote) from a random user. Naturally, the platform needs to resolve the classical trade-off between exploration (collecting feedback for all content) and exploitation (displaying the best content). We formulate this problem as a multi-arm bandit problem, where the number of arms (i.e., contributions) is increasing over time and depends on the strategic choices of arriving users. We first show that applying standard bandit algorithms incentivizes a flood of low cost contributions, which in turn leads to linear regret. We then propose Rand_UCB which adds an additional layer of randomization on top of the UCB algorithm to address the issue of flooding contributions. We show that Rand_UCB helps eliminate the incentives for low quality contributions, provides incentives for high quality contributions (due to bounded number of explorations for the low quality ones), and achieves sub-linear regrets with respect to displaying the current best arms.
Approximately Stable Matchings With Budget Constraints
Authors: Kawase Yasushi , Iwasaki Atsushi
Published: June 2022

This paper examines two-sided matching with budget constraints where one side (a firm or hospital) can make monetary transfers (offer wages) to the other (a worker or doctor). In a standard model, while multiple doctors can be matched to a single hospital, a hospital has a maximum quota; thus, the number of doctors assigned to a hospital cannot exceed a certain limit. In our model, in contrast, a hospital has a fixed budget; that is, the total amount of wages allocated by each hospital to doctors is constrained. With budget constraints, stable matchings may fail to exist and checking for the existence is hard. To deal with the nonexistence of stable matchings, we extend the "matching with contracts" model of Hatfield and Milgrom so that it deals with approximately stable matchings where each of the hospitals' utilities after deviation can increase by a factor up to a certain amount. We then propose two novel mechanisms that efficiently return a stable matching that exactly satisfies the budget constraints. Specifically, by sacrificing strategy-proofness, our first mechanism achieves the best possible bound. We also explore a special case on which a simple mechanism is strategy-proof for doctors, while maintaining the best possible bound of the general case.
Tool Auctions
Authors: Döcker Janosch , Dorn Britta , Endriss Ulle , De Haan Ronald , Schneckenburger Sebastian
Published: June 2022

We introduce tool auctions, a novel market mechanism for constructing a cost-efficient assembly line for producing a desired set of products from a given set of goods and tools. Such tools can be used to transform one type of good into a different one. We then study the computational complexity of tool auctions in detail, using methods from both classical and parameterized complexity theory. While solving such auctions is intractable in general, just as for the related frameworks of combinatorial and mixed auctions, we are able to identify several special cases of practical interest where designing efficient algorithms is possible.
Allocation Problems in Ride-Sharing Platforms: Online Matching With Offline Reusable Resources
Authors: Dickerson John , Sankararaman Karthik , Srinivasan Aravind , Xu Pan
Published: June 2022

Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1/2 − ε for any given ε > 0. We also show that no non-adaptive algorithm can achieve a ratio of 1/2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ride-sharing systems. We also present heuristics that perform well in practice.