Paper Group ANR 677
Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification. Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs. EXIT Analysis for Community Detection. Learning Best Response Strategies for Agents in Ad Exchanges. Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recen …
Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification
| Title | Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification |
| Authors | Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, Massimiliano Pontil |
| Abstract | We study the problem of fair binary classification using the notion of Equal Opportunity. It requires the true positive rate to distribute equally across the sensitive groups. Within this setting we show that the fair optimal classifier is obtained by recalibrating the Bayes classifier by a group-dependent threshold. We provide a constructive expression for the threshold. This result motivates us to devise a plug-in classification procedure based on both unlabeled and labeled datasets. While the latter is used to learn the output conditional probability, the former is used for calibration. The overall procedure can be computed in polynomial time and it is shown to be statistically consistent both in terms of the classification error and fairness measure. Finally, we present numerical experiments which indicate that our method is often superior or competitive with the state-of-the-art methods on benchmark datasets. |
| Tasks | Calibration |
| Published | 2019-06-12 |
| URL | https://arxiv.org/abs/1906.05082v2 |
| https://arxiv.org/pdf/1906.05082v2.pdf | |
| PWC | https://paperswithcode.com/paper/leveraging-labeled-and-unlabeled-data-for |
| Repo | |
| Framework | |
Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
| Title | Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs |
| Authors | Lorenzo Dall’Amico, Romain Couillet, Nicolas Tremblay |
| Abstract | Spectral clustering is one of the most popular, yet still incompletely understood, methods for community detection on graphs. This article studies spectral clustering based on the Bethe-Hessian matrix $H_r = (r^2-1)I_n + D-rA$ for sparse heterogeneous graphs (following the degree-corrected stochastic block model) in a two-class setting. For a specific value $r = \zeta$, clustering is shown to be insensitive to the degree heterogeneity. We then study the behavior of the informative eigenvector of $H_{\zeta}$ and, as a result, predict the clustering accuracy. The article concludes with an overview of the generalization to more than two classes along with extensive simulations on synthetic and real networks corroborating our findings. |
| Tasks | Community Detection |
| Published | 2019-01-25 |
| URL | https://arxiv.org/abs/1901.09715v3 |
| https://arxiv.org/pdf/1901.09715v3.pdf | |
| PWC | https://paperswithcode.com/paper/optimized-deformed-laplacian-for-spectrum |
| Repo | |
| Framework | |
EXIT Analysis for Community Detection
| Title | EXIT Analysis for Community Detection |
| Authors | Hussein Saad, Aria Nosratinia |
| Abstract | This paper employs the extrinsic information transfer (EXIT) method, a technique imported from the analysis of the iterative decoding of error control codes, to study the performance of belief propagation in community detection in the presence of side information. We consider both the detection of a single (hidden) community, as well as the problem of identifying two symmetric communities. For single community detection, this paper demonstrates the suitability of EXIT to predict the asymptotic phase transition for weak recovery. More importantly, EXIT analysis is leveraged to produce useful insights such as the performance of belief propagation near the threshold. For two symmetric communities, the asymptotic residual error for belief propagation is calculated under finite-alphabet side information, generalizing a previous result with noisy labels. EXIT analysis is used to illuminate the effect of side information on community detection, its relative importance depending on the correlation of the graphical information with node labels, as well as the effect of side information on residual errors. |
| Tasks | Community Detection |
| Published | 2019-01-08 |
| URL | http://arxiv.org/abs/1901.09656v1 |
| http://arxiv.org/pdf/1901.09656v1.pdf | |
| PWC | https://paperswithcode.com/paper/exit-analysis-for-community-detection |
| Repo | |
| Framework | |
Learning Best Response Strategies for Agents in Ad Exchanges
| Title | Learning Best Response Strategies for Agents in Ad Exchanges |
| Authors | Stavros Gerakaris, Subramanian Ramamoorthy |
| Abstract | Ad exchanges are widely used in platforms for online display advertising. Autonomous agents operating in these exchanges must learn policies for interacting profitably with a diverse, continually changing, but unknown market. We consider this problem from the perspective of a publisher, strategically interacting with an advertiser through a posted price mechanism. The learning problem for this agent is made difficult by the fact that information is censored, i.e., the publisher knows if an impression is sold but no other quantitative information. We address this problem using the Harsanyi-Bellman Ad Hoc Coordination (HBA) algorithm, which conceptualises this interaction in terms of a Stochastic Bayesian Game and arrives at optimal actions by best responding with respect to probabilistic beliefs maintained over a candidate set of opponent behaviour profiles. We adapt and apply HBA to the censored information setting of ad exchanges. Also, addressing the case of stochastic opponents, we devise a strategy based on a Kaplan-Meier estimator for opponent modelling. We evaluate the proposed method using simulations wherein we show that HBA-KM achieves substantially better competitive ratio and lower variance of return than baselines, including a Q-learning agent and a UCB-based online learning agent, and comparable to the offline optimal algorithm. |
| Tasks | Q-Learning |
| Published | 2019-02-10 |
| URL | http://arxiv.org/abs/1902.03588v1 |
| http://arxiv.org/pdf/1902.03588v1.pdf | |
| PWC | https://paperswithcode.com/paper/learning-best-response-strategies-for-agents |
| Repo | |
| Framework | |
Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances
| Title | Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances |
| Authors | Kaiqing Zhang, Zhuoran Yang, Tamer Başar |
| Abstract | Multi-agent reinforcement learning (MARL) has long been a significant and everlasting research topic in both machine learning and control. With the recent development of (single-agent) deep RL, there is a resurgence of interests in developing new MARL algorithms, especially those that are backed by theoretical analysis. In this paper, we review some recent advances a sub-area of this topic: decentralized MARL with networked agents. Specifically, multiple agents perform sequential decision-making in a common environment, without the coordination of any central controller. Instead, the agents are allowed to exchange information with their neighbors over a communication network. Such a setting finds broad applications in the control and operation of robots, unmanned vehicles, mobile sensor networks, and smart grid. This review is built upon several our research endeavors in this direction, together with some progresses made by other researchers along the line. We hope this review to inspire the devotion of more research efforts to this exciting yet challenging area. |
| Tasks | Decision Making, Multi-agent Reinforcement Learning |
| Published | 2019-12-09 |
| URL | https://arxiv.org/abs/1912.03821v1 |
| https://arxiv.org/pdf/1912.03821v1.pdf | |
| PWC | https://paperswithcode.com/paper/decentralized-multi-agent-reinforcement |
| Repo | |
| Framework | |
Short-Text Classification Using Unsupervised Keyword Expansion
| Title | Short-Text Classification Using Unsupervised Keyword Expansion |
| Authors | Duncan Cameron-Steinke |
| Abstract | Short-text classification, like all data science, struggles to achieve high performance using limited data. As a solution, a short sentence may be expanded with new and relevant feature words to form an artificially enlarged dataset, and add new features to testing data. This paper applies a novel approach to text expansion by generating new words directly for each input sentence, thus requiring no additional datasets or previous training. In this unsupervised approach, new keywords are formed within the hidden states of a pre-trained language model and then used to create extended pseudo documents. The word generation process was assessed by examining how well the predicted words matched to topics of the input sentence. It was found that this method could produce 3-10 relevant new words for each target topic, while generating just 1 word related to each non-target topic. Generated words were then added to short news headlines to create extended pseudo headlines. Experimental results have shown that models trained using the pseudo headlines can improve classification accuracy when limiting the number of training examples. |
| Tasks | Language Modelling, Text Classification |
| Published | 2019-09-16 |
| URL | https://arxiv.org/abs/1909.07512v1 |
| https://arxiv.org/pdf/1909.07512v1.pdf | |
| PWC | https://paperswithcode.com/paper/short-text-classification-using-unsupervised |
| Repo | |
| Framework | |
Dynamic Instance Normalization for Arbitrary Style Transfer
| Title | Dynamic Instance Normalization for Arbitrary Style Transfer |
| Authors | Yongcheng Jing, Xiao Liu, Yukang Ding, Xinchao Wang, Errui Ding, Mingli Song, Shilei Wen |
| Abstract | Prior normalization methods rely on affine transformations to produce arbitrary image style transfers, of which the parameters are computed in a pre-defined way. Such manually-defined nature eventually results in the high-cost and shared encoders for both style and content encoding, making style transfer systems cumbersome to be deployed in resource-constrained environments like on the mobile-terminal side. In this paper, we propose a new and generalized normalization module, termed as Dynamic Instance Normalization (DIN), that allows for flexible and more efficient arbitrary style transfers. Comprising an instance normalization and a dynamic convolution, DIN encodes a style image into learnable convolution parameters, upon which the content image is stylized. Unlike conventional methods that use shared complex encoders to encode content and style, the proposed DIN introduces a sophisticated style encoder, yet comes with a compact and lightweight content encoder for fast inference. Experimental results demonstrate that the proposed approach yields very encouraging results on challenging style patterns and, to our best knowledge, for the first time enables an arbitrary style transfer using MobileNet-based lightweight architecture, leading to a reduction factor of more than twenty in computational cost as compared to existing approaches. Furthermore, the proposed DIN provides flexible support for state-of-the-art convolutional operations, and thus triggers novel functionalities, such as uniform-stroke placement for non-natural images and automatic spatial-stroke control. |
| Tasks | Style Transfer |
| Published | 2019-11-16 |
| URL | https://arxiv.org/abs/1911.06953v1 |
| https://arxiv.org/pdf/1911.06953v1.pdf | |
| PWC | https://paperswithcode.com/paper/dynamic-instance-normalization-for-arbitrary |
| Repo | |
| Framework | |
A Molecular-MNIST Dataset for Machine Learning Study on Diffraction Imaging and Microscopy
| Title | A Molecular-MNIST Dataset for Machine Learning Study on Diffraction Imaging and Microscopy |
| Authors | Yan Zhang, Steve Farrell, Michael Crowley, Lee Makowski, Jack Deslippe |
| Abstract | An image dataset of 10 different size molecules, where each molecule has 2,000 structural variants, is generated from the 2D cross-sectional projection of Molecular Dynamics trajectories. The purpose of this dataset is to provide a benchmark dataset for the increasing need of machine learning, deep learning and image processing on the study of scattering, imaging and microscopy. |
| Tasks | |
| Published | 2019-11-15 |
| URL | https://arxiv.org/abs/1911.07644v1 |
| https://arxiv.org/pdf/1911.07644v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-molecular-mnist-dataset-for-machine |
| Repo | |
| Framework | |
Training neural networks to encode symbols enables combinatorial generalization
| Title | Training neural networks to encode symbols enables combinatorial generalization |
| Authors | Ivan Vankov, Jeffrey Bowers |
| Abstract | Combinatorial generalization - the ability to understand and produce novel combinations of already familiar elements - is considered to be a core capacity of the human mind and a major challenge to neural network models. A significant body of research suggests that conventional neural networks can’t solve this problem unless they are endowed with mechanisms specifically engineered for the purpose of representing symbols. In this paper we introduce a novel way of representing symbolic structures in connectionist terms - the vectors approach to representing symbols (VARS), which allows training standard neural architectures to encode symbolic knowledge explicitly at their output layers. In two simulations, we show that neural networks not only can learn to produce VARS representations, but in doing so they achieve combinatorial generalization in their symbolic and non-symbolic output. This adds to other recent work that has shown improved combinatorial generalization under specific training conditions, and raises the question of whether specific mechanisms or training routines are needed to support symbolic processing. |
| Tasks | |
| Published | 2019-03-29 |
| URL | https://arxiv.org/abs/1903.12354v2 |
| https://arxiv.org/pdf/1903.12354v2.pdf | |
| PWC | https://paperswithcode.com/paper/out-of-the-box-neural-networks-can-support |
| Repo | |
| Framework | |
Adversarial Image Translation: Unrestricted Adversarial Examples in Face Recognition Systems
| Title | Adversarial Image Translation: Unrestricted Adversarial Examples in Face Recognition Systems |
| Authors | Kazuya Kakizaki, Kosuke Yoshida |
| Abstract | Thanks to recent advances in deep neural networks (DNNs), face recognition systems have become highly accurate in classifying a large number of face images. However, recent studies have found that DNNs could be vulnerable to adversarial examples, raising concerns about the robustness of such systems. Adversarial examples that are not restricted to small perturbations could be more serious since conventional certified defenses might be ineffective against them. To shed light on the vulnerability to such adversarial examples, we propose a flexible and efficient method for generating unrestricted adversarial examples using image translation techniques. Our method enables us to translate a source image into any desired facial appearance with large perturbations to deceive target face recognition systems. Our experimental results indicate that our method achieved about $90$ and $80%$ attack success rates under white- and black-box settings, respectively, and that the translated images are perceptually realistic and maintain the identifiability of the individual while the perturbations are large enough to bypass certified defenses. |
| Tasks | Face Recognition |
| Published | 2019-05-09 |
| URL | https://arxiv.org/abs/1905.03421v3 |
| https://arxiv.org/pdf/1905.03421v3.pdf | |
| PWC | https://paperswithcode.com/paper/190503421 |
| Repo | |
| Framework | |
A Recent Survey on the Applications of Genetic Programming in Image Processing
| Title | A Recent Survey on the Applications of Genetic Programming in Image Processing |
| Authors | Asifullah Khan, Aqsa Saeed Qureshi, Noorul Wahab, Mutawara Hussain, Muhammad Yousaf Hamza |
| Abstract | During the last two decades, Genetic Programming (GP) has been largely used to tackle optimization, classification, and automatic features selection related tasks. The widespread use of GP is mainly due to its flexible and comprehensible tree-type structure. Similarly, research is also gaining momentum in the field of Image Processing (IP) because of its promising results over wide areas of applications ranging from medical IP to multispectral imaging. IP is mainly involved in applications such as computer vision, pattern recognition, image compression, storage and transmission, and medical diagnostics. This prevailing nature of images and their associated algorithm i.e complexities gave an impetus to the exploration of GP. GP has thus been used in different ways for IP since its inception. Many interesting GP techniques have been developed and employed in the field of IP. To give the research community an extensive view of these techniques, this paper presents the diverse applications of GP in IP and provides useful resources for further research. Also, comparison of different parameters used in ten different applications of IP are summarized in tabular form. Moreover, analysis of different parameters used in IP related tasks is carried-out to save the time needed in future for evaluating the parameters of GP. As more advancement is made in GP methodologies, its success in solving complex tasks not only related to IP but also in other fields will increase. Additionally, guidelines are provided for applying GP in IP related tasks, pros and cons of GP techniques are discussed, and some future directions are also set. |
| Tasks | Image Compression |
| Published | 2019-01-18 |
| URL | http://arxiv.org/abs/1901.07387v2 |
| http://arxiv.org/pdf/1901.07387v2.pdf | |
| PWC | https://paperswithcode.com/paper/a-recent-survey-on-the-applications-of |
| Repo | |
| Framework | |
ASNets: Deep Learning for Generalised Planning
| Title | ASNets: Deep Learning for Generalised Planning |
| Authors | Sam Toyer, Felipe Trevizan, Sylvie Thiébaux, Lexing Xie |
| Abstract | In this paper, we discuss the learning of generalised policies for probabilistic and classical planning problems using Action Schema Networks (ASNets). The ASNet is a neural network architecture that exploits the relational structure of (P)PDDL planning problems to learn a common set of weights that can be applied to any problem in a domain. By mimicking the actions chosen by a traditional, non-learning planner on a handful of small problems in a domain, ASNets are able to learn a generalised reactive policy that can quickly solve much larger instances from the domain. This work extends the ASNet architecture to make it more expressive, while still remaining invariant to a range of symmetries that exist in PPDDL problems. We also present a thorough experimental evaluation of ASNets, including a comparison with heuristic search planners on seven probabilistic and deterministic domains, an extended evaluation on over 18,000 Blocksworld instances, and an ablation study. Finally, we show that sparsity-inducing regularisation can produce ASNets that are compact enough for humans to understand, yielding insights into how the structure of ASNets allows them to generalise across a domain. |
| Tasks | |
| Published | 2019-08-04 |
| URL | https://arxiv.org/abs/1908.01362v1 |
| https://arxiv.org/pdf/1908.01362v1.pdf | |
| PWC | https://paperswithcode.com/paper/asnets-deep-learning-for-generalised-planning |
| Repo | |
| Framework | |
Learning Mixtures of Graphs from Epidemic Cascades
| Title | Learning Mixtures of Graphs from Epidemic Cascades |
| Authors | Jessica Hoffmann, Soumya Basu, Surbhi Goel, Constantine Caramanis |
| Abstract | We consider the problem of learning the weighted edges of a balanced mixture of two undirected graphs from epidemic cascades. While mixture models are popular modeling tools, algorithmic development with rigorous guarantees has lagged. Graph mixtures are apparently no exception: until now, very little is known about whether this problem is solvable. To the best of our knowledge, we establish the first necessary and sufficient conditions for this problem to be solvable in polynomial time on edge-separated graphs. When the conditions are met, i.e., when the graphs are connected with at least three edges, we give an efficient algorithm for learning the weights of both graphs with optimal sample complexity (up to log factors). We give complimentary results and provide sample-optimal (up to log factors) algorithms for mixtures of directed graphs of out-degree at least three, for mixture of undirected graphs of unbalanced and/or unknown priors. |
| Tasks | |
| Published | 2019-06-14 |
| URL | https://arxiv.org/abs/1906.06057v2 |
| https://arxiv.org/pdf/1906.06057v2.pdf | |
| PWC | https://paperswithcode.com/paper/disentangling-mixtures-of-epidemics-on-graphs |
| Repo | |
| Framework | |
Survey of Text-based Epidemic Intelligence: A Computational Linguistic Perspective
| Title | Survey of Text-based Epidemic Intelligence: A Computational Linguistic Perspective |
| Authors | Aditya Joshi, Sarvnaz Karimi, Ross Sparks, Cecile Paris, C Raina MacIntyre |
| Abstract | Epidemic intelligence deals with the detection of disease outbreaks using formal (such as hospital records) and informal sources (such as user-generated text on the web) of information. In this survey, we discuss approaches for epidemic intelligence that use textual datasets, referring to it as `text-based epidemic intelligence’. We view past work in terms of two broad categories: health mention classification (selecting relevant text from a large volume) and health event detection (predicting epidemic events from a collection of relevant text). The focus of our discussion is the underlying computational linguistic techniques in the two categories. The survey also provides details of the state-of-the-art in annotation techniques, resources and evaluation strategies for epidemic intelligence. | |
| Tasks | |
| Published | 2019-03-14 |
| URL | http://arxiv.org/abs/1903.05801v1 |
| http://arxiv.org/pdf/1903.05801v1.pdf | |
| PWC | https://paperswithcode.com/paper/survey-of-text-based-epidemic-intelligence-a |
| Repo | |
| Framework | |
Quantum Sparse Support Vector Machines
| Title | Quantum Sparse Support Vector Machines |
| Authors | Tomasz Arodz, Seyran Saeedi |
| Abstract | We present a quantum machine learning algorithm for training Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the $L_1$ norm of the feature weights vector. Sparse SVM results in a classifier that uses only a small fraction of the input features in making decisions, and is especially suitable for cases where the total number of features is at the same order, or larger, than the number of training samples. The algorithm utilizes recently proposed quantum solvers for semidefinite programming and linear programming problems. We show that while for an arbitrary binary classification problem no quantum speedup is achieved by using quantum SDP/LP solvers during training, there are realistic scenarios in which using a sparse linear classifier makes sense in terms of the expected accuracy of predictions, and polynomial quantum speedup compared to classical methods can be achieved. |
| Tasks | Quantum Machine Learning |
| Published | 2019-02-05 |
| URL | http://arxiv.org/abs/1902.01879v2 |
| http://arxiv.org/pdf/1902.01879v2.pdf | |
| PWC | https://paperswithcode.com/paper/quantum-sparse-support-vector-machines |
| Repo | |
| Framework | |
