April 3, 2020

# Paper Group ANR 27

Frozen Binomials on the Web: Word Ordering and Language Conventions in Online Text. Convo: What does conversational programming need? An exploration of machine learning interface design. Simultaneous Left Atrium Anatomy and Scar Segmentations via Deep Learning in Multiview Information with Attention. Information cartography in association rule mini …

#### Frozen Binomials on the Web: Word Ordering and Language Conventions in Online Text

Title Frozen Binomials on the Web: Word Ordering and Language Conventions in Online Text
Authors Katherine Van Koevering, Austin R. Benson, Jon Kleinberg
Abstract There is inherent information captured in the order in which we write words in a list. The orderings of binomials — lists of two words separated by and' or or’ — has been studied for more than a century. These binomials are common across many areas of speech, in both formal and informal text. In the last century, numerous explanations have been given to describe what order people use for these binomials, from differences in semantics to differences in phonology. These rules describe primarily `frozen’ binomials that exist in exactly one ordering and have lacked large-scale trials to determine efficacy. Online text provides a unique opportunity to study these lists in the context of informal text at a very large scale. In this work, we expand the view of binomials to include a large-scale analysis of both frozen and non-frozen binomials in a quantitative way. Using this data, we then demonstrate that most previously proposed rules are ineffective at predicting binomial ordering. By tracking the order of these binomials across time and communities we are able to establish additional, unexplored dimensions central to these predictions. Expanding beyond the question of individual binomials, we also explore the global structure of binomials in various communities, establishing a new model for these lists and analyzing this structure for non-frozen and frozen binomials. Additionally, novel analysis of trinomials — lists of length three — suggests that none of the binomials analysis applies in these cases. Finally, we demonstrate how large data sets gleaned from the web can be used in conjunction with older theories to expand and improve on old questions. |
Published 2020-03-07
URL https://arxiv.org/abs/2003.03612v1
PDF https://arxiv.org/pdf/2003.03612v1.pdf
PWC https://paperswithcode.com/paper/frozen-binomials-on-the-web-word-ordering-and
Repo
Framework

#### Convo: What does conversational programming need? An exploration of machine learning interface design

Title Convo: What does conversational programming need? An exploration of machine learning interface design
Authors Jessica Van Brummelen, Kevin Weng, Phoebe Lin, Catherine Yeo
Abstract Vast improvements in natural language understanding and speech recognition have paved the way for conversational interaction with computers. While conversational agents have often been used for short goal-oriented dialog, we know little about agents for developing computer programs. To explore the utility of natural language for programming, we conducted a study ($n$=45) comparing different input methods to a conversational programming system we developed. Participants completed novice and advanced tasks using voice-based, text-based, and voice-or-text-based systems. We found that users appreciated aspects of each system (e.g., voice-input efficiency, text-input precision) and that novice users were more optimistic about programming using voice-input than advanced users. Our results show that future conversational programming tools should be tailored to users’ programming experience and allow users to choose their preferred input mode. To reduce cognitive load, future interfaces can incorporate visualizations and possess custom natural language understanding and speech recognition models for programming.
Published 2020-03-03
URL https://arxiv.org/abs/2003.01318v1
PDF https://arxiv.org/pdf/2003.01318v1.pdf
PWC https://paperswithcode.com/paper/convo-what-does-conversational-programming
Repo
Framework

#### Simultaneous Left Atrium Anatomy and Scar Segmentations via Deep Learning in Multiview Information with Attention

