October 16, 2019

2848 words 14 mins read

Paper Group ANR 1127

The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. On the Graded Acceptability of Arguments in Abstract and Instantiated Argumentation. Skin Lesion Segmentation Using Atrous Convolution via DeepLab v3. Making Deep Heatmaps Robust to Partial Occlusions for 3D Object Pose Estimation. The Capacity Constrained Facility Location problem …

The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches


Title	The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Authors	Aris Filos-Ratsikas, Paul W. Goldberg
Abstract	We resolve the computational complexity of two problems known as NECKLACE-SPLITTING and DISCRETE HAM SANDWICH, showing that they are PPA-complete. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the CONSENSUS-HALVING problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our construction is a smooth embedding of the high-dimensional M"obius strip in the CONSENSUS-HALVING problem. These results settle the status of PPA as a class that captures the complexity of “natural” problems whose definitions do not incorporate a circuit.
Tasks
Published	2018-05-31
URL	http://arxiv.org/abs/1805.12559v2
PDF	http://arxiv.org/pdf/1805.12559v2.pdf
PWC	https://paperswithcode.com/paper/the-complexity-of-splitting-necklaces-and
Repo
Framework

On the Graded Acceptability of Arguments in Abstract and Instantiated Argumentation


Title	On the Graded Acceptability of Arguments in Abstract and Instantiated Argumentation
Authors	Davide Grossi, Sanjay Modgil
Abstract	The paper develops a formal theory of the degree of justification of arguments, which relies solely on the structure of an argumentation framework, and which can be successfully interfaced with approaches to instantiated argumentation. The theory is developed in three steps. First, the paper introduces a graded generalization of the two key notions underpinning Dung’s semantics: self-defense and conflict-freeness. This leads to a natural generalization of Dung’s semantics, whereby standard extensions are weakened or strengthened depending on the level of self-defense and conflict-freeness they meet. The paper investigates the fixpoint theory of these semantics, establishing existence results for them. Second, the paper shows how graded semantics readily provide an approach to argument rankings, offering a novel contribution to the recently growing research programme on ranking-based semantics. Third, this novel approach to argument ranking is applied and studied in the context of instantiated argumentation frameworks, and in so doing is shown to account for a simple form of accrual of arguments within the Dung paradigm. Finally, the theory is compared in detail with existing approaches.
Tasks
Published	2018-11-08
URL	http://arxiv.org/abs/1811.03355v1
PDF	http://arxiv.org/pdf/1811.03355v1.pdf
PWC	https://paperswithcode.com/paper/on-the-graded-acceptability-of-arguments-in
Repo
Framework

Skin Lesion Segmentation Using Atrous Convolution via DeepLab v3


Title	Skin Lesion Segmentation Using Atrous Convolution via DeepLab v3
Authors	Yujie Wang, Simon Sun, Jahow Yu, Dr. Limin Yu
Abstract	As melanoma diagnoses increase across the US, automated efforts to identify malignant lesions become increasingly of interest to the research community. Segmentation of dermoscopic images is the first step in this process, thus accuracy is crucial. Although techniques utilizing convolutional neural networks have been used in the past for lesion segmentation, we present a solution employing the recently published DeepLab 3, an atrous convolution method for image segmentation. Although the results produced by this run are not ideal, with a mean Jaccard index of 0.498, we believe that with further adjustments and modifications to the compatibility with the DeepLab code and with training on more powerful processing units, this method may achieve better results in future trials.
Tasks	Lesion Segmentation, Semantic Segmentation
Published	2018-07-24
URL	http://arxiv.org/abs/1807.08891v1
PDF	http://arxiv.org/pdf/1807.08891v1.pdf
PWC	https://paperswithcode.com/paper/skin-lesion-segmentation-using-atrous
Repo
Framework

Making Deep Heatmaps Robust to Partial Occlusions for 3D Object Pose Estimation


