OpenRaiser/Intern-Atlas huggingface dataset:
Sparse Tensor Algebra as a Parallel Programming Model
Venue: arXiv cs.MS 2015
Year: 2015

Dense and sparse tensors allow the representation of most bulk data structures in computational science applications. We show that sparse tensor algebra can also be used to express many of the transformations on these datasets, especially those which are parallelizable. Tensor computations are a natural generalization of matrix and graph computations. We extend the usual basic operations of tensor summation and contraction to arbitrary functions, and further operations such as reductions and mapping. The expression of these transformations in a high-level sparse linear algebra domain specific language allows our framework to understand their properties at runtime to select the preferred communication-avoiding algorithm. To demonstrate the efficacy of our approach, we show how key graph algorithms as well as common numerical kernels can be succinctly expressed using our interface and provide performance results of a general library implementation.
The cost of reading research. A study of Computer Science publication venues
Venue: arXiv cs.DL 2015
Year: 2015

What does the cost of academic publishing look like to the common researcher today? Our goal is to convey the current state of academic publishing, specifically in regards to the field of computer science and provide analysis and data to be used as a basis for future studies. We will focus on author and reader costs as they are the primary points of interaction within the publishing world. In this work, we restrict our focus to only computer science in order to make the data collection more feasible (the authors are computer scientists) and hope future work can analyze and collect data across all academic fields.
Implicit Sparse Code Hashing
Venue: arXiv cs.CV 2015
Year: 2015

