OpenRaiser/Intern-Atlas huggingface dataset:
All $α+uβ$-constacyclic codes of length $np^{s}$ over $\mathbb{F}_{p^{m}}+u\mathbb{F}_{p^{m}}$
Venue: arXiv cs.IT 2016
Year: 2016

Let $\mathbb{F}_{p^{m}}$ be a finite field with cardinality $p^{m}$ and $R=\mathbb{F}_{p^{m}}+u\mathbb{F}_{p^{m}}$ with $u^{2}=0$. We aim to determine all $α+uβ$-constacyclic codes of length $np^{s}$ over $R$, where $α,β\in\mathbb{F}_{p^{m}}^{*}$, $n, s\in\mathbb{N}_{+}$ and $\gcd(n,p)=1$. Let $α_{0}\in\mathbb{F}_{p^{m}}^{*}$ and $α_{0}^{p^{s}}=α$. The residue ring $R[x]/\langle x^{np^{s}}-α-uβ\rangle$ is a chain ring with the maximal ideal $\langle x^{n}-α_{0}\rangle$ in the case that $x^{n}-α_{0}$ is irreducible in $\mathbb{F}_{p^{m}}[x]$. If $x^{n}-α_{0}$ is reducible in $\mathbb{F}_{p^{m}}[x]$, we give the explicit expressions of the ideals of $R[x]/\langle x^{np^{s}}-α-uβ\rangle$. Besides, the number of codewords and the dual code of every $α+uβ$-constacyclic code are provided.
Outlier Edge Detection Using Random Graph Generation Models and Applications
Venue: arXiv cs.SI 2016
Year: 2016

Outliers are samples that are generated by different mechanisms from other normal data samples. Graphs, in particular social network graphs, may contain nodes and edges that are made by scammers, malicious programs or mistakenly by normal users. Detecting outlier nodes and edges is important for data mining and graph analytics. However, previous research in the field has merely focused on detecting outlier nodes. In this article, we study the properties of edges and propose outlier edge detection algorithms using two random graph generation models. We found that the edge-ego-network, which can be defined as the induced graph that contains two end nodes of an edge, their neighboring nodes and the edges that link these nodes, contains critical information to detect outlier edges. We evaluated the proposed algorithms by injecting outlier edges into some real-world graph data. Experiment results show that the proposed algorithms can effectively detect outlier edges. In particular, the algorithm based on the Preferential Attachment Random Graph Generation model consistently gives good performance regardless of the test graph data. Further more, the proposed algorithms are not limited in the area of outlier edge detection. We demonstrate three different applications that benefit from the proposed algorithms: 1) a preprocessing tool that improves the performance of graph clustering algorithms; 2) an outlier node detection algorithm; and 3) a novel noisy data clustering algorithm. These applications show the great potential of the proposed outlier edge detection techniques.
Limited Random Walk Algorithm for Big Graph Data Clustering
Venue: arXiv cs.SI 2016
Year: 2016

Graph clustering is an important technique to understand the relationships between the vertices in a big graph. In this paper, we propose a novel random-walk-based graph clustering method. The proposed method restricts the reach of the walking agent using an inflation function and a normalization function. We analyze the behavior of the limited random walk procedure and propose a novel algorithm for both global and local graph clustering problems. Previous random-walk-based algorithms depend on the chosen fitness function to find the clusters around a seed vertex. The proposed algorithm tackles the problem in an entirely different manner. We use the limited random walk procedure to find attracting vertices in a graph and use them as features to cluster the vertices. According to the experimental results on the simulated graph data and the real-world big graph data, the proposed method is superior to the state-of-the-art methods in solving graph clustering problems. Since the proposed method uses the embarrassingly parallel paradigm, it can be efficiently implemented and embedded in any parallel computing environment such as a MapReduce framework. Given enough computing resources, we are capable of clustering graphs with millions of vertices and hundreds millions of edges in a reasonable time.
Soft GPGPUs for Embedded FPGAs: An Architectural Evaluation
Venue: arXiv cs.AR 2016
Year: 2016

We present a customizable soft architecture which allows for the execution of GPGPU code on an FPGA without the need to recompile the design. Issues related to scaling the overlay architecture to multiple GPGPU multiprocessors are considered along with application-class architectural optimizations. The overlay architecture is optimized for FPGA implementation to support efficient use of embedded block memories and DSP blocks. This architecture supports direct CUDA compilation of integer computations to a binary which is executable on the FPGA-based GPGPU. The benefits of our architecture are evaluated for a collection of five standard CUDA benchmarks which are compiled using standard GPGPU compilation tools. Speedups of 44x, on average, versus a MicroBlaze microprocessor are achieved. We show dynamic energy savings versus a soft-core processor of 80% on average. Application-customized versions of the soft GPGPU can be used to further reduce dynamic energy consumption by an average of 14%.
Concrete Problems in AI Safety
Venue: arXiv cs.AI 2016
Year: 2016