Title Simultaneous Left Atrium Anatomy and Scar Segmentations via Deep Learning in Multiview Information with Attention
Authors Guang Yang, Jun Chen, Zhifan Gao, Shuo Li, Hao Ni, Elsa Angelini, Tom Wong, Raad Mohiaddin, Eva Nyktari, Ricardo Wage, Lei Xu, Yanping Zhang, Xiuquan Du, Heye Zhang, David Firmin, Jennifer Keegan
Abstract Three-dimensional late gadolinium enhanced (LGE) cardiac MR (CMR) of left atrial scar in patients with atrial fibrillation (AF) has recently emerged as a promising technique to stratify patients, to guide ablation therapy and to predict treatment success. This requires a segmentation of the high intensity scar tissue and also a segmentation of the left atrium (LA) anatomy, the latter usually being derived from a separate bright-blood acquisition. Performing both segmentations automatically from a single 3D LGE CMR acquisition would eliminate the need for an additional acquisition and avoid subsequent registration issues. In this paper, we propose a joint segmentation method based on multiview two-task (MVTT) recursive attention model working directly on 3D LGE CMR images to segment the LA (and proximal pulmonary veins) and to delineate the scar on the same dataset. Using our MVTT recursive attention model, both the LA anatomy and scar can be segmented accurately (mean Dice score of 93% for the LA anatomy and 87% for the scar segmentations) and efficiently (~0.27 seconds to simultaneously segment the LA anatomy and scars directly from the 3D LGE CMR dataset with 60-68 2D slices). Compared to conventional unsupervised learning and other state-of-the-art deep learning based methods, the proposed MVTT model achieved excellent results, leading to an automatic generation of a patient-specific anatomical model combined with scar segmentation for patients in AF.
Published 2020-02-02
URL https://arxiv.org/abs/2002.00440v1
PDF https://arxiv.org/pdf/2002.00440v1.pdf
PWC https://paperswithcode.com/paper/simultaneous-left-atrium-anatomy-and-scar
Repo
Framework

#### Information cartography in association rule mining

Title Information cartography in association rule mining
Authors Iztok Fister Jr., Iztok Fister
Abstract Association Rule Mining is a data mining method for discovering the interesting relations between attributes in a huge transaction database. Typically, algorithms for association rule mining generate a huge number of association rules, from which it is hard to extract structured knowledge and automatically present this in a form that would be suitable for the user. Recently, an information cartography has been proposed for creating structured summaries of information and visualizing with methodology called “metro maps”. This was applied to many problem domains. In the hope of widening its applicability domain, the aim of this study is to develop a method for the automatic creation of metro maps of information obtained by association rule mining. Although the proposed method consists of multiple steps, its core presents metro map construction that is defined in the study as an optimization problem, which is solved using an evolutionary algorithm. Finally, this was applied to four well-known UCI Machine Learning datasets and one sport dataset. Visualizing the resulted metro maps not only justifies the fact this is a suitable tool for presenting structured knowledge hidden in data, but also that they can even tell stories to users.
Published 2020-02-29
URL https://arxiv.org/abs/2003.00348v1
PDF https://arxiv.org/pdf/2003.00348v1.pdf
PWC https://paperswithcode.com/paper/information-cartography-in-association-rule
Repo
Framework

#### Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

Title Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
Authors Qiaomin Xie, Yudong Chen, Zhaoran Wang, Zhuoran Yang
Abstract We develop provably efficient reinforcement learning algorithms for two-player zero-sum Markov games in which the two players simultaneously take actions. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online settings of the problems are considered. In the offline setting, we control both players and the goal is to find the Nash Equilibrium efficiently by minimizing the worst-case duality gap. In the online setting, we control a single player to play against an arbitrary opponent and the goal is to minimize the regret. For both settings, we propose an optimistic variant of the least-squares minimax value iteration algorithm. We show that our algorithm is computationally efficient and provably achieves an $\tilde O(\sqrt{d^3 H^3 T})$ upper bound on the duality gap and regret, without requiring additional assumptions on the sampling model. We highlight that our setting requires overcoming several new challenges that are absent in Markov decision processes or turn-based Markov games. In particular, to achieve optimism in simultaneous-move Marko games, we construct both upper and lower confidence bounds of the value function, and then compute the optimistic policy by solving a general-sum matrix game with these bounds as the payoff matrices. As finding the Nash Equilibrium of such a general-sum game is computationally hard, our algorithm instead solves for a Coarse Correlated Equilibrium (CCE), which can be obtained efficiently via linear programming. To our best knowledge, such a CCE-based scheme for implementing optimism has not appeared in the literature and might be of interest in its own right.
Published 2020-02-17
URL https://arxiv.org/abs/2002.07066v2
PDF https://arxiv.org/pdf/2002.07066v2.pdf
PWC https://paperswithcode.com/paper/learning-zero-sum-simultaneous-move-markov
Repo
Framework

#### Convex Duality of Deep Neural Networks

