OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Dynamic Topic Modeling with Clustered Latent Dirichlet Allocation (CLDA)
Venue: arXiv cs.IR 2019
Year: 2019

Topic modeling, a method for extracting the underlying themes from a collection of documents, is an increasingly important component of the design of intelligent systems enabling the sense-making of highly dynamic and diverse streams of text data. Traditional methods such as Dynamic Topic Modeling (DTM) do not lend themselves well to direct parallelization because of dependencies from one time step to another. In this paper, we introduce and empirically analyze Clustered Latent Dirichlet Allocation (CLDA), a method for extracting dynamic latent topics from a collection of documents. Our approach is based on data decomposition in which the data is partitioned into segments, followed by topic modeling on the individual segments. The resulting local models are then combined into a global solution using clustering. The decomposition and resulting parallelization leads to very fast runtime even on very large datasets. Our approach furthermore provides insight into how the composition of topics changes over time and can also be applied using other data partitioning strategies over any discrete features of the data, such as geographic features or classes of users. In this paper CLDA is applied successfully to seventeen years of NIPS conference papers (2,484 documents and 3,280,697 words), seventeen years of computer science journal abstracts (533,560 documents and 32,551,540 words), and to forty years of the PubMed corpus (4,025,978 documents and 273,853,980 words).
Oracle-Efficient Online Learning and Auction Design
Venue: arXiv cs.LG 2019
Year: 2019

We consider the design of computationally efficient online learning algorithms in an adversarial setting in which the learner has access to an offline optimization oracle. We present an algorithm called Generalized Follow-the-Perturbed-Leader and provide conditions under which it is oracle-efficient while achieving vanishing regret. Our results make significant progress on an open problem raised by Hazan and Koren, who showed that oracle-efficient algorithms do not exist in general and asked whether one can identify properties under which oracle-efficient online learning may be possible. Our auction-design framework considers an auctioneer learning an optimal auction for a sequence of adversarially selected valuations with the goal of achieving revenue that is almost as good as the optimal auction in hindsight, among a class of auctions. We give oracle-efficient learning results for: (1) VCG auctions with bidder-specific reserves in single-parameter settings, (2) envy-free item pricing in multi-item auctions, and (3) s-level auctions of Morgenstern and Roughgarden for single-item settings. The last result leads to an approximation of the overall optimal Myerson auction when bidders' valuations are drawn according to a fast-mixing Markov process, extending prior work that only gave such guarantees for the i.i.d. setting. Finally, we derive various extensions, including: (1) oracle-efficient algorithms for the contextual learning setting in which the learner has access to side information (such as bidder demographics), (2) learning with approximate oracles such as those based on Maximal-in-Range algorithms, and (3) no-regret bidding in simultaneous auctions, resolving an open problem of Daskalakis and Syrgkanis.
An Efficient Approach to Boosting Performance of Deep Spiking Network Training
Venue: arXiv cs.LG 2019
Year: 2019

Nowadays deep learning is dominating the field of machine learning with state-of-the-art performance in various application areas. Recently, spiking neural networks (SNNs) have been attracting a great deal of attention, notably owning to their power efficiency, which can potentially allow us to implement a low-power deep learning engine suitable for real-time/mobile applications. However, implementing SNN-based deep learning remains challenging, especially gradient-based training of SNNs by error backpropagation. We cannot simply propagate errors through SNNs in conventional way because of the property of SNNs that process discrete data in the form of a series. Consequently, most of the previous studies employ a workaround technique, which first trains a conventional weighted-sum deep neural network and then maps the learning weights to the SNN under training, instead of training SNN parameters directly. In order to eliminate this workaround, recently proposed is a new class of SNN named deep spiking networks (DSNs), which can be trained directly (without a mapping from conventional deep networks) by error backpropagation with stochastic gradient descent. In this paper, we show that the initialization of the membrane potential on the backward path is an important step in DSN training, through diverse experiments performed under various conditions. Furthermore, we propose a simple and efficient method that can improve DSN training by controlling the initial membrane potential on the backward path. In our experiments, adopting the proposed approach allowed us to boost the performance of DSN training in terms of converging time and accuracy.
Ear Recognition: More Than a Survey
Venue: arXiv cs.CV 2019
Year: 2019

Automatic identity recognition from ear images represents an active field of research within the biometric community. The ability to capture ear images from a distance and in a covert manner makes the technology an appealing choice for surveillance and security applications as well as other application domains. Significant contributions have been made in the field over recent years, but open research problems still remain and hinder a wider (commercial) deployment of the technology. This paper presents an overview of the field of automatic ear recognition (from 2D images) and focuses specifically on the most recent, descriptor-based methods proposed in this area. Open challenges are discussed and potential research directions are outlined with the goal of providing the reader with a point of reference for issues worth examining in the future. In addition to a comprehensive review on ear recognition technology, the paper also introduces a new, fully unconstrained dataset of ear images gathered from the web and a toolbox implementing several state-of-the-art techniques for ear recognition. The dataset and toolbox are meant to address some of the open issues in the field and are made publicly available to the research community.
On the Energy Efficient Displacement of Random Sensors for Interference and Connectivity
Venue: arXiv cs.DS 2019
Year: 2019

