January 29, 2020

3136 words 15 mins read

Paper Group ANR 681

A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman Problem. Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs. A mathematical model for universal semantics. Avaya Conversational Intelligence: A Real-Time System for Spoken Language Understanding in Human-Human Call Center Con …

A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman Problem


Title	A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman Problem
Authors	Mehdi El Krari, Belaïd Ahiod
Abstract	The Travelling Salesman Problem (TSP) is one of the most popular Combinatorial Optimization Problem. It is well solicited for the large variety of applications that it can solve, but also for its difficulty to find optimal solutions. One of the variants of the TSP is the Generalized TSP (GTSP), where the TSP is considered as a special case which makes the GTSP harder to solve. We propose in this paper a new memetic algorithm based on the well-known Breakout Local Search (BLS) metaheuristic to provide good solutions for GTSP instances. Our approach is competitive compared to other recent memetic algorithms proposed for the GTSP and gives at the same time some improvements to BLS to reduce its runtime.
Tasks	Combinatorial Optimization
Published	2019-10-19
URL	https://arxiv.org/abs/1911.01966v1
PDF	https://arxiv.org/pdf/1911.01966v1.pdf
PWC	https://paperswithcode.com/paper/a-memetic-algorithm-based-on-breakout-local
Repo
Framework

Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs


Title	Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs
Authors	Xi Gao, Han Zhang, Aliakbar Panahi, Tom Arodz
Abstract	When samples have internal structure, we often see a mismatch between the objective optimized during training and the model’s goal during inference. For example, in sequence-to-sequence modeling we are interested in high-quality translated sentences, but training typically uses maximum likelihood at the word level. The natural training-time loss would involve a combinatorial problem – dynamic programming-based global sequence alignment – but solutions to combinatorial problems are not differentiable with respect to their input parameters, so surrogate, differentiable losses are used instead. Here, we show how to perform gradient descent over combinatorial optimization algorithms that involve continuous parameters, for example edge weights, and can be efficiently expressed as linear programs. We demonstrate usefulness of gradient descent over combinatorial optimization in sequence-to-sequence modeling using differentiable encoder-decoder architecture with softmax or Gumbel-softmax, and in image classification in a weakly supervised setting where instead of the correct class for each photo, only groups of photos labeled with correct but unordered set of classes are available during training.
Tasks	Combinatorial Optimization, Graph Matching, Image Classification
Published	2019-10-18
URL	https://arxiv.org/abs/1910.08211v3
PDF	https://arxiv.org/pdf/1910.08211v3.pdf
PWC	https://paperswithcode.com/paper/combinatorial-losses-through-generalized
Repo
Framework

A mathematical model for universal semantics


Title	A mathematical model for universal semantics
Authors	Weinan E, Yajun Zhou
Abstract	We characterize the meaning of words with language-independent numerical fingerprints, through a mathematical analysis of recurring patterns in texts. Approximating texts by Markov processes on a long-range time scale, we are able to extract topics, discover synonyms, and sketch semantic fields from a particular document of moderate length, without consulting external knowledge-base or thesaurus. Our Markov semantic model allows us to represent each topical concept by a low-dimensional vector, interpretable as algebraic invariants in succinct statistical operations on the document, targeting local environments of individual words. These language-independent semantic representations enable a robot reader to both understand short texts in a given language (automated question-answering) and match medium-length texts across different languages (automated word translation). Our semantic fingerprints quantify local meaning of words in 14 representative languages across 5 major language families, suggesting a universal and cost-effective mechanism by which human languages are processed at the semantic level. Our protocols and source codes are publicly available on https://github.com/yajun-zhou/linguae-naturalis-principia-mathematica
Tasks	Question Answering
Published	2019-07-29
URL	https://arxiv.org/abs/1907.12293v6
PDF	https://arxiv.org/pdf/1907.12293v6.pdf
PWC	https://paperswithcode.com/paper/a-mathematical-model-for-linguistic
Repo
Framework

Avaya Conversational Intelligence: A Real-Time System for Spoken Language Understanding in Human-Human Call Center Conversations


