January 27, 2020

3211 words 16 mins read

Paper Group ANR 1114

Complexity-entropy analysis at different levels of organization in written language. Quantum algorithms for Second-Order Cone Programming and Support Vector Machines. Congestion Analysis of Convolutional Neural Network-Based Pedestrian Counting Methods on Helicopter Footage. Evaluating Bregman Divergences for Probability Learning from Crowd. Mono3D …

Complexity-entropy analysis at different levels of organization in written language


Title	Complexity-entropy analysis at different levels of organization in written language
Authors	E. Estevez-Rams, A. Mesa Rodriguez, D. Estevez-Moya
Abstract	Written language is complex. A written text can be considered an attempt to convey a meaningful message which ends up being constrained by language rules, context dependence and highly redundant in its use of resources. Despite all these constraints, unpredictability is an essential element of natural language. Here we present the use of entropic measures to assert the balance between predictability and surprise in written text. In short, it is possible to measure innovation and context preservation in a document. It is shown that this can also be done at the different levels of organization of a text. The type of analysis presented is reasonably general, and can also be used to analyze the same balance in other complex messages such as DNA, where a hierarchy of organizational levels are known to exist.
Tasks
Published	2019-03-14
URL	http://arxiv.org/abs/1903.07416v1
PDF	http://arxiv.org/pdf/1903.07416v1.pdf
PWC	https://paperswithcode.com/paper/complexity-entropy-analysis-at-different
Repo
Framework

Quantum algorithms for Second-Order Cone Programming and Support Vector Machines


Title	Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
Authors	Iordanis Kerenidis, Anupam Prakash, Dániel Szilágyi
Abstract	Second order cone programs (SOCPs) are a class of structured convex optimization problems that generalize linear programs. We present a quantum algorithm for SOCPs based on a quantum variant of the interior point method. Our algorithm outputs a classical solution to the SOCP with objective value $\epsilon$ close to the optimal in time $\widetilde{O} \left( n\sqrt{r} \frac{\zeta \kappa}{\delta^2} \log \left(1/\epsilon\right) \right)$ where $r$ is the rank and $n$ the dimension of the SOCP, $\delta$ bounds the distance from strict feasibility for the intermediate solutions, $\zeta$ is a parameter bounded by $\sqrt{n}$, and $\kappa$ is an upper bound on the condition number of matrices arising in the classical interior point method for SOCPs. We present applications to the support vector machine (SVM) problem in machine learning that reduces to SOCPs. We provide experimental evidence that the quantum algorithm achieves an asymptotic speedup over classical SVM algorithms with a running time $\widetilde{O}(n^{2.557})$ for random SVM instances. The best known classical algorithms for such instances have complexity $\widetilde{O} \left( n^{\omega+0.5}\log(1/\epsilon) \right)$, where $\omega$ is the matrix multiplication exponent that has a theoretical value of around $2.373$, but is closer to $3$ in practice.
Tasks
Published	2019-08-19
URL	https://arxiv.org/abs/1908.06720v2
PDF	https://arxiv.org/pdf/1908.06720v2.pdf
PWC	https://paperswithcode.com/paper/quantum-algorithms-for-second-order-cone
Repo
Framework

Congestion Analysis of Convolutional Neural Network-Based Pedestrian Counting Methods on Helicopter Footage


Title	Congestion Analysis of Convolutional Neural Network-Based Pedestrian Counting Methods on Helicopter Footage
Authors	Gergely Csönde, Yoshihide Sekimoto, Takehiro Kashiyama
Abstract	Over the past few years, researchers have presented many different applications for convolutional neural networks, including those for the detection and recognition of objects from images. The desire to understand our own nature has always been an important motivation for research. Thus, the visual recognition of humans is among the most important issues facing machine learning today. Most solutions for this task have been developed and tested by using several publicly available datasets. These datasets typically contain images taken from street-level closed-circuit television cameras offering a low-angle view. There are major differences between such images and those taken from the sky. In addition, aerial images are often very congested, containing hundreds of targets. These factors may have significant impact on the quality of the results. In this paper, we investigate state-of-the-art methods for counting pedestrians and the related performance of aerial footage. Furthermore, we analyze this performance with respect to the congestion levels of the images.
Tasks
Published	2019-11-05
URL	https://arxiv.org/abs/1911.01672v1
PDF	https://arxiv.org/pdf/1911.01672v1.pdf
PWC	https://paperswithcode.com/paper/congestion-analysis-of-convolutional-neural
Repo
Framework