Title Convex Duality of Deep Neural Networks
Authors Tolga Ergen, Mert Pilanci
Abstract We study regularized deep neural networks and introduce an analytic framework to characterize the structure of the hidden layers. We show that a set of optimal hidden layer weight matrices for a norm regularized deep neural network training problem can be explicitly found as the extreme points of a convex set. For two-layer linear networks, we first formulate a convex dual program and prove that strong duality holds. We then extend our derivations to prove that strong duality also holds for certain deep networks. In particular, for linear deep networks, we show that each optimal layer weight matrix is rank-one and aligns with the previous layers when the network output is scalar. We also extend our analysis to the vector outputs and other convex loss functions. More importantly, we show that the same characterization can also be applied to deep ReLU networks with rank-one inputs, where we prove that strong duality still holds and optimal layer weight matrices are rank-one for scalar output networks. As a corollary, we prove that norm regularized deep ReLU networks yield spline interpolation for one-dimensional datasets which was previously known only for two-layer networks. We then verify our theoretical results via several numerical experiments.
Published 2020-02-22
URL https://arxiv.org/abs/2002.09773v1
PDF https://arxiv.org/pdf/2002.09773v1.pdf
PWC https://paperswithcode.com/paper/convex-duality-of-deep-neural-networks
Repo
Framework

#### A Robust Speaker Clustering Method Based on Discrete Tied Variational Autoencoder

Title A Robust Speaker Clustering Method Based on Discrete Tied Variational Autoencoder
Authors Chen Feng, Jianzong Wang, Tongxu Li, Junqing Peng, Jing Xiao
Abstract Recently, the speaker clustering model based on aggregation hierarchy cluster (AHC) is a common method to solve two main problems: no preset category number clustering and fix category number clustering. In general, model takes features like i-vectors as input of probability and linear discriminant analysis model (PLDA) aims to form the distance matric in long voice application scenario, and then clustering results are obtained through the clustering model. However, traditional speaker clustering method based on AHC has the shortcomings of long-time running and remains sensitive to environment noise. In this paper, we propose a novel speaker clustering method based on Mutual Information (MI) and a non-linear model with discrete variable, which under the enlightenment of Tied Variational Autoencoder (TVAE), to enhance the robustness against noise. The proposed method named Discrete Tied Variational Autoencoder (DTVAE) which shortens the elapsed time substantially. With experience results, it outperforms the general model and yields a relative Accuracy (ACC) improvement and significant time reduction.
Published 2020-03-04
URL https://arxiv.org/abs/2003.01955v1
PDF https://arxiv.org/pdf/2003.01955v1.pdf
PWC https://paperswithcode.com/paper/a-robust-speaker-clustering-method-based-on
Repo
Framework

#### Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena

Title Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
Authors Matt Emschwiller, David Gamarnik, Eren C. Kızıldağ, Ilias Zadik
Abstract In the context of neural network models, overparametrization refers to the phenomena whereby these models appear to generalize well on the unseen data, even though the number of parameters significantly exceeds the sample sizes, and the model perfectly fits the in-training data. A conventional explanation of this phenomena is based on self-regularization properties of algorithms used to train the data. In this paper we prove a series of results which provide a somewhat diverging explanation. Adopting a teacher/student model where the teacher network is used to generate the predictions and student network is trained on the observed labeled data, and then tested on out-of-sample data, we show that any student network interpolating the data generated by a teacher network generalizes well, provided that the sample size is at least an explicit quantity controlled by data dimension and approximation guarantee alone, regardless of the number of internal nodes of either teacher or student network. Our claim is based on approximating both teacher and student networks by polynomial (tensor) regression models with degree depending on the desired accuracy and network depth only. Such a parametrization notably does not depend on the number of internal nodes. Thus a message implied by our results is that parametrizing wide neural networks by the number of hidden nodes is misleading, and a more fitting measure of parametrization complexity is the number of regression coefficients associated with tensorized data. In particular, this somewhat reconciles the generalization ability of neural networks with more classical statistical notions of data complexity and generalization bounds. Our empirical results on MNIST and Fashion-MNIST datasets indeed confirm that tensorized regression achieves a good out-of-sample performance, even when the degree of the tensor is at most two.
Published 2020-03-23
URL https://arxiv.org/abs/2003.10523v1
PDF https://arxiv.org/pdf/2003.10523v1.pdf
PWC https://paperswithcode.com/paper/neural-networks-and-polynomial-regression
Repo
Framework

