January 29, 2020

3027 words 15 mins read

Paper Group ANR 605

Rates of Convergence for Large-scale Nearest Neighbor Classification. Direct Quantification for Coronary Artery Stenosis Using Multiview Learning. Preference rules for label ranking: Mining patterns in multi-target relations. NeuType: A Simple and Effective Neural Network Approach for Predicting Missing Entity Type Information in Knowledge Bases. I …

Rates of Convergence for Large-scale Nearest Neighbor Classification


Title	Rates of Convergence for Large-scale Nearest Neighbor Classification
Authors	Xingye Qiao, Jiexin Duan, Guang Cheng
Abstract	Nearest neighbor is a popular class of classification methods with many desirable properties. For a large data set which cannot be loaded into the memory of a single machine due to computation, communication, privacy, or ownership limitations, we consider the divide and conquer scheme: the entire data set is divided into small subsamples, on which nearest neighbor predictions are made, and then a final decision is reached by aggregating the predictions on subsamples by majority voting. We name this method the big Nearest Neighbor (bigNN) classifier, and provide its rates of convergence under minimal assumptions, in terms of both the excess risk and the classification instability, which are proven to be the same rates as the oracle nearest neighbor classifier and cannot be improved. To significantly reduce the prediction time that is required for achieving the optimal rate, we also consider the pre-training acceleration technique applied to the bigNN method, with proven convergence rate. We find that in the distributed setting, the optimal choice of the neighbor $k$ should scale with both the total sample size and the number of partitions, and there is a theoretical upper limit for the latter. Numerical studies have verified the theoretical findings.
Tasks
Published	2019-09-03
URL	https://arxiv.org/abs/1909.01464v2
PDF	https://arxiv.org/pdf/1909.01464v2.pdf
PWC	https://paperswithcode.com/paper/rates-of-convergence-for-large-scale-nearest
Repo
Framework

Direct Quantification for Coronary Artery Stenosis Using Multiview Learning


Title	Direct Quantification for Coronary Artery Stenosis Using Multiview Learning
Authors	Dong Zhang, Guang Yang, Shu Zhao, Yanping Zhang, Heye Zhang, Shuo Li
Abstract	The quantification of the coronary artery stenosis is of significant clinical importance in coronary artery disease diagnosis and intervention treatment. It aims to quantify the morphological indices of the coronary artery lesions such as minimum lumen diameter, reference vessel diameter, lesion length, and these indices are the reference of the interventional stent placement. In this study, we propose a direct multiview quantitative coronary angiography (DMQCA) model as an automatic clinical tool to quantify the coronary artery stenosis from X-ray coronary angiography images. The proposed DMQCA model consists of a multiview module with two attention mechanisms, a key-frame module, and a regression module, to achieve direct accurate multiple-index estimation. The multi-view module comprehensively learns the Spatio-temporal features of coronary arteries through a three-dimensional convolution. The attention mechanisms of each view focus on the subtle feature of the lesion region and capture the important context information. The key-frame module learns the subtle features of the stenosis through successive dilated residual blocks. The regression module finally generates the indices estimation from multiple features.
Tasks	Multiview Learning
Published	2019-07-20
URL	https://arxiv.org/abs/1907.10032v2
PDF	https://arxiv.org/pdf/1907.10032v2.pdf
PWC	https://paperswithcode.com/paper/direct-quantification-for-coronary-artery
Repo
Framework

Preference rules for label ranking: Mining patterns in multi-target relations


Title	Preference rules for label ranking: Mining patterns in multi-target relations
Authors	Cláudio Rebelo de Sá, Paulo Azevedo, Carlos Soares, Alípio Mário Jorge, Arno Knobbe
Abstract	In this paper we investigate two variants of association rules for preference data, Label Ranking Association Rules and Pairwise Association Rules. Label Ranking Association Rules (LRAR) are the equivalent of Class Association Rules (CAR) for the Label Ranking task. In CAR, the consequent is a single class, to which the example is expected to belong to. In LRAR, the consequent is a ranking of the labels. The generation of LRAR requires special support and confidence measures to assess the similarity of rankings. In this work, we carry out a sensitivity analysis of these similarity-based measures. We want to understand which datasets benefit more from such measures and which parameters have more influence in the accuracy of the model. Furthermore, we propose an alternative type of rules, the Pairwise Association Rules (PAR), which are defined as association rules with a set of pairwise preferences in the consequent. While PAR can be used both as descriptive and predictive models, they are essentially descriptive models. Experimental results show the potential of both approaches.
Tasks
Published	2019-03-20
URL	http://arxiv.org/abs/1903.08504v1
PDF	http://arxiv.org/pdf/1903.08504v1.pdf
PWC	https://paperswithcode.com/paper/preference-rules-for-label-ranking-mining
Repo
Framework