Title	Making Deep Heatmaps Robust to Partial Occlusions for 3D Object Pose Estimation
Authors	Markus Oberweger, Mahdi Rad, Vincent Lepetit
Abstract	We introduce a novel method for robust and accurate 3D object pose estimation from a single color image under large occlusions. Following recent approaches, we first predict the 2D projections of 3D points related to the target object and then compute the 3D pose from these correspondences using a geometric method. Unfortunately, as the results of our experiments show, predicting these 2D projections using a regular CNN or a Convolutional Pose Machine is highly sensitive to partial occlusions, even when these methods are trained with partially occluded examples. Our solution is to predict heatmaps from multiple small patches independently and to accumulate the results to obtain accurate and robust predictions. Training subsequently becomes challenging because patches with similar appearances but different positions on the object correspond to different heatmaps. However, we provide a simple yet effective solution to deal with such ambiguities. We show that our approach outperforms existing methods on two challenging datasets: The Occluded LineMOD dataset and the YCB-Video dataset, both exhibiting cluttered scenes with highly occluded objects. Project website: https://www.tugraz.at/institute/icg/research/team-lepetit/research-projects/robust-object-pose-estimation/
Tasks	Pose Estimation
Published	2018-04-11
URL	http://arxiv.org/abs/1804.03959v3
PDF	http://arxiv.org/pdf/1804.03959v3.pdf
PWC	https://paperswithcode.com/paper/making-deep-heatmaps-robust-to-partial
Repo
Framework

The Capacity Constrained Facility Location problem