#### Splitting Convolutional Neural Network Structures for Efficient Inference

Title Splitting Convolutional Neural Network Structures for Efficient Inference
Abstract For convolutional neural networks (CNNs) that have a large volume of input data, memory management becomes a major concern. Memory cost reduction can be an effective way to deal with these problems that can be realized through different techniques such as feature map pruning, input data splitting, etc. Among various methods existing in this area of research, splitting the network structure is an interesting research field, and there are a few works done in this area. In this study, the problem of reducing memory utilization using network structure splitting is addressed. A new technique is proposed to split the network structure into small parts that consume lower memory than the original network. The split parts can be processed almost separately, which provides an essential role for better memory management. The split approach has been tested on two well-known network structures of VGG16 and ResNet18 for the classification of CIFAR10 images. Simulation results show that the splitting method reduces both the number of computational operations as well as the amount of memory consumption.
Published 2020-02-09
URL https://arxiv.org/abs/2002.03302v1
PDF https://arxiv.org/pdf/2002.03302v1.pdf
PWC https://paperswithcode.com/paper/splitting-convolutional-neural-network
Repo
Framework

#### Reinforced active learning for image segmentation

Title Reinforced active learning for image segmentation
Authors Arantxa Casanova, Pedro O. Pinheiro, Negar Rostamzadeh, Christopher J. Pal
Abstract Learning-based approaches for semantic segmentation have two inherent challenges. First, acquiring pixel-wise labels is expensive and time-consuming. Second, realistic segmentation datasets are highly unbalanced: some categories are much more abundant than others, biasing the performance to the most represented ones. In this paper, we are interested in focusing human labelling effort on a small subset of a larger pool of data, minimizing this effort while maximizing performance of a segmentation model on a hold-out set. We present a new active learning strategy for semantic segmentation based on deep reinforcement learning (RL). An agent learns a policy to select a subset of small informative image regions – opposed to entire images – to be labeled, from a pool of unlabeled data. The region selection decision is made based on predictions and uncertainties of the segmentation model being trained. Our method proposes a new modification of the deep Q-network (DQN) formulation for active learning, adapting it to the large-scale nature of semantic segmentation problems. We test the proof of concept in CamVid and provide results in the large-scale dataset Cityscapes. On Cityscapes, our deep RL region-based DQN approach requires roughly 30% less additional labeled data than our most competitive baseline to reach the same performance. Moreover, we find that our method asks for more labels of under-represented categories compared to the baselines, improving their performance and helping to mitigate class imbalance.
Published 2020-02-16
URL https://arxiv.org/abs/2002.06583v1
PDF https://arxiv.org/pdf/2002.06583v1.pdf
PWC https://paperswithcode.com/paper/reinforced-active-learning-for-image-1
Repo
Framework

#### Objects detection for remote sensing images based on polar coordinates

Title Objects detection for remote sensing images based on polar coordinates
Authors Lin Zhou, Haoran Wei, Hao Li, Yue Zhang, Xian Sun, Wenzhe Zhao
Abstract Oriented and horizontal bounding box are two typical output forms in the field of remote sensing object detection. In this filed, most present state-of-the-art detectors belong to anchor-based method and perform regression tasks in Cartesian coordinates, which cause the design of oriented detectors is much more complicated than the horizontal ones, because the former usually needs to devise more complex rotated anchors, rotated Intersection-over-Union (IOU) and rotated Non Maximum Supression (NMS). In this paper, we propose a novel anchor-free detector modeled in polar coordinates to detect objects for remote sensing images, which makes the acquisition of oriented output form be as simple as the horizontal one. Our model, named Polar Remote Sensing Object Detector (P-RSDet), takes the center point of each object as the pole point and the horizontal positive direction as the polar axis to establish the polar coordinate system. The detection of one object can be regarded as predictions of one polar radius and two polar angles for both horizontal and oriented bounding box by our model. P-RSDet realizes the combination of two output forms with minimum cost. Experiments show that our P-RSDet achieves competitive performances on DOTA, UCAS-AOD and NWPU VHR-10 datasets on both horizontal and oreinted detection fileds.
Published 2020-01-09
URL https://arxiv.org/abs/2001.02988v2
PDF https://arxiv.org/pdf/2001.02988v2.pdf
PWC https://paperswithcode.com/paper/objects-detection-for-remote-sensing-images
Repo
Framework