Title	Avaya Conversational Intelligence: A Real-Time System for Spoken Language Understanding in Human-Human Call Center Conversations
Authors	Jan Mizgajski, Adrian Szymczak, Robert Głowski, Piotr Szymański, Piotr Żelasko, Łukasz Augustyniak, Mikołaj Morzy, Yishay Carmiel, Jeff Hodson, Łukasz Wójciak, Daniel Smoczyk, Adam Wróbel, Bartosz Borowik, Adam Artajew, Marcin Baran, Cezary Kwiatkowski, Marzena Żyła-Hoppe
Abstract	Avaya Conversational Intelligence(ACI) is an end-to-end, cloud-based solution for real-time Spoken Language Understanding for call centers. It combines large vocabulary, real-time speech recognition, transcript refinement, and entity and intent recognition in order to convert live audio into a rich, actionable stream of structured events. These events can be further leveraged with a business rules engine, thus serving as a foundation for real-time supervision and assistance applications. After the ingestion, calls are enriched with unsupervised keyword extraction, abstractive summarization, and business-defined attributes, enabling offline use cases, such as business intelligence, topic mining, full-text search, quality assurance, and agent training. ACI comes with a pretrained, configurable library of hundreds of intents and a robust intent training environment that allows for efficient, cost-effective creation and customization of customer-specific intents.
Tasks	Abstractive Text Summarization, Keyword Extraction, Speech Recognition, Spoken Language Understanding
Published	2019-09-02
URL	https://arxiv.org/abs/1909.02851v1
PDF	https://arxiv.org/pdf/1909.02851v1.pdf
PWC	https://paperswithcode.com/paper/avaya-conversational-intelligence-a-real-time
Repo
Framework

I Bet You Are Wrong: Gambling Adversarial Networks for Structured Semantic Segmentation


Title	I Bet You Are Wrong: Gambling Adversarial Networks for Structured Semantic Segmentation
Authors	Laurens Samson, Nanne van Noord, Olaf Booij, Michael Hofmann, Efstratios Gavves, Mohsen Ghafoorian
Abstract	Adversarial training has been recently employed for realizing structured semantic segmentation, in which the aim is to preserve higher-level scene structural consistencies in dense predictions. However, as we show, value-based discrimination between the predictions from the segmentation network and ground-truth annotations can hinder the training process from learning to improve structural qualities as well as disabling the network from properly expressing uncertainties. In this paper, we rethink adversarial training for semantic segmentation and propose to formulate the fake/real discrimination framework with a correct/incorrect training objective. More specifically, we replace the discriminator with a “gambler” network that learns to spot and distribute its budget in areas where the predictions are clearly wrong, while the segmenter network tries to leave no clear clues for the gambler where to bet. Empirical evaluation on two road-scene semantic segmentation tasks shows that not only does the proposed method re-enable expressing uncertainties, it also improves pixel-wise and structure-based metrics.
Tasks	Semantic Segmentation
Published	2019-08-07
URL	https://arxiv.org/abs/1908.02711v1
PDF	https://arxiv.org/pdf/1908.02711v1.pdf
PWC	https://paperswithcode.com/paper/i-bet-you-are-wrong-gambling-adversarial
Repo
Framework

Semi-automatic System for Title Construction


Title	Semi-automatic System for Title Construction
Authors	Swagata Duari, Vasudha Bhatnagar
Abstract	In this paper, we propose a semi-automatic system for title construction from scientific abstracts. The system extracts and recommends impactful words from the text, which the author can creatively use to construct an appropriate title for the manuscript. The work is based on the hypothesis that keywords are good candidates for title construction. We extract important words from the document by inducing a supervised keyword extraction model. The model is trained on novel features extracted from graph-of-text representation of the document. We empirically show that these graph-based features are capable of discriminating keywords from non-keywords. We further establish empirically that the proposed approach can be applied to any text irrespective of the training domain and corpus. We evaluate the proposed system by computing the overlap between extracted keywords and the list of title-words for documents, and we observe a macro-averaged precision of 82%.
Tasks	Keyword Extraction
Published	2019-05-01
URL	http://arxiv.org/abs/1905.00470v1
PDF	http://arxiv.org/pdf/1905.00470v1.pdf
PWC	https://paperswithcode.com/paper/semi-automatic-system-for-title-construction
Repo
Framework

Gap-Increasing Policy Evaluation for Efficient and Noise-Tolerant Reinforcement Learning