Evaluating Bregman Divergences for Probability Learning from Crowd


Title	Evaluating Bregman Divergences for Probability Learning from Crowd
Authors	F. A. Mena, R. Ñanculef
Abstract	The crowdsourcing scenarios are a good example of having a probability distribution over some categories showing what the people in a global perspective thinks. Learn a predictive model of this probability distribution can be of much more valuable that learn only a discriminative model that gives the most likely category of the data. Here we present differents models that adapts having probability distribution as target to train a machine learning model. We focus on the Bregman divergences framework to used as objective function to minimize. The results show that special care must be taken when build a objective function and consider a equal optimization on neural network in Keras framework.
Tasks
Published	2019-01-30
URL	http://arxiv.org/abs/1901.10653v1
PDF	http://arxiv.org/pdf/1901.10653v1.pdf
PWC	https://paperswithcode.com/paper/evaluating-bregman-divergences-for
Repo
Framework

Mono3D++: Monocular 3D Vehicle Detection with Two-Scale 3D Hypotheses and Task Priors


Title	Mono3D++: Monocular 3D Vehicle Detection with Two-Scale 3D Hypotheses and Task Priors
Authors	Tong He, Stefano Soatto
Abstract	We present a method to infer 3D pose and shape of vehicles from a single image. To tackle this ill-posed problem, we optimize two-scale projection consistency between the generated 3D hypotheses and their 2D pseudo-measurements. Specifically, we use a morphable wireframe model to generate a fine-scaled representation of vehicle shape and pose. To reduce its sensitivity to 2D landmarks, we jointly model the 3D bounding box as a coarse representation which improves robustness. We also integrate three task priors, including unsupervised monocular depth, a ground plane constraint as well as vehicle shape priors, with forward projection errors into an overall energy function.
Tasks
Published	2019-01-11
URL	http://arxiv.org/abs/1901.03446v1
PDF	http://arxiv.org/pdf/1901.03446v1.pdf
PWC	https://paperswithcode.com/paper/mono3d-monocular-3d-vehicle-detection-with
Repo
Framework

Exploring Auxiliary Context: Discrete Semantic Transfer Hashing for Scalable Image Retrieval


Title	Exploring Auxiliary Context: Discrete Semantic Transfer Hashing for Scalable Image Retrieval
Authors	Lei Zhu, Zi Huang, Zhihui Li, Liang Xie, Heng Tao Shen
Abstract	Unsupervised hashing can desirably support scalable content-based image retrieval (SCBIR) for its appealing advantages of semantic label independence, memory and search efficiency. However, the learned hash codes are embedded with limited discriminative semantics due to the intrinsic limitation of image representation. To address the problem, in this paper, we propose a novel hashing approach, dubbed as \emph{Discrete Semantic Transfer Hashing} (DSTH). The key idea is to \emph{directly} augment the semantics of discrete image hash codes by exploring auxiliary contextual modalities. To this end, a unified hashing framework is formulated to simultaneously preserve visual similarities of images and perform semantic transfer from contextual modalities. Further, to guarantee direct semantic transfer and avoid information loss, we explicitly impose the discrete constraint, bit–uncorrelation constraint and bit-balance constraint on hash codes. A novel and effective discrete optimization method based on augmented Lagrangian multiplier is developed to iteratively solve the optimization problem. The whole learning process has linear computation complexity and desirable scalability. Experiments on three benchmark datasets demonstrate the superiority of DSTH compared with several state-of-the-art approaches.
Tasks	Content-Based Image Retrieval, Image Retrieval
Published	2019-04-25
URL	http://arxiv.org/abs/1904.11207v1
PDF	http://arxiv.org/pdf/1904.11207v1.pdf
PWC	https://paperswithcode.com/paper/exploring-auxiliary-context-discrete-semantic
Repo
Framework

Pearson Distance is not a Distance