NeuType: A Simple and Effective Neural Network Approach for Predicting Missing Entity Type Information in Knowledge Bases


Title	NeuType: A Simple and Effective Neural Network Approach for Predicting Missing Entity Type Information in Knowledge Bases
Authors	Jon Arne Bø Hovda, Darío Garigliotti, Krisztian Balog
Abstract	Knowledge bases store information about the semantic types of entities, which can be utilized in a range of information access tasks. This information, however, is often incomplete, due to new entities emerging on a daily basis. We address the task of automatically assigning types to entities in a knowledge base from a type taxonomy. Specifically, we present two neural network architectures, which take short entity descriptions and, optionally, information about related entities as input. Using the DBpedia knowledge base for experimental evaluation, we demonstrate that these simple architectures yield significant improvements over the current state of the art.
Tasks
Published	2019-07-05
URL	https://arxiv.org/abs/1907.03007v1
PDF	https://arxiv.org/pdf/1907.03007v1.pdf
PWC	https://paperswithcode.com/paper/neutype-a-simple-and-effective-neural-network
Repo
Framework

Improving Question Generation with Sentence-level Semantic Matching and Answer Position Inferring


Title	Improving Question Generation with Sentence-level Semantic Matching and Answer Position Inferring
Authors	Xiyao Ma, Qile Zhu, Yanlin Zhou, Xiaolin Li, Dapeng Wu
Abstract	Taking an answer and its context as input, sequence-to-sequence models have made considerable progress on question generation. However, we observe that these approaches often generate wrong question words or keywords and copy answer-irrelevant words from the input. We believe that lacking global question semantics and exploiting answer position-awareness not well are the key root causes. In this paper, we propose a neural question generation model with two concrete modules: sentence-level semantic matching and answer position inferring. Further, we enhance the initial state of the decoder by leveraging the answer-aware gated fusion mechanism. Experimental results demonstrate that our model outperforms the state-of-the-art (SOTA) models on SQuAD and MARCO datasets. Owing to its generality, our work also improves the existing models significantly.
Tasks	Question Generation
Published	2019-12-02
URL	https://arxiv.org/abs/1912.00879v3
PDF	https://arxiv.org/pdf/1912.00879v3.pdf
PWC	https://paperswithcode.com/paper/improving-question-generation-with-sentence
Repo
Framework

VLSI Mask Optimization: From Shallow To Deep Learning


Title	VLSI Mask Optimization: From Shallow To Deep Learning
Authors	Haoyu Yang, Wei Zhong, Yuzhe Ma, Hao Geng, Ran Chen, Wanli Chen, Bei Yu
Abstract	VLSI mask optimization is one of the most critical stages in manufacturability aware design, which is costly due to the complicated mask optimization and lithography simulation. Recent researches have shown prominent advantages of machine learning techniques dealing with complicated and big data problems, which bring potential of dedicated machine learning solution for DFM problems and facilitate the VLSI design cycle. In this paper, we focus on a heterogeneous OPC framework that assists mask layout optimization. Preliminary results show the efficiency and effectiveness of proposed frameworks that have the potential to be alternatives to existing EDA solutions.
Tasks
Published	2019-12-16
URL	https://arxiv.org/abs/1912.07254v1
PDF	https://arxiv.org/pdf/1912.07254v1.pdf
PWC	https://paperswithcode.com/paper/vlsi-mask-optimization-from-shallow-to-deep
Repo
Framework

Multi-Task Semantic Dependency Parsing with Policy Gradient for Learning Easy-First Strategies