Title	Gap-Increasing Policy Evaluation for Efficient and Noise-Tolerant Reinforcement Learning
Authors	Tadashi Kozuno, Dongqi Han, Kenji Doya
Abstract	In real-world applications of reinforcement learning (RL), noise from inherent stochasticity of environments is inevitable. However, current policy evaluation algorithms, which plays a key role in many RL algorithms, are either prone to noise or inefficient. To solve this issue, we introduce a novel policy evaluation algorithm, which we call Gap-increasing RetrAce Policy Evaluation (GRAPE). It leverages two recent ideas: (1) gap-increasing value update operators in advantage learning for noise-tolerance and (2) off-policy eligibility trace in Retrace algorithm for efficient learning. We provide detailed theoretical analysis of the new algorithm that shows its efficiency and noise-tolerance inherited from Retrace and advantage learning. Furthermore, our analysis shows that GRAPE’s learning is significantly efficient than that of a simple learning-rate-based approach while keeping the same level of noise-tolerance. We applied GRAPE to control problems and obtained experimental results supporting our theoretical analysis.
Tasks
Published	2019-06-18
URL	https://arxiv.org/abs/1906.07586v1
PDF	https://arxiv.org/pdf/1906.07586v1.pdf
PWC	https://paperswithcode.com/paper/gap-increasing-policy-evaluation-for
Repo
Framework

LISA: a MATLAB package for Longitudinal Image Sequence Analysis


Title	LISA: a MATLAB package for Longitudinal Image Sequence Analysis
Authors	Jang Ik Cho, Xiaofeng Wang, Yifan Xu, Jiayang Sun
Abstract	Large sequences of images (or movies) can now be obtained on an unprecedented scale, which poses fundamental challenges to the existing image analysis techniques. The challenges include heterogeneity, (automatic) alignment, multiple comparisons, potential artifacts, and hidden noises. This paper introduces our MATLAB package, Longitudinal Image Sequence Analysis (LISA), as a one-stop ensemble of image processing and analysis tool for comparing a general class of images from either different times, sessions, or subjects. Given two contrasting sequences of images, the image processing in LISA starts with selecting a region of interest in two representative images, followed by automatic or manual segmentation and registration. Automatic segmentation de-noises an image using a mixture of Gaussian distributions of the pixel intensity values, while manual segmentation applies a user-chosen intensity cut-off value to filter out noises. Automatic registration aligns the contrasting images based on a mid-line regression whereas manual registration lines up the images along a reference line formed by two user-selected points. The processed images are then rendered for simultaneous statistical comparisons to generate D, S, T, and P-maps. The D map represents a curated difference of contrasting images, the S map is the non-parametrically smoothed differences, the T map presents the variance-adjusted, smoothed differences, and the P-map provides multiplicity-controlled p-values. These maps reveal the regions with significant differences due to either longitudinal, subject-specific, or treatment changes. A user can skip the image processing step to dive directly into the statistical analysis step if the images have already been processed. Hence, LISA offers flexibility in applying other image pre-processing tools. LISA also has a parallel computing option for high definition images.
Tasks
Published	2019-02-16
URL	http://arxiv.org/abs/1902.06131v1
PDF	http://arxiv.org/pdf/1902.06131v1.pdf
PWC	https://paperswithcode.com/paper/lisa-a-matlab-package-for-longitudinal-image
Repo
Framework


Title	Cross-Modal Interaction Networks for Query-Based Moment Retrieval in Videos
Authors	Zhu Zhang, Zhijie Lin, Zhou Zhao, Zhenxin Xiao
Abstract	Query-based moment retrieval aims to localize the most relevant moment in an untrimmed video according to the given natural language query. Existing works often only focus on one aspect of this emerging task, such as the query representation learning, video context modeling or multi-modal fusion, thus fail to develop a comprehensive system for further performance improvement. In this paper, we introduce a novel Cross-Modal Interaction Network (CMIN) to consider multiple crucial factors for this challenging task, including (1) the syntactic structure of natural language queries; (2) long-range semantic dependencies in video context and (3) the sufficient cross-modal interaction. Specifically, we devise a syntactic GCN to leverage the syntactic structure of queries for fine-grained representation learning, propose a multi-head self-attention to capture long-range semantic dependencies from video context, and next employ a multi-stage cross-modal interaction to explore the potential relations of video and query contents. The extensive experiments demonstrate the effectiveness of our proposed method.
Tasks	Representation Learning
Published	2019-06-06
URL	https://arxiv.org/abs/1906.02497v2
PDF	https://arxiv.org/pdf/1906.02497v2.pdf
PWC	https://paperswithcode.com/paper/cross-modal-interaction-networks-for-query
Repo
Framework

