OpenRaiser/Intern-Atlas huggingface dataset:
Entity Embeddings of Categorical Variables
Venue: arXiv cs.LG 2016
Year: 2016

We map categorical variables in a function approximation problem into Euclidean spaces, which are the entity embeddings of the categorical variables. The mapping is learned by a neural network during the standard supervised training process. Entity embedding not only reduces memory usage and speeds up neural networks compared with one-hot encoding, but more importantly by mapping similar values close to each other in the embedding space it reveals the intrinsic properties of the categorical variables. We applied it successfully in a recent Kaggle competition and were able to reach the third position with relative simple features. We further demonstrate in this paper that entity embedding helps the neural network to generalize better when the data is sparse and statistics is unknown. Thus it is especially useful for datasets with lots of high cardinality features, where other methods tend to overfit. We also demonstrate that the embeddings obtained from the trained neural network boost the performance of all tested machine learning methods considerably when used as the input features instead. As entity embedding defines a distance measure for categorical variables it can be used for visualizing categorical data and for data clustering.
evt_MNIST: A spike based version of traditional MNIST
Venue: arXiv cs.NE 2016
Year: 2016

Benchmarks and datasets have important role in evaluation of machine learning algorithms and neural network implementations. Traditional dataset for images such as MNIST is applied to evaluate efficiency of different training algorithms in neural networks. This demand is different in Spiking Neural Networks (SNN) as they require spiking inputs. It is widely believed, in the biological cortex the timing of spikes is irregular. Poisson distributions provide adequate descriptions of the irregularity in generating appropriate spikes. Here, we introduce a spike-based version of MNSIT (handwritten digits dataset),using Poisson distribution and show the Poissonian property of the generated streams. We introduce a new version of evt_MNIST which can be used for neural network evaluation.
A Hybrid Approach to Query Answering under Expressive Datalog+/-
Venue: arXiv cs.DB 2016
Year: 2016

Datalog+/- is a family of ontology languages that combine good computational properties with high expressive power. Datalog+/- languages are provably able to capture the most relevant Semantic Web languages. In this paper we consider the class of weakly-sticky (WS) Datalog+/- programs, which allow for certain useful forms of joins in rule bodies as well as extending the well-known class of weakly-acyclic TGDs. So far, only non-deterministic algorithms were known for answering queries on WS Datalog+/- programs. We present novel deterministic query answering algorithms under WS Datalog+/-. In particular, we propose: (1) a bottom-up grounding algorithm based on a query-driven chase, and (2) a hybrid approach based on transforming a WS program into a so-called sticky one, for which query rewriting techniques are known. We discuss how our algorithms can be optimized and effectively applied for query answering in real-world scenarios.
Word2VisualVec: Image and Video to Sentence Matching by Visual Feature Prediction
Venue: arXiv cs.CV 2016
Year: 2016

This paper strives to find the sentence best describing the content of an image or video. Different from existing works, which rely on a joint subspace for image / video to sentence matching, we propose to do so in a visual space only. We contribute Word2VisualVec, a deep neural network architecture that learns to predict a deep visual encoding of textual input based on sentence vectorization and a multi-layer perceptron. We thoroughly analyze its architectural design, by varying the sentence vectorization strategy, network depth and the deep feature to predict for image to sentence matching. We also generalize Word2VisualVec for matching a video to a sentence, by extending the predictive abilities to 3-D ConvNet features as well as a visual-audio representation. Experiments on four challenging image and video benchmarks detail Word2VisualVec's properties, capabilities for image and video to sentence matching, and on all datasets its state-of-the-art results.
Sparse p-Adic Data Coding for Computationally Efficient and Effective Big Data Analytics
Venue: arXiv cs.IT 2016
Year: 2016

We develop the theory and practical implementation of p-adic sparse coding of data. Rather than the standard, sparsifying criterion that uses the $L_0$ pseudo-norm, we use the p-adic norm. We require that the hierarchy or tree be node-ranked, as is standard practice in agglomerative and other hierarchical clustering, but not necessarily with decision trees. In order to structure the data, all computational processing operations are direct reading of the data, or are bounded by a constant number of direct readings of the data, implying linear computational time. Through p-adic sparse data coding, efficient storage results, and for bounded p-adic norm stored data, search and retrieval are constant time operations. Examples show the effectiveness of this new approach to content-driven encoding and displaying of data.
An Arithmetic Coding Scheme for Blocked-based Compressive Sensing of Images
Venue: arXiv cs.IT 2016
Year: 2016

