OpenRaiser/Intern-Atlas huggingface dataset:
Dropout Rademacher Complexity of Deep Neural Networks
Venue: arXiv cs.NE 2014
Year: 2014

Great successes of deep neural networks have been witnessed in various real applications. Many algorithmic and implementation techniques have been developed, however, theoretical understanding of many aspects of deep neural networks is far from clear. A particular interesting issue is the usefulness of dropout, which was motivated from the intuition of preventing complex co-adaptation of feature detectors. In this paper, we study the Rademacher complexity of different types of dropout, and our theoretical results disclose that for shallow neural networks (with one or none hidden layer) dropout is able to reduce the Rademacher complexity in polynomial, whereas for deep neural networks it can amazingly lead to an exponential reduction of the Rademacher complexity.
Efficient and Generalized Decentralized Monitoring of Regular Languages
Venue: arXiv cs.SE 2014
Year: 2014

The main contribution of this paper is an efficient and generalized decentralized monitoring algorithm allowing to detect satisfaction or violation of any regular specification by local monitors alone in a system without central observation point. Our algorithm does not assume any form of synchronization between system events and communication of monitors, uses state machines as underlying mechanism for efficiency, and tries to keep the number and size of messages exchanged between monitors to a minimum. We provide a full implementation of the algorithm with an open-source benchmark to evaluate its efficiency in terms of number, size of exchanged messages, and delay induced by communication between monitors. Experimental results demonstrate the effectiveness of our algorithm which outperforms the previous most general one along several (new) monitoring metrics.
Scalable Kernel Clustering: Approximate Kernel k-means
Venue: arXiv cs.CV 2014
Year: 2014

Kernel-based clustering algorithms have the ability to capture the non-linear structure in real world data. Among various kernel-based clustering algorithms, kernel k-means has gained popularity due to its simple iterative nature and ease of implementation. However, its run-time complexity and memory footprint increase quadratically in terms of the size of the data set, and hence, large data sets cannot be clustered efficiently. In this paper, we propose an approximation scheme based on randomization, called the Approximate Kernel k-means. We approximate the cluster centers using the kernel similarity between a few sampled points and all the points in the data set. We show that the proposed method achieves better clustering performance than the traditional low rank kernel approximation based clustering schemes. We also demonstrate that its running time and memory requirements are significantly lower than those of kernel k-means, with only a small reduction in the clustering quality on several public domain large data sets. We then employ ensemble clustering techniques to further enhance the performance of our algorithm.
Simple parallel and distributed algorithms for spectral graph sparsification
Venue: arXiv cs.DS 2014
Year: 2014

We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling. Leveraging the algorithms of Baswana and Sen for computing spanners, we obtain the first distributed spectral sparsification algorithm. We also obtain a parallel algorithm with improved work and time guarantees. Combining this algorithm with the parallel framework of Peng and Spielman for solving symmetric diagonally dominant linear systems, we get a parallel solver which is much closer to being practical and significantly more efficient in terms of the total work.
Graph Theory versus Minimum Rank for Index Coding
Venue: arXiv cs.IT 2014
Year: 2014

We obtain novel index coding schemes and show that they provably outperform all previously known graph theoretic bounds proposed so far. Further, we establish a rather strong negative result: all known graph theoretic bounds are within a logarithmic factor from the chromatic number. This is in striking contrast to minrank since prior work has shown that it can outperform the chromatic number by a polynomial factor in some cases. The conclusion is that all known graph theoretic bounds are not much stronger than the chromatic number.
A Hybrid Modified Semantic Matching Algorithm Based on Instances Detection With Case Study on Renewable Energy
Venue: arXiv cs.SE 2014
Year: 2014

This Matching input keywords with historical or information domain is an important point in modern computations in order to find the best match information domain for specific input queries. Matching algorithms represents hot area of researches in computer science and artificial intelligence. In the area of text matching, it is more reliable to study semantics of the pattern and query in terms of semantic matching. This paper improves the semantic matching results between input queries and information ontology domain. The contributed algorithm is a hybrid technique that is based on matching extracted instances from booth, the queries and in information domain. The instances extraction algorithm that is presented in this paper are contributed which is based on mathematical and statistical analysis of objects with respect to each other and also with respect to marked objects. The instances that are instances from the queries and information domain are subjected to semantic matching to find the best match, match percentage, and to improve the decision making process. An application case was studied in this paper which is related to renewable energy, where the input queries represents the customer requirements input and the knowledge domain is renewable energy vendors profiles. The comparison was made with most known recent matching researches.
Development of Interactive Instructional Model Using Augmented Reality based on Edutainment to Enhance Emotional Quotient
Venue: arXiv cs.CY 2014
Year: 2014