Rapid progress in machine learning and artificial intelligence (AI) has brought increasing attention to the potential impacts of AI technologies on society. In this paper we discuss one such potential impact: the problem of accidents in machine learning systems, defined as unintended and harmful behavior that may emerge from poor design of real-world AI systems. We present a list of five practical research problems related to accident risk, categorized according to whether the problem originates from having the wrong objective function ("avoiding side effects" and "avoiding reward hacking"), an objective function that is too expensive to evaluate frequently ("scalable supervision"), or undesirable behavior during the learning process ("safe exploration" and "distributional shift"). We review previous work in these areas as well as suggesting research directions with a focus on relevance to cutting-edge AI systems. Finally, we consider the high-level question of how to think most productively about the safety of forward-looking applications of AI.
Strategic Contention Resolution with Limited Feedback
Venue: arXiv cs.GT 2016
Year: 2016

In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on \emph{acknowledgment-based} protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. Users that do not transmit will not receive any feedback. We are interested in equilibrium protocols, where no player has an incentive to deviate. The limited feedback makes the design of equilibrium protocols a hard task as best response policies usually have to be modeled as Partially Observable Markov Decision Processes, which are hard to analyze. Nevertheless, we show how to circumvent this for the case of two players and present an equilibrium protocol. For many players, we give impossibility results for a large class of acknowledgment-based protocols, namely \emph{age-based} and \emph{backoff} protocols with finite expected finishing time. Finally, we provide an age-based equilibrium protocol, which has infinite expected finishing time, but every player finishes in linear time with high probability.
Crowdsourcing scoring of immunohistochemistry images: Evaluating Performance of the Crowd and an Automated Computational Method
Venue: arXiv cs.CV 2016
Year: 2016

The assessment of protein expression in immunohistochemistry (IHC) images provides important diagnostic, prognostic and predictive information for guiding cancer diagnosis and therapy. Manual scoring of IHC images represents a logistical challenge, as the process is labor intensive and time consuming. Since the last decade, computational methods have been developed to enable the application of quantitative methods for the analysis and interpretation of protein expression in IHC images. These methods have not yet replaced manual scoring for the assessment of IHC in the majority of diagnostic laboratories and in many large-scale research studies. An alternative approach is crowdsourcing the quantification of IHC images to an undefined crowd. The aim of this study is to quantify IHC images for labeling of ER status with two different crowdsourcing approaches, image labeling and nuclei labeling, and compare their performance with automated methods. Crowdsourcing-derived scores obtained greater concordance with the pathologist interpretations for both image labeling and nuclei labeling tasks (83% and 87%), as compared to the pathologist concordance achieved by the automated method (81%) on 5,483 TMA images from 1,909 breast cancer patients. This analysis shows that crowdsourcing the scoring of protein expression in IHC images is a promising new approach for large scale cancer molecular pathology studies.
Improving Testability and Reuse by Transitioning to Functional Programming
Venue: arXiv cs.SE 2016
Year: 2016

Declarative styles such as functional programming (FP) are rapidly gaining ground on their imperative cousins, including procedural and object-oriented programming. The shift is subtle because it is happening within the context of multiparadigm programming languages such as JavaScript. FP is better suited to modern processes like test-driven development (TDD), and architectures like massively parallel, cloud-based computing. This article describes the technical details that characterize the shift from imperative to FP and implications for software quality management, particularly reuse and testability.
Two-stage algorithms for covering array construction
Venue: arXiv cs.DS 2016
Year: 2016

Modern software systems often consist of many different components, each with a number of options. Although unit tests may reveal faulty options for individual components, functionally correct components may interact in unforeseen ways to cause a fault. Covering arrays are used to test for interactions among components systematically. A two-stage framework, providing a number of concrete algorithms, is developed for the efficient construction of covering arrays. %Our framework divides the construction in two stages. In the first stage, a time and memory efficient randomized algorithm covers most of the interactions. In the second stage, a more sophisticated search covers the remainder in relatively few tests. In this way, the storage limitations of the sophisticated search algorithms are avoided; hence the range of the number of components for which the algorithm can be applied is extended, without increasing the number of tests. Many of the framework instantiations can be tuned to optimize a memory-quality trade-off, so that fewer tests can be achieved using more memory. The algorithms developed outperform the currently best known methods when the number of components ranges from 20 to 60, the number of options for each ranges from 3 to 6, and $t$-way interactions are covered for $t\in \{5,6\}$. In some cases a reduction in the number of tests by more than $50\%$ is achieved.
Étude de Problèmes d'Optimisation Combinatoire à Multiples Composantes Interdépendantes
Venue: arXiv cs.AI 2016
Year: 2016