#### An End-to-End Framework for Unsupervised Pose Estimation of Occluded Pedestrians

Title An End-to-End Framework for Unsupervised Pose Estimation of Occluded Pedestrians
Authors Sudip Das, Perla Sai Raj Kishore, Ujjwal Bhattacharya
Abstract Pose estimation in the wild is a challenging problem, particularly in situations of (i) occlusions of varying degrees and (ii) crowded outdoor scenes. Most of the existing studies of pose estimation did not report the performance in similar situations. Moreover, pose annotations for occluded parts of human figures have not been provided in any of the relevant standard datasets which in turn creates further difficulties to the required studies for pose estimation of the entire figure of occluded humans. Well known pedestrian detection datasets such as CityPersons contains samples of outdoor scenes but it does not include pose annotations. Here, we propose a novel multi-task framework for end-to-end training towards the entire pose estimation of pedestrians including in situations of any kind of occlusion. To tackle this problem for training the network, we make use of a pose estimation dataset, MS-COCO, and employ unsupervised adversarial instance-level domain adaptation for estimating the entire pose of occluded pedestrians. The experimental studies show that the proposed framework outperforms the SOTA results for pose estimation, instance segmentation and pedestrian detection in cases of heavy occlusions (HO) and reasonable + heavy occlusions (R + HO) on the two benchmark datasets.
Published 2020-02-15
URL https://arxiv.org/abs/2002.06429v1
PDF https://arxiv.org/pdf/2002.06429v1.pdf
PWC https://paperswithcode.com/paper/an-end-to-end-framework-for-unsupervised-pose
Repo
Framework

#### Cautious Reinforcement Learning with Logical Constraints

Title Cautious Reinforcement Learning with Logical Constraints
Authors Mohammadhosein Hasanbeig, Alessandro Abate, Daniel Kroening
Abstract This paper presents the concept of an adaptive safe padding that forces Reinforcement Learning (RL) to synthesise optimal control policies while ensuring safety during the learning process. Policies are synthesised to satisfy a goal, expressed as a temporal logic formula, with maximal probability. Enforcing the RL agent to stay safe during learning might limit the exploration, however we show that the proposed architecture is able to automatically handle the trade-off between efficient progress in exploration (towards goal satisfaction) and ensuring safety. Theoretical guarantees are available on the optimality of the synthesised policies and on the convergence of the learning algorithm. Experimental results are provided to showcase the performance of the proposed method.
Published 2020-02-26
URL https://arxiv.org/abs/2002.12156v2
PDF https://arxiv.org/pdf/2002.12156v2.pdf
PWC https://paperswithcode.com/paper/cautious-reinforcement-learning-with-logical
Repo
Framework

#### Finding archetypal patterns for binary questionnaires

Title Finding archetypal patterns for binary questionnaires
Authors Ismael Cabero, Irene Epifanio
Abstract Archetypal analysis is an exploratory tool that explains a set of observations as mixtures of pure (extreme) patterns. If the patterns are actual observations of the sample, we refer to them as archetypoids. For the first time, we propose to use archetypoid analysis for binary observations. This tool can contribute to the understanding of a binary data set, as in the multivariate case. We illustrate the advantages of the proposed methodology in a simulation study and two applications, one exploring objects (rows) and the other exploring items (columns). One is related to determining student skill set profiles and the other to describing item response functions.
Published 2020-02-28
URL https://arxiv.org/abs/2003.00043v1
PDF https://arxiv.org/pdf/2003.00043v1.pdf
PWC https://paperswithcode.com/paper/finding-archetypal-patterns-for-binary
Repo
Framework

#### Functional Sequential Treatment Allocation with Covariates

Title Functional Sequential Treatment Allocation with Covariates
Authors Anders Bredahl Kock, David Preinerstorfer, Bezirgen Veliyev
Abstract We consider a multi-armed bandit problem with covariates. Given a realization of the covariate vector, instead of targeting the treatment with highest conditional expectation, the decision maker targets the treatment which maximizes a general functional of the conditional potential outcome distribution, e.g., a conditional quantile, trimmed mean, or a socio-economic functional such as an inequality, welfare or poverty measure. We develop expected regret lower bounds for this problem, and construct a near minimax optimal assignment policy.