Title	Multi-Task Semantic Dependency Parsing with Policy Gradient for Learning Easy-First Strategies
Authors	Shuhei Kurita, Anders Søgaard
Abstract	In Semantic Dependency Parsing (SDP), semantic relations form directed acyclic graphs, rather than trees. We propose a new iterative predicate selection (IPS) algorithm for SDP. Our IPS algorithm combines the graph-based and transition-based parsing approaches in order to handle multiple semantic head words. We train the IPS model using a combination of multi-task learning and task-specific policy gradient training. Trained this way, IPS achieves a new state of the art on the SemEval 2015 Task 18 datasets. Furthermore, we observe that policy gradient training learns an easy-first strategy.
Tasks	Dependency Parsing, Multi-Task Learning, Semantic Dependency Parsing
Published	2019-06-04
URL	https://arxiv.org/abs/1906.01239v1
PDF	https://arxiv.org/pdf/1906.01239v1.pdf
PWC	https://paperswithcode.com/paper/multi-task-semantic-dependency-parsing-with
Repo
Framework

Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning


Title	Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning
Authors	Jian Wu, Saul Toscano-Palmerin, Peter I. Frazier, Andrew Gordon Wilson
Abstract	Bayesian optimization is popular for optimizing time-consuming black-box objectives. Nonetheless, for hyperparameter tuning in deep neural networks, the time required to evaluate the validation error for even a few hyperparameter settings remains a bottleneck. Multi-fidelity optimization promises relief using cheaper proxies to such objectives — for example, validation error for a network trained using a subset of the training points or fewer iterations than required for convergence. We propose a highly flexible and practical approach to multi-fidelity Bayesian optimization, focused on efficiently optimizing hyperparameters for iteratively trained supervised learning models. We introduce a new acquisition function, the trace-aware knowledge-gradient, which efficiently leverages both multiple continuous fidelity controls and trace observations — values of the objective at a sequence of fidelities, available when varying fidelity using training iterations. We provide a provably convergent method for optimizing our acquisition function and show it outperforms state-of-the-art alternatives for hyperparameter tuning of deep neural networks and large-scale kernel learning.
Tasks
Published	2019-03-12
URL	http://arxiv.org/abs/1903.04703v1
PDF	http://arxiv.org/pdf/1903.04703v1.pdf
PWC	https://paperswithcode.com/paper/practical-multi-fidelity-bayesian
Repo
Framework

Geometric Losses for Distributional Learning


Title	Geometric Losses for Distributional Learning
Authors	Arthur Mensch, Mathieu Blondel, Gabriel Peyré
Abstract	Building upon recent advances in entropy-regularized optimal transport, and upon Fenchel duality between measures and continuous functions , we propose a generalization of the logistic loss that incorporates a metric or cost between classes. Unlike previous attempts to use optimal transport distances for learning, our loss results in unconstrained convex objective functions, supports infinite (or very large) class spaces, and naturally defines a geometric generalization of the softmax operator. The geometric properties of this loss make it suitable for predicting sparse and singular distributions, for instance supported on curves or hyper-surfaces. We study the theoretical properties of our loss and show-case its effectiveness on two applications: ordinal regression and drawing generation.
Tasks
Published	2019-05-15
URL	https://arxiv.org/abs/1905.06005v1
PDF	https://arxiv.org/pdf/1905.06005v1.pdf
PWC	https://paperswithcode.com/paper/geometric-losses-for-distributional-learning
Repo
Framework

Sparse-Dense Subspace Clustering


Title	Sparse-Dense Subspace Clustering
Authors	Shuai Yang, Wenqi Zhu, Yuesheng Zhu
Abstract	Subspace clustering refers to the problem of clustering high-dimensional data into a union of low-dimensional subspaces. Current subspace clustering approaches are usually based on a two-stage framework. In the first stage, an affinity matrix is generated from data. In the second one, spectral clustering is applied on the affinity matrix. However, the affinity matrix produced by two-stage methods cannot fully reveal the similarity between data points from the same subspace (intra-subspace similarity), resulting in inaccurate clustering. Besides, most approaches fail to solve large-scale clustering problems due to poor efficiency. In this paper, we first propose a new scalable sparse method called Iterative Maximum Correlation (IMC) to learn the affinity matrix from data. Then we develop Piecewise Correlation Estimation (PCE) to densify the intra-subspace similarity produced by IMC. Finally we extend our work into a Sparse-Dense Subspace Clustering (SDSC) framework with a dense stage to optimize the affinity matrix for two-stage methods. We show that IMC is efficient when clustering large-scale data, and PCE ensures better performance for IMC. We show the universality of our SDSC framework as well. Experiments on several data sets demonstrate the effectiveness of our approaches. Moreover, we are the first one to apply densification on affinity matrix before spectral clustering, and SDSC constitutes the first attempt to build a universal three-stage subspace clustering framework.
Tasks
Published	2019-10-20
URL	https://arxiv.org/abs/1910.08909v1
PDF	https://arxiv.org/pdf/1910.08909v1.pdf
PWC	https://paperswithcode.com/paper/sparse-dense-subspace-clustering
Repo
Framework

