OpenRaiser/Intern-Atlas huggingface dataset:
Laplacian regularized low rank subspace clustering
Venue: arXiv cs.CV 2016
Year: 2016

The problem of fitting a union of subspaces to a collection of data points drawn from multiple subspaces is considered in this paper. In the traditional low rank representation model, the dictionary used to represent the data points is chosen as the data points themselves and thus the dictionary is corrupted with noise. This problem is solved in the low rank subspace clustering model which decomposes the corrupted data matrix as the sum of a clean and self-expressive dictionary plus a matrix of noise and gross errors. Also, the clustering results of the low rank representation model can be enhanced by using a graph of data similarity. This model is called Laplacian regularized low rank representation model with a graph regularization term added to the objective function. Inspired from the above two ideas, in this paper a Laplacian regularized low rank subspace clustering model is proposed. This model uses a clean dictionary to represent the data points and a graph regularization term is also incorporated in the objective function. Experimental results show that, compared with the traditional low rank representation model, low rank subspace clustering model and several other state-of-the-art subspace clustering model, the model proposed in this paper can get better subspace clustering results with lower clustering error.
Generating the Functions with Regular Graphs under Composition
Venue: arXiv cs.FL 2016
Year: 2016

While automata theory often concerns itself with regular predicates, relations corresponding to acceptance by a finite state automaton, in this article we study the regular functions, such relations which are also functions in the set-theoretic sense. Here we present a small (but necessarily infinite) collection of (multi-ary) functions which generate the regular functions under composition. To this end, this paper presents an interpretation of the powerset determinization construction in terms of compositions of input-to-run maps. Furthermore, known results using the Krohn-Rhodes theorem to further decompose our generating set are spelled out in detail, alongside some coding tricks for dealing with variable length words. This will include two clear proofs of the Krohn-Rhodes Theorem in modern notation.
Node Isolation of Secure Wireless Sensor Networks under a Heterogeneous Channel Model
Venue: arXiv cs.IT 2016
Year: 2016

We investigate the secure connectivity of wireless sensor networks under a heterogeneous random key predistribution scheme and a heterogeneous channel model. In particular, we study a random graph formed by the intersection of an inhomogeneous random key graph with an inhomogeneous Erdős-Rényi graph. The former graph is naturally induced by the heterogeneous random key predistribution scheme while the latter graph constitutes a heterogeneous on/off channel model; wherein, the wireless channel between a class-$i$ node and a class-$j$ node is on with probability $α_{ij}$ independently. We present conditions (in the form of zero-one laws) on how to scale the parameters of the intersection model so that it has no isolated node with high probability as the number of nodes gets large. We also present numerical results to support these zero-one laws in the finite-node regime.
Online and Random-order Load Balancing Simultaneously
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of online load balancing under lp-norms: sequential jobs need to be assigned to one of the machines and the goal is to minimize the lp-norm of the machine loads. This generalizes the classical problem of scheduling for makespan minimization (case l_infty) and has been thoroughly studied. However, despite the recent push for beyond worst-case analyses, no such results are known for this problem. In this paper we provide algorithms with simultaneous guarantees for the worst-case model as well as for the random-order (i.e. secretary) model, where an arbitrary set of jobs comes in random order. First, we show that the greedy algorithm (with restart), known to have optimal O(p) worst-case guarantee, also has a (typically) improved random-order guarantee. However, the behavior of this algorithm in the random-order model degrades with p. We then propose algorithm SIMULTANEOUSLB that has simultaneously optimal guarantees (within constants) in both worst-case and random-order models. In particular, the random-order guarantee of SIMULTANEOUSLB improves as p increases. One of the main components is a new algorithm with improved regret for Online Linear Optimization (OLO) over the non-negative vectors in the lq ball. Interestingly, this OLO algorithm is also used to prove a purely probabilistic inequality that controls the correlations arising in the random-order model, a common source of difficulty for the analysis. Another important component used in both SIMULTANEOUSLB and our OLO algorithm is a smoothing of the lp-norm that may be of independent interest. This smoothness property allows us to see algorithm SIMULTANEOUSLB as essentially a greedy one in the worst-case model and as a primal-dual one in the random-order model, which is instrumental for its simultaneous guarantees.
UTD-CRSS Systems for 2016 NIST Speaker Recognition Evaluation
Venue: arXiv cs.CL 2016
Year: 2016