The research aims to develop an interactive instructional model using augmented reality based on edutainment to enhance emotional quotient and evaluate the model. Two phases of the research will be carried out: a development and an evaluation of the model. Samples are experts in the field of IT, child psychology, and 7th grade curriculum management. Ten experts are selected by purposive sampling method. The obtained data are analyzed using mean and standard deviation. The research result demonstrates the following findings: 1) The results of this research show that Model consists of 3 elements: IIAR, EduLA, and EQ. EQ is a means to assess EQ based on Time Series Experimental Design using 2 kinds of tools; i.e. EQ Assessment by programs in tablet computers, and EQ Assessment by behavioral observation. 2) The ten experts have evaluated the model and commented that the developed model showed high suitability.
Privacy Shielding against Mass Surveillance
Venue: arXiv cs.CY 2014
Year: 2014

Privacy Shielding against Mass Surveillance provides a step by step tactical approach to protecting the privacy of all the users of the internet from mass surveillance programs by the governments and other state agencies. Protection of privacy is of prime importance and Privacy Shielding provides the right means against mass surveillance programs and from malicious users trying to gain access to your systems. Although protection is difficult when massive government agencies like the National Security Agency and The Government Communications Headquarters target internet users for surveillance, it is possible because the target is not you as an individual but the entire mass as a whole. With the right approach and a broad perspective of the term Privacy, it is possible for one to freely access and share information over the internet without being victims of surveillance.
Connecting Spiking Neurons to a Spiking Memristor Network Changes the Memristor Dynamics
Venue: arXiv cs.ET 2014
Year: 2014

Memristors have been suggested as neuromorphic computing elements. Spike-time dependent plasticity and the Hodgkin-Huxley model of the neuron have both been modelled effectively by memristor theory. The d.c. response of the memristor is a current spike. Based on these three facts we suggest that memristors are well-placed to interface directly with neurons. In this paper we show that connecting a spiking memristor network to spiking neuronal cells causes a change in the memristor network dynamics by: removing the memristor spikes, which we show is due to the effects of connection to aqueous medium; causing a change in current decay rate consistent with a change in memristor state; presenting more-linear $I-t$ dynamics; and increasing the memristor spiking rate, as a consequence of interaction with the spiking neurons. This demonstrates that neurons are capable of communicating directly with memristors, without the need for computer translation.
Is Spiking Logic the Route to Memristor-Based Computers?
Venue: arXiv cs.ET 2014
Year: 2014

Memristors have been suggested as a novel route to neuromorphic computing based on the similarity between neurons (synapses and ion pumps) and memristors. The D.C. action of the memristor is a current spike, which we think will be fruitful for building memristor computers. In this paper, we introduce 4 different logical assignations to implement sequential logic in the memristor and introduce the physical rules, summation, `bounce-back', directionality and `diminishing returns', elucidated from our investigations. We then demonstrate how memristor sequential logic works by instantiating a NOT gate, an AND gate and a Full Adder with a single memristor. The Full Adder makes use of the memristor's memory to add three binary values together and outputs the value, the carry digit and even the order they were input in.
Between Linearizability and Quiescent Consistency: Quantitative Quiescent Consistency
Venue: arXiv cs.PL 2014
Year: 2014

Linearizability is the de facto correctness criterion for concurrent data structures. Unfortunately, linearizability imposes a performance penalty which scales linearly in the number of contending threads. Quiescent consistency is an alternative criterion which guarantees that a concurrent data structure behaves correctly when accessed sequentially. Yet quiescent consistency says very little about executions that have any contention. We define quantitative quiescent consistency (QQC), a relaxation of linearizability where the degree of relaxation is proportional to the degree of contention. When quiescent, no relaxation is allowed, and therefore QQC refines quiescent consistency, unlike other proposed relaxations of linearizability. We show that high performance counters and stacks designed to satisfy quiescent consistency continue to satisfy QQC. The precise assumptions under which QQC holds provides fresh insight on these structures. To demonstrate the robustness of QQC, we provide three natural characterizations and prove compositionality.
How to Kill Epsilons with a Dagger -- A Coalgebraic Take on Systems with Algebraic Label Structure
Venue: arXiv cs.LO 2014
Year: 2014

We propose an abstract framework for modeling state-based systems with internal behavior as e.g. given by silent or $ε$-transitions. Our approach employs monads with a parametrized fixpoint operator $\dagger$ to give a semantics to those systems and implement a sound procedure of abstraction of the internal transitions, whose labels are seen as the unit of a free monoid. More broadly, our approach extends the standard coalgebraic framework for state-based systems by taking into account the algebraic structure of the labels of their transitions. This allows to consider a wide range of other examples, including Mazurkiewicz traces for concurrent systems.
Notes on the existence of solutions in the pairwise comparisons method using the Heuristic Rating Estimation approach
Venue: arXiv cs.DM 2014
Year: 2014