Computer Vision-based Accident Detection in Traffic Surveillance


Title	Computer Vision-based Accident Detection in Traffic Surveillance
Authors	Earnest Paul Ijjina, Dhananjai Chand, Savyasachi Gupta, Goutham K
Abstract	Computer vision-based accident detection through video surveillance has become a beneficial but daunting task. In this paper, a neoteric framework for detection of road accidents is proposed. The proposed framework capitalizes on Mask R-CNN for accurate object detection followed by an efficient centroid based object tracking algorithm for surveillance footage. The probability of an accident is determined based on speed and trajectory anomalies in a vehicle after an overlap with other vehicles. The proposed framework provides a robust method to achieve a high Detection Rate and a low False Alarm Rate on general road-traffic CCTV surveillance footage. This framework was evaluated on diverse conditions such as broad daylight, low visibility, rain, hail, and snow using the proposed dataset. This framework was found effective and paves the way to the development of general-purpose vehicular accident detection algorithms in real-time.
Tasks	Object Detection, Object Tracking
Published	2019-11-22
URL	https://arxiv.org/abs/1911.10037v1
PDF	https://arxiv.org/pdf/1911.10037v1.pdf
PWC	https://paperswithcode.com/paper/computer-vision-based-accident-detection-in
Repo
Framework

Fast And Efficient Boolean Matrix Factorization By Geometric Segmentation


Title	Fast And Efficient Boolean Matrix Factorization By Geometric Segmentation
Authors	Changlin Wan, Wennan Chang, Tong Zhao, Mengya Li, Sha Cao, Chi Zhang
Abstract	Boolean matrix has been used to represent digital information in many fields, including bank transaction, crime records, natural language processing, protein-protein interaction, etc. Boolean matrix factorization (BMF) aims to find an approximation of a binary matrix as the Boolean product of two low rank Boolean matrices, which could generate vast amount of information for the patterns of relationships between the features and samples. Inspired by binary matrix permutation theories and geometric segmentation, we developed a fast and efficient BMF approach called MEBF (Median Expansion for Boolean Factorization). Overall, MEBF adopted a heuristic approach to locate binary patterns presented as submatrices that are dense in 1’s. At each iteration, MEBF permutates the rows and columns such that the permutated matrix is approximately Upper Triangular-Like (UTL) with so-called Simultaneous Consecutive-ones Property (SC1P). The largest submatrix dense in 1 would lies on the upper triangular area of the permutated matrix, and its location was determined based on a geometric segmentation of a triangular. We compared MEBF with other state of the art approaches on data scenarios with different sparsity and noise levels. MEBF demonstrated superior performances in lower reconstruction error, and higher computational efficiency, as well as more accurate sparse patterns than popular methods such as ASSO, PANDA and MP. We demonstrated the application of MEBF on both binary and non-binary data sets, and revealed its further potential in knowledge retrieving and data denoising.
Tasks	Denoising
Published	2019-09-09
URL	https://arxiv.org/abs/1909.03991v2
PDF	https://arxiv.org/pdf/1909.03991v2.pdf
PWC	https://paperswithcode.com/paper/mebf-a-fast-and-efficient-boolean-matrix
Repo
Framework

A New Approach to Adaptive Data Analysis and Learning via Maximal Leakage


