July 28, 2019

3143 words 15 mins read

Paper Group ANR 177

Existence versus Exploitation: The Opacity of Backbones and Backdoors Under a Weak Assumption. Lexical representation explains cortical entrainment during speech comprehension. Learning Neural Networks with Two Nonlinear Layers in Polynomial Time. Multi-Label Zero-Shot Human Action Recognition via Joint Latent Ranking Embedding. Concentration Bound …

Existence versus Exploitation: The Opacity of Backbones and Backdoors Under a Weak Assumption


Title	Existence versus Exploitation: The Opacity of Backbones and Backdoors Under a Weak Assumption
Authors	Lane A. Hemaspaandra, David E. Narváez
Abstract	Backdoors and backbones of Boolean formulas are hidden structural properties. A natural goal, already in part realized, is that solver algorithms seek to obtain substantially better performance by exploiting these structures. However, the present paper is not intended to improve the performance of SAT solvers, but rather is a cautionary paper. In particular, the theme of this paper is that there is a potential chasm between the existence of such structures in the Boolean formula and being able to effectively exploit them. This does not mean that these structures are not useful to solvers. It does mean that one must be very careful not to assume that it is computationally easy to go from the existence of a structure to being able to get one’s hands on it and/or being able to exploit the structure. For example, in this paper we show that, under the assumption that P $\neq$ NP, there are easily recognizable families of Boolean formulas with strong backdoors that are easy to find, yet for which it is hard (in fact, NP-complete) to determine whether the formulas are satisfiable. We also show that, also under the assumption P $\neq$ NP, there are easily recognizable sets of Boolean formulas for which it is hard (in fact, NP-complete) to determine whether they have a large backbone.
Tasks
Published	2017-06-14
URL	http://arxiv.org/abs/1706.04582v8
PDF	http://arxiv.org/pdf/1706.04582v8.pdf
PWC	https://paperswithcode.com/paper/existence-versus-exploitation-the-opacity-of
Repo
Framework

Lexical representation explains cortical entrainment during speech comprehension


Title	Lexical representation explains cortical entrainment during speech comprehension
Authors	Stefan Frank, Jinbiao Yang
Abstract	Results from a recent neuroimaging study on spoken sentence comprehension have been interpreted as evidence for cortical entrainment to hierarchical syntactic structure. We present a simple computational model that predicts the power spectra from this study, even though the model’s linguistic knowledge is restricted to the lexical level, and word-level representations are not combined into higher-level units (phrases or sentences). Hence, the cortical entrainment results can also be explained from the lexical properties of the stimuli, without recourse to hierarchical syntax.
Tasks
Published	2017-06-18
URL	http://arxiv.org/abs/1706.05656v6
PDF	http://arxiv.org/pdf/1706.05656v6.pdf
PWC	https://paperswithcode.com/paper/lexical-representation-explains-cortical
Repo
Framework

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time


Title	Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
Authors	Surbhi Goel, Adam Klivans
Abstract	We give a polynomial-time algorithm for learning neural networks with one layer of sigmoids feeding into any Lipschitz, monotone activation function (e.g., sigmoid or ReLU). We make no assumptions on the structure of the network, and the algorithm succeeds with respect to {\em any} distribution on the unit ball in $n$ dimensions (hidden weight vectors also have unit norm). This is the first assumption-free, provably efficient algorithm for learning neural networks with two nonlinear layers. Our algorithm– {\em Alphatron}– is a simple, iterative update rule that combines isotonic regression with kernel methods. It outputs a hypothesis that yields efficient oracle access to interpretable features. It also suggests a new approach to Boolean learning problems via real-valued conditional-mean functions, sidestepping traditional hardness results from computational learning theory. Along these lines, we subsume and improve many longstanding results for PAC learning Boolean functions to the more general, real-valued setting of {\em probabilistic concepts}, a model that (unlike PAC learning) requires non-i.i.d. noise-tolerance.
Tasks
Published	2017-09-18
URL	http://arxiv.org/abs/1709.06010v4
PDF	http://arxiv.org/pdf/1709.06010v4.pdf
PWC	https://paperswithcode.com/paper/learning-neural-networks-with-two-nonlinear
Repo
Framework