Pairwise comparisons are a well-known method for modelling of the subjective preferences of a decision maker. A popular implementation of the method is based on solving an eigenvalue problem for M - the matrix of pairwise comparisons. This does not take into account the actual values of preference. The Heuristic Rating Estimation (HRE) approach is a modification of this method in which allows modelling of the reference values. To determine the relative order of preferences is to solve a certain linear equation system defined by the matrix A and the constant term vector b (both derived from M). The article explores the properties of these equation systems. In particular, it is proven that for some small data inconsistency the A matrix is an M-matrix, hence the equation proposed by the HRE approach has a unique strictly positive solution.
A propositional system induced by Japaridze's approach to IF logic
Venue: arXiv cs.LO 2014
Year: 2014

Cirquent calculus is a new proof-theoretic and semantic approach introduced for the needs of computability logic by G.Japaridze, who also showed that, through cirquent calculus, one can capture, refine and generalize independence-friendly (IF) logic. Specifically, the approach allows us to account for independence from propositional connectives in the same spirit as the traditional IF logic accounts for independence from quantifiers. Japaridze's treatment of IF logic, however, was purely semantical, and no deductive system was proposed. The present paper constructs a formal system sound and complete w.r.t. the propositional fragment of Japaridze's cirquent-based semantics for IF logic. Such a system can thus be considered an axiomatization of purely propositional IF logic in its full generality.
On the Phase Space of Block-Hiding Strategies in Bitcoin-like networks
Venue: arXiv cs.CR 2014
Year: 2014

We calculate the probability of success of block-hiding mining strategies in Bitcoin-like networks. These strategies involve building a secret branch of the block-tree and publishing it opportunistically, aiming to replace the top of the main branch and rip the reward associated with the secretly mined blocks. We identify two types of block-hiding strategies and chart the parameter space where those are more beneficial than the standard mining strategy described in Nakamoto's paper. Our analysis suggests a generalization of the notion of the relative hashing power as a measure for a miner's influence on the network. Block-hiding strategies are beneficial only when this measure of influence exceeds a certain threshold.
Guided Support for Collaborative Modeling, Enactment and Simulation of Software Development Processes
Venue: arXiv cs.SE 2014
Year: 2014

Recently, the awareness of the importance of distributed software development has been growing in the software engineering community. Economic constraints, more and more outsourcing of development activities, and the increasing spatial distribution of companies come along with challenges of how to organize distributed development. In this article, we reason that a common process understanding is mandatory for successful distributed development. Integrated process planning, guidance and enactment are seen as enabling technologies to reach a unique process view. We sketch a synthesis of the software process modeling environment SPEARMINT and the XCHIPS system for web-based process support. Hereby, planners and developers are provided with collaborative planning and enactment support and advanced process guidance via electronic process guides (EPGs). We describe the usage of this integrated environment by using a case study for the development of a learning system.
Minimum Entropy Submodular Optimization (and Fairness in Cooperative Games)
Venue: arXiv cs.DS 2014
Year: 2014

We study minimum entropy submodular optimization, a common generalization of the minimum entropy set cover problem, studied earlier by Cardinal et al., and the submodular set cover problem. We give a general bound of the approximation performance of the greedy algorithm using an approach that can be interpreted in terms of a particular type of biased network flows. As an application we rederive known results for the Minimum Entropy Set Cover and Minimum Entropy Orientation problems, and obtain a nontrivial bound for a new problem called the Minimum Entropy Spanning Tree problem. The problem can be applied to (and is partly motivated by) the definition of worst-case approaches to fairness in concave cooperative games, similar to the notion of price of anarchy in noncooperative settings.
Incremental Entity Resolution from Linked Documents
Venue: arXiv cs.DB 2014
Year: 2014