Title	Pearson Distance is not a Distance
Authors	Victor Solo
Abstract	The Pearson distance between a pair of random variables $X,Y$ with correlation $\rho_{xy}$, namely, 1-$\rho_{xy}$, has gained widespread use, particularly for clustering, in areas such as gene expression analysis, brain imaging and cyber security. In all these applications it is implicitly assumed/required that the distance measures be metrics, thus satisfying the triangle inequality. We show however, that Pearson distance is not a metric. We go on to show that this can be repaired by recalling the result, (well known in other literature) that $\sqrt{1-\rho_{xy}}$ is a metric. We similarly show that a related measure of interest, $1-\rho_{xy}$, which is invariant to the sign of $\rho_{xy}$, is not a metric but that $\sqrt{1-\rho_{xy}^2}$ is. We also give generalizations of these results.
Tasks
Published	2019-08-15
URL	https://arxiv.org/abs/1908.06029v1
PDF	https://arxiv.org/pdf/1908.06029v1.pdf
PWC	https://paperswithcode.com/paper/pearson-distance-is-not-a-distance
Repo
Framework

Feature Selection and Extraction for Graph Neural Networks


Title	Feature Selection and Extraction for Graph Neural Networks
Authors	Deepak Bhaskar Acharya, Dr. Huaming Zhang
Abstract	Graph Neural Networks (GNNs) have been a latest hot research topic in data science, due to the fact that they use the ubiquitous data structure graphs as the underlying elements for constructing and training neural networks. In a GNN, each node has numerous features associated with it. The entire task (for example, classification, or clustering) utilizes the features of the nodes to make decisions, at node level or graph level. In this paper, (1) we extend the feature selection algorithm presented in via Gumbel Softmax to GNNs. We conduct a series of experiments on our feature selection algorithms, using various benchmark datasets: Cora, Citeseer and Pubmed. (2) We implement a mechanism to rank the extracted features. We demonstrate the effectiveness of our algorithms, for both feature selection and ranking. For the Cora dataset, (1) we use the algorithm to select 225 features out of 1433 features. Our experimental results demonstrate their effectiveness for the same classification problem. (2) We extract features such that they are linear combinations of the original features, where the coefficients for each extracted features are non-negative and sum up to one. We propose an algorithm to rank the extracted features in the sense that when using them for the same classification problem, the accuracy goes down gradually for the extracted features within the rank 1 - 50, 51 - 100, 100 - 150, and 151 - 200.
Tasks	Feature Selection
Published	2019-10-23
URL	https://arxiv.org/abs/1910.10682v2
PDF	https://arxiv.org/pdf/1910.10682v2.pdf
PWC	https://paperswithcode.com/paper/feature-selection-and-extraction-for-graph
Repo
Framework

Anonymising Queries by Semantic Decomposition


Title	Anonymising Queries by Semantic Decomposition
Authors	Danushka Bollegala, Tomoya Machide, Ken-ichi Kawarabayashi
Abstract	Protecting the privacy of search engine users is an important requirement in many information retrieval scenarios. A user might not want a search engine to guess his or her information need despite requesting relevant results. We propose a method to protect the privacy of search engine users by decomposing the queries using semantically \emph{related} and unrelated \emph{distractor} terms. Instead of a single query, the search engine receives multiple decomposed query terms. Next, we reconstruct the search results relevant to the original query term by aggregating the search results retrieved for the decomposed query terms. We show that the word embeddings learnt using a distributed representation learning method can be used to find semantically related and distractor query terms. We derive the relationship between the \emph{anonymity} achieved through the proposed query anonymisation method and the \emph{reconstructability} of the original search results using the decomposed queries. We analytically study the risk of discovering the search engine users’ information intents under the proposed query anonymisation method, and empirically evaluate its robustness against clustering-based attacks. Our experimental results show that the proposed method can accurately reconstruct the search results for user queries, without compromising the privacy of the search engine users.
Tasks	Information Retrieval, Representation Learning, Word Embeddings
Published	2019-09-12
URL	https://arxiv.org/abs/1909.05819v1
PDF	https://arxiv.org/pdf/1909.05819v1.pdf
PWC	https://paperswithcode.com/paper/anonymising-queries-by-semantic-decomposition
Repo
Framework

Finding Needles in a Moving Haystack: Prioritizing Alerts with Adversarial Reinforcement Learning


