OpenRaiser/Intern-Atlas huggingface dataset:
Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms
Venue: arXiv cs.DS 2014
Year: 2014

Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notion of parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for \textsc{Harmless Set}, \textsc{Differential} and \textsc{Multiple Nonblocker}, all of them can be considered in the context of securing networks or information propagation.
Nearest Keyword Set Search in Multi-dimensional Datasets
Venue: arXiv cs.DB 2014
Year: 2014

Keyword-based search in text-rich multi-dimensional datasets facilitates many novel applications and tools. In this paper, we consider objects that are tagged with keywords and are embedded in a vector space. For these datasets, we study queries that ask for the tightest groups of points satisfying a given set of keywords. We propose a novel method called ProMiSH (Projection and Multi Scale Hashing) that uses random projection and hash-based index structures, and achieves high scalability and speedup. We present an exact and an approximate version of the algorithm. Our empirical studies, both on real and synthetic datasets, show that ProMiSH has a speedup of more than four orders over state-of-the-art tree-based techniques. Our scalability tests on datasets of sizes up to 10 million and dimensions up to 100 for queries having up to 9 keywords show that ProMiSH scales linearly with the dataset size, the dataset dimension, the query size, and the result size.
A study on effectiveness of extreme learning machine
Venue: arXiv cs.NE 2014
Year: 2014

Extreme learning machine (ELM), proposed by Huang et al., has been shown a promising learning algorithm for single-hidden layer feedforward neural networks (SLFNs). Nevertheless, because of the random choice of input weights and biases, the ELM algorithm sometimes makes the hidden layer output matrix H of SLFN not full column rank, which lowers the effectiveness of ELM. This paper discusses the effectiveness of ELM and proposes an improved algorithm called EELM that makes a proper selection of the input weights and bias before calculating the output weights, which ensures the full column rank of H in theory. This improves to some extend the learning rate (testing accuracy, prediction accuracy, learning time) and the robustness property of the networks. The experimental results based on both the benchmark function approximation and real-world problems including classification and regression applications show the good performances of EELM.
Real-Time Misbehavior Detection in IEEE 802.11e Based WLANs
Venue: arXiv cs.NI 2014
Year: 2014

The Enhanced Distributed Channel Access (EDCA) specification in the IEEE 802.11e standard supports heterogeneous backoff parameters and arbitration inter-frame space (AIFS), which makes a selfish node easy to manipulate these parameters and misbehave. In this case, the network-wide fairness cannot be achieved any longer. Many existing misbehavior detectors, primarily designed for legacy IEEE 802.11 networks, become inapplicable in such a heterogeneous network configuration. In this paper, we propose a novel real-time hybrid-share (HS) misbehavior detector for IEEE 802.11e based wireless local area networks (WLANs). The detector keeps updating its state based on every successful transmission and makes detection decisions by comparing its state with a threshold. We develop mathematical analysis of the detector performance in terms of both false positive rate and average detection rate. Numerical results show that the proposed detector can effectively detect both contention window based and AIFS based misbehavior with only a short detection window.
Mining Mid-level Features for Action Recognition Based on Effective Skeleton Representation
Venue: arXiv cs.CV 2014
Year: 2014

Recently, mid-level features have shown promising performance in computer vision. Mid-level features learned by incorporating class-level information are potentially more discriminative than traditional low-level local features. In this paper, an effective method is proposed to extract mid-level features from Kinect skeletons for 3D human action recognition. Firstly, the orientations of limbs connected by two skeleton joints are computed and each orientation is encoded into one of the 27 states indicating the spatial relationship of the joints. Secondly, limbs are combined into parts and the limb's states are mapped into part states. Finally, frequent pattern mining is employed to mine the most frequent and relevant (discriminative, representative and non-redundant) states of parts in continuous several frames. These parts are referred to as Frequent Local Parts or FLPs. The FLPs allow us to build powerful bag-of-FLP-based action representation. This new representation yields state-of-the-art results on MSR DailyActivity3D and MSR ActionPairs3D.
Simple Subroutine for Inhomogeneous Deployment
Venue: arXiv cs.IT 2014
Year: 2014