Multi-Label Zero-Shot Human Action Recognition via Joint Latent Ranking Embedding


Title	Multi-Label Zero-Shot Human Action Recognition via Joint Latent Ranking Embedding
Authors	Qian Wang, Ke Chen
Abstract	Human action recognition refers to automatic recognizing human actions from a video clip. In reality, there often exist multiple human actions in a video stream. Such a video stream is often weakly-annotated with a set of relevant human action labels at a global level rather than assigning each label to a specific video episode corresponding to a single action, which leads to a multi-label learning problem. Furthermore, there are many meaningful human actions in reality but it would be extremely difficult to collect/annotate video clips regarding all of various human actions, which leads to a zero-shot learning scenario. To the best of our knowledge, there is no work that has addressed all the above issues together in human action recognition. In this paper, we formulate a real-world human action recognition task as a multi-label zero-shot learning problem and propose a framework to tackle this problem in a holistic way. Our framework holistically tackles the issue of unknown temporal boundaries between different actions for multi-label learning and exploits the side information regarding the semantic relationship between different human actions for knowledge transfer. Consequently, our framework leads to a joint latent ranking embedding for multi-label zero-shot human action recognition. A novel neural architecture of two component models and an alternate learning algorithm are proposed to carry out the joint latent ranking embedding learning. Thus, multi-label zero-shot recognition is done by measuring relatedness scores of action labels to a test video clip in the joint latent visual and semantic embedding spaces. We evaluate our framework with different settings, including a novel data split scheme designed especially for evaluating multi-label zero-shot learning, on two datasets: Breakfast and Charades. The experimental results demonstrate the effectiveness of our framework.
Tasks	Multi-Label Learning, Temporal Action Localization, Transfer Learning, Zero-Shot Learning
Published	2017-09-15
URL	http://arxiv.org/abs/1709.05107v3
PDF	http://arxiv.org/pdf/1709.05107v3.pdf
PWC	https://paperswithcode.com/paper/multi-label-zero-shot-human-action
Repo
Framework

Concentration Bounds for High Sensitivity Functions Through Differential Privacy


Title	Concentration Bounds for High Sensitivity Functions Through Differential Privacy
Authors	Kobbi Nissim, Uri Stemmer
Abstract	A new line of work [Dwork et al. STOC 2015], [Hardt and Ullman FOCS 2014], [Steinke and Ullman COLT 2015], [Bassily et al. STOC 2016] demonstrates how differential privacy [Dwork et al. TCC 2006] can be used as a mathematical tool for guaranteeing generalization in adaptive data analysis. Specifically, if a differentially private analysis is applied on a sample S of i.i.d. examples to select a low-sensitivity function f, then w.h.p. f(S) is close to its expectation, although f is being chosen based on the data. Very recently, Steinke and Ullman observed that these generalization guarantees can be used for proving concentration bounds in the non-adaptive setting, where the low-sensitivity function is fixed beforehand. In particular, they obtain alternative proofs for classical concentration bounds for low-sensitivity functions, such as the Chernoff bound and McDiarmid’s Inequality. In this work, we set out to examine the situation for functions with high-sensitivity, for which differential privacy does not imply generalization guarantees under adaptive analysis. We show that differential privacy can be used to prove concentration bounds for such functions in the non-adaptive setting.
Tasks
Published	2017-03-06
URL	http://arxiv.org/abs/1703.01970v1
PDF	http://arxiv.org/pdf/1703.01970v1.pdf
PWC	https://paperswithcode.com/paper/concentration-bounds-for-high-sensitivity
Repo
Framework

FontCode: Embedding Information in Text Documents using Glyph Perturbation