Differential pulse-code modulation (DPCM) is recently coupled with uniform scalar quantization (SQ) to improve the rate-distortion (RD) performance for the block-based quantized compressive sensing (CS) of images. In this framework, for each block's CS measurements, a prediction is generated based on the reconstructed CS measurements of the previous blocks and subtracted from measurements of the current block in the measurement domain. The resulting residual is then quantized by uniform SQ to generate the quantization index. However, the entropy coding is still required to remove the statistical redundancies between the quantization indices and generate the bitstream. Thus, in this paper, we proposed an arithmetic coding scheme for the quantization index within DPCM-plus-SQ framework by analyzing their statistics. Experimental results demonstrate that further RD performance can be achieved compared to original DPCM-plus-SQ scheme and transform coefficient coding in CABAC.
Uniquely Restricted Matchings in Interval Graphs
Venue: arXiv cs.DM 2016
Year: 2016

A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. ("Uniquely restricted matchings", M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality "strong independent set" in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.
Extension Complexity of Independent Set Polytopes
Venue: arXiv cs.CC 2016
Year: 2016

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $Ω(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $Θ(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth.
On $r$-Guarding Thin Orthogonal Polygons
Venue: arXiv cs.CG 2016
Year: 2016

Guarding a polygon with few guards is an old and well-studied problem in computational geometry. Here we consider the following variant: We assume that the polygon is orthogonal and thin in some sense, and we consider a point $p$ to guard a point $q$ if and only if the minimum axis-aligned rectangle spanned by $p$ and $q$ is inside the polygon. A simple proof shows that this problem is NP-hard on orthogonal polygons with holes, even if the polygon is thin. If there are no holes, then a thin polygon becomes a tree polygon in the sense that the so-called dual graph of the polygon is a tree. It was known that finding the minimum set of $r$-guards is polynomial for tree polygons, but the run-time was $\tilde{O}(n^{17})$. We show here that with a different approach the running time becomes linear, answering a question posed by Biedl et al. (SoCG 2011). Furthermore, the approach is much more general, allowing to specify subsets of points to guard and guards to use, and it generalizes to polygons with $h$ holes or thickness $K$, becoming fixed-parameter tractable in $h+K$.
A Survey of Memristive Threshold Logic Circuits
Venue: arXiv cs.ET 2016
Year: 2016

In this paper, we review the different memristive threshold logic (MTL) circuits that are inspired from the synaptic action of flow of neurotransmitters in the biological brain. Brain like generalisation ability and area minimisation of these threshold logic circuits aim towards crossing the Moores law boundaries at device, circuits and systems levels.Fast switching memory, signal processing, control systems, programmable logic, image processing, reconfigurable computing, and pattern recognition are identified as some of the potential applications of MTL systems. The physical realization of nanoscale devices with memristive behaviour from materials like TiO2, ferroelectrics, silicon, and polymers has accelerated research effort in these application areas inspiring the scientific community to pursue design of high speed, low cost, low power and high density neuromorphic architectures.
Analytical Studies of Fragmented-Spectrum Multi-Level OFDM-CDMA Technique in Cognitive Radio Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we present a multi-user resource allocation framework using fragmented-spectrum synchronous OFDM-CDMA modulation over a frequency-selective fading channel. In particular, given pre-existing communications in the spectrum where the system is operating, a channel sensing and estimation method is used to obtain information of subcarrier availability. Given this information, some real-valued multi-level orthogonal codes, which are orthogonal codes with values of $\{\pm1,\pm2,\pm3,\pm4, ... \}$, are provided for emerging new users, i.e., cognitive radio users. Additionally, we have obtained a closed form expression for bit error rate of cognitive radio receivers in terms of detection probability of primary users, CR users' sensing time and CR users' signal to noise ratio. Moreover, simulation results obtained in this paper indicate the precision with which the analytical results have been obtained in modeling the aforementioned system.
Deep Convolutional Neural Networks and Data Augmentation for Acoustic Event Detection
Venue: arXiv cs.SD 2016
Year: 2016

We propose a novel method for Acoustic Event Detection (AED). In contrast to speech, sounds coming from acoustic events may be produced by a wide variety of sources. Furthermore, distinguishing them often requires analyzing an extended time period due to the lack of a clear sub-word unit. In order to incorporate the long-time frequency structure for AED, we introduce a convolutional neural network (CNN) with a large input field. In contrast to previous works, this enables to train audio event detection end-to-end. Our architecture is inspired by the success of VGGNet and uses small, 3x3 convolutions, but more depth than previous methods in AED. In order to prevent over-fitting and to take full advantage of the modeling capabilities of our network, we further propose a novel data augmentation method to introduce data variation. Experimental results show that our CNN significantly outperforms state of the art methods including Bag of Audio Words (BoAW) and classical CNNs, achieving a 16% absolute improvement.
How Many Cooks Spoil the Soup?
Venue: arXiv cs.DC 2016
Year: 2016

In this work, we study the following basic question: "How much parallelism does a distributed task permit?" Our definition of parallelism (or symmetry) here is not in terms of speed, but in terms of identical roles that processes have at the same time in the execution. We initiate this study in population protocols, a very simple model that not only allows for a straightforward definition of what a role is, but also encloses the challenge of isolating the properties that are due to the protocol from those that are due to the adversary scheduler, who controls the interactions between the processes. We (i) give a partial characterization of the set of predicates on input assignments that can be stably computed with maximum symmetry, i.e., $Θ(N_{min})$, where $N_{min}$ is the minimum multiplicity of a state in the initial configuration, and (ii) we turn our attention to the remaining predicates and prove a strong impossibility result for the parity predicate: the inherent symmetry of any protocol that stably computes it is upper bounded by a constant that depends on the size of the protocol.
An Approach to Find Missing Values in Medical Datasets
Venue: arXiv cs.DB 2016
Year: 2016

Mining medical datasets is a challenging problem before data mining researchers as these datasets have several hidden challenges compared to conventional datasets.Starting from the collection of samples through field experiments and clinical trials to performing classification,there are numerous challenges at every stage in the mining process. The preprocessing phase in the mining process itself is a challenging issue when, we work on medical datasets. One of the prime challenges in mining medical datasets is handling missing values which is part of preprocessing phase. In this paper, we address the issue of handling missing values in medical dataset consisting of categorical attribute values. The main contribution of this research is to use the proposed imputation measure to estimate and fix the missing values. We discuss a case study to demonstrate the working of proposed measure.
A Distributed Auctioneer for Resource Allocation in Decentralized Systems
Venue: arXiv cs.GT 2016
Year: 2016

In decentralized systems, nodes often need to coordinate to access shared resources in a fair manner. One approach to perform such arbitration is to rely on auction mechanisms. Although there is an extensive literature that studies auctions, most of these works assume the existence of a central, trusted auctioneer. Unfortunately, in fully decentralized systems, where the nodes that need to cooperate operate under separate spheres of control, such central trusted entity may not exist. Notable examples of such decentralized systems include community networks, clouds of clouds, cooperative nano data centres, among others. In this paper, we make theoretical and practical contributions to distribute the role of the auctioneer. From the theoretical perspective, we propose a framework of distributed simulations of the auctioneer that are Nash equilibria resilient to coalitions and asynchrony. From the practical perspective, our protocols leverage the distributed nature of the simulations to parallelise the execution. We have implemented a prototype that instantiates the framework for bandwidth allocation in community networks, and evaluated it in a real distributed setting.
Attributes for Improved Attributes: A Multi-Task Network for Attribute Classification
Venue: arXiv cs.CV 2016
Year: 2016

Attributes, or semantic features, have gained popularity in the past few years in domains ranging from activity recognition in video to face verification. Improving the accuracy of attribute classifiers is an important first step in any application which uses these attributes. In most works to date, attributes have been considered to be independent. However, we know this not to be the case. Many attributes are very strongly related, such as heavy makeup and wearing lipstick. We propose to take advantage of attribute relationships in three ways: by using a multi-task deep convolutional neural network (MCNN) sharing the lowest layers amongst all attributes, sharing the higher layers for related attributes, and by building an auxiliary network on top of the MCNN which utilizes the scores from all attributes to improve the final classification of each attribute. We demonstrate the effectiveness of our method by producing results on two challenging publicly available datasets.
Efficient estimation of probability of conflict between air traffic using Subset Simulation
Venue: arXiv cs.SY 2016
Year: 2016

This paper presents an efficient method for estimating the probability of conflict between air traffic within a block of airspace. Autonomous Sense-and-Avoid is an essential safety feature to enable Unmanned Air Systems to operate alongside other (manned or unmanned) air traffic. The ability to estimate probability of conflict between traffic is an essential part of Sense-and-Avoid. Such probabilities are typically very low. Evaluating low probabilities using naive Direct Monte Carlo generates a significant computational load. This paper applies a technique called Subset Simulation. The small failure probabilities are computed as a product of larger conditional failure probabilities, reducing the computational load whilst improving the accuracy of the probability estimates. The reduction in the number of samples required can be one or more orders of magnitude. The utility of the approach is demonstrated by modeling a series of conflicting and potentially conflicting scenarios based on the standard Rules of the Air.
Towards Real-time Simulation of Hyperelastic Materials
Venue: arXiv cs.GR 2016
Year: 2016

We present a new method for real-time physics-based simulation supporting many different types of hyperelastic materials. Previous methods such as Position Based or Projective Dynamics are fast, but support only limited selection of materials; even classical materials such as the Neo-Hookean elasticity are not supported. Recently, Xu et al. [2015] introduced new "spline-based materials" which can be easily controlled by artists to achieve desired animation effects. Simulation of these types of materials currently relies on Newton's method, which is slow, even with only one iteration per timestep. In this paper, we show that Projective Dynamics can be interpreted as a quasi-Newton method. This insight enables very efficient simulation of a large class of hyperelastic materials, including the Neo-Hookean, spline-based materials, and others. The quasi-Newton interpretation also allows us to leverage ideas from numerical optimization. In particular, we show that our solver can be further accelerated using L-BFGS updates (Limited-memory Broyden-Fletcher-Goldfarb-Shanno algorithm). Our final method is typically more than 10 times faster than one iteration of Newton's method without compromising quality. In fact, our result is often more accurate than the result obtained with one iteration of Newton's method. Our method is also easier to implement, implying reduced software development costs.
HybridRanker: Integrating network structure and disease knowledge to prioritize cancer candidate genes
Venue: arXiv cs.CE 2016
Year: 2016

One of the notable fields in studying the genetics of cancer is disease gene identification which affects disease treatment and drug discovery. Many researches have been done in this field. Genome-wide association studies (GWAS) are one of them that focus on the identification of diseases-susceptible loci on chromosomes. Recently, computational approaches, known as gene prioritization methods have been used to identify candidate disease genes. Gene prioritization methods integrate several data sources to discover and prioritize the most probable candidate disease genes. In this paper, we propose a prioritization method, called HybridRanker which is a network-based technique and it also uses experimental data to identify candidate cancer genes. We apply our proposed method on colorectal cancer data. It is notable to say that in HybridRanker, for considering both local and global network information of a protein-protein interaction network, different algorithms such as shortest-path, random walk with restart and network propagation are exploited. By using these algorithms, initial scores are given to genes within the network. Furthermore, by looking through diseases with similar symptoms and also comorbid diseases and by extracting their causing genes, the gene scores are recalculated. We also use gene-phenotype relations for an additional scoring of the candidate genes. Our method is validated and compared with other prioritization methods in leave one-out cross-validation and the comparison results show the better performance of the HybridRanker.
The Complexity of Rummikub Problems
Venue: arXiv cs.CC 2016
Year: 2016

Rummikub is a tile-based game in which each player starts with a hand of $14$ tiles. A tile has a value and a suit. The players form sets consisting of tiles with the same suit and consecutive values (runs) or tiles with the same value and different suits (groups). The corresponding optimization problem is, given a hand of tiles, to form valid sets such that the score (sum of tile values) is maximized. We first present an algorithm that solves this problem in polynomial time. Next, we analyze the impact on the computational complexity when we generalize over various input parameters. Finally, we attempt to better understand some aspects involved in human play by means of an experiment that considers counting problems related to the number of possible immediately winning hands.
A New Approach in Persian Handwritten Letters Recognition Using Error Correcting Output Coding
Venue: arXiv cs.CV 2016
Year: 2016

Classification Ensemble, which uses the weighed polling of outputs, is the art of combining a set of basic classifiers for generating high-performance, robust and more stable results. This study aims to improve the results of identifying the Persian handwritten letters using Error Correcting Output Coding (ECOC) ensemble method. Furthermore, the feature selection is used to reduce the costs of errors in our proposed method. ECOC is a method for decomposing a multi-way classification problem into many binary classification tasks; and then combining the results of the subtasks into a hypothesized solution to the original problem. Firstly, the image features are extracted by Principal Components Analysis (PCA). After that, ECOC is used for identification the Persian handwritten letters which it uses Support Vector Machine (SVM) as the base classifier. The empirical results of applying this ensemble method using 10 real-world data sets of Persian handwritten letters indicate that this method has better results in identifying the Persian handwritten letters than other ensemble methods and also single classifications. Moreover, by testing a number of different features, this paper found that we can reduce the additional cost in feature selection stage by using this method.