Spatial modeling of wireless networks via analytical means has been considered as a widely practiced mechanism for inference. As a result, some geometrical deployment models have been proposed in literature. Although practical in certain simulation instances, these models do not always produce inhomogeneous nodal geometries in an effective and simple manner for practical deployment situations. Therefore, we conceptualized a flexible approach for realizing random inhomogeneity by proposing the area-specific deployment (ASD) algorithm, which takes into account the clustering tendency of users. Overall, the developed spatial-level network tool has the distinct advantage of automatically producing infinitely many random realizations of users' geometry by simply entering three parameters to the simulator: the size of the cellular network, the number of deployment layers, and the overall quantity of nodes.
Speeding-up Graphical Model Optimization via a Coarse-to-fine Cascade of Pruning Classifiers
Venue: arXiv cs.CV 2014
Year: 2014

We propose a general and versatile framework that significantly speeds-up graphical model optimization while maintaining an excellent solution accuracy. The proposed approach relies on a multi-scale pruning scheme that is able to progressively reduce the solution space by use of a novel strategy based on a coarse-to-fine cascade of learnt classifiers. We thoroughly experiment with classic computer vision related MRF problems, where our framework constantly yields a significant time speed-up (with respect to the most efficient inference methods) and obtains a more accurate solution than directly optimizing the MRF.
Coalition Formation Game for Cooperative Cognitive Radio Using Gibbs Sampling
Venue: arXiv cs.GT 2014
Year: 2014

This paper considers a cognitive radio network in which each secondary user selects a primary user to assist in order to get a chance of accessing the primary user channel. Thus, each group of secondary users assisting the same primary user forms a coaltion. Within each coalition, sequential relaying is employed, and a relay ordering algorithm is used to make use of the relays in an efficient manner. It is required then to find the optimal sets of secondary users assisting each primary user such that the sum of their rates is maximized. The problem is formulated as a coalition formation game, and a Gibbs Sampling based algorithm is used to find the optimal coalition structure.
Selection of Most Appropriate Backpropagation Training Algorithm in Data Pattern Recognition
Venue: arXiv cs.NE 2014
Year: 2014

There are several training algorithms for backpropagation method in neural network. Not all of these algorithms have the same accuracy level demonstrated through the percentage level of suitability in recognizing patterns in the data. In this research tested 12 training algorithms specifically in recognize data patterns of test validity. The basic network parameters used are the maximum allowable epoch = 1000, target error = 10-3, and learning rate = 0.05. Of the twelve training algorithms each performed 20 times looping. The test results obtained that the percentage rate of the great match is trainlm algorithm with alpha 5% have adequate levels of suitability of 87.5% at the level of significance of 0.000. This means the most appropriate training algorithm in recognizing the the data pattern of test validity is the trainlm algorithm.
Stochastic Testing Method for Transistor-Level Uncertainty Quantification Based on Generalized Polynomial Chaos
Venue: arXiv cs.CE 2014
Year: 2014

Uncertainties have become a major concern in integrated circuit design. In order to avoid the huge number of repeated simulations in conventional Monte Carlo flows, this paper presents an intrusive spectral simulator for statistical circuit analysis. Our simulator employs the recently developed generalized polynomial chaos expansion to perform uncertainty quantification of nonlinear transistor circuits with both Gaussian and non-Gaussian random parameters. We modify the nonintrusive stochastic collocation (SC) method and develop an intrusive variant called stochastic testing (ST) method to accelerate the numerical simulation. Compared with the stochastic Galerkin (SG) method, the resulting coupled deterministic equations from our proposed ST method can be solved in a decoupled manner at each time point. At the same time, ST uses fewer samples and allows more flexible time step size controls than directly using a nonintrusive SC solver. These two properties make ST more efficient than SG and than existing SC methods, and more suitable for time-domain circuit simulation. Simulation results of several digital, analog and RF circuits are reported. Since our algorithm is based on generic mathematical models, the proposed ST algorithm can be applied to many other engineering problems.
Taking into Account the Differences between Actively and Passively Acquired Data: The Case of Active Learning with Support Vector Machines for Imbalanced Datasets
Venue: arXiv cs.LG 2014
Year: 2014