Title	The Capacity Constrained Facility Location problem
Authors	Haris Aziz, Hau Chan, Barton E. Lee, David C. Parkes
Abstract	We initiate the study of the capacity constrained facility location problem from a mechanism design perspective. The capacity constrained setting leads to a new strategic environment where a facility serves a subset of the population, which is endogenously determined by the ex-post Nash equilibrium of an induced subgame and is not directly controlled by the mechanism designer. Our focus is on mechanisms that are ex-post dominant-strategy incentive compatible (DIC) at the reporting stage. We provide a complete characterization of DIC mechanisms via the family of Generalized Median Mechanisms (GMMs). In general, the social welfare optimal mechanism is not DIC. Adopting the worst-case approximation measure, we attain tight lower bounds on the approximation ratio of any DIC mechanism. The well-known median mechanism is shown to be optimal among the family of DIC mechanisms for certain capacity ranges. Surprisingly, the framework we introduce provides a new characterization for the family of GMMs, and is responsive to gaps in the current social choice literature highlighted by Border and Jordan (1983) and Barbar{`a}, Mass{'o} and Serizawa (1998).
Tasks
Published	2018-06-04
URL	http://arxiv.org/abs/1806.00960v2
PDF	http://arxiv.org/pdf/1806.00960v2.pdf
PWC	https://paperswithcode.com/paper/the-capacity-constrained-facility-location
Repo
Framework

Inductive Learning of Answer Set Programs from Noisy Examples


Title	Inductive Learning of Answer Set Programs from Noisy Examples
Authors	Mark Law, Alessandra Russo, Krysia Broda
Abstract	In recent years, non-monotonic Inductive Logic Programming has received growing interest. Specifically, several new learning frameworks and algorithms have been introduced for learning under the answer set semantics, allowing the learning of common-sense knowledge involving defaults and exceptions, which are essential aspects of human reasoning. In this paper, we present a noise-tolerant generalisation of the learning from answer sets framework. We evaluate our ILASP3 system, both on synthetic and on real datasets, represented in the new framework. In particular, we show that on many of the datasets ILASP3 achieves a higher accuracy than other ILP systems that have previously been applied to the datasets, including a recently proposed differentiable learning framework.
Tasks	Common Sense Reasoning
Published	2018-08-25
URL	http://arxiv.org/abs/1808.08441v1
PDF	http://arxiv.org/pdf/1808.08441v1.pdf
PWC	https://paperswithcode.com/paper/inductive-learning-of-answer-set-programs
Repo
Framework

Transfer Learning in Brain-Computer Interfaces with Adversarial Variational Autoencoders


Title	Transfer Learning in Brain-Computer Interfaces with Adversarial Variational Autoencoders
Authors	Ozan Ozdenizci, Ye Wang, Toshiaki Koike-Akino, Deniz Erdogmus
Abstract	We introduce adversarial neural networks for representation learning as a novel approach to transfer learning in brain-computer interfaces (BCIs). The proposed approach aims to learn subject-invariant representations by simultaneously training a conditional variational autoencoder (cVAE) and an adversarial network. We use shallow convolutional architectures to realize the cVAE, and the learned encoder is transferred to extract subject-invariant features from unseen BCI users’ data for decoding. We demonstrate a proof-of-concept of our approach based on analyses of electroencephalographic (EEG) data recorded during a motor imagery BCI experiment.
Tasks	EEG, Representation Learning, Transfer Learning
Published	2018-12-17
URL	http://arxiv.org/abs/1812.06857v1
PDF	http://arxiv.org/pdf/1812.06857v1.pdf
PWC	https://paperswithcode.com/paper/transfer-learning-in-brain-computer
Repo
Framework

An Anytime Algorithm for Task and Motion MDPs


Title	An Anytime Algorithm for Task and Motion MDPs
Authors	Siddharth Srivastava, Nishant Desai, Richard Freedman, Shlomo Zilberstein
Abstract	Integrated task and motion planning has emerged as a challenging problem in sequential decision making, where a robot needs to compute high-level strategy and low-level motion plans for solving complex tasks. While high-level strategies require decision making over longer time-horizons and scales, their feasibility depends on low-level constraints based upon the geometries and continuous dynamics of the environment. The hybrid nature of this problem makes it difficult to scale; most existing approaches focus on deterministic, fully observable scenarios. We present a new approach where the high-level decision problem occurs in a stochastic setting and can be modeled as a Markov decision process. In contrast to prior efforts, we show that complete MDP policies, or contingent behaviors, can be computed effectively in an anytime fashion. Our algorithm continuously improves the quality of the solution and is guaranteed to be probabilistically complete. We evaluate the performance of our approach on a challenging, realistic test problem: autonomous aircraft inspection. Our results show that we can effectively compute consistent task and motion policies for the most likely execution-time outcomes using only a fraction of the computation required to develop the complete task and motion policy.
Tasks	Decision Making, Motion Planning
Published	2018-02-16
URL	http://arxiv.org/abs/1802.05835v1
PDF	http://arxiv.org/pdf/1802.05835v1.pdf
PWC	https://paperswithcode.com/paper/an-anytime-algorithm-for-task-and-motion-mdps
Repo
Framework

Matrix completion and extrapolation via kernel regression


Title	Matrix completion and extrapolation via kernel regression
Authors	Pere Giménez-Febrer, Alba Pagès-Zamora, Georgios B. Giannakis
Abstract	Matrix completion and extrapolation (MCEX) are dealt with here over reproducing kernel Hilbert spaces (RKHSs) in order to account for prior information present in the available data. Aiming at a faster and low-complexity solver, the task is formulated as a kernel ridge regression. The resultant MCEX algorithm can also afford online implementation, while the class of kernel functions also encompasses several existing approaches to MC with prior information. Numerical tests on synthetic and real datasets show that the novel approach performs faster than widespread methods such as alternating least squares (ALS) or stochastic gradient descent (SGD), and that the recovery error is reduced, especially when dealing with noisy data.
Tasks	Matrix Completion
Published	2018-08-01
URL	http://arxiv.org/abs/1808.00441v2
PDF	http://arxiv.org/pdf/1808.00441v2.pdf
PWC	https://paperswithcode.com/paper/matrix-completion-and-extrapolation-via
Repo
Framework

Disfluency Detection using a Noisy Channel Model and a Deep Neural Language Model


Title	Disfluency Detection using a Noisy Channel Model and a Deep Neural Language Model
Authors	Paria Jamshid Lou, Mark Johnson
Abstract	This paper presents a model for disfluency detection in spontaneous speech transcripts called LSTM Noisy Channel Model. The model uses a Noisy Channel Model (NCM) to generate n-best candidate disfluency analyses and a Long Short-Term Memory (LSTM) language model to score the underlying fluent sentences of each analysis. The LSTM language model scores, along with other features, are used in a MaxEnt reranker to identify the most plausible analysis. We show that using an LSTM language model in the reranking process of noisy channel disfluency model improves the state-of-the-art in disfluency detection.
Tasks	Language Modelling
Published	2018-08-28
URL	http://arxiv.org/abs/1808.09091v1
PDF	http://arxiv.org/pdf/1808.09091v1.pdf
PWC	https://paperswithcode.com/paper/disfluency-detection-using-a-noisy-channel
Repo
Framework

Bounded Information Rate Variational Autoencoders


Title	Bounded Information Rate Variational Autoencoders
Authors	D. T. Braithwaite, W. B. Kleijn
Abstract	This paper introduces a new member of the family of Variational Autoencoders (VAE) that constrains the rate of information transferred by the latent layer. The latent layer is interpreted as a communication channel, the information rate of which is bound by imposing a pre-set signal-to-noise ratio. The new constraint subsumes the mutual information between the input and latent variables, combining naturally with the likelihood objective of the observed data as used in a conventional VAE. The resulting Bounded-Information-Rate Variational Autoencoder (BIR-VAE) provides a meaningful latent representation with an information resolution that can be specified directly in bits by the system designer. The rate constraint can be used to prevent overtraining, and the method naturally facilitates quantisation of the latent variables at the set rate. Our experiments confirm that the BIR-VAE has a meaningful latent representation and that its performance is at least as good as state-of-the-art competing algorithms, but with lower computational complexity.
Tasks
Published	2018-07-19
URL	http://arxiv.org/abs/1807.07306v2
PDF	http://arxiv.org/pdf/1807.07306v2.pdf
PWC	https://paperswithcode.com/paper/bounded-information-rate-variational
Repo
Framework

Global sensitivity analysis for optimization with variable selection


Title	Global sensitivity analysis for optimization with variable selection
Authors	Adrien Spagnol, Rodolphe Le Riche, Sebastien Da Veiga
Abstract	The optimization of high dimensional functions is a key issue in engineering problems but it frequently comes at a cost that is not acceptable since it usually involves a complex and expensive computer code. Engineers often overcome this limitation by first identifying which parameters drive the most the function variations: non-influential variables are set to a fixed value and the optimization procedure is carried out with the remaining influential variables. Such variable selection is performed through influence measures that are meaningful for regression problems. However it does not account for the specific structure of optimization problems where we would like to identify which variables most lead to constraints satisfaction and low values of the objective function. In this paper, we propose a new sensitivity analysis that accounts for the specific aspects of optimization problems. In particular, we introduce an influence measure based on the Hilbert-Schmidt Independence Criterion to characterize whether a design variable matters to reach low values of the objective function and to satisfy the constraints. This sensitivity measure makes it possible to sort the inputs and reduce the problem dimension. We compare a random and a greedy strategies to set the values of the non-influential variables before conducting a local optimization. Applications to several test-cases show that this variable selection and the greedy strategy significantly reduce the number of function evaluations at a limited cost in terms of solution performance.
Tasks
Published	2018-11-12
URL	http://arxiv.org/abs/1811.04646v1
PDF	http://arxiv.org/pdf/1811.04646v1.pdf
PWC	https://paperswithcode.com/paper/global-sensitivity-analysis-for-optimization
Repo
Framework

Fusing Recency into Neural Machine Translation with an Inter-Sentence Gate Model


Title	Fusing Recency into Neural Machine Translation with an Inter-Sentence Gate Model
Authors	Shaohui Kuang, Deyi Xiong
Abstract	Neural machine translation (NMT) systems are usually trained on a large amount of bilingual sentence pairs and translate one sentence at a time, ignoring inter-sentence information. This may make the translation of a sentence ambiguous or even inconsistent with the translations of neighboring sentences. In order to handle this issue, we propose an inter-sentence gate model that uses the same encoder to encode two adjacent sentences and controls the amount of information flowing from the preceding sentence to the translation of the current sentence with an inter-sentence gate. In this way, our proposed model can capture the connection between sentences and fuse recency from neighboring sentences into neural machine translation. On several NIST Chinese-English translation tasks, our experiments demonstrate that the proposed inter-sentence gate model achieves substantial improvements over the baseline.
Tasks	Machine Translation
Published	2018-06-12
URL	http://arxiv.org/abs/1806.04466v1
PDF	http://arxiv.org/pdf/1806.04466v1.pdf
PWC	https://paperswithcode.com/paper/fusing-recency-into-neural-machine
Repo
Framework

Using accumulation to optimize deep residual neural nets


Title	Using accumulation to optimize deep residual neural nets
Authors	Yatin Saraiya
Abstract	Residual Neural Networks [1] won first place in all five main tracks of the ImageNet and COCO 2015 competitions. This kind of network involves the creation of pluggable modules such that the output contains a residual from the input. The residual in that paper is the identity function. We propose to include residuals from all lower layers, suitably normalized, to create the residual. This way, all previous layers contribute equally to the output of a layer. We show that our approach is an improvement on [1] for the CIFAR-10 dataset.
Tasks
Published	2018-01-14
URL	http://arxiv.org/abs/1803.05778v1
PDF	http://arxiv.org/pdf/1803.05778v1.pdf
PWC	https://paperswithcode.com/paper/using-accumulation-to-optimize-deep-residual
Repo
Framework

Are 2D-LSTM really dead for offline text recognition?


Title	Are 2D-LSTM really dead for offline text recognition?
Authors	Bastien Moysset, Ronaldo Messina
Abstract	There is a recent trend in handwritten text recognition with deep neural networks to replace 2D recurrent layers with 1D, and in some cases even completely remove the recurrent layers, relying on simple feed-forward convolutional only architectures. The most used type of recurrent layer is the Long-Short Term Memory (LSTM). The motivations to do so are many: there are few open-source implementations of 2D-LSTM, even fewer supporting GPU implementations (currently cuDNN only implements 1D-LSTM); 2D recurrences reduce the amount of computations that can be parallelized, and thus possibly increase the training/inference time; recurrences create global dependencies with respect to the input, and sometimes this may not be desirable. Many recent competitions were won by systems that employed networks that use 2D-LSTM layers. Most previous work that compared 1D or pure feed-forward architectures to 2D recurrent models have done so on simple datasets or did not fully optimize the “baseline” 2D model compared to the challenger model, which was dully optimized. In this work, we aim at a fair comparison between 2D and competing models and also extensively evaluate them on more complex datasets that are more representative of challenging “real-world” data, compared to “academic” datasets that are more restricted in their complexity. We aim at determining when and why the 1D and 2D recurrent models have different results. We also compare the results with a language model to assess if linguistic constraints do level the performance of the different networks. Our results show that for challenging datasets, 2D-LSTM networks still seem to provide the highest performances and we propose a visualization strategy to explain it.
Tasks	Language Modelling
Published	2018-11-27
URL	http://arxiv.org/abs/1811.10899v1
PDF	http://arxiv.org/pdf/1811.10899v1.pdf
PWC	https://paperswithcode.com/paper/are-2d-lstm-really-dead-for-offline-text
Repo
Framework