This extended abstract presents an overview on NP-hard optimization problems with multiple interdependent components. These problems occur in many real-world applications: industrial applications, engineering, and logistics. The fact that these problems are composed of many sub-problems that are NP-hard makes them even more challenging to solve using exact algorithms. This is mainly due to the high complexity of this class of algorithms and the hardness of the problems themselves. The main source of difficulty of these problems is the presence of internal dependencies between sub-problems. This aspect of interdependence of components is presented, and some outlines on solving approaches are briefly introduced from a (meta)heuristics and evolutionary computation perspective.
Link Prediction via Matrix Completion
Venue: arXiv cs.SI 2016
Year: 2016

Inspired by practical importance of social networks, economic networks, biological networks and so on, studies on large and complex networks have attracted a surge of attentions in the recent years. Link prediction is a fundamental issue to understand the mechanisms by which new links are added to the networks. We introduce the method of robust principal component analysis (robust PCA) into link prediction, and estimate the missing entries of the adjacency matrix. On one hand, our algorithm is based on the sparsity and low rank property of the matrix, on the other hand, it also performs very well when the network is dense. This is because a relatively dense real network is also sparse in comparison to the complete graph. According to extensive experiments on real networks from disparate fields, when the target network is connected and sufficiently dense, whatever it is weighted or unweighted, our method is demonstrated to be very effective and with prediction accuracy being considerably improved comparing with many state-of-the-art algorithms.
Learning text representation using recurrent convolutional neural network with highway layers
Venue: arXiv cs.CL 2016
Year: 2016

Recently, the rapid development of word embedding and neural networks has brought new inspiration to various NLP and IR tasks. In this paper, we describe a staged hybrid model combining Recurrent Convolutional Neural Networks (RCNN) with highway layers. The highway network module is incorporated in the middle takes the output of the bi-directional Recurrent Neural Network (Bi-RNN) module in the first stage and provides the Convolutional Neural Network (CNN) module in the last stage with the input. The experiment shows that our model outperforms common neural network models (CNN, RNN, Bi-RNN) on a sentiment analysis task. Besides, the analysis of how sequence length influences the RCNN with highway layers shows that our model could learn good representation for the long text.
Grouping the executables to detect malware with high accuracy
Venue: arXiv cs.CR 2016
Year: 2016

The metamorphic malware variants with the same malicious behavior (family), can obfuscate themselves to look different from each other. This variation in structure leads to a huge signature database for traditional signature matching techniques to detect them. In order to effective and efficient detection of malware in large amounts of executables, we need to partition these files into groups which can identify their respective families. In addition, the grouping criteria should be chosen such a way that, it can also be applied to unknown files encounter on computers for classification. This paper discusses the study of malware and benign executables in groups to detect unknown malware with high accuracy. We studied sizes of malware generated by three popular second generation malware (metamorphic malware) creator kits viz. G2, PS-MPC and NGVCK, and observed that the size variation in any two generated malware from same kit is not much. Hence, we grouped the executables on the basis of malware sizes by using Optimal k-Means Clustering algorithm and used these obtained groups to select promising features for training (Random forest, J48, LMT, FT and NBT) classifiers to detect variants of malware or unknown malware. We find that detection of malware on the basis of their respected file sizes gives accuracy up to 99.11% from the classifiers.
Bias Correction in Saupe Tensor Estimation
Venue: arXiv cs.CE 2016
Year: 2016

Estimation of the Saupe tensor is central to the determination of molecular structures from residual dipolar couplings (RDC) or chemical shift anisotropies. Assuming a given template structure, the singular value decomposition (SVD) method proposed in Losonczi et al. 1999 has been used traditionally to estimate the Saupe tensor. Despite its simplicity, whenever the template structure has large structural noise, the eigenvalues of the estimated tensor have a magnitude systematically smaller than their actual values. This leads to systematic error when calculating the eigenvalue dependent parameters, magnitude and rhombicity. We propose here a Monte Carlo simulation method to remove such bias. We further demonstrate the effectiveness of our method in the setting when the eigenvalue estimates from multiple template protein fragments are available and their average is used as an improved eigenvalue estimator. For both synthetic and experimental RDC datasets of ubiquitin, when using template fragments corrupted by large noise, the magnitude of our proposed bias-reduced estimator generally reaches at least 90% of the actual value, whereas the magnitude of SVD estimator can be shrunk below 80% of the true value.
Toward Word Embedding for Personalized Information Retrieval
Venue: arXiv cs.IR 2016
Year: 2016