In many government applications we often find that information about entities, such as persons, are available in disparate data sources such as passports, driving licences, bank accounts, and income tax records. Similar scenarios are commonplace in large enterprises having multiple customer, supplier, or partner databases. Each data source maintains different aspects of an entity, and resolving entities based on these attributes is a well-studied problem. However, in many cases documents in one source reference those in others; e.g., a person may provide his driving-licence number while applying for a passport, or vice-versa. These links define relationships between documents of the same entity (as opposed to inter-entity relationships, which are also often used for resolution). In this paper we describe an algorithm to cluster documents that are highly likely to belong to the same entity by exploiting inter-document references in addition to attribute similarity. Our technique uses a combination of iterative graph-traversal, locality-sensitive hashing, iterative match-merge, and graph-clustering to discover unique entities based on a document corpus. A unique feature of our technique is that new sets of documents can be added incrementally while having to re-resolve only a small subset of a previously resolved entity-document collection. We present performance and quality results on two data-sets: a real-world database of companies and a large synthetically generated `population' database. We also demonstrate benefit of using inter-document references for clustering in the form of enhanced recall of documents for resolution.
Caching and Coded Multicasting: Multiple Groupcast Index Coding
Venue: arXiv cs.IT 2014
Year: 2014

The capacity of caching networks has received considerable attention in the past few years. A particularly studied setting is the case of a single server (e.g., a base station) and multiple users, each of which caches segments of files in a finite library. Each user requests one (whole) file in the library and the server sends a common coded multicast message to satisfy all users at once. The problem consists of finding the smallest possible codeword length to satisfy such requests. In this paper we consider the generalization to the case where each user places $L \geq 1$ requests. The obvious naive scheme consists of applying $L$ times the order-optimal scheme for a single request, obtaining a linear in $L$ scaling of the multicast codeword length. We propose a new achievable scheme based on multiple groupcast index coding that achieves a significant gain over the naive scheme. Furthermore, through an information theoretic converse we find that the proposed scheme is approximately optimal within a constant factor of (at most) $18$.
A Powerful Genetic Algorithm for Traveling Salesman Problem
Venue: arXiv cs.NE 2014
Year: 2014

This paper presents a powerful genetic algorithm(GA) to solve the traveling salesman problem (TSP). To construct a powerful GA, I use edge swapping(ES) with a local search procedure to determine good combinations of building blocks of parent solutions for generating even better offspring solutions. Experimental results on well studied TSP benchmarks demonstrate that the proposed GA is competitive in finding very high quality solutions on instances with up to 16,862 cities.
Managing information and knowledge sharing cultures in higher educations institutions
Venue: arXiv cs.CY 2014
Year: 2014

Information and knowledge (IK) are very important for any institution including education higher institution. Those IK are stored in every single individual in organization in the form of experiences, skills, etc. The growth of the higher education institution nowadays relies on how an institution manage the dissemination of those IK over the organization by using information technology (IT). This article discusses several ways and tools for engaging persons in the organization to build sharing cultures. This article gives some view of freely availabe application over internet to be used for IK sharing cultures.
MICA: A fast short-read aligner that takes full advantage of Intel Many Integrated Core Architecture (MIC)
Venue: arXiv cs.DC 2014
Year: 2014

Background: Short-read aligners have recently gained a lot of speed by exploiting the massive parallelism of GPU. An uprising alternative to GPU is Intel MIC; supercomputers like Tianhe-2, currently top of TOP500, is built with 48,000 MIC boards to offer ~55 PFLOPS. The CPU-like architecture of MIC allows CPU-based software to be parallelized easily; however, the performance is often inferior to GPU counterparts as an MIC board contains only ~60 cores (while a GPU board typically has over a thousand cores). Results: To better utilize MIC-enabled computers for NGS data analysis, we developed a new short-read aligner MICA that is optimized in view of MICs limitation and the extra parallelism inside each MIC core. Experiments on aligning 150bp paired-end reads show that MICA using one MIC board is 4.9 times faster than the BWA-MEM (using 6-core of a top-end CPU), and slightly faster than SOAP3-dp (using a GPU). Furthermore, MICAs simplicity allows very efficient scale-up when multiple MIC boards are used in a node (3 cards give a 14.1-fold speedup over BWA-MEM). Summary: MICA can be readily used by MIC-enabled supercomputers for production purpose. We have tested MICA on Tianhe-2 with 90 WGS samples (17.47 Tera-bases), which can be aligned in an hour less than 400 nodes. MICA has impressive performance even though the current MIC is at its initial stage of development (the next generation of MIC has been announced to release in late 2014).
Fixed Error Asymptotics For Erasure and List Decoding
Venue: arXiv cs.IT 2014
Year: 2014

We derive the optimum second-order coding rates, known as second-order capacities, for erasure and list decoding. For erasure decoding for discrete memoryless channels, we show that second-order capacity is $\sqrt{V}Φ^{-1}(ε_t)$ where $V$ is the channel dispersion and $ε_t$ is the total error probability, i.e., the sum of the erasure and undetected errors. We show numerically that the expected rate at finite blocklength for erasures decoding can exceed the finite blocklength channel coding rate. We also show that the analogous result also holds for lossless source coding with decoder side information, i.e., Slepian-Wolf coding. For list decoding, we consider list codes of deterministic size that scales as $\exp(\sqrt{n}l)$ and show that the second-order capacity is $l+\sqrt{V}Φ^{-1}(ε)$ where $ε$ is the permissible error probability. We also consider lists of polynomial size $n^α$ and derive bounds on the third-order coding rate in terms of the order of the polynomial $α$. These bounds are tight for symmetric and singular channels. The direct parts of the coding theorems leverage on the simple threshold decoder and converses are proved using variants of the hypothesis testing converse.