This document briefly describes the systems submitted by the Center for Robust Speech Systems (CRSS) from The University of Texas at Dallas (UTD) to the 2016 National Institute of Standards and Technology (NIST) Speaker Recognition Evaluation (SRE). We developed several UBM and DNN i-Vector based speaker recognition systems with different data sets and feature representations. Given that the emphasis of the NIST SRE 2016 is on language mismatch between training and enrollment/test data, so-called domain mismatch, in our system development we focused on: (1) using unlabeled in-domain data for centralizing data to alleviate the domain mismatch problem, (2) finding the best data set for training LDA/PLDA, (3) using newly proposed dimension reduction technique incorporating unlabeled in-domain data before PLDA training, (4) unsupervised speaker clustering of unlabeled data and using them alone or with previous SREs for PLDA training, (5) score calibration using only unlabeled data and combination of unlabeled and development (Dev) data as separate experiments.
Co-Occuring Directions Sketching for Approximate Matrix Multiply
Venue: arXiv cs.LG 2016
Year: 2016

We introduce co-occurring directions sketching, a deterministic algorithm for approximate matrix product (AMM), in the streaming model. We show that co-occuring directions achieves a better error bound for AMM than other randomized and deterministic approaches for AMM. Co-occurring directions gives a $1 + ε$ -approximation of the optimal low rank approximation of a matrix product. Empirically our algorithm outperforms competing methods for AMM, for a small sketch size. We validate empirically our theoretical findings and algorithms
Potentials and Challenges of Light Fidelity Based Indoor Communication System
Venue: arXiv cs.NI 2016
Year: 2016

In this era of modern devices and high speed communication the issue of spectral overloading is increasing with time and becoming more serious. With the advancement in LED industry, light fidelity (Li-Fi) based indoor network is an attractive substitute for the existing radio frequency (RF) based communication networks. Because of its capability to perform dual function of lighting as well as high speed communication, Li-Fi is attracting both industrial as well as academic researchers. The Li-Fi networking paradigm offers performance enhancements which can make it an attractive backup option to be used for networking setup in Internet of things (IOT) and its indoor capabilities make it an attractive choice for large scale indoor communication in next generation wireless networking environment. This paper discusses key potentials of Li-Fi based indoor communication system and point out the challenges which indoor based Li-Fi network is facing under the knowledge of existing research work in the field of Li-Fi.
Activity Maximization by Effective Information Diffusion in Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

In a social network, even about the same information the excitements between different pairs of users are different. If you want to spread a piece of new information and maximize the expected total amount of excitements, which seed users should you choose? This problem indeed is substantially different from the renowned influence maximization problem and cannot be tackled using the existing approaches. In this paper, motivated by the demand in a few interesting applications, we model the novel problem of activity maximization. We tackle the problem systematically. We first analyze the complexity and the approximability of the problem. We develop an upper bound and a lower bound that are submodular so that the Sandwich framework can be applied. We then devise a polling-based randomized algorithm that guarantees a data dependent approximation factor. Our experiments on three real data sets clearly verify the effectiveness and scalability of our method, as well as the advantage of our method against the other heuristic methods.
MIMO Systems With Low-Resolution ADCs: Linear Coding Approach
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a multiple-input multiple-output (MIMO) system with low-resolution analog-to-digital converters (ADCs). In this system, the paper presents a new MIMO detection approach using coding theory. The principal idea of the proposed approach is to transform a non-linear MIMO channel to a linear MIMO channel by leveraging both a $p$-level quantizer and a lattice code where $p\geq 2$. After transforming to the linear MIMO channel with the sets of finite input and output elements, efficient MIMO detection methods are proposed to attain both diversity and multiplexing gains by using algebraic coding theory. In particular, using the proposed methods, the analytical characterizations of achievable rates are derived for different MIMO configurations. One major observation is that the proposed approach is particularly useful for a large MIMO system with the ADCs that use a few bits.
Hybrid clustering-classification neural network in the medical diagnostics of reactive arthritis
Venue: arXiv cs.LG 2016
Year: 2016

The hybrid clustering-classification neural network is proposed. This network allows increasing a quality of information processing under the condition of overlapping classes due to the rational choice of a learning rate parameter and introducing a special procedure of fuzzy reasoning in the clustering process, which occurs both with an external learning signal (supervised) and without the one (unsupervised). As similarity measure neighborhood function or membership one, cosine structures are used, which allow to provide a high flexibility due to self-learning-learning process and to provide some new useful properties. Many realized experiments have confirmed the efficiency of proposed hybrid clustering-classification neural network; also, this network was used for solving diagnostics task of reactive arthritis.
On the distance of stabilizer quantum codes from $J$-affine variety codes
Venue: arXiv cs.IT 2016
Year: 2016