Title	Finding Needles in a Moving Haystack: Prioritizing Alerts with Adversarial Reinforcement Learning
Authors	Liang Tong, Aron Laszka, Chao Yan, Ning Zhang, Yevgeniy Vorobeychik
Abstract	Detection of malicious behavior is a fundamental problem in security. One of the major challenges in using detection systems in practice is in dealing with an overwhelming number of alerts that are triggered by normal behavior (the so-called false positives), obscuring alerts resulting from actual malicious activity. While numerous methods for reducing the scope of this issue have been proposed, ultimately one must still decide how to prioritize which alerts to investigate, and most existing prioritization methods are heuristic, for example, based on suspiciousness or priority scores. We introduce a novel approach for computing a policy for prioritizing alerts using adversarial reinforcement learning. Our approach assumes that the attackers know the full state of the detection system and dynamically choose an optimal attack as a function of this state, as well as of the alert prioritization policy. The first step of our approach is to capture the interaction between the defender and attacker in a game theoretic model. To tackle the computational complexity of solving this game to obtain a dynamic stochastic alert prioritization policy, we propose an adversarial reinforcement learning framework. In this framework, we use neural reinforcement learning to compute best response policies for both the defender and the adversary to an arbitrary stochastic policy of the other. We then use these in a double-oracle framework to obtain an approximate equilibrium of the game, which in turn yields a robust stochastic policy for the defender. Extensive experiments using case studies in fraud and intrusion detection demonstrate that our approach is effective in creating robust alert prioritization policies.
Tasks	Intrusion Detection
Published	2019-06-20
URL	https://arxiv.org/abs/1906.08805v1
PDF	https://arxiv.org/pdf/1906.08805v1.pdf
PWC	https://paperswithcode.com/paper/finding-needles-in-a-moving-haystack
Repo
Framework

DeepMUSIC: Multiple Signal Classification via Deep Learning


Title	DeepMUSIC: Multiple Signal Classification via Deep Learning
Authors	Ahmet M. Elbir
Abstract	This letter introduces a deep learning (DL) framework for direction-of-arrival (DOA) estimation. Previous works in DL context mostly consider a single or two target scenario which is a strong limitation in practice. Hence, in this work, we propose a DL framework for multiple signal classification (DeepMUSIC). We design multiple deep convolutional neural networks (CNNs), each of which is dedicated to a subregion of the angular spectrum. In particular, each CNN is fed with the array covariance matrix and it learns the MUSIC spectra of the corresponding angular subregion. We have shown, through simulations, that the proposed DeepMUSIC framework has superior estimation accuracy and exhibits less computational complexity in comparison with both DL and non-DL based techniques.
Tasks
Published	2019-12-09
URL	https://arxiv.org/abs/1912.04357v3
PDF	https://arxiv.org/pdf/1912.04357v3.pdf
PWC	https://paperswithcode.com/paper/deepmusic-direction-finding-via-deep-learning
Repo
Framework

Networkmetrics unraveled: MBDA in Action


Title	Networkmetrics unraveled: MBDA in Action
Authors	José Camacho, Rasmus Bro, David Kotz
Abstract	We propose networkmetrics, a new data-driven approach for monitoring, troubleshooting and understanding communication networks using multivariate analysis. Networkmetric models are powerful machine-learning tools to interpret and interact with data collected from a network. In this paper, we illustrate the application of Multivariate Big Data Analysis (MBDA), a recently proposed networkmetric method with application to Big Data sets. We use MBDA for the detection and troubleshooting of network problems in a campus-wide Wi-Fi network. Data includes a seven-year trace (from 2012 to 2018) of the network’s most recent activity, with approximately 3,000 distinct access points, 40,000 authenticated users, and 600,000 distinct Wi-Fi stations. This is the longest and largest Wi-Fi trace known to date. To analyze this data, we propose learning and visualization procedures that extend MBDA. These procedures result in a methodology that allows network analysts to identify problems and diagnose and troubleshoot them, optimizing the network performance. In the paper, we go through the entire workflow of the approach, illustrating its application in detail and discussing processing times for parallel hardware.
Tasks
Published	2019-07-05
URL	https://arxiv.org/abs/1907.02677v1
PDF	https://arxiv.org/pdf/1907.02677v1.pdf
PWC	https://paperswithcode.com/paper/networkmetrics-unraveled-mbda-in-action
Repo
Framework

Learning Personalized Attribute Preference via Multi-task AUC Optimization