Ensemble approach for natural language question answering problem


Title	Ensemble approach for natural language question answering problem
Authors	Anna Aniol, Marcin Pietron
Abstract	Machine comprehension, answering a question depending on a given context paragraph is a typical task of Natural Language Understanding. It requires to model complex dependencies existing between the question and the context paragraph. There are many neural network models attempting to solve the problem of question answering. The best models have been selected, studied and compared with each other. All the selected models are based on the neural attention mechanism concept. Additionally, studies on a SQUAD dataset were performed. The subsets of queries were extracted and then each model was analyzed how it deals with specific group of queries. Based on these three model ensemble model was created and tested on SQUAD dataset. It outperforms the best Mnemonic Reader model.
Tasks	Question Answering, Reading Comprehension
Published	2019-08-26
URL	https://arxiv.org/abs/1908.09720v2
PDF	https://arxiv.org/pdf/1908.09720v2.pdf
PWC	https://paperswithcode.com/paper/ensemble-approach-for-natural-language
Repo
Framework

Imitation Learning for Human Pose Prediction


Title	Imitation Learning for Human Pose Prediction
Authors	Borui Wang, Ehsan Adeli, Hsu-kuang Chiu, De-An Huang, Juan Carlos Niebles
Abstract	Modeling and prediction of human motion dynamics has long been a challenging problem in computer vision, and most existing methods rely on the end-to-end supervised training of various architectures of recurrent neural networks. Inspired by the recent success of deep reinforcement learning methods, in this paper we propose a new reinforcement learning formulation for the problem of human pose prediction, and develop an imitation learning algorithm for predicting future poses under this formulation through a combination of behavioral cloning and generative adversarial imitation learning. Our experiments show that our proposed method outperforms all existing state-of-the-art baseline models by large margins on the task of human pose prediction in both short-term predictions and long-term predictions, while also enjoying huge advantage in training speed.
Tasks	Human Pose Forecasting, Imitation Learning, Pose Prediction
Published	2019-09-08
URL	https://arxiv.org/abs/1909.03449v1
PDF	https://arxiv.org/pdf/1909.03449v1.pdf
PWC	https://paperswithcode.com/paper/imitation-learning-for-human-pose-prediction
Repo
Framework

Pricing Mechanism for Resource Sustainability in Competitive Online Learning Multi-Agent Systems


Title	Pricing Mechanism for Resource Sustainability in Competitive Online Learning Multi-Agent Systems
Authors	Ezra Tampubolon, Holger Boche
Abstract	In this paper, we consider the problem of resource congestion control for competing online learning agents. On the basis of non-cooperative game as the model for the interaction between the agents, and the noisy online mirror ascent as the model for rational behavior of the agents, we propose a novel pricing mechanism which gives the agents incentives for sustainable use of the resources. Our mechanism is distributed and resource-centric, in the sense that it is done by the resources themselves and not by a centralized instance, and that it is based rather on the congestion state of the resources than the preferences of the agents. In case that the noise is persistent, and for several choices of the intrinsic parameter of the agents, such as their learning rate, and of the mechanism parameters, such as the learning rate of -, the progressivity of the price-setters, and the extrinsic price sensitivity of the agents, we show that the accumulative violation of the resource constraints of the resulted iterates is sub-linear w.r.t. the time horizon. Moreover, we provide numerical simulations to support our theoretical findings.
Tasks
Published	2019-10-21
URL	https://arxiv.org/abs/1910.09314v1
PDF	https://arxiv.org/pdf/1910.09314v1.pdf
PWC	https://paperswithcode.com/paper/pricing-mechanism-for-resource-sustainability
Repo
Framework

Data Augmentation for Leaf Segmentation and Counting Tasks in Rosette Plants


