bluuebunny/crossref_metadata_2025 huggingface dataset:
Convexity of b-matching Games
Authors: Kumabe Soh , Maehara Takanori
Published: July 2020

The b-matching game is a cooperative game defined on a graph.

The game generalizes the matching game to allow each individual to have more than one partner.

The game has several applications, such as the roommate assignment, the multi-item version of the seller-buyer assignment, and the international kidney exchange.

Compared with the standard matching game, the b-matching game is computationally hard.

In particular, the core non-emptiness problem and the core membership problem are co-NP-hard.

Therefore, we focus on the convexity of the game, which is a sufficient condition of the core non-emptiness and often more tractable concept than the core non-emptiness.

It also has several additional benefits.

In this study, we give a necessary and sufficient condition of the convexity of the b-matching game.

This condition also gives an O(n log n + m α(n)) time algorithm to determine whether a given game is convex or not, where n and m are the number of vertices and edges of a given graph, respectively, and α(・) is the inverse-Ackermann function.

Using our characterization, we also give a polynomial-time algorithm to compute the Shapley value of a convex b-matching game.
Only Relevant Information Matters: Filtering Out Noisy Samples To Boost RL
Authors: Flet-Berliac Yannis , Preux Philippe
Published: July 2020

In reinforcement learning, policy gradient algorithms optimize the policy directly and rely on sampling efficiently an environment. Nevertheless, while most sampling procedures are based on direct policy sampling, self-performance measures could be used to improve such sampling prior to each policy update. Following this line of thought, we introduce SAUNA, a method where non-informative transitions are rejected from the gradient update. The level of information is estimated according to the fraction of variance explained by the value function: a measure of the discrepancy between V and the empirical returns. In this work, we use this criterion to select samples that are useful to learn from, and we demonstrate that this selection can significantly improve the performance of policy gradient methods. In this paper: (a) We introduce the SAUNA method to filter transitions. (b) We conduct experiments on a set of benchmark continuous control problems. SAUNA significantly improves performance. (c) We investigate how SAUNA reliably selects samples with the most positive impact on learning and study its improvement on both performance and sample efficiency.
Consistent MetaReg: Alleviating Intra-task Discrepancy for Better Meta-knowledge
Authors: Tian Pinzhuo , Qi Lei , Dong Shaokang , Shi Yinghuan , Gao Yang
Published: July 2020

In the few-shot learning scenario, the data-distribution discrepancy between training data and test data in a task usually exists due to the limited data. However, most existing meta-learning approaches seldom consider this intra-task discrepancy in the meta-training phase which might deteriorate the performance. To overcome this limitation, we develop a new consistent meta-regularization method to reduce the intra-task data-distribution discrepancy. Moreover, the proposed meta-regularization method could be readily inserted into existing optimization-based meta-learning models to learn better meta-knowledge. Particularly, we provide the theoretical analysis to prove that using the proposed meta-regularization, the conventional gradient-based meta-learning method can reach the lower regret bound. The extensive experiments also demonstrate the effectiveness of our method, which indeed improves the performances of the state-of-the-art gradient-based meta-learning models in the few-shot classification task.
Temporal Attribute Prediction via Joint Modeling of Multi-Relational Structure Evolution
Authors: Garg Sankalp , Sharma Navodita , Jin Woojeong , Ren Xiang
Published: July 2020

Time series prediction is an important problem in machine learning. Previous methods for time series prediction did not involve additional information. With a lot of dynamic knowledge graphs available, we can use this additional information to predict the time series better. Recently, there has been a focus on the application of deep representation learning on dynamic graphs. These methods predict the structure of the graph by reasoning over the interactions in the graph at previous time steps. In this paper, we propose a new framework to incorporate the information from dynamic knowledge graphs for time series prediction. We show that if the information contained in the graph and the time series data are closely related, then this inter-dependence can be used to predict the time series with improved accuracy. Our framework, DArtNet, learns a static embedding for every node in the graph as well as a dynamic embedding which is dependent on the dynamic attribute value (time-series). Then it captures the information from the neighborhood by taking a relation specific mean and encodes the history information using RNN. We jointly train the model link prediction and attribute prediction. We evaluate our method on five specially curated datasets for this problem and show a consistent improvement in time series prediction results. We release the data and code of model DArtNet for future research.
Tight Approximation for Proportional Approval Voting
Authors: Dudycz Szymon , Manurangsi Pasin , Marcinkowski Jan , Sornat Krzysztof
Published: July 2020