Title	FontCode: Embedding Information in Text Documents using Glyph Perturbation
Authors	Chang Xiao, Cheng Zhang, Changxi Zheng
Abstract	We introduce FontCode, an information embedding technique for text documents. Provided a text document with specific fonts, our method embeds user-specified information in the text by perturbing the glyphs of text characters while preserving the text content. We devise an algorithm to chooses unobtrusive yet machine-recognizable glyph perturbations, leveraging a recently developed generative model that alters the glyphs of each character continuously on a font manifold. We then introduce an algorithm that embeds a user-provided message in the text document and produces an encoded document whose appearance is minimally perturbed from the original document. We also present a glyph recognition method that recovers the embedded information from an encoded document stored as a vector graphic or pixel image, or even on a printed paper. In addition, we introduce a new error-correction coding scheme that rectifies a certain number of recognition errors. Lastly, we demonstrate that our technique enables a wide array of applications, using it as a text document metadata holder, an unobtrusive optical barcode, a cryptographic message embedding scheme, and a text document signature.
Tasks
Published	2017-07-28
URL	http://arxiv.org/abs/1707.09418v1
PDF	http://arxiv.org/pdf/1707.09418v1.pdf
PWC	https://paperswithcode.com/paper/fontcode-embedding-information-in-text
Repo
Framework

RUBER: An Unsupervised Method for Automatic Evaluation of Open-Domain Dialog Systems


Title	RUBER: An Unsupervised Method for Automatic Evaluation of Open-Domain Dialog Systems
Authors	Chongyang Tao, Lili Mou, Dongyan Zhao, Rui Yan
Abstract	Open-domain human-computer conversation has been attracting increasing attention over the past few years. However, there does not exist a standard automatic evaluation metric for open-domain dialog systems; researchers usually resort to human annotation for model evaluation, which is time- and labor-intensive. In this paper, we propose RUBER, a Referenced metric and Unreferenced metric Blended Evaluation Routine, which evaluates a reply by taking into consideration both a groundtruth reply and a query (previous user-issued utterance). Our metric is learnable, but its training does not require labels of human satisfaction. Hence, RUBER is flexible and extensible to different datasets and languages. Experiments on both retrieval and generative dialog systems show that RUBER has a high correlation with human annotation.
Tasks
Published	2017-01-11
URL	http://arxiv.org/abs/1701.03079v2
PDF	http://arxiv.org/pdf/1701.03079v2.pdf
PWC	https://paperswithcode.com/paper/ruber-an-unsupervised-method-for-automatic
Repo
Framework

Convolutional Neural Knowledge Graph Learning


Title	Convolutional Neural Knowledge Graph Learning
Authors	Feipeng Zhao, Martin Renqiang Min, Chen Shen, Amit Chakraborty
Abstract	Previous models for learning entity and relationship embeddings of knowledge graphs such as TransE, TransH, and TransR aim to explore new links based on learned representations. However, these models interpret relationships as simple translations on entity embeddings. In this paper, we try to learn more complex connections between entities and relationships. In particular, we use a Convolutional Neural Network (CNN) to learn entity and relationship representations in knowledge graphs. In our model, we treat entities and relationships as one-dimensional numerical sequences with the same length. After that, we combine each triplet of head, relationship, and tail together as a matrix with height 3. CNN is applied to the triplets to get confidence scores. Positive and manually corrupted negative triplets are used to train the embeddings and the CNN model simultaneously. Experimental results on public benchmark datasets show that the proposed model outperforms state-of-the-art models on exploring unseen relationships, which proves that CNN is effective to learn complex interactive patterns between entities and relationships.
Tasks	Entity Embeddings, Knowledge Graphs
Published	2017-10-23
URL	http://arxiv.org/abs/1710.08502v2
PDF	http://arxiv.org/pdf/1710.08502v2.pdf
PWC	https://paperswithcode.com/paper/convolutional-neural-knowledge-graph-learning
Repo
Framework

Long-Term Evolution of Genetic Programming Populations


Title	Long-Term Evolution of Genetic Programming Populations
Authors	W. B. Langdon
Abstract	We evolve binary mux-6 trees for up to 100000 generations evolving some programs with more than a hundred million nodes. Our unbounded Long-Term Evolution Experiment LTEE GP appears not to evolve building blocks but does suggests a limit to bloat. We do see periods of tens even hundreds of generations where the population is 100 percent functionally converged. The distribution of tree sizes is not as predicted by theory.
Tasks
Published	2017-03-24
URL	http://arxiv.org/abs/1703.08481v1
PDF	http://arxiv.org/pdf/1703.08481v1.pdf
PWC	https://paperswithcode.com/paper/long-term-evolution-of-genetic-programming
Repo
Framework

Predictive Learning: Using Future Representation Learning Variantial Autoencoder for Human Action Prediction


