OpenRaiser/Intern-Atlas huggingface dataset:
Data Augmentation in Emotion Classification Using Generative Adversarial Networks
Venue: arXiv cs.CV 2017
Year: 2017

It is a difficult task to classify images with multiple class labels using only a small number of labeled examples, especially when the label (class) distribution is imbalanced. Emotion classification is such an example of imbalanced label distribution, because some classes of emotions like \emph{disgusted} are relatively rare comparing to other labels like {\it happy or sad}. In this paper, we propose a data augmentation method using generative adversarial networks (GAN). It can complement and complete the data manifold and find better margins between neighboring classes. Specifically, we design a framework with a CNN model as the classifier and a cycle-consistent adversarial networks (CycleGAN) as the generator. In order to avoid gradient vanishing problem, we employ the least-squared loss as adversarial loss. We also propose several evaluation methods on three benchmark datasets to validate GAN's performance. Empirical results show that we can obtain 5%~10% increase in the classification accuracy after employing the GAN-based data augmentation techniques.
How Do Software Startups Pivot? Empirical Results from a Multiple Case Study
Venue: arXiv cs.CY 2017
Year: 2017

In order to handle intense time pressure and survive in dynamic market, software startups have to make crucial decisions constantly on whether to change directions or stay on chosen courses, or in the terms of Lean Startup, to pivot or to persevere. The existing research and knowledge on software startup pivots are very limited. In this study, we focused on understanding the pivoting processes of software startups, and identified the triggering factors and pivot types. To achieve this, we employed a multiple case study approach, and analyzed the data obtained from four software startups. The initial findings show that different software startups make different types of pivots related to business and technology during their product development life cycle. The pivots are triggered by various factors including negative customer feedback.
Oversampling for Imbalanced Learning Based on K-Means and SMOTE
Venue: arXiv cs.LG 2017
Year: 2017

Learning from class-imbalanced data continues to be a common and challenging problem in supervised learning as standard classification algorithms are designed to handle balanced class distributions. While different strategies exist to tackle this problem, methods which generate artificial data to achieve a balanced class distribution are more versatile than modifications to the classification algorithm. Such techniques, called oversamplers, modify the training data, allowing any classifier to be used with class-imbalanced datasets. Many algorithms have been proposed for this task, but most are complex and tend to generate unnecessary noise. This work presents a simple and effective oversampling method based on k-means clustering and SMOTE oversampling, which avoids the generation of noise and effectively overcomes imbalances between and within classes. Empirical results of extensive experiments with 71 datasets show that training data oversampled with the proposed method improves classification results. Moreover, k-means SMOTE consistently outperforms other popular oversampling methods. An implementation is made available in the python programming language.
SPARK: Static Program Analysis Reasoning and Retrieving Knowledge
Venue: arXiv cs.PL 2017
Year: 2017

Program analysis is a technique to reason about programs without executing them, and it has various applications in compilers, integrated development environments, and security. In this work, we present a machine learning pipeline that induces a security analyzer for programs by example. The security analyzer determines whether a program is either secure or insecure based on symbolic rules that were deduced by our machine learning pipeline. The machine pipeline is two-staged consisting of a Recurrent Neural Networks (RNN) and an Extractor that converts an RNN to symbolic rules. To evaluate the quality of the learned symbolic rules, we propose a sampling-based similarity measurement between two infinite regular languages. We conduct a case study using real-world data. In this work, we discuss the limitations of existing techniques and possible improvements in the future. The results show that with sufficient training data and a fair distribution of program paths it is feasible to deducing symbolic security rules for the OpenJDK library with millions lines of code.
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Venue: arXiv cs.DM 2017
Year: 2017

Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. In this paper, we provide a new upper bound on $f(n)$, the maximum number of stable matchings that a stable matching instance with $n$ men and $n$ women can have. It has been a long-standing open problem to understand the asymptotic behavior of $f(n)$ as $n\to\infty$, first posed by Donald Knuth in the 1970s. Until now the best lower bound was approximately $2.28^n$, and the best upper bound was $2^{n\log n- O(n)}$. In this paper, we show that for all $n$, $f(n) \leq c^n$ for some universal constant $c$. This matches the lower bound up to the base of the exponent. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call "mixing". The latter might be of independent interest.
Towards Hardware Implementation of Double-Layer Perceptron Based on Metal-Oxide Memristive Nanostructures
Venue: arXiv cs.ET 2017
Year: 2017