Actively sampled data can have very different characteristics than passively sampled data. Therefore, it's promising to investigate using different inference procedures during AL than are used during passive learning (PL). This general idea is explored in detail for the focused case of AL with cost-weighted SVMs for imbalanced data, a situation that arises for many HLT tasks. The key idea behind the proposed InitPA method for addressing imbalance is to base cost models during AL on an estimate of overall corpus imbalance computed via a small unbiased sample rather than the imbalance in the labeled training data, which is the leading method used during PL.
Cryptanalyzing an image encryption algorithm based on scrambling and Veginere cipher
Venue: arXiv cs.CR 2014
Year: 2014

Recently, an image encryption algorithm based on scrambling and Vegin`ere cipher has been proposed. However, it was soon cryptanalyzed by Zhang et al. using a combination of chosen-plaintext attack and differential attack. This paper briefly reviews the two attack methods proposed by Zhang et al. and outlines the mathematical interpretations of them. Based on their work, we present an improved chosen-plaintext attack to further reduce the number of chosen-plaintexts required, which is proved to be optimal. Moreover, it is found that an elaborately designed known-plaintex attack can efficiently compromise the image cipher under study. This finding is verified by both mathematical analysis and numerical simulations. The cryptanalyzing techniques described in this paper may provide some insights for designing secure and efficient multimedia ciphers.
Ensembles of Random Sphere Cover Classifiers
Venue: arXiv cs.LG 2014
Year: 2014

We propose and evaluate alternative ensemble schemes for a new instance based learning classifier, the Randomised Sphere Cover (RSC) classifier. RSC fuses instances into spheres, then bases classification on distance to spheres rather than distance to instances. The randomised nature of RSC makes it ideal for use in ensembles. We propose two ensemble methods tailored to the RSC classifier; $αβ$RSE, an ensemble based on instance resampling and $α$RSSE, a subspace ensemble. We compare $αβ$RSE and $α$RSSE to tree based ensembles on a set of UCI datasets and demonstrates that RSC ensembles perform significantly better than some of these ensembles, and not significantly worse than the others. We demonstrate via a case study on six gene expression data sets that $α$RSSE can outperform other subspace ensemble methods on high dimensional data when used in conjunction with an attribute filter. Finally, we perform a set of Bias/Variance decomposition experiments to analyse the source of improvement in comparison to a base classifier.
Adaptive Tag Selection for Image Annotation
Venue: arXiv cs.CV 2014
Year: 2014

Not all tags are relevant to an image, and the number of relevant tags is image-dependent. Although many methods have been proposed for image auto-annotation, the question of how to determine the number of tags to be selected per image remains open. The main challenge is that for a large tag vocabulary, there is often a lack of ground truth data for acquiring optimal cutoff thresholds per tag. In contrast to previous works that pre-specify the number of tags to be selected, we propose in this paper adaptive tag selection. The key insight is to divide the vocabulary into two disjoint subsets, namely a seen set consisting of tags having ground truth available for optimizing their thresholds and a novel set consisting of tags without any ground truth. Such a division allows us to estimate how many tags shall be selected from the novel set according to the tags that have been selected from the seen set. The effectiveness of the proposed method is justified by our participation in the ImageCLEF 2014 image annotation task. On a set of 2,065 test images with ground truth available for 207 tags, the benchmark evaluation shows that compared to the popular top-$k$ strategy which obtains an F-score of 0.122, adaptive tag selection achieves a higher F-score of 0.223. Moreover, by treating the underlying image annotation system as a black box, the new method can be used as an easy plug-in to boost the performance of existing systems.
Fingerprint Classification Based on Depth Neural Network
Venue: arXiv cs.CV 2014
Year: 2014

Fingerprint classification is an effective technique for reducing the candidate numbers of fingerprints in the stage of matching in automatic fingerprint identification system (AFIS). In recent years, deep learning is an emerging technology which has achieved great success in many fields, such as image processing, natural language processing and so on. In this paper, we only choose the orientation field as the input feature and adopt a new method (stacked sparse autoencoders) based on depth neural network for fingerprint classification. For the four-class problem, we achieve a classification of 93.1 percent using the depth network structure which has three hidden layers (with 1.8% rejection) in the NIST-DB4 database. And then we propose a novel method using two classification probabilities for fuzzy classification which can effectively enhance the accuracy of classification. By only adjusting the probability threshold, we get the accuracy of classification is 96.1% (setting threshold is 0.85), 97.2% (setting threshold is 0.90) and 98.0% (setting threshold is 0.95). Using the fuzzy method, we obtain higher accuracy than other methods.
Deep Regression for Face Alignment
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we present a deep regression approach for face alignment. The deep architecture consists of a global layer and multi-stage local layers. We apply the back-propagation algorithm with the dropout strategy to jointly optimize the regression parameters. We show that the resulting deep regressor gradually and evenly approaches the true facial landmarks stage by stage, avoiding the tendency to yield over-strong early stage regressors while over-weak later stage regressors. Experimental results show that our approach achieves the state-of-the-art
Solving the Maximum-Weight Connected Subgraph Problem to Optimality
Venue: arXiv cs.DS 2014
Year: 2014

Given an undirected node-weighted graph, the Maximum-Weight Connected Subgraph problem (MWCS) is to identify a subset of nodes of maximalsum of weights that induce a connected subgraph. MWCS is closely related to the well-studied Prize Collecting Steiner Tree problem and has many applications in different areas, including computational biology, network design and computer vision. The problem is NP-hard and even hard to approximate within a constant factor. In this work we describe an algorithmic scheme for solving MWCS to provable optimality, which is based on preprocessing rules, new results on decomposing an instance into its biconnected and triconnected components and a branch-and-cut approach combined with a primal heuristic. We demonstrate the performance of our method on the benchmark instances of the 11th DIMACS implementation challenge consisting of MWCS as well as transformed PCST instances.
A Bayesian model for recognizing handwritten mathematical expressions
Venue: arXiv cs.AI 2014
Year: 2014

Recognizing handwritten mathematics is a challenging classification problem, requiring simultaneous identification of all the symbols comprising an input as well as the complex two-dimensional relationships between symbols and subexpressions. Because of the ambiguity present in handwritten input, it is often unrealistic to hope for consistently perfect recognition accuracy. We present a system which captures all recognizable interpretations of the input and organizes them in a parse forest from which individual parse trees may be extracted and reported. If the top-ranked interpretation is incorrect, the user may request alternates and select the recognition result they desire. The tree extraction step uses a novel probabilistic tree scoring strategy in which a Bayesian network is constructed based on the structure of the input, and each joint variable assignment corresponds to a different parse tree. Parse trees are then reported in order of decreasing probability. Two accuracy evaluations demonstrate that the resulting recognition system is more accurate than previous versions (which used non-probabilistic methods) and other academic math recognizers.
Learning and approximation capability of orthogonal super greedy algorithm
Venue: arXiv cs.LG 2014
Year: 2014

We consider the approximation capability of orthogonal super greedy algorithms (OSGA) and its applications in supervised learning. OSGA is concerned with selecting more than one atoms in each iteration step, which, of course, greatly reduces the computational burden when compared with the conventional orthogonal greedy algorithm (OGA). We prove that even for function classes that are not the convex hull of the dictionary, OSGA does not degrade the approximation capability of OGA provided the dictionary is incoherent. Based on this, we deduce a tight generalization error bound for OSGA learning. Our results show that in the realm of supervised learning, OSGA provides a possibility to further reduce the computational burden of OGA in the premise of maintaining its prominent generalization capability.
Multilevel Network Games
Venue: arXiv cs.GT 2014
Year: 2014

We consider a multilevel network game, where nodes can improve their communication costs by connecting to a high-speed network. The $n$ nodes are connected by a static network and each node can decide individually to become a gateway to the high-speed network. The goal of a node $v$ is to minimize its private costs, i.e., the sum (SUM-game) or maximum (MAX-game) of communication distances from $v$ to all other nodes plus a fixed price $α> 0$ if it decides to be a gateway. Between gateways the communication distance is $0$, and gateways also improve other nodes' distances by behaving as shortcuts. For the SUM-game, we show that for $α\leq n-1$, the price of anarchy is $Θ(n/\sqrtα)$ and in this range equilibria always exist. In range $α\in (n-1,n(n-1))$ the price of anarchy is $Θ(\sqrtα)$, and for $α\geq n(n-1)$ it is constant. For the MAX-game, we show that the price of anarchy is either $Θ(1 + n/\sqrtα)$, for $α\geq 1$, or else $1$. Given a graph with girth of at least $4α$, equilibria always exist. Concerning the dynamics, both the SUM-game and the MAX-game are not potential games. For the SUM-game, we even show that it is not weakly acyclic.
Distributed Consensus of Linear Multi-Agent Systems with Switching Directed Topologies
Venue: arXiv cs.SY 2014
Year: 2014

This paper addresses the distributed consensus problem for a linear multi-agent system with switching directed communication topologies. By appropriately introducing a linear transformation, the consensus problem is equivalently converted to a stabilization problem for a class of switched linear systems. Some sufficient consensus conditions are then derived by using tools from the matrix theory and stability analysis of switched systems. It is proved that consensus in such a multi-agent system can be ensured if each agent is stabilizable and each possible directed topology contains a directed spanning tree. Finally, a numerical simulation is given for illustration.
Active-Threaded Algorithms for Provenance Cognition in the Cloud preserving Low Overhead and Fault Tolerance
Venue: arXiv cs.DC 2014
Year: 2014

Provenance is the derivation history of information about the origin of data and processes. For a highly dynamic system such as the cloud, provenance must be effectively detected to be used as proves to ensure accountability during digital forensic investigations. This paper proposes active-threaded provenance cognition algorithms that ensure effective and high speed detection of provenance information in the activity layer of the cloud. The algorithms also support encapsulation of the provenance information on specific targets. Performance evaluation of the proposed algorithms reveal mean delay of 8.198 seconds that is below the pre-defined benchmark of 10 seconds. Standard deviation and cumulative frequencies for delays are found to be 1.434 and 45.1% respectively.
Statistical Estimation: From Denoising to Sparse Regression and Hidden Cliques
Venue: arXiv cs.IT 2014
Year: 2014

These notes review six lectures given by Prof. Andrea Montanari on the topic of statistical estimation for linear models. The first two lectures cover the principles of signal recovery from linear measurements in terms of minimax risk. Subsequent lectures demonstrate the application of these principles to several practical problems in science and engineering. Specifically, these topics include denoising of error-laden signals, recovery of compressively sensed signals, reconstruction of low-rank matrices, and also the discovery of hidden cliques within large networks.
Instability of Sharing Systems in the Presence of Retransmissions
Venue: arXiv cs.PF 2014
Year: 2014

Retransmissions represent a primary failure recovery mechanism on all layers of communication network architecture. Similarly, fair sharing, e.g. processor sharing (PS), is a widely accepted approach to resource allocation among multiple users. Recent work has shown that retransmissions in failure-prone, e.g. wireless ad hoc, networks can cause heavy tails and long delays. In this paper, we discover a new phenomenon showing that PS-based scheduling induces complete instability with zero throughput in the presence of retransmissions, regardless of how low the traffic load may be. This phenomenon occurs even when the job sizes are bounded/fragmented, e.g. deterministic. Our analytical results are further validated via simulation experiments. Moreover, our work demonstrates that scheduling one job at a time, such as first-come-first-serve, achieves stability and should be preferred in these systems.