This paper presents preliminary works on using Word Embedding (word2vec) for query expansion in the context of Personalized Information Retrieval. Traditionally, word embeddings are learned on a general corpus, like Wikipedia. In this work we try to personalize the word embeddings learning, by achieving the learning on the user's profile. The word embeddings are then in the same context than the user interests. Our proposal is evaluated on the CLEF Social Book Search 2016 collection. The results obtained show that some efforts should be made in the way to apply Word Embedding in the context of Personalized Information Retrieval.
The word entropy of natural languages
Venue: arXiv cs.CL 2016
Year: 2016

The average uncertainty associated with words is an information-theoretic concept at the heart of quantitative and computational linguistics. The entropy has been established as a measure of this average uncertainty - also called average information content. We here use parallel texts of 21 languages to establish the number of tokens at which word entropies converge to stable values. These convergence points are then used to select texts from a massively parallel corpus, and to estimate word entropies across more than 1000 languages. Our results help to establish quantitative language comparisons, to understand the performance of multilingual translation systems, and to normalize semantic similarity measures.
Deciding Hyperproperties
Venue: arXiv cs.LO 2016
Year: 2016

Hyperproperties, like observational determinism or symmetry, cannot be expressed as properties of individual computation traces, because they describe a relation between multiple computation traces. HyperLTL is a temporal logic that captures such relations through trace variables, which are introduced through existential and universal trace quantifiers and can be used to refer to multiple computations at the same time. In this paper, we study the satisfiability problem of HyperLTL. We show that the problem is PSPACE-complete for alternation-free formulas (and, hence, no more expensive than LTL satisfiability), EXPSPACE-complete for exists-forall-formulas, and undecidable for forall-exists-formulas. Many practical hyperproperties can be expressed as alternation-free formulas. Our results show that both satisfiability and implication are decidable for such properties.
Domain Name System Security and Privacy: Old Problems and New Challenges
Venue: arXiv cs.CR 2016
Year: 2016

The domain name system (DNS) is an important protocol in today's Internet operation, and is the standard naming convention between domain names, names that are easy to read, understand, and remember by humans, to IP address of Internet resources. The wealth of research activities on DNS in general and security and privacy in particular suggest that all problems in this domain are solved. Reality however is that despite the large body of literature on various aspects of DNS, there are still many challenges that need to be addressed. In this paper, we review the various activities in the research community on DNS operation, security, and privacy, and outline various challenges and open research directions that need to be tackled.
Deep Feature Fusion Network for Answer Quality Prediction in Community Question Answering
Venue: arXiv cs.IR 2016
Year: 2016

Community Question Answering (cQA) forums have become a popular medium for soliciting direct answers to specific questions of users from experts or other experienced users on a given topic. However, for a given question, users sometimes have to sift through a large number of low-quality or irrelevant answers to find out the answer which satisfies their information need. To alleviate this, the problem of Answer Quality Prediction (AQP) aims to predict the quality of an answer posted in response to a forum question. Current AQP systems either learn models using - a) various hand-crafted features (HCF) or b) use deep learning (DL) techniques which automatically learn the required feature representations. In this paper, we propose a novel approach for AQP known as - "Deep Feature Fusion Network (DFFN)" which leverages the advantages of both hand-crafted features and deep learning based systems. Given a question-answer pair along with its metadata, DFFN independently - a) learns deep features using a Convolutional Neural Network (CNN) and b) computes hand-crafted features using various external resources and then combines them using a deep neural network trained to predict the final answer quality. DFFN achieves state-of-the-art performance on the standard SemEval-2015 and SemEval-2016 benchmark datasets and outperforms baseline approaches which individually employ either HCF or DL based techniques alone.
E-commerce in Your Inbox: Product Recommendations at Scale
Venue: arXiv cs.AI 2016
Year: 2016

In recent years online advertising has become increasingly ubiquitous and effective. Advertisements shown to visitors fund sites and apps that publish digital content, manage social networks, and operate e-mail services. Given such large variety of internet resources, determining an appropriate type of advertising for a given platform has become critical to financial success. Native advertisements, namely ads that are similar in look and feel to content, have had great success in news and social feeds. However, to date there has not been a winning formula for ads in e-mail clients. In this paper we describe a system that leverages user purchase history determined from e-mail receipts to deliver highly personalized product ads to Yahoo Mail users. We propose to use a novel neural language-based algorithm specifically tailored for delivering effective product recommendations, which was evaluated against baselines that included showing popular products and products predicted based on co-occurrence. We conducted rigorous offline testing using a large-scale product purchase data set, covering purchases of more than 29 million users from 172 e-commerce websites. Ads in the form of product recommendations were successfully tested on online traffic, where we observed a steady 9% lift in click-through rates over other ad formats in mail, as well as comparable lift in conversion rates. Following successful tests, the system was launched into production during the holiday season of 2014.