Title	Predictive Learning: Using Future Representation Learning Variantial Autoencoder for Human Action Prediction
Authors	Yu Runsheng, Shi Zhenyu, Ma Qiongxiong, Qing Laiyun
Abstract	The unsupervised Pretraining method has been widely used in aiding human action recognition. However, existing methods focus on reconstructing the already present frames rather than generating frames which happen in future.In this paper, We propose an improved Variantial Autoencoder model to extract the features with a high connection to the coming scenarios, also known as Predictive Learning. Our framework lists as following: two steam 3D-convolution neural networks are used to extract both spatial and temporal information as latent variables. Then a resample method is introduced to create new normal distribution probabilistic latent variables and finally, the deconvolution neural network will use these latent variables generate next frames. Through this possess, we train the model to focus more on how to generate the future and thus it will extract the future high connected features. In the experiment stage, A large number of experiments on UT and UCF101 datasets reveal that future generation aids Prediction does improve the performance. Moreover, the Future Representation Learning Network reach a higher score than other methods when in half observation. This means that Future Representation Learning is better than the traditional Representation Learning and other state- of-the-art methods in solving the human action prediction problems to some extends.
Tasks	Representation Learning, Temporal Action Localization
Published	2017-11-25
URL	http://arxiv.org/abs/1711.09265v2
PDF	http://arxiv.org/pdf/1711.09265v2.pdf
PWC	https://paperswithcode.com/paper/predictive-learning-using-future
Repo
Framework

Exploring the Syntactic Abilities of RNNs with Multi-task Learning


Title	Exploring the Syntactic Abilities of RNNs with Multi-task Learning
Authors	Emile Enguehard, Yoav Goldberg, Tal Linzen
Abstract	Recent work has explored the syntactic abilities of RNNs using the subject-verb agreement task, which diagnoses sensitivity to sentence structure. RNNs performed this task well in common cases, but faltered in complex sentences (Linzen et al., 2016). We test whether these errors are due to inherent limitations of the architecture or to the relatively indirect supervision provided by most agreement dependencies in a corpus. We trained a single RNN to perform both the agreement task and an additional task, either CCG supertagging or language modeling. Multi-task training led to significantly lower error rates, in particular on complex sentences, suggesting that RNNs have the ability to evolve more sophisticated syntactic representations than shown before. We also show that easily available agreement training data can improve performance on other syntactic tasks, in particular when only a limited amount of training data is available for those tasks. The multi-task paradigm can also be leveraged to inject grammatical knowledge into language models.
Tasks	CCG Supertagging, Language Modelling, Multi-Task Learning
Published	2017-06-12
URL	http://arxiv.org/abs/1706.03542v1
PDF	http://arxiv.org/pdf/1706.03542v1.pdf
PWC	https://paperswithcode.com/paper/exploring-the-syntactic-abilities-of-rnns
Repo
Framework

Self-Paced Multitask Learning with Shared Knowledge


Title	Self-Paced Multitask Learning with Shared Knowledge
Authors	Keerthiram Murugesan, Jaime Carbonell
Abstract	This paper introduces self-paced task selection to multitask learning, where instances from more closely related tasks are selected in a progression of easier-to-harder tasks, to emulate an effective human education strategy, but applied to multitask machine learning. We develop the mathematical foundation for the approach based on iterative selection of the most appropriate task, learning the task parameters, and updating the shared knowledge, optimizing a new bi-convex loss function. This proposed method applies quite generally, including to multitask feature learning, multitask learning with alternating structure optimization, etc. Results show that in each of the above formulations self-paced (easier-to-harder) task selection outperforms the baseline version of these methods in all the experiments.
Tasks
Published	2017-03-02
URL	http://arxiv.org/abs/1703.00977v2
PDF	http://arxiv.org/pdf/1703.00977v2.pdf
PWC	https://paperswithcode.com/paper/self-paced-multitask-learning-with-shared
Repo
Framework

Discovering conversational topics and emotions associated with Demonetization tweets in India