We address the problem of converting large-scale high-dimensional image data into binary codes so that approximate nearest-neighbor search over them can be efficiently performed. Different from most of the existing unsupervised approaches for yielding binary codes, our method is based on a dimensionality-reduction criterion that its resulting mapping is designed to preserve the image relationships entailed by the inner products of sparse codes, rather than those implied by the Euclidean distances in the ambient space. While the proposed formulation does not require computing any sparse codes, the underlying computation model still inevitably involves solving an unmanageable eigenproblem when extremely high-dimensional descriptors are used. To overcome the difficulty, we consider the column-sampling technique and presume a special form of rotation matrix to facilitate subproblem decomposition. We test our method on several challenging image datasets and demonstrate its effectiveness by comparing with state-of-the-art binary coding techniques.
On the diameter of hyperbolic random graphs
Venue: arXiv cs.DM 2015
Year: 2015

Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing performs close to optimal (Boguná, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent $β$ and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is $\mathcal O((\log n)^{32/((3-β)(5-β)) + 1})$ (Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of $\mathcal O((\log n)^{2/(3-β)})$ and a lower bound of $Ω(\log n)$.
Transfer Learning in Brain-Computer Interfaces
Venue: arXiv cs.HC 2015
Year: 2015

The performance of brain-computer interfaces (BCIs) improves with the amount of available training data, the statistical distribution of this data, however, varies across subjects as well as across sessions within individual subjects, limiting the transferability of training data or trained models between them. In this article, we review current transfer learning techniques in BCIs that exploit shared structure between training data of multiple subjects and/or sessions to increase performance. We then present a framework for transfer learning in the context of BCIs that can be applied to any arbitrary feature space, as well as a novel regression estimation method that is specifically designed for the structure of a system based on the electroencephalogram (EEG). We demonstrate the utility of our framework and method on subject-to-subject transfer in a motor-imagery paradigm as well as on session-to-session transfer in one patient diagnosed with amyotrophic lateral sclerosis (ALS), showing that it is able to outperform other comparable methods on an identical dataset.
A Multi-Agent Framework for Testing Distributed Systems
Venue: arXiv cs.DC 2015
Year: 2015

Software testing is a very expensive and time consuming process. It can account for up to 50% of the total cost of the software development. Distributed systems make software testing a daunting task. The research described in this paper investigates a novel multi-agent framework for testing 3-tier distributed systems. This paper describes the framework architecture as well as the communication mechanism among agents in the architecture. Web-based application is examined as a case study to validate the proposed framework. The framework is considered as a step forward to automate testing for distributed systems in order to enhance their reliability within an acceptable range of cost and time.
Discrete and Continuous Systems of Logic in Nuclear Magnetic Resonance
Venue: arXiv cs.ET 2015
Year: 2015

We implement several non-binary logic systems using the spin dynamics of nuclear spins in nuclear magnetic resonance (NMR). The NMR system is a suitable test system because of its high degree of experimental control; findings from NMR implementations are relevant for other computational platforms exploiting particles with spin, such as electrons or photons. While we do not expect the NMR system to become a practical computational device, it is uniquely useful to explore strengths and weaknesses of unconventional computational approaches, such as non-binary logic.
Rethinking the Inception Architecture for Computer Vision
Venue: arXiv cs.CV 2015
Year: 2015

Convolutional networks are at the core of most state-of-the-art computer vision solutions for a wide variety of tasks. Since 2014 very deep convolutional networks started to become mainstream, yielding substantial gains in various benchmarks. Although increased model size and computational cost tend to translate to immediate quality gains for most tasks (as long as enough labeled data is provided for training), computational efficiency and low parameter count are still enabling factors for various use cases such as mobile vision and big-data scenarios. Here we explore ways to scale up networks in ways that aim at utilizing the added computation as efficiently as possible by suitably factorized convolutions and aggressive regularization. We benchmark our methods on the ILSVRC 2012 classification challenge validation set demonstrate substantial gains over the state of the art: 21.2% top-1 and 5.6% top-5 error for single frame evaluation using a network with a computational cost of 5 billion multiply-adds per inference and with using less than 25 million parameters. With an ensemble of 4 models and multi-crop evaluation, we report 3.5% top-5 error on the validation set (3.6% error on the test set) and 17.3% top-1 error on the validation set.
HBTM: A Heartbeat-based Behavior Detection Mechanism for POSIX Threads and OpenMP Applications
Venue: arXiv cs.DC 2015
Year: 2015

Extreme-scale computing involves hundreds of millions of threads with multi-level parallelism running on large-scale hierarchical and heterogeneous hardware. In POSIX threads and OpenMP applications, some key behaviors occurring in runtime such as thread failure, busy waiting, and exit need to be accurately and timely detected. However, for the most of these applications, there are lack of unified and efficient detection mechanisms to do this. In this paper, a heartbeat-based behavior detection mechanism for POSIX threads (Pthreads) and OpenMP applications (HBTM) is proposed. In the design, two types of implementations are conducted, centralized and decentralized respectively. In both implementations, unified API has been designed to guarantee the generality of the mechanism. Meanwhile, a ring-based detection algorithm is designed to ease the burden of the centra thread at runtime. To evaluate the mechanism, the NAS Parallel Benchmarks (NPB) are used to test the performance of the HBTM. The experimental results show that the HBTM supports detection of behaviors of POSIX threads and OpenMP applications while acquiring a short latency and near 1% overhead.
Duelist Algorithm: An Algorithm Inspired by How Duelist Improve Their Capabilities in a Duel
Venue: arXiv cs.NE 2015
Year: 2015

This paper proposes an optimization algorithm based on how human fight and learn from each duelist. Since this algorithm is based on population, the proposed algorithm starts with an initial set of duelists. The duel is to determine the winner and loser. The loser learns from the winner, while the winner try their new skill or technique that may improve their fighting capabilities. A few duelists with highest fighting capabilities are called as champion. The champion train a new duelists such as their capabilities. The new duelist will join the tournament as a representative of each champion. All duelist are re-evaluated, and the duelists with worst fighting capabilities is eliminated to maintain the amount of duelists. Two optimization problem is applied for the proposed algorithm, together with genetic algorithm, particle swarm optimization and imperialist competitive algorithm. The results show that the proposed algorithm is able to find the better global optimum and faster iteration.
Annotating Character Relationships in Literary Texts
Venue: arXiv cs.CL 2015
Year: 2015

We present a dataset of manually annotated relationships between characters in literary texts, in order to support the training and evaluation of automatic methods for relation type prediction in this domain (Makazhanov et al., 2014; Kokkinakis, 2013) and the broader computational analysis of literary character (Elson et al., 2010; Bamman et al., 2014; Vala et al., 2015; Flekova and Gurevych, 2015). In this work, we solicit annotations from workers on Amazon Mechanical Turk for 109 texts ranging from Homer's _Iliad_ to Joyce's _Ulysses_ on four dimensions of interest: for a given pair of characters, we collect judgments as to the coarse-grained category (professional, social, familial), fine-grained category (friend, lover, parent, rival, employer), and affinity (positive, negative, neutral) that describes their primary relationship in a text. We do not assume that this relationship is static; we also collect judgments as to whether it changes at any point in the course of the text.
A Mutual Information Approach to Calculating Nonlinearity
Venue: arXiv cs.IT 2015
Year: 2015

A new method to measure nonlinear dependence between two variables is described using mutual information to analyze the separate linear and nonlinear components of dependence. This technique, which gives an exact value for the proportion of linear dependence, is then compared with another common test for linearity, the Brock, Dechert and Scheinkman (BDS) test.
Spin-Torque Sensors for Energy Efficient High Speed Long Interconnects
Venue: arXiv cs.ET 2015
Year: 2015

In this paper, we propose a Spin-Torque (ST) based sensing scheme that can enable energy efficient multi-bit long distance interconnect architectures. Current-mode interconnects have recently been proposed to overcome the performance degradations associated with conventional voltage mode Copper (Cu) interconnects. However, the performance of current mode interconnects are limited by analog current sensing transceivers and equalization circuits. As a solution, we propose the use of ST based receivers that use Magnetic Tunnel Junctions (MTJ) and simple digital components for current-to-voltage conversion and do not require analog transceivers. We incorporate Spin-Hall Metal (SHM) in our design to achieve high speed sensing. We show both single and multi-bit operations that reveal major benefits at higher speeds. Our simulation results show that the proposed technique consumes only 3.93-4.72 fJ/bit/mm energy while operating at 1-2 Gbits/sec; which is considerably better than existing charge based interconnects. In addition, Voltage Controlled Magnetic Anisotropy (VCMA) can reduce the required current at the sensor. With the inclusion of VCMA, the energy consumption can be further reduced to 2.02-4.02 fJ/bit/mm
On the Degrees of Freedom of Signals on Graphs
Venue: arXiv cs.IT 2015
Year: 2015

Continuous-time signals are well known for not being perfectly localized in both time and frequency domains. Conversely, a signal defined over the vertices of a graph can be perfectly localized in both vertex and frequency domains. We derive the conditions ensuring the validity of this property and then, building on this theory, we provide the conditions for perfect reconstruction of a graph signal from its samples. Next, we provide a finite step algorithm for the reconstruction of a band-limited signal from its samples and then we show the effect of sampling a non perfectly band-limited signal and show how to select the bandwidth that minimizes the mean square reconstruction error.
Compressive hyperspectral imaging via adaptive sampling and dictionary learning
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a new sampling strategy for hyperspectral signals that is based on dictionary learning and singular value decomposition (SVD). Specifically, we first learn a sparsifying dictionary from training spectral data using dictionary learning. We then perform an SVD on the dictionary and use the first few left singular vectors as the rows of the measurement matrix to obtain the compressive measurements for reconstruction. The proposed method provides significant improvement over the conventional compressive sensing approaches. The reconstruction performance is further improved by reconditioning the sensing matrix using matrix balancing. We also demonstrate that the combination of dictionary learning and SVD is robust by applying them to different datasets.
A context-aware matching game for user association in wireless small cell networks
Venue: arXiv cs.NI 2015
Year: 2015

Small cell networks are seen as a promising technology for boosting the performance of future wireless networks. In this paper, we propose a novel context-aware user-cell association approach for small cell networks that exploits the information about the velocity and trajectory of the users while also taking into account their quality of service (QoS) requirements. We formulate the problem in the framework of matching theory with externalities in which the agents, namely users and small cell base stations (SCBSs), have strict interdependent preferences over the members of the opposite set. To solve the problem, we propose a novel algorithm that leads to a stable matching among the users and SCBSs. We show that the proposed approach can better balance the traffic among the cells while also satisfying the QoS of the users. Simulation results show that the proposed matching algorithm yields significant performance advantages relative to traditional context-unaware approaches.
Bayesian Matrix Completion via Adaptive Relaxed Spectral Regularization
Venue: arXiv cs.NA 2015
Year: 2015

Bayesian matrix completion has been studied based on a low-rank matrix factorization formulation with promising results. However, little work has been done on Bayesian matrix completion based on the more direct spectral regularization formulation. We fill this gap by presenting a novel Bayesian matrix completion method based on spectral regularization. In order to circumvent the difficulties of dealing with the orthonormality constraints of singular vectors, we derive a new equivalent form with relaxed constraints, which then leads us to design an adaptive version of spectral regularization feasible for Bayesian inference. Our Bayesian method requires no parameter tuning and can infer the number of latent factors automatically. Experiments on synthetic and real datasets demonstrate encouraging results on rank recovery and collaborative filtering, with notably good results for very sparse matrices.
Deep Reinforcement Learning with Attention for Slate Markov Decision Processes with High-Dimensional States and Actions
Venue: arXiv cs.AI 2015
Year: 2015

Many real-world problems come with action spaces represented as feature vectors. Although high-dimensional control is a largely unsolved problem, there has recently been progress for modest dimensionalities. Here we report on a successful attempt at addressing problems of dimensionality as high as $2000$, of a particular form. Motivated by important applications such as recommendation systems that do not fit the standard reinforcement learning frameworks, we introduce Slate Markov Decision Processes (slate-MDPs). A Slate-MDP is an MDP with a combinatorial action space consisting of slates (tuples) of primitive actions of which one is executed in an underlying MDP. The agent does not control the choice of this executed action and the action might not even be from the slate, e.g., for recommendation systems for which all recommendations can be ignored. We use deep Q-learning based on feature representations of both the state and action to learn the value of whole slates. Unlike existing methods, we optimize for both the combinatorial and sequential aspects of our tasks. The new agent's superiority over agents that either ignore the combinatorial or sequential long-term value aspect is demonstrated on a range of environments with dynamics from a real-world recommendation system. Further, we use deep deterministic policy gradients to learn a policy that for each position of the slate, guides attention towards the part of the action space in which the value is the highest and we only evaluate actions in this area. The attention is used within a sequentially greedy procedure leveraging submodularity. Finally, we show how introducing risk-seeking can dramatically improve the agents performance and ability to discover more far reaching strategies.
Building Memory with Concept Learning Capabilities from Large-scale Knowledge Base
Venue: arXiv cs.CL 2015
Year: 2015

We present a new perspective on neural knowledge base (KB) embeddings, from which we build a framework that can model symbolic knowledge in the KB together with its learning process. We show that this framework well regularizes previous neural KB embedding model for superior performance in reasoning tasks, while having the capabilities of dealing with unseen entities, that is, to learn their embeddings from natural language descriptions, which is very like human's behavior of learning semantic concepts.
Nearly optimal separations between communication (or query) complexity and partitions
Venue: arXiv cs.CC 2015
Year: 2015

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and the author. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from lifting the query separation to communication complexity.
Toward a Taxonomy and Computational Models of Abnormalities in Images
Venue: arXiv cs.CV 2015
Year: 2015

The human visual system can spot an abnormal image, and reason about what makes it strange. This task has not received enough attention in computer vision. In this paper we study various types of atypicalities in images in a more comprehensive way than has been done before. We propose a new dataset of abnormal images showing a wide range of atypicalities. We design human subject experiments to discover a coarse taxonomy of the reasons for abnormality. Our experiments reveal three major categories of abnormality: object-centric, scene-centric, and contextual. Based on this taxonomy, we propose a comprehensive computational model that can predict all different types of abnormality in images and outperform prior arts in abnormality recognition.
Proposition of a Theoretical Model for Missing Data Imputation using Deep Learning and Evolutionary Algorithms
Venue: arXiv cs.NE 2015
Year: 2015

In the last couple of decades, there has been major advancements in the domain of missing data imputation. The techniques in the domain include amongst others: Expectation Maximization, Neural Networks with Evolutionary Algorithms or optimization techniques and K-Nearest Neighbor approaches to solve the problem. The presence of missing data entries in databases render the tasks of decision-making and data analysis nontrivial. As a result this area has attracted a lot of research interest with the aim being to yield accurate and time efficient and sensitive missing data imputation techniques especially when time sensitive applications are concerned like power plants and winding processes. In this article, considering arbitrary and monotone missing data patterns, we hypothesize that the use of deep neural networks built using autoencoders and denoising autoencoders in conjunction with genetic algorithms, swarm intelligence and maximum likelihood estimator methods as novel data imputation techniques will lead to better imputed values than existing techniques. Also considered are the missing at random, missing completely at random and missing not at random missing data mechanisms. We also intend to use fuzzy logic in tandem with deep neural networks to perform the missing data imputation tasks, as well as different building blocks for the deep neural networks like Stacked Restricted Boltzmann Machines and Deep Belief Networks to test our hypothesis. The motivation behind this article is the need for missing data imputation techniques that lead to better imputed values than existing methods with higher accuracies and lower errors.