Construction and training principles have been proposed and tested for an artificial neural network based on metal-oxide thin-film nanostructures possessing bipolar resistive switching (memristive) effect. Experimental electronic circuit of neural network is implemented as a double-layer perceptron with a weight matrix composed of 32 memristive devices. The network training algorithm takes into account technological variations of the parameters of memristive nanostructures. Despite the limited size of weight matrix the developed neural network model is well scalable and capable of solving nonlinear classification problems.
On Automata Recognizing Birecurrent Sets
Venue: arXiv cs.FL 2017
Year: 2017

In this note we study automata recognizing birecurrent sets. A set of words is birecurrent if the minimal partial DFA recognizing this set and the minimal partial DFA recognizing the reversal of this set are both strongly connected. This notion was introduced by Perrin, and Dolce et al. provided a characterization of such sets. We prove that deciding whether a partial DFA recognizes a birecurrent set is a PSPACE-complete problem. We show that this problem is PSPACE-complete even in the case of binary partial DFAs with all states accepting and in the case of binary complete DFAs. We also consider a related problem of computing the rank of a partial DFA.
The Minimum Distance of Some Narrow-Sense Primitive BCH Codes
Venue: arXiv cs.IT 2017
Year: 2017

Due to wide applications of BCH codes, the determination of their minimum distance is of great interest. However, this is a very challenging problem for which few theoretical results have been reported in the last four decades. Even for the narrow-sense primitive BCH codes, which form the most well-studied subclass of BCH codes, there are very few theoretical results on the minimum distance. In this paper, we present new results on the minimum distance of narrow-sense primitive BCH codes with special Bose distance. We prove that for a prime power $q$, the $q$-ary narrow-sense primitive BCH code with length $q^m-1$ and Bose distance $q^m-q^{m-1}-q^i-1$, where $\frac{m-2}{2} \le i \le m-\lfloor \frac{m}{3} \rfloor-1$, has minimum distance $q^m-q^{m-1}-q^i-1$. This is achieved by employing the beautiful theory of sets of quadratic forms, symmetric bilinear forms and alternating bilinear forms over finite fields, which can be best described using the framework of association schemes.
One Model to Rule them all: Multitask and Multilingual Modelling for Lexical Analysis
Venue: arXiv cs.CL 2017
Year: 2017

When learning a new skill, you take advantage of your preexisting skills and knowledge. For instance, if you are a skilled violinist, you will likely have an easier time learning to play cello. Similarly, when learning a new language you take advantage of the languages you already speak. For instance, if your native language is Norwegian and you decide to learn Dutch, the lexical overlap between these two languages will likely benefit your rate of language acquisition. This thesis deals with the intersection of learning multiple tasks and learning multiple languages in the context of Natural Language Processing (NLP), which can be defined as the study of computational processing of human language. Although these two types of learning may seem different on the surface, we will see that they share many similarities. The traditional approach in NLP is to consider a single task for a single language at a time. However, recent advances allow for broadening this approach, by considering data for multiple tasks and languages simultaneously. This is an important approach to explore further as the key to improving the reliability of NLP, especially for low-resource languages, is to take advantage of all relevant data whenever possible. In doing so, the hope is that in the long term, low-resource languages can benefit from the advances made in NLP which are currently to a large extent reserved for high-resource languages. This, in turn, may then have positive consequences for, e.g., language preservation, as speakers of minority languages will have a lower degree of pressure to using high-resource languages. In the short term, answering the specific research questions posed should be of use to NLP researchers working towards the same goal.
Design and Analysis of a Secure Three Factor User Authentication Scheme Using Biometric and Smart Card
Venue: arXiv cs.CR 2017
Year: 2017

Password security can no longer provide enough security in the area of remote user authentication. Considering this security drawback, researchers are trying to find solution with multifactor remote user authentication system. Recently, three factor remote user authentication using biometric and smart card has drawn a considerable attention of the researchers. However, most of the current proposed schemes have security flaws. They are vulnerable to attacks like user impersonation attack, server masquerading attack, password guessing attack, insider attack, denial of service attack, forgery attack, etc. Also, most of them are unable to provide mutual authentication, session key agreement and password, or smart card recovery system. Considering these drawbacks, we propose a secure three factor user authentication scheme using biometric and smart card. Through security analysis, we show that our proposed scheme can overcome drawbacks of existing systems and ensure high security in remote user authentication.
Toward real-time data query systems in HEP
Venue: arXiv cs.DC 2017
Year: 2017