This paper investigates the problem of the minimilization of energy consumption in reallocation of wireless mobile sensors network (WMSN) to assure good communication without interference. Fix $d\in\mathbb{N}\setminus\{0\}.$ Assume $n$ sensors are initially randomly placed in the hyperoctant $[0,\infty)^d$ according to $d$ identical and independent Poisson processes each with arrival rate $λ>0.$ Let $0< s \le v$ be given real numbers. We are allowed to move the sensors, so that every two consecutive sensors are placed at distance greater than or equal to $s$ and less than or equal to $v.$ Fix $a\ge 1.$ Assume that $i-$th sensor is displaced a distance equal to $m(i).$ The cost measure for the displacement of the team of sensors is the sum $\sum_{i=1}^{n}d_i^a$ ($a-$total movement). In this work, we discover and explain a sharp decline and a sharp increase (a threshold phenomena) in the expected minimal $a-$total movement around the interference-connectivity distances $s,v$ equal to $\frac{1}λ.$
Browsix: Bridging the Gap Between Unix and the Browser
Venue: arXiv cs.OS 2019
Year: 2019

Applications written to run on conventional operating systems typically depend on OS abstractions like processes, pipes, signals, sockets, and a shared file system. Porting these applications to the web currently requires extensive rewriting or hosting significant portions of code server-side because browsers present a nontraditional runtime environment that lacks OS functionality. This paper presents Browsix, a framework that bridges the considerable gap between conventional operating systems and the browser, enabling unmodified programs expecting a Unix-like environment to run directly in the browser. Browsix comprises two core parts: (1) a JavaScript-only system that makes core Unix features (including pipes, concurrent processes, signals, sockets, and a shared file system) available to web applications; and (2) extended JavaScript runtimes for C, C++, Go, and Node.js that support running programs written in these languages as processes in the browser. Browsix supports running a POSIX shell, making it straightforward to connect applications together via pipes. We illustrate Browsix's capabilities via case studies that demonstrate how it eases porting legacy applications to the browser and enables new functionality. We demonstrate a Browsix-enabled LaTeX editor that operates by executing unmodified versions of pdfLaTeX and BibTeX. This browser-only LaTeX editor can render documents in seconds, making it fast enough to be practical. We further demonstrate how Browsix lets us port a client-server application to run entirely in the browser for disconnected operation. Creating these applications required less than 50 lines of glue code and no code modifications, demonstrating how easily Browsix can be used to build sophisticated web applications from existing parts without modification.
Discriminative Correlation Filter with Channel and Spatial Reliability
Venue: arXiv cs.CV 2019
Year: 2019

Short-term tracking is an open and challenging problem for which discriminative correlation filters (DCF) have shown excellent performance. We introduce the channel and spatial reliability concepts to DCF tracking and provide a novel learning algorithm for its efficient and seamless integration in the filter update and the tracking process. The spatial reliability map adjusts the filter support to the part of the object suitable for tracking. This both allows to enlarge the search region and improves tracking of non-rectangular objects. Reliability scores reflect channel-wise quality of the learned filters and are used as feature weighting coefficients in localization. Experimentally, with only two simple standard features, HoGs and Colornames, the novel CSR-DCF method -- DCF with Channel and Spatial Reliability -- achieves state-of-the-art results on VOT 2016, VOT 2015 and OTB100. The CSR-DCF runs in real-time on a CPU.
Food Image Recognition by Using Convolutional Neural Networks (CNNs)
Venue: arXiv cs.CV 2019
Year: 2019

Food image recognition is one of the promising applications of visual object recognition in computer vision. In this study, a small-scale dataset consisting of 5822 images of ten categories and a five-layer CNN was constructed to recognize these images. The bag-of-features (BoF) model coupled with support vector machine (SVM) was first evaluated for image classification, resulting in an overall accuracy of 56%; while the CNN model performed much better with an overall accuracy of 74%. Data augmentation techniques based on geometric transformation were applied to increase the size of training images, which achieved a significantly improved accuracy of more than 90% while preventing the overfitting issue that occurred to the CNN based on raw training data. Further improvements can be expected by collecting more images and optimizing the network architecture and hyper-parameters.
Multivariate Submodular Optimization
Venue: arXiv cs.DS 2019
Year: 2019