Title	A New Approach to Adaptive Data Analysis and Learning via Maximal Leakage
Authors	Amedeo Roberto Esposito, Michael Gastpar, Ibrahim Issa
Abstract	There is an increasing concern that most current published research findings are false. The main cause seems to lie in the fundamental disconnection between theory and practice in data analysis. While the former typically relies on statistical independence, the latter is an inherently adaptive process: new hypotheses are formulated based on the outcomes of previous analyses. A recent line of work tries to mitigate these issues by enforcing constraints, such as differential privacy, that compose adaptively while degrading gracefully and thus provide statistical guarantees even in adaptive contexts. Our contribution consists in the introduction of a new approach, based on the concept of Maximal Leakage, an information-theoretic measure of leakage of information. The main result allows us to compare the probability of an event happening when adaptivity is considered with respect to the non-adaptive scenario. The bound we derive represents a generalization of the bounds used in non-adaptive scenarios (e.g., McDiarmid’s inequality for $c$-sensitive functions, false discovery error control via significance level, etc.), and allows us to replicate or even improve, in certain regimes, the results obtained using Max-Information or Differential Privacy. In contrast with the line of work started by Dwork et al., our results do not rely on Differential Privacy but are, in principle, applicable to every algorithm that has a bounded leakage, including the differentially private algorithms and the ones with a short description length.
Tasks
Published	2019-03-05
URL	http://arxiv.org/abs/1903.01777v1
PDF	http://arxiv.org/pdf/1903.01777v1.pdf
PWC	https://paperswithcode.com/paper/a-new-approach-to-adaptive-data-analysis-and
Repo
Framework

A Large-Scale Multi-Length Headline Corpus for Analyzing Length-Constrained Headline Generation Model Evaluation


Title	A Large-Scale Multi-Length Headline Corpus for Analyzing Length-Constrained Headline Generation Model Evaluation
Authors	Yuta Hitomi, Yuya Taguchi, Hideaki Tamori, Ko Kikuta, Jiro Nishitoba, Naoaki Okazaki, Kentaro Inui, Manabu Okumura
Abstract	Browsing news articles on multiple devices is now possible. The lengths of news article headlines have precise upper bounds, dictated by the size of the display of the relevant device or interface. Therefore, controlling the length of headlines is essential when applying the task of headline generation to news production. However, because there is no corpus of headlines of multiple lengths for a given article, previous research on controlling output length in headline generation has not discussed whether the system outputs could be adequately evaluated without multiple references of different lengths. In this paper, we introduce two corpora, which are Japanese News Corpus (JNC) and JApanese MUlti-Length Headline Corpus (JAMUL), to confirm the validity of previous evaluation settings. The JNC provides common supervision data for headline generation. The JAMUL is a large-scale evaluation dataset for headlines of three different lengths composed by professional editors. We report new findings on these corpora; for example, although the longest length reference summary can appropriately evaluate the existing methods controlling output length, this evaluation setting has several problems.
Tasks
Published	2019-03-28
URL	https://arxiv.org/abs/1903.11771v4
PDF	https://arxiv.org/pdf/1903.11771v4.pdf
PWC	https://paperswithcode.com/paper/a-large-scale-multi-length-headline-corpus
Repo
Framework

Prototype-based classifiers in the presence of concept drift: A modelling framework


Title	Prototype-based classifiers in the presence of concept drift: A modelling framework
Authors	Michael Biehl, Fthi Abadi, Christina Göpfert, Barbara Hammer
Abstract	We present a modelling framework for the investigation of prototype-based classifiers in non-stationary environments. Specifically, we study Learning Vector Quantization (LVQ) systems trained from a stream of high-dimensional, clustered data.We consider standard winner-takes-all updates known as LVQ1. Statistical properties of the input data change on the time scale defined by the training process. We apply analytical methods borrowed from statistical physics which have been used earlier for the exact description of learning in stationary environments. The suggested framework facilitates the computation of learning curves in the presence of virtual and real concept drift. Here we focus on timedependent class bias in the training data. First results demonstrate that, while basic LVQ algorithms are suitable for the training in non-stationary environments, weight decay as an explicit mechanism of forgetting does not improve the performance under the considered drift processes.
Tasks	Quantization
Published	2019-03-18
URL	http://arxiv.org/abs/1903.07273v1
PDF	http://arxiv.org/pdf/1903.07273v1.pdf
PWC	https://paperswithcode.com/paper/prototype-based-classifiers-in-the-presence
Repo
Framework