Exploratory data analysis tools must respond quickly to a user's questions, so that the answer to one question (e.g. a visualized histogram or fit) can influence the next. In some SQL-based query systems used in industry, even very large (petabyte) datasets can be summarized on a human timescale (seconds), employing techniques such as columnar data representation, caching, indexing, and code generation/JIT-compilation. This article describes progress toward realizing such a system for High Energy Physics (HEP), focusing on the intermediate problems of optimizing data access and calculations for "query sized" payloads, such as a single histogram or group of histograms, rather than large reconstruction or data-skimming jobs. These techniques include direct extraction of ROOT TBranches into Numpy arrays and compilation of Python analysis functions (rather than SQL) to be executed very quickly. We will also discuss the problem of caching and actively delivering jobs to worker nodes that have the necessary input data preloaded in cache. All of these pieces of the larger solution are available as standalone GitHub repositories, and could be used in current analyses.
Distributed Unmixing of Hyperspectral Data With Sparsity Constraint
Venue: arXiv cs.CV 2017
Year: 2017

Spectral unmixing (SU) is a data processing problem in hyperspectral remote sensing. The significant challenge in the SU problem is how to identify endmembers and their weights, accurately. For estimation of signature and fractional abundance matrices in a blind problem, nonnegative matrix factorization (NMF) and its developments are used widely in the SU problem. One of the constraints which was added to NMF is sparsity constraint that was regularized by L 1/2 norm. In this paper, a new algorithm based on distributed optimization has been used for spectral unmixing. In the proposed algorithm, a network including single-node clusters has been employed. Each pixel in hyperspectral images considered as a node in this network. The distributed unmixing with sparsity constraint has been optimized with diffusion LMS strategy, and then the update equations for fractional abundance and signature matrices are obtained. Simulation results based on defined performance metrics, illustrate advantage of the proposed algorithm in spectral unmixing of hyperspectral data compared with other methods. The results show that the AAD and SAD of the proposed approach are improved respectively about 6 and 27 percent toward distributed unmixing in SNR=25dB.
Learning Stable and Energetically Economical Walking with RAMone
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we optimize over the control parameter space of our planar-bipedal robot, RAMone, for stable and energetically economical walking at various speeds. We formulate this task as an episodic reinforcement learning problem and use Covariance Matrix Adaptation. The parameters we are interested in modifying include gains from our Hybrid Zero Dynamics style controller and from RAMone's low-level motor controllers.
Automatic Differentiation for Tensor Algebras
Venue: arXiv cs.SC 2017
Year: 2017

Kjolstad et. al. proposed a tensor algebra compiler. It takes expressions that define a tensor element-wise, such as $f_{ij}(a,b,c,d) = \exp\left[-\sum_{k=0}^4 \left((a_{ik}+b_{jk})^2\, c_{ii} + d_{i+k}^3 \right) \right]$, and generates the corresponding compute kernel code. For machine learning, especially deep learning, it is often necessary to compute the gradient of a loss function $l(a,b,c,d)=l(f(a,b,c,d))$ with respect to parameters $a,b,c,d$. If tensor compilers are to be applied in this field, it is necessary to derive expressions for the derivatives of element-wise defined tensors, i.e. expressions for $(da)_{ik}=\partial l/\partial a_{ik}$. When the mapping between function indices and argument indices is not 1:1, special attention is required. For the function $f_{ij} (x) = x_i^2$, the derivative of the loss is $(dx)_i=\partial l/\partial x_i=\sum_j (df)_{ij}2x_i$; the sum is necessary because index $j$ does not appear in the indices of $f$. Another example is $f_{i}(x)=x_{ii}^2$, where $x$ is a matrix; here we have $(dx)_{ij}=δ_{ij}(df)_i2x_{ii}$; the Kronecker delta is necessary because the derivative is zero for off-diagonal elements. Another indexing scheme is used by $f_{ij}(x)=\exp x_{i+j}$; here the correct derivative is $(dx)_{k}=\sum_i (df)_{i,k-i} \exp x_{k}$, where the range of the sum must be chosen appropriately. In this publication we present an algorithm that can handle any case in which the indices of an argument are an arbitrary linear combination of the indices of the function, thus all the above examples can be handled. Sums (and their ranges) and Kronecker deltas are automatically inserted into the derivatives as necessary. Additionally, the indices are transformed, if required (as in the last example). The algorithm outputs a symbolic expression that can be subsequently fed into a tensor algebra compiler. Source code is provided.
"Attention" for Detecting Unreliable News in the Information Age
Venue: arXiv cs.CL 2017
Year: 2017

An Unreliable news is any piece of information which is false or misleading, deliberately spread to promote political, ideological and financial agendas. Recently the problem of unreliable news has got a lot of attention as the number instances of using news and social media outlets for propaganda have increased rapidly. This poses a serious threat to society, which calls for technology to automatically and reliably identify unreliable news sources. This paper is an effort made in this direction to build systems for detecting unreliable news articles. In this paper, various NLP algorithms were built and evaluated on Unreliable News Data 2017 dataset. Variants of hierarchical attention networks (HAN) are presented for encoding and classifying news articles which achieve the best results of 0.944 ROC-AUC. Finally, Attention layer weights are visualized to understand and give insight into the decisions made by HANs. The results obtained are very promising and encouraging to deploy and use these systems in the real world to mitigate the problem of unreliable news.
Deep Stacking Networks for Low-Resource Chinese Word Segmentation with Transfer Learning
Venue: arXiv cs.CL 2017
Year: 2017