In approval-based multiwinner elections, we are given a set of voters, a set of candidates, and, for each voter, a set of candidates approved by the voter. The goal is to find a committee of size k that maximizes the total utility of the voters. In this paper, we study approximability of Thiele rules, which are known to be NP-hard to solve exactly. We provide a tight polynomial time approximation algorithm for a natural class of geometrically dominant weights that includes such voting rules as Proportional Approval Voting or p-Geometric. The algorithm is relatively simple: first we solve a linear program and then we round a solution by employing a framework called pipage rounding due to Ageev and Sviridenko (2004) and Calinescu et al. (2011). We provide a matching lower bound via a reduction from the Label Cover problem. Moreover, assuming a conjecture called Gap-ETH, we show that better approximation ratio cannot be obtained even in time f(k)*pow(n,o(k)).
Learning in the Wild with Incremental Skeptical Gaussian Processes
Authors: Bontempelli Andrea , Teso Stefano , Giunchiglia Fausto , Passerini Andrea
Published: July 2020

The ability to learn from human supervision is fundamental for personal assistants and other interactive applications of AI. Two central challenges for deploying interactive learners in the wild are the unreliable nature of the supervision and the varying complexity of the prediction task. We address a simple but representative setting, incremental classification in the wild, where the supervision is noisy and the number of classes grows over time. In order to tackle this task, we propose a redesign of skeptical learning centered around Gaussian Processes (GPs). Skeptical learning is a recent interactive strategy in which, if the machine is sufficiently confident that an example is mislabeled, it asks the annotator to reconsider her feedback. In many cases, this is often enough to obtain clean supervision. Our redesign, dubbed ISGP , leverages the uncertainty estimates supplied by GPs to better allocate labeling and contradiction queries, especially in the presence of noise. Our experiments on synthetic and real-world data show that, as a result, while the original formulation of skeptical learning produces over-confident models that can fail completely in the wild, ISGP works well at varying levels of noise and as new classes are observed.
Seq-U-Net: A One-Dimensional Causal U-Net for Efficient Sequence Modelling
Authors: Stoller Daniel , Tian Mi , Ewert Sebastian , Dixon Simon
Published: July 2020

Convolutional neural networks (CNNs) with dilated filters such as the Wavenet or the Temporal Convolutional Network (TCN) have shown good results in a variety of sequence modelling tasks. While their receptive field grows exponentially with the number of layers, computing the convolutions over very long sequences of features in each layer is time and memory-intensive, and prohibits the use of longer receptive fields in practice. To increase efficiency, we make use of the "slow feature" hypothesis stating that many features of interest are slowly varying over time. For this, we use a U-Net architecture that computes features at multiple time-scales and adapt it to our auto-regressive scenario by making convolutions causal. We apply our model ("Seq-U-Net") to a variety of tasks including language and audio generation. In comparison to TCN and Wavenet, our network consistently saves memory and computation time, with speed-ups for training and inference of over 4x in the audio generation experiment in particular, while achieving a comparable performance on real-world tasks.
Independent Skill Transfer for Deep Reinforcement Learning
Authors: Tian Qiangxing , Wang Guanchu , Liu Jinxin , Wang Donglin , Kang Yachen
Published: July 2020

Recently, diverse primitive skills have been learned by adopting the entropy as intrinsic reward, which further shows that new practical skills can be produced by combining a variety of primitive skills. This is essentially skill transfer, very useful for learning high-level skills but quite challenging due to the low efficiency of transferring primitive skills. In this paper, we propose a novel efficient skill transfer method, where we learn independent skills and only independent components of skills are transferred instead of the whole set of skills. More concretely, independent components of skills are obtained through independent component analysis (ICA), which always have a smaller amount (or lower dimension) compared with their mixtures. With a lower dimension, independent skill transfer (IST) exhibits a higher efficiency on learning a given task. Extensive experiments including three robotic tasks demonstrate the effectiveness and high efficiency of our proposed IST method in comparison to direct primitive-skill transfer and conventional reinforcement learning.
Unsupervised Representation Learning by Predicting Random Distances
Authors: Wang Hu , Pang Guansong , Shen Chunhua , Ma Congbo
Published: July 2020