Self-orthogonal $J$-affine variety codes have been successfully used to obtain quantum stabilizer codes with excellent parameters. In a previous paper we gave formulae for the dimension of this family of quantum codes, but no bound for the minimum distance was given. In this work, we show how to derive quantum stabilizer codes with designed minimum distance from $J$-affine variety codes and their subfield-subcodes. Moreover, this allows us to obtain new quantum codes, some of them either, with better parameters, or with larger distances than the previously known codes.
A Survey: Embedded Systems Supporting By Different Operating Systems
Venue: arXiv cs.OH 2016
Year: 2016

In these days embedded system have an important role in different Fields and applications like Network embedded system , Real-time embedded systems which supports the mission-critical domains, mostly having the time constraints, Stand-alone systems which includes the network router etc. A great deployment in the processors made for completing the demanding needs of the users. There is also a large-scale deployment occurs in sensor networks for providing the advance facilities, for handled such type of embedded systems a specific operating system must provide. This paper presents some software infrastructures that have the ability of supporting such types of embedded systems.
Artificial Intelligence Safety and Cybersecurity: a Timeline of AI Failures
Venue: arXiv cs.AI 2016
Year: 2016

In this work, we present and analyze reported failures of artificially intelligent systems and extrapolate our analysis to future AIs. We suggest that both the frequency and the seriousness of future AI failures will steadily increase. AI Safety can be improved based on ideas developed by cybersecurity experts. For narrow AIs safety failures are at the same, moderate, level of criticality as in cybersecurity, however for general AI, failures have a fundamentally different impact. A single failure of a superintelligent system may cause a catastrophic event without a chance for recovery. The goal of cybersecurity is to reduce the number of successful attacks on the system; the goal of AI Safety is to make sure zero attacks succeed in bypassing the safety mechanisms. Unfortunately, such a level of performance is unachievable. Every security system will eventually fail; there is no such thing as a 100% secure system.
A recommender system for efficient discovery of new anomalies in large-scale access logs
Venue: arXiv cs.IR 2016
Year: 2016

We present a novel, non-standard recommender system for large-scale security policy management(SPM). Our system Helios discovers and recommends unknown and unseen anomalies in large-scale access logs with minimal supervision and no starting information on users and items. Typical recommender systems assume availability of user- and item-related information, but such information is not usually available in access logs. To resolve this problem, we first use discrete categorical labels to construct categorical combinations from access logs in a bootstrapping manner. Then, we utilize rank statistics of entity rank and order categorical combinations for recommendation. From a double-sided cold start, with minimal supervision, Helios learns to recommend most salient anomalies at large-scale, and provides visualizations to security experts to explain rationale behind the recommendations. Our experiments show Helios to be suitable for large-scale applications: from cold starts, in less than 60 minutes, Helios can analyze roughly 4.6 billion records in logs of 400GB with about 300 million potential categorical combinations, then generate ranked categorical combinations as recommended discoveries. We also show that, even with limited computing resources, Helios accelerates unknown and unseen anomaly discovery process for SPM by 1 to 3 orders of magnitude, depending on use cases. In addition, Helios' design is flexible with metrics and measurement fields used for discoveries and recommendations. Overall, our system leads to more efficient and customizable SPM processes with faster discoveries of unseen and unknown anomalies.
Memshare: a Dynamic Multi-tenant Memory Key-value Cache
Venue: arXiv cs.OS 2016
Year: 2016

Web application performance is heavily reliant on the hit rate of memory-based caches. Current DRAM-based web caches statically partition their memory across multiple applications sharing the cache. This causes under utilization of memory which negatively impacts cache hit rates. We present Memshare, a novel web memory cache that dynamically manages memory across applications. Memshare provides a resource sharing model that guarantees private memory to different applications while dynamically allocating the remaining shared memory to optimize overall hit rate. Today's high cost of DRAM storage and the availability of high performance CPU and memory bandwidth, make web caches memory capacity bound. Memshare's log-structured design allows it to provide significantly higher hit rates and dynamically partition memory among applications at the expense of increased CPU and memory bandwidth consumption. In addition, Memshare allows applications to use their own eviction policy for their objects, independent of other applications. We implemented Memshare and ran it on a week-long trace from a commercial memcached provider. We demonstrate that Memshare increases the combined hit rate of the applications in the trace by an 6.1% (from 84.7% hit rate to 90.8% hit rate) and reduces the total number of misses by 39.7% without affecting system throughput or latency. Even for single-tenant applications, Memshare increases the average hit rate of the current state-of-the-art memory cache by an additional 2.7% on our real-world trace.
LP Rounding and Combinatorial Algorithms for Minimizing Active and Busy Time
Venue: arXiv cs.DS 2016
Year: 2016