In recent years, neural networks have proven to be effective in Chinese word segmentation. However, this promising performance relies on large-scale training data. Neural networks with conventional architectures cannot achieve the desired results in low-resource datasets due to the lack of labelled training data. In this paper, we propose a deep stacking framework to improve the performance on word segmentation tasks with insufficient data by integrating datasets from diverse domains. Our framework consists of two parts, domain-based models and deep stacking networks. The domain-based models are used to learn knowledge from different datasets. The deep stacking networks are designed to integrate domain-based models. To reduce model conflicts, we innovatively add communication paths among models and design various structures of deep stacking networks, including Gaussian-based Stacking Networks, Concatenate-based Stacking Networks, Sequence-based Stacking Networks and Tree-based Stacking Networks. We conduct experiments on six low-resource datasets from various domains. Our proposed framework shows significant performance improvements on all datasets compared with several strong baselines.
Optimal Checkpointing for Secure Intermittently-Powered IoT Devices
Venue: arXiv cs.DC 2017
Year: 2017

Energy harvesting is a promising solution to power Internet of Things (IoT) devices. Due to the intermittent nature of these energy sources, one cannot guarantee forward progress of program execution. Prior work has advocated for checkpointing the intermediate state to off-chip non-volatile memory (NVM). Encrypting checkpoints addresses the security concern, but significantly increases the checkpointing overheads. In this paper, we propose a new online checkpointing policy that judiciously determines when to checkpoint so as to minimize application time to completion while guaranteeing security. Compared to state-of-the-art checkpointing schemes that do not account for the overheads of encrypted checkpoints we improve execution time up to 1.4x.
Inference-Based Similarity Search in Randomized Montgomery Domains for Privacy-Preserving Biometric Identification
Venue: arXiv cs.CR 2017
Year: 2017

Similarity search is essential to many important applications and often involves searching at scale on high-dimensional data based on their similarity to a query. In biometric applications, recent vulnerability studies have shown that adversarial machine learning can compromise biometric recognition systems by exploiting the biometric similarity information. Existing methods for biometric privacy protection are in general based on pairwise matching of secured biometric templates and have inherent limitations in search efficiency and scalability. In this paper, we propose an inference-based framework for privacy-preserving similarity search in Hamming space. Our approach builds on an obfuscated distance measure that can conceal Hamming distance in a dynamic interval. Such a mechanism enables us to systematically design statistically reliable methods for retrieving most likely candidates without knowing the exact distance values. We further propose to apply Montgomery multiplication for generating search indexes that can withstand adversarial similarity analysis, and show that information leakage in randomized Montgomery domains can be made negligibly small. Our experiments on public biometric datasets demonstrate that the inference-based approach can achieve a search accuracy close to the best performance possible with secure computation methods, but the associated cost is reduced by orders of magnitude compared to cryptographic primitives.
Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion
Venue: arXiv cs.DS 2017
Year: 2017

We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of \emph{fooling views} and exemplify its strength by proving two new lower bounds for triangle membership in the CONGEST(B) model: (i) Any $1$-round algorithm requires $B\geq cΔ\log n$ for a constant $c>0$. (ii) If $B=1$, even in constant-degree graphs any algorithm must take $Ω(\log^* n)$ rounds. The implication of the former is the first proven separation between the LOCAL and the CONGEST models for deterministic triangle membership. The latter result is the first non-trivial lower bound on the number of rounds required, even for \emph{triangle detection}, under limited bandwidth. All previous known techniques are provably incapable of giving these bounds. We hope that our approach may pave the way for proving lower bounds for additional problems in various settings of distributed computing for which previous techniques do not suffice.
Performance Comparison of Algorithms for Movie Rating Estimation
Venue: arXiv cs.IR 2017
Year: 2017

In this paper, our goal is to compare performances of three different algorithms to predict the ratings that will be given to movies by potential users where we are given a user-movie rating matrix based on the past observations. To this end, we evaluate User-Based Collaborative Filtering, Iterative Matrix Factorization and Yehuda Koren's Integrated model using neighborhood and factorization where we use root mean square error (RMSE) as the performance evaluation metric. In short, we do not observe significant differences between performances, especially when the complexity increase is considered. We can conclude that Iterative Matrix Factorization performs fairly well despite its simplicity.