Title	Learning Personalized Attribute Preference via Multi-task AUC Optimization
Authors	Zhiyong Yang, Qianqian Xu, Xiaochun Cao, Qingming Huang
Abstract	Traditionally, most of the existing attribute learning methods are trained based on the consensus of annotations aggregated from a limited number of annotators. However, the consensus might fail in settings, especially when a wide spectrum of annotators with different interests and comprehension about the attribute words are involved. In this paper, we develop a novel multi-task method to understand and predict personalized attribute annotations. Regarding the attribute preference learning for each annotator as a specific task, we first propose a multi-level task parameter decomposition to capture the evolution from a highly popular opinion of the mass to highly personalized choices that are special for each person. Meanwhile, for personalized learning methods, ranking prediction is much more important than accurate classification. This motivates us to employ an Area Under ROC Curve (AUC) based loss function to improve our model. On top of the AUC-based loss, we propose an efficient method to evaluate the loss and gradients. Theoretically, we propose a novel closed-form solution for one of our non-convex subproblem, which leads to provable convergence behaviors. Furthermore, we also provide a generalization bound to guarantee a reasonable performance. Finally, empirical analysis consistently speaks to the efficacy of our proposed method.
Tasks
Published	2019-06-18
URL	https://arxiv.org/abs/1906.07341v1
PDF	https://arxiv.org/pdf/1906.07341v1.pdf
PWC	https://paperswithcode.com/paper/learning-personalized-attribute-preference
Repo
Framework


Title	Social-BiGAT: Multimodal Trajectory Forecasting using Bicycle-GAN and Graph Attention Networks
Authors	Vineet Kosaraju, Amir Sadeghian, Roberto Martín-Martín, Ian Reid, S. Hamid Rezatofighi, Silvio Savarese
Abstract	Predicting the future trajectories of multiple interacting agents in a scene has become an increasingly important problem for many different applications ranging from control of autonomous vehicles and social robots to security and surveillance. This problem is compounded by the presence of social interactions between humans and their physical interactions with the scene. While the existing literature has explored some of these cues, they mainly ignored the multimodal nature of each human’s future trajectory. In this paper, we present Social-BiGAT, a graph-based generative adversarial network that generates realistic, multimodal trajectory predictions by better modelling the social interactions of pedestrians in a scene. Our method is based on a graph attention network (GAT) that learns reliable feature representations that encode the social interactions between humans in the scene, and a recurrent encoder-decoder architecture that is trained adversarially to predict, based on the features, the humans’ paths. We explicitly account for the multimodal nature of the prediction problem by forming a reversible transformation between each scene and its latent noise vector, as in Bicycle-GAN. We show that our framework achieves state-of-the-art performance comparing it to several baselines on existing trajectory forecasting benchmarks.
Tasks	Autonomous Vehicles
Published	2019-07-04
URL	https://arxiv.org/abs/1907.03395v2
PDF	https://arxiv.org/pdf/1907.03395v2.pdf
PWC	https://paperswithcode.com/paper/social-bigat-multimodal-trajectory
Repo
Framework

Dynamic Spatial Verification for Large-Scale Object-Level Image Retrieval


Title	Dynamic Spatial Verification for Large-Scale Object-Level Image Retrieval
Authors	Joel Brogan, Aparna Bharati, Daniel Moreira, Kevin Bowyer, Patrick Flynn, Anderson Rocha, Walter Scheirer
Abstract	Images from social media can reflect diverse viewpoints, heated arguments, and expressions of creativity, adding new complexity to retrieval tasks. Researchers working onContent-Based Image Retrieval (CBIR) have traditionally tuned their algorithms to match filtered results with user search intent. However, we are now bombarded with composite images of unknown origin, authenticity, and even meaning. With such uncertainty, users may not have an initial idea of what the results of a search query should look like. For instance, hidden people, spliced objects, and subtly altered scenes can be difficult for a user to detect initially in a meme image, but may contribute significantly to its composition. We propose a new approach for spatial verification that aims at modeling object-level regions dynamically clustering keypoints in a 2D Hough space, which are then used to accurately weight small contributing objects within the results, without the need for costly object detection steps. We call this method Objects in Scene to Objects in Scene (OS2OS) score, and it is optimized for fast matrix operations on CPUs. OS2OS performs comparably to state-of-the-art methods in classic CBIR problems, on the Oxford5K, Paris 6K, and Google-Landmarks datasets, without the need for bounding boxes. It also succeeds in emerging retrieval tasks such as image composite matching in the NIST MFC2018 dataset and meme-style composite imagery fromReddit.
Tasks	Content-Based Image Retrieval, Image Retrieval, Object Detection
Published	2019-03-24
URL	https://arxiv.org/abs/1903.10019v4
PDF	https://arxiv.org/pdf/1903.10019v4.pdf
PWC	https://paperswithcode.com/paper/needle-in-a-haystack-a-framework-for-seeking
Repo
Framework