Title	Data Augmentation for Leaf Segmentation and Counting Tasks in Rosette Plants
Authors	Dmitry Kuznichov, Alon Zvirin, Yaron Honen, Ron Kimmel
Abstract	Deep learning techniques involving image processing and data analysis are constantly evolving. Many domains adapt these techniques for object segmentation, instantiation and classification. Recently, agricultural industries adopted those techniques in order to bring automation to farmers around the globe. One analysis procedure required for automatic visual inspection in this domain is leaf count and segmentation. Collecting labeled data from field crops and greenhouses is a complicated task due to the large variety of crops, growth seasons, climate changes, phenotype diversity, and more, especially when specific learning tasks require a large amount of labeled data for training. Data augmentation for training deep neural networks is well established, examples include data synthesis, using generative semi-synthetic models, and applying various kinds of transformations. In this paper we propose a method that preserves the geometric structure of the data objects, thus keeping the physical appearance of the data-set as close as possible to imaged plants in real agricultural scenes. The proposed method provides state of the art results when applied to the standard benchmark in the field, namely, the ongoing Leaf Segmentation Challenge hosted by Computer Vision Problems in Plant Phenotyping.
Tasks	Data Augmentation, Semantic Segmentation
Published	2019-03-20
URL	http://arxiv.org/abs/1903.08583v1
PDF	http://arxiv.org/pdf/1903.08583v1.pdf
PWC	https://paperswithcode.com/paper/data-augmentation-for-leaf-segmentation-and
Repo
Framework

Graph-to-Graph Transformer for Transition-based Dependency Parsing


Title	Graph-to-Graph Transformer for Transition-based Dependency Parsing
Authors	Alireza Mohammadshahi, James Henderson
Abstract	Transition-based dependency parsing is a challenging task for conditioning on and predicting structures. We demonstrate state-of-the-art results on this benchmark with the Graph2Graph Transformer architecture. This novel architecture supports both the input and output of arbitrary graphs via its attention mechanism. It can also be integrated both with previous neural network structured prediction techniques and with existing Transformer pre-trained models. Both with and without BERT pretraining, adding dependency graph inputs via the attention mechanism results in significant improvements over previously proposed mechanism for encoding the partial parse tree, resulting in accuracies which improve the state-of-the-art in transition-based dependency parsing, achieving 95.64% UAS and 93.81% LAS performance on Stanford WSJ dependencies. Graph2Graph Transformers are not restricted to tree structures and can be easily applied to a wide range of NLP tasks.
Tasks	Dependency Parsing, Structured Prediction, Transition-Based Dependency Parsing
Published	2019-11-08
URL	https://arxiv.org/abs/1911.03561v1
PDF	https://arxiv.org/pdf/1911.03561v1.pdf
PWC	https://paperswithcode.com/paper/graph-to-graph-transformer-for-transition
Repo
Framework

A Class of Parameterized Loss Functions for Classification: Optimization Tradeoffs and Robustness Characteristics


Title	A Class of Parameterized Loss Functions for Classification: Optimization Tradeoffs and Robustness Characteristics
Authors	Tyler Sypherd, Mario Diaz, Harshit Laddha, Lalitha Sankar, Peter Kairouz, Gautam Dasarathy
Abstract	Recently, a parametrized class of loss functions called $\alpha$-loss, $\alpha \in [1,\infty]$, has been introduced for classification. This family, which includes the log-loss and the 0-1 loss as special cases, comes with compelling properties including an equivalent margin-based form which is classification-calibrated for all $\alpha$. We introduce a generalization of this family to the entire range of $\alpha \in (0,\infty]$ and establish how the parameter $\alpha$ enables the practitioner to choose among a host of operating conditions that are important in modern machine learning tasks. We prove that smaller $\alpha$ values are more conducive to faster optimization; in fact, $\alpha$-loss is convex for $\alpha \le 1$ and quasi-convex for $\alpha >1$. Moreover, we establish bounds to quantify the degradation of the local-quasi-convexity of the optimization landscape as $\alpha$ increases; we show that this directly translates to a computational slow down. On the other hand, our theoretical results also suggest that larger $\alpha$ values lead to better generalization performance. This is a consequence of the ability of the $\alpha$-loss to limit the effect of less likely data as $\alpha$ increases from 1, thereby facilitating robustness to outliers and noise in the training data. We provide strong evidence supporting this assertion with several experiments on benchmark datasets that establish the efficacy of $\alpha$-loss for $\alpha > 1$ in robustness to errors in the training data. Of equal interest is the fact that, for $\alpha < 1$, our experiments show that the decreased robustness seems to counteract class imbalances in training data.
Tasks
Published	2019-06-05
URL	https://arxiv.org/abs/1906.02314v4
PDF	https://arxiv.org/pdf/1906.02314v4.pdf
PWC	https://paperswithcode.com/paper/a-tunable-loss-function-for-classification
Repo
Framework