We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline and required processing length. The jobs need to be scheduled on a machine so that at most g jobs are active at any given time. The duration for which a machine is active (i.e., "on") is referred to as its active time. The goal is to find a feasible schedule for all jobs, minimizing the total active time. When preemption is allowed at integer time points, we show that a minimal feasible schedule already yields a 3-approximation (and this bound is tight) and we further improve this to a 2-approximation via LP rounding techniques. Our second contribution is for the non-preemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NP-hard, we allow for an unbounded number of virtual machines, each having capacity of g. This problem is known as the busy time problem in the literature and a 4-approximation is known for this problem. We develop a new combinatorial algorithm that gives a 3-approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields an algorithm that is 2-approximate.
Price of Transparency in Strategic Machine Learning
Venue: arXiv cs.GT 2016
Year: 2016

Based on the observation that the transparency of an algorithm comes with a cost for the algorithm designer when the users (data providers) are strategic, this paper studies the impact of strategic intent of the users on the design and performance of transparent ML algorithms. We quantitatively study the {\bf price of transparency} in the context of strategic classification algorithms, by modeling the problem as a nonzero-sum game between the users and the algorithm designer. The cost of having a transparent algorithm is measured by a quantity, named here as price of transparency which is the ratio of the designer cost at the Stackelberg equilibrium, when the algorithm is transparent (which allows users to be strategic) to that of the setting where the algorithm is not transparent.
Opportunistic Device-to-Device Communication in Cellular networks: From Theory to Practice
Venue: arXiv cs.NI 2016
Year: 2016

This dissertation studies different aspects of D2D communications and its impact on the key performance indicators of the network. We design an architecture for the collaboration of cellular users by means of timely exploited D2D opportunities. We begin by presenting the analytical study on opportunistic outband D2D communications. The study reveals the great potential of opportunistic outband D2D communications for enhancing energy efficiency, fairness, and capacity of cellular networks when groups of D2D users can be form and managed in the cellular network. Then we introduce a protocol that is compatible with the latest release of IEEE and 3GPP standards and allows for implementation of our proposal in a today's cellular network. To validate our analytical findings, we use our experimental Software Defined Radio (SDR)-based testbed to further study our proposal in a real world scenario. The experimental results confirm the outstanding potential of opportunistic outband D2D communications. Finally, we investigate the performance merits and disadvantages of different D2D modes. Our investigation reveals, despite the common belief, that all D2D modes are complementary and their merits are scenario based.
The geometry of rank decompositions of matrix multiplication I: 2x2 matrices
Venue: arXiv cs.CC 2016
Year: 2016

This is the first in a series of papers on rank decompositions of the matrix multiplication tensor. In this paper we: establish general facts about rank decompositions of tensors, describe potential ways to search for new matrix multiplication decompositions, give a geometric proof of the theorem of Burichenko's theorem establishing the symmetry group of Strassen's algorithm, and present two particularly nice subfamilies in the Strassen family of decompositions.
A Proposed Algorithm for Minimum Vertex Cover Problem and its Testing
Venue: arXiv cs.DM 2016
Year: 2016

The paper presents an algorithm for minimum vertex cover problem, which is an NP-Complete problem. The algorithm computes a minimum vertex cover of each input simple graph. Tested by the attached MATLAB programs, Stage 1 of the algorithm is applicable to, i.e., yields a proved minimum vertex cover for, about 99.99% of the tested 610,000 graphs of order 16 and 99.67% of the tested 1,200 graphs of order 32, and Stage 2 of the algorithm is applicable to all of the above tested graphs. All of the tested graphs are randomly generated graphs of random "edge density" or in other words, random probability of each edge. It is proved that Stage 1 and Stage 2 of the algorithm run in $O(n^{5+logn})$ and $O(n^{3(5+logn)/2})$ time respectively, where $n$ is the order of input graph. Because there is no theoretical proof yet that Stage 2 is applicable to all graphs, further stages of the algorithm are proposed, which are in a general form that is consistent with Stages 1 and 2.
Word Embeddings to Enhance Twitter Gang Member Profile Identification
Venue: arXiv cs.SI 2016
Year: 2016

Gang affiliates have joined the masses who use social media to share thoughts and actions publicly. Interestingly, they use this public medium to express recent illegal actions, to intimidate others, and to share outrageous images and statements. Agencies able to unearth these profiles may thus be able to anticipate, stop, or hasten the investigation of gang-related crimes. This paper investigates the use of word embeddings to help identify gang members on Twitter. Building on our previous work, we generate word embeddings that translate what Twitter users post in their profile descriptions, tweets, profile images, and linked YouTube content to a real vector format amenable for machine learning classification. Our experimental results show that pre-trained word embeddings can boost the accuracy of supervised learning algorithms trained over gang members social media posts.