Deep neural networks have gained great success in a broad range of tasks due to its remarkable capability to learn semantically rich features from high-dimensional data. However, they often require large-scale labelled data to successfully learn such features, which significantly hinders their adaption in unsupervised learning tasks, such as anomaly detection and clustering, and limits their applications to critical domains where obtaining massive labelled data is prohibitively expensive. To enable unsupervised learning on those domains, in this work we propose to learn features without using any labelled data by training neural networks to predict data distances in a randomly projected space. Random mapping is a theoretically proven approach to obtain approximately preserved distances. To well predict these distances, the representation learner is optimised to learn genuine class structures that are implicitly embedded in the randomly projected space. Empirical results on 19 real-world datasets show that our learned representations substantially outperform a few state-of-the-art methods for both anomaly detection and clustering tasks. Code is available at: \url{https://git.io/RDP}
Approximate Pareto Set for Fair and Efficient Allocation: Few Agent Types or Few Resource Types
Authors: Nguyen Trung Thanh , Rothe Jörg
Published: July 2020

In fair division of indivisible goods, finding an allocation that satisfies fairness and efficiency simultaneously is highly desired but

computationally hard. We solve this problem approximately in polynomial time by modeling it as a bi-criteria optimization problem

that can be solved efficiently by determining an approximate Pareto set of bounded size. We focus on two criteria: max-min fairness and

utilitarian efficiency, and study this problem for the setting when there are only a few item types or a few agent types. We show in both cases that one can construct an approximate Pareto set in time polynomial in the input size, either by designing a dynamic programming scheme, or a linear-programming algorithm. Our techniques strengthen known methods and can be potentially applied to other notions of fairness and efficiency as well.
Quadratic Sparse Gaussian Graphical Model Estimation Method for Massive Variables
Authors: Zhang Jiaqi , Wang Meng , Li Qinchi , Wang Sen , Chang Xiaojun , Wang Beilun
Published: July 2020

We consider the problem of estimating a sparse Gaussian Graphical Model with a special graph topological structure and more than a million variables. Most previous scalable estimators still contain expensive calculation steps (e.g., matrix inversion or Hessian matrix calculation) and become infeasible in high-dimensional scenarios, where p (number of variables) is larger than n (number of samples). To overcome this challenge, we propose a novel method, called Fast and Scalable Inverse Covariance Estimator by Thresholding (FST). FST first obtains a graph structure by applying a generalized threshold to the sample covariance matrix. Then, it solves multiple block-wise subproblems via element-wise thresholding. By using matrix thresholding instead of matrix inversion as the computational bottleneck, FST reduces its computational complexity to a much lower order of magnitude (O(p2)). We show that FST obtains the same sharp convergence rate O(√(log max{p, n}/n) as other state-of-the-art methods. We validate the method empirically, on multiple simulated datasets and one real-world dataset, and show that FST is two times faster than the four baselines while achieving a lower error rate under both Frobenius-norm and max-norm.
A Deep Reinforcement Learning Approach to Concurrent Bilateral Negotiation
Authors: Bagga Pallavi , Paoletti Nicola , Alrayes Bedour , Stathis Kostas
Published: July 2020

We present a novel negotiation model that allows an agent to learn how to negotiate during concurrent bilateral negotiations in unknown and dynamic e-markets. The agent uses an actor-critic architecture with model-free reinforcement learning to learn a strategy expressed as a deep neural network. We pre-train the strategy by supervision from synthetic market data, thereby decreasing the exploration time required for learning during negotiation. As a result, we can build automated agents for concurrent negotiations that can adapt to different e-market settings without the need to be pre-programmed. Our experimental evaluation shows that our deep reinforcement learning based agents outperform two existing well-known negotiation strategies in one-to-many concurrent bilateral negotiations for a range of e-market settings.
Hybrid Learning for Multi-agent Cooperation with Sub-optimal Demonstrations
Authors: Peng Peixi , Xing Junliang , Cao Lili
Published: July 2020

This paper aims to learn multi-agent cooperation where each agent performs its actions in a decentralized way. In this case, it is very challenging to learn decentralized policies when the rewards are global and sparse. Recently, learning from demonstrations (LfD) provides a promising way to handle this challenge. However, in many practical tasks, the available demonstrations are often sub-optimal. To learn better policies from these sub-optimal demonstrations, this paper follows a centralized learning and decentralized execution framework and proposes a novel hybrid learning method based on multi-agent actor-critic. At first, the expert trajectory returns generated from demonstration actions are used to pre-train the centralized critic network. Then, multi-agent decisions are made by best response dynamics based on the critic and used to train the decentralized actor networks. Finally, the demonstrations are updated by the actor networks, and the critic and actor networks are learned jointly by running the above two steps alliteratively. We evaluate the proposed approach on a real-time strategy combat game. Experimental results show that the approach outperforms many competing demonstration-based methods.
Bayesian Optimization using Pseudo-Points
Authors: Qian Chao , Xiong Hang , Xue Ke
Published: July 2020

Bayesian optimization (BO) is a popular approach for expensive black-box optimization, with applications including parameter tuning, experimental design, and robotics. BO usually models the objective function by a Gaussian process (GP), and iteratively samples the next data point by maximizing an acquisition function. In this paper, we propose a new general framework for BO by generating pseudo-points (i.e., data points whose objective values are not evaluated) to improve the GP model. With the classic acquisition function, i.e., upper confidence bound (UCB), we prove that the cumulative regret can be generally upper bounded. Experiments using UCB and other acquisition functions, i.e., probability of improvement (PI) and expectation of improvement (EI), on synthetic as well as real-world problems clearly show the advantage of generating pseudo-points.
On Metric DBSCAN with Low Doubling Dimension
Authors: Ding Hu , Yang Fan , Wang Mingyue
Published: July 2020

The density based clustering method Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a popular method for outlier recognition and has received tremendous attention from many different areas. A major issue of the original DBSCAN is that the time complexity could be as large as quadratic. Most of existing DBSCAN algorithms focus on developing efficient index structures to speed up the procedure in low-dimensional Euclidean space. However, the research of DBSCAN in high-dimensional Euclidean space or general metric spaces is still quite limited, to the best of our knowledge. In this paper, we consider the metric DBSCAN problem under the assumption that the inliers (excluding the outliers) have a low doubling dimension. We apply a novel randomized k-center clustering idea to reduce the complexity of range query, which is the most time consuming step in the whole DBSCAN procedure. Our proposed algorithms do not need to build any complicated data structures and are easy to implement in practice. The experimental results show that our algorithms can significantly outperform the existing DBSCAN algorithms in terms of running time.
Multi-Feedback Bandit Learning with Probabilistic Contexts
Authors: Yang Luting , Yang Jianyi , Ren Shaolei
Published: July 2020

Contextual bandit is a classic multi-armed bandit setting, where side information (i.e., context) is available before arm selection. A standard assumption is that exact contexts are perfectly known prior to arm selection and only single feedback is returned. In this work, we focus on multi-feedback bandit learning with probabilistic contexts, where a bundle of contexts are revealed to the agent along with their corresponding probabilities at the beginning of each round. This models such scenarios as where contexts are drawn from the probability output of a neural network and the reward function is jointly determined by multiple feedback signals. We propose a kernelized learning algorithm based on upper confidence bound to choose the optimal arm in reproducing kernel Hilbert space for each context bundle. Moreover, we theoretically establish an upper bound on the cumulative regret with respect to an oracle that knows the optimal arm given probabilistic contexts, and show that the bound grows sublinearly with time. Our simula- tion on machine learning model recommendation further validates the sub-linearity of our cumulative regret and demonstrates that our algorithm outper- forms the approach that selects arms based on the most probable context.
Greedy Convex Ensemble
Authors: Nguyen Thanh Tan , Ye Nan , Bartlett Peter
Published: July 2020

We consider learning a convex combination of basis models, and present some new theoretical and empirical results that demonstrate the effectiveness of a greedy approach. Theoretically, we first consider whether we can use linear, instead of convex, combinations, and obtain generalization results similar to existing ones for learning from a convex hull. We obtain a negative result that even the linear hull of very simple basis functions can have unbounded capacity, and is thus prone to overfitting; on the other hand, convex hulls are still rich but have bounded capacities. Secondly, we obtain a generalization bound for a general class of Lipschitz loss functions. Empirically, we first discuss how a convex combination can be greedily learned with early stopping, and how a convex combination can be non-greedily learned when the number of basis models is known a priori. Our experiments suggest that the greedy scheme is competitive with or better than several baselines, including boosting and random forests. The greedy algorithm requires little effort in hyper-parameter tuning, and also seems able to adapt to the underlying complexity of the problem. Our code is available at https://github.com/tan1889/gce.
Computational Aspects of Conditional Minisum Approval Voting in Elections with Interdependent Issues
Authors: Markakis Evangelos , Papasotiropoulos Georgios
Published: July 2020

Approval voting provides a simple, practical framework for multi-issue elections, and the most representative example among such election rules is the classic Minisum approval voting rule.

We consider a generalization of Minisum, introduced by the work of Barrot and Lang [2016], referred to as Conditional Minisum, where voters are also allowed to express dependencies between issues.

The price we have to pay when we move to this higher level of expressiveness is that we end up with a computationally hard rule. Motivated by this, we focus on the computational aspects of Conditional Minisum, where progress has been rather scarce so far.

We identify restrictions to every voter's dependencies, under which we provide the first multiplicative approximation algorithms for the problem.

The restrictions involve upper bounds on the number of dependencies an issue can have on the others. At the same time, by additionally requiring certain structural properties for the union of dependencies cast by the whole electorate, we obtain optimal efficient algorithms for well-motivated special cases.

Overall, our work provides a better understanding on the complexity implications introduced by conditional voting.
Weakly-Supervised Multi-view Multi-instance Multi-label Learning
Authors: Xing Yuying , Yu Guoxian , Wang Jun , Domeniconi Carlotta , Zhang Xiangliang
Published: July 2020

Multi-view, Multi-instance, and Multi-label Learning (M3L) can model complex objects (bags), which are represented with different feature views, made of diverse instances, and annotated with discrete non-exclusive labels. Existing M3L approaches assume a complete correspondence between bags and views, and also assume a complete annotation for training. However, in practice, neither the correspondence between bags, nor the bags' annotations are complete. To tackle such a weakly-supervised M3L task, a solution called WSM3L is introduced. WSM3L adapts multimodal dictionary learning to learn a shared dictionary (representational space) across views and individual encoding vectors of bags for each view. The label similarity and feature similarity of encoded bags are jointly used to match bags across views. In addition, it replenishes the annotations of a bag based on the annotations of its neighborhood bags, and introduces a dispatch and aggregation term to dispatch bag-level annotations to instances and to reversely aggregate instance-level annotations to bags. WSM3L unifies these objectives and processes in a joint objective function to predict the instance-level and bag-level annotations in a coordinated fashion, and it further introduces an alternative solution for the objective function optimization. Extensive experimental results show the effectiveness of WSM3L on benchmark datasets.
I²HRL: Interactive Influence-based Hierarchical Reinforcement Learning
Authors: Wang Rundong , Yu Runsheng , An Bo , Rabinovich Zinovi
Published: July 2020

Hierarchical reinforcement learning (HRL) is a promising approach to solve tasks with long time horizons and sparse rewards. It is often implemented as a high-level policy assigning subgoals to a low-level policy. However, it suffers the high-level non-stationarity problem since the low-level policy is constantly changing. The non-stationarity also leads to the data efficiency problem: policies need more data at non-stationary states to stabilize training. To address these issues, we propose a novel HRL method: Interactive Influence-based Hierarchical Reinforcement Learning (I^2HRL). First, inspired by agent modeling, we enable the interaction between the low-level and high-level policies to stabilize the high-level policy training. The high-level policy makes decisions conditioned on the received low-level policy representation as well as the state of the environment. Second, we furthermore stabilize the high-level policy via an information-theoretic regularization with minimal dependence on the changing low-level policy. Third, we propose the influence-based exploration to more frequently visit the non-stationary states where more transition data is needed. We experimentally validate the effectiveness of the proposed solution in several tasks in MuJoCo domains by demonstrating that our approach can significantly boost the learning performance and accelerate learning compared with state-of-the-art HRL methods.
Discovering Subsequence Patterns for Next POI Recommendation
Authors: Zhao Kangzhi , Zhang Yong , Yin Hongzhi , Wang Jin , Zheng Kai , Zhou Xiaofang , Xing Chunxiao
Published: July 2020

Next Point-of-Interest (POI) recommendation plays an important role in location-based services. State-of-the-art methods learn the POI-level sequential patterns in the user's check-in sequence but ignore the subsequence patterns that often represent the socio-economic activities or coherence of preference of the users. However, it is challenging to integrate the semantic subsequences due to the difficulty to predefine the granularity of the complex but meaningful subsequences. In this paper, we propose Adaptive Sequence Partitioner with Power-law Attention (ASPPA) to automatically identify each semantic subsequence of POIs and discover their sequential patterns. Our model adopts a state-based stacked recurrent neural network to hierarchically learn the latent structures of the user's check-in sequence. We also design a power-law attention mechanism to integrate the domain knowledge in spatial and temporal contexts. Extensive experiments on two real-world datasets demonstrate the effectiveness of our model.
Label Enhancement for Label Distribution Learning via Prior Knowledge
Authors: Gao Yongbiao , Zhang Yu , Geng Xin
Published: July 2020

Label distribution learning (LDL) is a novel machine learning paradigm that gives a description degree of each label to an instance. However, most of training datasets only contain simple logical labels rather than label distributions due to the difficulty of obtaining the label distributions directly. We propose to use the prior knowledge to recover the label distributions. The process of recovering the label distributions from the logical labels is called label enhancement. In this paper, we formulate the label enhancement as a dynamic decision process. Thus, the label distribution is adjusted by a series of actions conducted by a reinforcement learning agent according to sequential state representations. The target state is defined by the prior knowledge. Experimental results show that the proposed approach outperforms the state-of-the-art methods in both age estimation and image emotion recognition.
Multi-Scale Group Transformer for Long Sequence Modeling in Speech Separation
Authors: Zhao Yucheng , Luo Chong , Zha Zheng-Jun , Zeng Wenjun
Published: July 2020

In this paper, we introduce Transformer to the time-domain methods for single-channel speech separation. Transformer has the potential to boost speech separation performance because of its strong sequence modeling capability. However, its computational complexity, which grows quadratically with the sequence length, has made it largely inapplicable to speech applications. To tackle this issue, we propose a novel variation of Transformer, named multi-scale group Transformer (MSGT). The key ideas are group self-attention, which significantly reduces the complexity, and multi-scale fusion, which retains Transform's ability to capture long-term dependency. We implement two versions of MSGT with different complexities, and apply them to a well-known time-domain speech separation method called Conv-TasNet. By simply replacing the original temporal convolutional network (TCN) with MSGT, our approach called MSGT-TasNet achieves a large gain over Conv-TasNet on both WSJ0-2mix and WHAM! benchmarks. Without bells and whistles, the performance of MSGT-TasNet is already on par with the SOTA methods.
Unsupervised Domain Adaptation with Dual-Scheme Fusion Network for Medical Image Segmentation
Authors: Zou Danbing , Zhu Qikui , Yan Pingkun
Published: July 2020

Domain adaptation aims to alleviate the problem of retraining a pre-trained model when applying it to a different domain, which requires large amount of additional training data of the target domain. Such an objective is usually achieved by establishing connections between the source domain labels and target domain data. However, this imbalanced source-to-target one way pass may not eliminate the domain gap, which limits the performance of the pre-trained model. In this paper, we propose an innovative Dual-Scheme Fusion Network (DSFN) for unsupervised domain adaptation. By building both source-to-target and target-to-source connections, this balanced joint information flow helps reduce the domain gap to further improve the network performance. The mechanism is further applied to the inference stage, where both the original input target image and the generated source images are segmented with the proposed joint network. The results are fused to obtain more robust segmentation. Extensive experiments of unsupervised cross-modality medical image segmentation are conducted on two tasks -- brain tumor segmentation and cardiac structures segmentation. The experimental results show that our method achieved significant performance improvement over other state-of-the-art domain adaptation methods.
Inferring Degrees from Incomplete Networks and Nonlinear Dynamics
Authors: Jiang Chunheng , Gao Jianxi , Magdon-Ismail Malik
Published: July 2020

Inferring topological characteristics of complex networks from observed data is critical to understand the dynamical behavior of networked systems, ranging from the Internet and the World Wide Web to biological networks and social networks. Prior studies usually focus on the structure-based estimation to infer network sizes, degree distributions, average degrees, and more. Little effort attempted to estimate the specific degree of each vertex from a sampled induced graph, which prevents us from measuring the lethality of nodes in protein networks and influencers in social networks. The current approaches dramatically fail for a tiny sampled induced graph and require a specific sampling method and a large sample size. These approaches neglect information of the vertex state, representing the dynamical behavior of the networked system, such as the biomass of species or expression of a gene, which is useful for degree estimation. We fill this gap by developing a framework to infer individual vertex degrees using both information of the sampled topology and vertex state. We combine the mean-field theory with combinatorial optimization to learn vertex degrees. Experimental results on real networks with a variety of dynamics demonstrate that our framework can produce reliable degree estimates and dramatically improve existing link prediction methods by replacing the sampled degrees with our estimated degrees.
Binary Classification from Positive Data with Skewed Confidence
Authors: Shinoda Kazuhiko , Kaji Hirotaka , Sugiyama Masashi
Published: July 2020

Positive-confidence (Pconf) classification [Ishida et al., 2018] is a promising weakly-supervised learning method which trains a binary classifier only from positive data equipped with confidence. However, in practice, the confidence may be skewed by bias arising in an annotation process. The Pconf classifier cannot be properly learned with skewed confidence, and consequently, the classification performance might be deteriorated. In this paper, we introduce the parameterized model of the skewed confidence, and propose the method for selecting the hyperparameter which cancels out the negative impact of the skewed confidence under the assumption that we have the misclassification rate of positive samples as a prior knowledge. We demonstrate the effectiveness of the proposed method through a synthetic experiment with simple linear models and benchmark problems with neural network models. We also apply our method to drivers’ drowsiness prediction to show that it works well with a real-world problem where confidence is obtained based on manual annotation.
Generating Behavior-Diverse Game AIs with Evolutionary Multi-Objective Deep Reinforcement Learning
Authors: Shen Ruimin , Zheng Yan , Hao Jianye , Meng Zhaopeng , Chen Yingfeng , Fan Changjie , Liu Yang
Published: July 2020

Generating diverse behaviors for game artificial intelligence (Game AI) has been long recognized as a challenging task in the game industry. Designing a Game AI with a satisfying behavioral characteristic (style) heavily depends on the domain knowledge and is hard to achieve manually. Deep reinforcement learning sheds light on advancing the automatic Game AI design. However, most of them focus on creating a superhuman Game AI, ignoring the importance of behavioral diversity in games. To bridge the gap, we introduce a new framework, named EMOGI, which can automatically generate desirable styles with almost no domain knowledge. More importantly, EMOGI succeeds in creating a range of diverse styles, providing behavior-diverse Game AIs. Evaluations on the Atari and real commercial games indicate that, compared to existing algorithms, EMOGI performs better in generating diverse behaviors and significantly improves the efficiency of Game AI design.
CDC: Classification Driven Compression for Bandwidth Efficient Edge-Cloud Collaborative Deep Learning
Authors: Dong Yuanrui , Zhao Peng , Yu Hanqiao , Zhao Cong , Yang Shusen
Published: July 2020

The emerging edge-cloud collaborative Deep Learning (DL) paradigm aims at improving the performance of practical DL implementations in terms of cloud bandwidth consumption, response latency, and data privacy preservation. Focusing on bandwidth efficient edge-cloud collaborative training of DNN-based classifiers, we present CDC, a Classification Driven Compression framework that reduces bandwidth consumption while preserving classification accuracy of edge-cloud collaborative DL. Specifically, to reduce bandwidth consumption, for resource-limited edge servers, we develop a lightweight autoencoder with a classification guidance for compression with classification driven feature preservation, which allows edges to only upload the latent code of raw data for accurate global training on the Cloud. Additionally, we design an adjustable quantization scheme adaptively pursuing the tradeoff between bandwidth consumption and classification accuracy under different network conditions, where only fine-tuning is required for rapid compression ratio adjustment. Results of extensive experiments demonstrate that, compared with DNN training with raw data, CDC consumes 14.9× less bandwidth with an accuracy loss no more than 1.06%, and compared with DNN training with data compressed by AE without guidance, CDC introduces at least 100% lower accuracy loss.
Automatic Emergency Diagnosis with Knowledge-Based Tree Decoding
Authors: Wang Ke , Chen Xuyan , Chen Ning , Chen Ting
Published: July 2020

Automatic diagnosis based on clinical notes is critical especially in the emergency department, where a fast and professional result is vital in assuring proper and timely treatment. Previous works formalize this task as plain text classification and fail to utilize the medically significant tree structure of International Classification of Diseases (ICD) coding system. Besides, external medical knowledge is rarely used before, and we explore it by extracting relevant materials from Wikipedia or Baidupedia. In this paper, we propose a knowledge-based tree decoding model (K-BTD), and the inference procedure is a top-down decoding process from the root node to leaf nodes. The stepwise inference procedure enables the model to give support for decision at each step, which visualizes the diagnosis procedure and adds to the interpretability of final predictions. Experiments on real-world data from the emergency department of a large-scale hospital indicate that the proposed model outperforms all baselines in both micro-F1 and macro-F1, and reduce the semantic distance dramatically.
Exploiting Mutual Information for Substructure-aware Graph Representation Learning
Authors: Wang Pengyang , Fu Yanjie , Zhou Yuanchun , Liu Kunpeng , Li Xiaolin , Hua Kien
Published: July 2020

In this paper, we design and evaluate a new substructure-aware Graph Representation Learning (GRL) approach. GRL aims to map graph structure information into low-dimensional representations. While extensive efforts have been made for modeling global and/or local structure information, GRL can be improved by substructure information. Some recent studies exploit adversarial learning to incorporate substructure awareness, but hindered by unstable convergence. This study will address the major research question: is there a better way to integrate substructure awareness into GRL? As subsets of the graph structure, interested substructures (i.e., subgraph) are unique and representative for differentiating graphs, leading to the high correlation between the representation of the graph-level structure and substructures. Since mutual information (MI) is to evaluate the mutual dependence between two variables, we develop a MI inducted substructure-aware GRL method. We decompose the GRL pipeline into two stages: (1) node-level, where we introduce to maximize MI between the original and learned representation by the intuition that the original and learned representation should be highly correlated; (2) graph-level, where we preserve substructures by maximizing MI between the graph-level structure and substructure representation. Finally, we present extensive experimental results to demonstrate the improved performances of our method with real-world data.
A Two-Stage Matheuristic Algorithm for Classical Inventory Routing Problem
Authors: Su Zhouxing , Huang Shihao , Li Chungen , Lü Zhipeng
Published: July 2020

The inventory routing problem (IRP), which is NP-hard, tackles the combination of inventory management and transportation optimization in supply chains. It seeks a minimum-cost schedule which utilizes a single vehicle to perform deliveries in multiple periods, so that no customer runs out of stock. Specifically, the solution of IRP can be represented as how many products should be delivered to which customer during each period, as well as the route in each period. We propose a two-stage matheuristic (TSMH) algorithm to solve the IRP. The first stage optimizes the overall schedule and generates an initial solution by a relax-and-repair method. The second stage employs an iterated tabu search procedure to achieve a fine-grained optimization to the current solution. Tested on 220 most commonly used benchmark instances, TSMH obtains advantages comparing to the state-of-the-art algorithms. The experimental results show that the proposed algorithm can obtain not only the optimal solutions for most small instances, but also better upper bounds for 40 out of 60 large instances. These results demonstrate that the TSMH algorithm is effective and efficient in solving the IRP. In addition, the comparative experiments justify the importance of two optimization stages of TSMH.
Why We Go Where We Go: Profiling User Decisions on Choosing POIs
Authors: Hu Renjun , Lu Xinjiang , Liu Chuanren , Li Yanyan , Liu Hao , Gu Jingjing , Ma Shuai , Xiong Hui
Published: July 2020

While Point-of-Interest (POI) recommendation has been a popular topic of study for some time, little progress has been made for understanding why and how people make their decisions for the selection of POIs. To this end, in this paper, we propose a user decision profiling framework, named PROUD, which can identify the key factors in people's decisions on choosing POIs. Specifically, we treat each user decision as a set of factors and provide a method for learning factor embeddings. A unique perspective of our approach is to identify key factors, while preserving decision structures seamlessly, via a novel scalar projection maximization objective. Exactly solving the objective is non-trivial due to a sparsity constraint. To address this, our PROUD adopts a self projection attention and an L2 regularized sparse activation to directly estimate the likelihood of each factor to be a key factor. Finally, extensive experiments on real-world data validate the advantage of PROUD in preserving user decision structures. Also, our case study indicates that the identified key decision factors can help us to provide more interpretable recommendations and analyses.
A Game Theoretic Approach For Core Resilience
Authors: Medya Sourav , Ma Tiyani , Silva Arlei , Singh Ambuj
Published: July 2020

K-cores are maximal induced subgraphs where all vertices have degree at least k. These dense patterns have applications in community detection, network visualization and protein function prediction. However, k-cores can be quite unstable to network modifications, which motivates the question: How resilient is the k-core structure of a network, such as the Web or Facebook, to edge deletions? We investigate this question from an algorithmic perspective. More specifically, we study the problem of computing a small set of edges for which the removal minimizes the k-core structure of a network. This paper provides a comprehensive characterization of the hardness of the k-core minimization problem (KCM), including innaproximability and parameterized complexity. Motivated by these challenges, we propose a novel algorithm inspired by Shapley value---a cooperative game-theoretic concept--- that is able to leverage the strong interdependencies in the effects of edge removals in the search space. We efficiently approximate Shapley values using a randomized algorithm with probabilistic guarantees. Our experiments, show that the proposed algorithm outperforms competing solutions in terms of k-core minimization while being able to handle large graphs. Moreover, we illustrate how KCM can be applied in the analysis of the k-core resilience of networks.
Learning Model with Error -- Exposing the Hidden Model of BAYHENN
Authors: Wong Harry W. H. , Ma Jack P. K. , Wong Donald P. H. , Ng Lucien K. L. , Chow Sherman S. M.
Published: July 2020

Privacy-preserving deep neural network (DNN) inference remains an intriguing problem even after the rapid developments of different communities. One challenge is that cryptographic techniques such as homomorphic encryption (HE) do not natively support non-linear computations (e.g., sigmoid). A recent work, BAYHENN (Xie et al., IJCAI'19), considers HE over the Bayesian neural network (BNN). The novelty lies in "meta-prediction" over a few noisy DNNs. The claim was that the clients can get intermediate outputs (to apply non-linear function) but are still prevented from learning the exact model parameters, which was justified via the widely-used learning-with-error (LWE) assumption (with Gaussian noises as the error). This paper refutes the security claim of BAYHENN via both theoretical and empirical analyses. We formally define a security game with different oracle queries capturing two realistic threat models. Our attack assuming a semi-honest adversary reveals all the parameters of single-layer BAYHENN, which generalizes to recovering the whole model that is "as good as" the BNN approximation of the original DNN, either under the malicious adversary model or with an increased number of oracle queries.

This shows the need for rigorous security analysis ("the noise introduced by BNN can obfuscate the model" fails -- it is beyond what LWE guarantees) and calls for the collaboration between cryptographers and machine-learning experts to devise practical yet provably-secure solutions.
Altruism in Coalition Formation Games
Authors: Kerkmann Anna Maria , Rothe Jörg
Published: July 2020

Nguyen et al. [2016] introduced altruistic hedonic games in which agents’ utilities depend not only on their own preferences but also on those of their friends in the same coalition. We propose to extend their model to coalition formation games in general, considering also the friends in other coalitions. Comparing the two models, we argue that excluding some friends from the altruistic behavior of an agent is a major disadvantage that comes with the restriction to hedonic games. After introducing our model, we additionally study some common stability notions and provide a computational analysis of the associated verification and existence problems.
Hierarchical Linear Disentanglement of Data-Driven Conceptual Spaces
Authors: Alshaikh Rana , Bouraoui Zied , Schockaert Steven
Published: July 2020

Conceptual spaces are geometric meaning representations in which similar entities are represented by similar vectors. They are widely used in cognitive science, but there has been relatively little work on learning such representations from data. In particular, while standard representation learning methods can be used to induce vector space embeddings from text corpora, these differ from conceptual spaces in two crucial ways. First, the dimensions of a conceptual space correspond to salient semantic features, known as quality dimensions, whereas the dimensions of learned vector space embeddings typically lack any clear interpretation. This has been partially addressed in previous work, which has shown that it is possible to identify directions in learned vector spaces which capture semantic features. Second, conceptual spaces are normally organised into a set of domains, each of which is associated with a separate vector space. In contrast, learned embeddings represent all entities in a single vector space. Our hypothesis in this paper is that such single-space representations are sub-optimal for learning quality dimensions, due to the fact that semantic features are often only relevant to a subset of the entities. We show that this issue can be mitigated by identifying features in a hierarchical fashion. Intuitively, the top-level features split the vector space into different domains, making it possible to subsequently identify domain-specific quality dimensions.