Title	Discovering conversational topics and emotions associated with Demonetization tweets in India
Authors	Mitodru Niyogi, Asim K. Pal
Abstract	Social media platforms contain great wealth of information which provides us opportunities explore hidden patterns or unknown correlations, and understand people’s satisfaction with what they are discussing. As one showcase, in this paper, we summarize the data set of Twitter messages related to recent demonetization of all Rs. 500 and Rs. 1000 notes in India and explore insights from Twitter’s data. Our proposed system automatically extracts the popular latent topics in conversations regarding demonetization discussed in Twitter via the Latent Dirichlet Allocation (LDA) based topic model and also identifies the correlated topics across different categories. Additionally, it also discovers people’s opinions expressed through their tweets related to the event under consideration via the emotion analyzer. The system also employs an intuitive and informative visualization to show the uncovered insight. Furthermore, we use an evaluation measure, Normalized Mutual Information (NMI), to select the best LDA models. The obtained LDA results show that the tool can be effectively used to extract discussion topics and summarize them for further manual analysis.
Tasks
Published	2017-11-11
URL	http://arxiv.org/abs/1711.04115v1
PDF	http://arxiv.org/pdf/1711.04115v1.pdf
PWC	https://paperswithcode.com/paper/discovering-conversational-topics-and
Repo
Framework

Finite Sample Analyses for TD(0) with Function Approximation


Title	Finite Sample Analyses for TD(0) with Function Approximation
Authors	Gal Dalal, Balázs Szörényi, Gugan Thoppe, Shie Mannor
Abstract	TD(0) is one of the most commonly used algorithms in reinforcement learning. Despite this, there is no existing finite sample analysis for TD(0) with function approximation, even for the linear case. Our work is the first to provide such results. Existing convergence rates for Temporal Difference (TD) methods apply only to somewhat modified versions, e.g., projected variants or ones where stepsizes depend on unknown problem parameters. Our analyses obviate these artificial alterations by exploiting strong properties of TD(0). We provide convergence rates both in expectation and with high-probability. The two are obtained via different approaches that use relatively unknown, recently developed stochastic approximation techniques.
Tasks
Published	2017-04-04
URL	http://arxiv.org/abs/1704.01161v4
PDF	http://arxiv.org/pdf/1704.01161v4.pdf
PWC	https://paperswithcode.com/paper/finite-sample-analyses-for-td0-with-function
Repo
Framework

A 3D fully convolutional neural network and a random walker to segment the esophagus in CT


Title	A 3D fully convolutional neural network and a random walker to segment the esophagus in CT
Authors	Tobias Fechter, Sonja Adebahr, Dimos Baltas, Ismail Ben Ayed, Christian Desrosiers, Jose Dolz
Abstract	Precise delineation of organs at risk (OAR) is a crucial task in radiotherapy treatment planning, which aims at delivering high dose to the tumour while sparing healthy tissues. In recent years algorithms showed high performance and the possibility to automate this task for many OAR. However, for some OAR precise delineation remains challenging. The esophagus with a versatile shape and poor contrast is among these structures. To tackle these issues we propose a 3D fully (convolutional neural network (CNN) driven random walk (RW) approach to automatically segment the esophagus on CT. First, a soft probability map is generated by the CNN. Then an active contour model (ACM) is fitted on the probability map to get a first estimation of the center line. The outputs of the CNN and ACM are then used in addition to CT Hounsfield values to drive the RW. Evaluation and training was done on 50 CTs with peer reviewed esophagus contours. Results were assessed regarding spatial overlap and shape similarities. The generated contours showed a mean Dice coefficient of 0.76, an average symmetric square distance of 1.36 mm and an average Hausdorff distance of 11.68 compared to the reference. These figures translate into a very good agreement with the reference contours and an increase in accuracy compared to other methods. We show that by employing a CNN accurate estimations of esophagus location can be obtained and refined by a post processing RW step. One of the main advantages compared to previous methods is that our network performs convolutions in a 3D manner, fully exploiting the 3D spatial context and performing an efficient and precise volume-wise prediction. The whole segmentation process is fully automatic and yields esophagus delineations in very good agreement with the used gold standard, showing that it can compete with previously published methods.
Tasks
Published	2017-04-21
URL	http://arxiv.org/abs/1704.06544v1
PDF	http://arxiv.org/pdf/1704.06544v1.pdf
PWC	https://paperswithcode.com/paper/a-3d-fully-convolutional-neural-network-and-a
Repo
Framework