Submodular functions have found a wealth of new applications in data science and machine learning models in recent years. This has been coupled with many algorithmic advances in the area of submodular optimization: (SO) $\min/\max~f(S): S \in \mathcal{F}$, where $\mathcal{F}$ is a given family of feasible sets over a ground set $V$ and $f:2^V \rightarrow \mathbb{R}$ is submodular. In this work we focus on a more general class of \emph{multivariate submodular optimization} (MVSO) problems: $\min/\max~f (S_1,S_2,\ldots,S_k): S_1 \uplus S_2 \uplus \cdots \uplus S_k \in \mathcal{F}$. Here we use $\uplus$ to denote disjoint union and hence this model is attractive where resources are being allocated across $k$ agents, who share a `joint' multivariate nonnegative objective $f(S_1,S_2,\ldots,S_k)$ that captures some type of submodularity (i.e. diminishing returns) property. We provide some explicit examples and potential applications for this new framework. For maximization, we show that practical algorithms such as accelerated greedy variants and distributed algorithms achieve good approximation guarantees for very general families (such as matroids and $p$-systems). For arbitrary families, we show that monotone (resp. nonmonotone) MVSO admits an $α(1-1/e)$ (resp. $α\cdot 0.385$) approximation whenever monotone (resp. nonmonotone) SO admits an $α$-approximation over the multilinear formulation. This substantially expands the family of tractable models for submodular maximization. For minimization, we show that if SO admits a $β$-approximation over \emph{modular} functions, then MVSO admits a $\frac{β\cdot n}{1+(n-1)(1-c)}$-approximation where $c\in [0,1]$ denotes the curvature of $f$, and this is essentially tight. Finally, we prove that MVSO has an $αk$-approximation whenever SO admits an $α$-approximation over the convex formulation.
Finite Blocklength Analysis of Energy Harvesting Channels
Venue: arXiv cs.IT 2019
Year: 2019

We consider Additive White Gaussian Noise channels and Discrete Memoryless channels when the transmitter harvests energy from the environment. These can model wireless sensor networks as well as Internet of Things. By providing a unifying framework that works for any energy harvesting channel, we study these channels assuming an infinite energy buffer and provide the corresponding achievability and converse bounds on the channel capacity in the finite blocklength regime. We additionally provide moderate deviation asymptotic bounds as well.
A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search
Venue: arXiv cs.CV 2019
Year: 2019

Approximate Nearest Neighbor Search (ANNS) is a fundamental problem in many areas of machine learning and data mining. During the past decade, numerous hashing algorithms are proposed to solve this problem. Every proposed algorithm claims outperform other state-of-the-art hashing methods. However, the evaluation of these hashing papers was not thorough enough, and those claims should be re-examined. The ultimate goal of an ANNS method is returning the most accurate answers (nearest neighbors) in the shortest time. If implemented correctly, almost all the hashing methods will have their performance improved as the code length increases. However, many existing hashing papers only report the performance with the code length shorter than 128. In this paper, we carefully revisit the problem of search with a hash index, and analyze the pros and cons of two popular hash index search procedures. Then we proposed a very simple but effective two level index structures and make a thorough comparison of eleven popular hashing algorithms. Surprisingly, the random-projection-based Locality Sensitive Hashing (LSH) is the best performed algorithm, which is in contradiction to the claims in all the other ten hashing papers. Despite the extreme simplicity of random-projection-based LSH, our results show that the capability of this algorithm has been far underestimated. For the sake of reproducibility, all the codes used in the paper are released on GitHub, which can be used as a testing platform for a fair comparison between various hashing algorithms.
Computing Approximate Greatest Common Right Divisors of Differential Polynomials
Venue: arXiv cs.SC 2019
Year: 2019

Differential (Ore) type polynomials with "approximate" polynomial coefficients are introduced. These provide an effective notion of approximate differential operators, with a strong algebraic structure. We introduce the approximate Greatest Common Right Divisor Problem (GCRD) of differential polynomials, as a non-commutative generalization of the well-studied approximate GCD problem. Given two differential polynomials, we present an algorithm to find nearby differential polynomials with a non-trivial GCRD, where nearby is defined with respect to a suitable coefficient norm. Intuitively, given two linear differential polynomials as input, the (approximate) GCRD problem corresponds to finding the (approximate) differential polynomial whose solution space is the intersection of the solution spaces of the two inputs. The approximate GCRD problem is proven to be locally well-posed. A method based on the singular value decomposition of a differential Sylvester matrix is developed to produce an initial approximation of the GCRD. With a sufficiently good initial approximation, Newton iteration is shown to converge quadratically to an optimal solution. Finally, sufficient conditions for existence of a solution to the global problem are presented along with examples demonstrating that no solution exists when these conditions are not satisfied.
Large-scale network motif analysis using compression
Venue: arXiv cs.LG 2019
Year: 2019

We introduce a new method for finding network motifs: interesting or informative subgraph patterns in a network. Subgraphs are motifs when their frequency in the data is high compared to the expected frequency under a null model. To compute this expectation, a full or approximate count of the occurrences of a motif is normally repeated on as many as 1000 random graphs sampled from the null model; a prohibitively expensive step. We use ideas from the Minimum Description Length (MDL) literature to define a new measure of motif relevance. With our method, samples from the null model are not required. Instead we compute the probability of the data under the null model and compare this to the probability under a specially designed alternative model. With this new relevance test, we can search for motifs by random sampling, rather than requiring an accurate count of all instances of a motif. This allows motif analysis to scale to networks with billions of links.
Regular Separability of One Counter Automata
Venue: arXiv cs.FL 2019
Year: 2019

The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other. Our main result is decidability, and PSpace-completeness, of the regular separability problem for languages of one counter automata without zero tests (also known as one counter nets). This contrasts with undecidability of the regularity problem for one counter nets, and with undecidability of the regular separability problem for one counter automata, which is our second result.
On The Equivalence of Projections In Relative $α$-Entropy and Rényi Divergence
Venue: arXiv cs.IT 2019
Year: 2019

The aim of this work is to establish that two recently published projection theorems, one dealing with a parametric generalization of relative entropy and another dealing with Rényi divergence, are equivalent under a correspondence on the space of probability measures. Further, we demonstrate that the associated "Pythagorean" theorems are equivalent under this correspondence. Finally, we apply Eguchi's method of obtaining Riemannian metrics from general divergence functions to show that the geometry arising from the above divergences are equivalent under the aforementioned correspondence.
On the Binary Lossless Many-Help-One Problem with Independently Degraded Helpers
Venue: arXiv cs.IT 2019
Year: 2019

Although the rate region for the lossless many-help-one problem with independently degraded helpers is already "solved", its solution is given in terms of a convex closure over a set of auxiliary random variables. Thus, for any such a problem in particular, an optimization over the set of auxiliary random variables is required to truly solve the rate region. Providing the solution is surprisingly difficult even for an example as basic as binary sources. In this work, we derive a simple and tight inner bound on the rate region's lower boundary for the lossless many-help-one problem with independently degraded helpers when specialized to sources that are binary, uniformly distributed, and interrelated through symmetric channels. This scenario finds important applications in emerging cooperative communication schemes in which the direct-link transmission is assisted via multiple lossy relaying links. Numerical results indicate that the derived inner bound proves increasingly tight as the helpers become more degraded.
Malicious URL Detection using Machine Learning: A Survey
Venue: arXiv cs.LG 2019
Year: 2019

Malicious URL, a.k.a. malicious website, is a common and serious threat to cybersecurity. Malicious URLs host unsolicited content (spam, phishing, drive-by exploits, etc.) and lure unsuspecting users to become victims of scams (monetary loss, theft of private information, and malware installation), and cause losses of billions of dollars every year. It is imperative to detect and act on such threats in a timely manner. Traditionally, this detection is done mostly through the usage of blacklists. However, blacklists cannot be exhaustive, and lack the ability to detect newly generated malicious URLs. To improve the generality of malicious URL detectors, machine learning techniques have been explored with increasing attention in recent years. This article aims to provide a comprehensive survey and a structural understanding of Malicious URL Detection techniques using machine learning. We present the formal formulation of Malicious URL Detection as a machine learning task, and categorize and review the contributions of literature studies that addresses different dimensions of this problem (feature representation, algorithm design, etc.). Further, this article provides a timely and comprehensive survey for a range of different audiences, not only for machine learning researchers and engineers in academia, but also for professionals and practitioners in cybersecurity industry, to help them understand the state of the art and facilitate their own research and practical applications. We also discuss practical issues in system design, open research challenges, and point out some important directions for future research.
Next Generation Backscatter Communication: Systems, Techniques and Applications
Venue: arXiv cs.IT 2019
Year: 2019

The rapid growth of IoT driven by recent advancements in consumer electronics, 5G communication technologies, and cloud-computing enabled big-data analytics, has recently attracted tremendous attention from both the industry and academia. One of the major open challenges for IoT is the limited network lifetime due to massive IoT devices being powered by batteries with finite capacities. The low-power and low-complexity backscatter communications (BackCom), which simply relies on passive reflection and modulation of an incident radio-frequency (RF) wave, has emerged to be a promising technology for tackling this challenge. However, the contemporary BackCom has several major limitations, such as short transmission range, low data rate, and uni-directional information transmission. The article aims at introducing the recent advances in the active area of BackCom. Specifically, we provide a systematic introduction of the next generation BackCom covering basic principles, systems, techniques besides IoT applications. Lastly, we describe the IoT application scenarios with the next generation BackCom.