OpenRaiser/Intern-Atlas huggingface dataset:
Liquid State Machine with Dendritically Enhanced Readout for Low-power, Neuromorphic VLSI Implementations
Venue: arXiv cs.ET 2014
Year: 2014

In this paper, we describe a new neuro-inspired, hardware-friendly readout stage for the liquid state machine (LSM), a popular model for reservoir computing. Compared to the parallel perceptron architecture trained by the p-delta algorithm, which is the state of the art in terms of performance of readout stages, our readout architecture and learning algorithm can attain better performance with significantly less synaptic resources making it attractive for VLSI implementation. Inspired by the nonlinear properties of dendrites in biological neurons, our readout stage incorporates neurons having multiple dendrites with a lumped nonlinearity. The number of synaptic connections on each branch is significantly lower than the total number of connections from the liquid neurons and the learning algorithm tries to find the best 'combination' of input connections on each branch to reduce the error. Hence, the learning involves network rewiring (NRW) of the readout network similar to structural plasticity observed in its biological counterparts. We show that compared to a single perceptron using analog weights, this architecture for the readout can attain, even by using the same number of binary valued synapses, up to 3.3 times less error for a two-class spike train classification problem and 2.4 times less error for an input rate approximation task. Even with 60 times larger synapses, a group of 60 parallel perceptrons cannot attain the performance of the proposed dendritically enhanced readout. An additional advantage of this method for hardware implementations is that the 'choice' of connectivity can be easily implemented exploiting address event representation (AER) protocols commonly used in current neuromorphic systems where the connection matrix is stored in memory. Also, due to the use of binary synapses, our proposed method is more robust against statistical variations.
Resource Allocation Frameworks for Network-coded Layered Multimedia Multicast Services
Venue: arXiv cs.IT 2014
Year: 2014

The explosive growth of content-on-the-move, such as video streaming to mobile devices, has propelled research on multimedia broadcast and multicast schemes. Multi-rate transmission strategies have been proposed as a means of delivering layered services to users experiencing different downlink channel conditions. In this paper, we consider Point-to-Multipoint layered service delivery across a generic cellular system and improve it by applying different random linear network coding approaches. We derive packet error probability expressions and use them as performance metrics in the formulation of resource allocation frameworks. The aim of these frameworks is both the optimization of the transmission scheme and the minimization of the number of broadcast packets on each downlink channel, while offering service guarantees to a predetermined fraction of users. As a case of study, our proposed frameworks are then adapted to the LTE-A standard and the eMBMS technology. We focus on the delivery of a video service based on the H.264/SVC standard and demonstrate the advantages of layered network coding over multi-rate transmission. Furthermore, we establish that the choice of both the network coding technique and resource allocation method play a critical role on the network footprint, and the quality of each received video layer.
Justifying Answer Sets using Argumentation
Venue: arXiv cs.AI 2014
Year: 2014

An answer set is a plain set of literals which has no further structure that would explain why certain literals are part of it and why others are not. We show how argumentation theory can help to explain why a literal is or is not contained in a given answer set by defining two justification methods, both of which make use of the correspondence between answer sets of a logic program and stable extensions of the Assumption-Based Argumentation (ABA) framework constructed from the same logic program. Attack Trees justify a literal in argumentation-theoretic terms, i.e. using arguments and attacks between them, whereas ABA-Based Answer Set Justifications express the same justification structure in logic programming terms, that is using literals and their relationships. Interestingly, an ABA-Based Answer Set Justification corresponds to an admissible fragment of the answer set in question, and an Attack Tree corresponds to an admissible fragment of the stable extension corresponding to this answer set.
Algebraic reputation model RepRank and its application to spambot detection
Venue: arXiv cs.SI 2014
Year: 2014

Due to popularity surge social networks became lucrative targets for spammers and guerilla marketers, who are trying to game ranking systems and broadcast their messages at little to none cost. Ranking systems, for example Twitter's Trends, can be gamed by scripted users also called bots, who are automatically or semi-automatically twitting essentially the same message. Judging by the prices and abundance of supply from PR firms this is an easy to implement and widely used tactic, at least in Russian blogosphere. Aggregative analysis of social networks should at best mark those messages as spam or at least correctly downplay their importance as they represent opinions only of a few, if dedicated, users. Hence bot detection plays a crucial role in social network mining and analysis. In this paper we propose technique called RepRank which could be viewed as Markov chain based model for reputation propagation on graphs utilizing simultaneous trust and anti-trust propagation and provide effective numerical approach for its computation. Comparison with another models such as TrustRank and some of its modifications on sample of 320000 Russian speaking Twitter users is presented. The dataset is presented as well.
Finding Action Tubes
Venue: arXiv cs.CV 2014
Year: 2014

We address the problem of action detection in videos. Driven by the latest progress in object detection from 2D images, we build action models using rich feature hierarchies derived from shape and kinematic cues. We incorporate appearance and motion in two ways. First, starting from image region proposals we select those that are motion salient and thus are more likely to contain the action. This leads to a significant reduction in the number of regions being processed and allows for faster computations. Second, we extract spatio-temporal feature representations to build strong classifiers using Convolutional Neural Networks. We link our predictions to produce detections consistent in time, which we call action tubes. We show that our approach outperforms other techniques in the task of action detection.
PU Learning for Matrix Completion
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we consider the matrix completion problem when the observations are one-bit measurements of some underlying matrix M, and in particular the observed samples consist only of ones and no zeros. This problem is motivated by modern applications such as recommender systems and social networks where only "likes" or "friendships" are observed. The problem of learning from only positive and unlabeled examples, called PU (positive-unlabeled) learning, has been studied in the context of binary classification. We consider the PU matrix completion problem, where an underlying real-valued matrix M is first quantized to generate one-bit observations and then a subset of positive entries is revealed. Under the assumption that M has bounded nuclear norm, we provide recovery guarantees for two different observation models: 1) M parameterizes a distribution that generates a binary matrix, 2) M is thresholded to obtain a binary matrix. For the first case, we propose a "shifted matrix completion" method that recovers M using only a subset of indices corresponding to ones, while for the second case, we propose a "biased matrix completion" method that recovers the (thresholded) binary matrix. Both methods yield strong error bounds --- if M is n by n, the Frobenius error is bounded as O(1/((1-rho)n), where 1-rho denotes the fraction of ones observed. This implies a sample complexity of O(n\log n) ones to achieve a small error, when M is dense and n is large. We extend our methods and guarantees to the inductive matrix completion problem, where rows and columns of M have associated features. We provide efficient and scalable optimization procedures for both the methods and demonstrate the effectiveness of the proposed methods for link prediction (on real-world networks consisting of over 2 million nodes and 90 million links) and semi-supervised clustering tasks.
Wireless Communication System with RF-based Energy Harvesting: From Information Theory to Green System
Venue: arXiv cs.IT 2014
Year: 2014

Harvesting energy from ambient environment is a new promising solution to free electronic devices from electric wire or limited-lifetime battery, which may find very significant applications in sensor networks and body-area networks. This paper mainly investigate the fundamental limits of information transmission in wireless communication system with RF-based energy harvesting, in which a master node acts not only as an information source but also an energy source for child node while only information is transmitted back from child to master node. Three typical structures: optimum receiver, orthogonal receiver and power splitting receiver are considered where two way information transmission between two nodes under an unique external power supply constraint at master node are jointly investigated in the viewpoint of systemic level. We explicitly characterize the achievable capacity-rate region and also discuss the effect of signal processing power consumption at child node. The optimal transmission strategy corresponding to the most energy-efficient status, namely the point on the boundary of achievable capacity-rate region, is derived with help of conditional capacity function. Simulation confirms the substantial gains of employing optimal transmission strategy and optimum receiver structure. Besides, a typical application on minimizing required transmit power to green system is presented.
Analogous Dynamics of Boolean Network
Venue: arXiv cs.DM 2014
Year: 2014

Different Boolean networks may reveal similar dynamics although their definition differs, then preventing their distinction from the observations. This raises the question about the sufficiency of a particular Boolean network for properly reproducing a modeled phenomenon to make realistic predictions. The question actually depends on the invariant properties of behaviorally similar Boolean networks. In this article, we address this issue by considering that the similarity is formalized by isomorphism on graphs modeling their dynamics. The similarity also depends on the parameter governing the updating policy, called the mode. We define a general characterization of the group of isomorphism preserving the mode. From this characterization, we deduce invariant structural properties of the interaction graph and conditions to maintain an equivalence through mode variation.
Bayesian Mechanism Design with Efficiency, Privacy, and Approximate Truthfulness
Venue: arXiv cs.GT 2014
Year: 2014

Recently, there has been a number of papers relating mechanism design and privacy (e.g., see \cite{MT07,Xia11,CCKMV11,NST12,NOS12,HK12}). All of these papers consider a worst-case setting where there is no probabilistic information about the players' types. In this paper, we investigate mechanism design and privacy in the \emph{Bayesian} setting, where the players' types are drawn from some common distribution. We adapt the notion of \emph{differential privacy} to the Bayesian mechanism design setting, obtaining \emph{Bayesian differential privacy}. We also define a robust notion of approximate truthfulness for Bayesian mechanisms, which we call \emph{persistent approximate truthfulness}. We give several classes of mechanisms (e.g., social welfare mechanisms and histogram mechanisms) that achieve both Bayesian differential privacy and persistent approximate truthfulness. These classes of mechanisms can achieve optimal (economic) efficiency, and do not use any payments. We also demonstrate that by considering the above mechanisms in a modified mechanism design model, the above mechanisms can achieve actual truthfulness.
An Evolutionary Approach for Optimizing Hierarchical Multi-Agent System Organization
Venue: arXiv cs.MA 2014
Year: 2014

It has been widely recognized that the performance of a multi-agent system is highly affected by its organization. A large scale system may have billions of possible ways of organization, which makes it impractical to find an optimal choice of organization using exhaustive search methods. In this paper, we propose a genetic algorithm aided optimization scheme for designing hierarchical structures of multi-agent systems. We introduce a novel algorithm, called the hierarchical genetic algorithm, in which hierarchical crossover with a repair strategy and mutation of small perturbation are used. The phenotypic hierarchical structure space is translated to the genome-like array representation space, which makes the algorithm genetic-operator-literate. A case study with 10 scenarios of a hierarchical information retrieval model is provided. Our experiments have shown that competitive baseline structures which lead to the optimal organization in terms of utility can be found by the proposed algorithm during the evolutionary search. Compared with the traditional genetic operators, the newly introduced operators produced better organizations of higher utility more consistently in a variety of test cases. The proposed algorithm extends of the search processes of the state-of-the-art multi-agent organization design methodologies, and is more computationally efficient in a large search space.
A Convex Sparse PCA for Feature Analysis
Venue: arXiv cs.LG 2014
Year: 2014

Principal component analysis (PCA) has been widely applied to dimensionality reduction and data pre-processing for different applications in engineering, biology and social science. Classical PCA and its variants seek for linear projections of the original variables to obtain a low dimensional feature representation with maximal variance. One limitation is that it is very difficult to interpret the results of PCA. In addition, the classical PCA is vulnerable to certain noisy data. In this paper, we propose a convex sparse principal component analysis (CSPCA) algorithm and apply it to feature analysis. First we show that PCA can be formulated as a low-rank regression optimization problem. Based on the discussion, the l 2 , 1 -norm minimization is incorporated into the objective function to make the regression coefficients sparse, thereby robust to the outliers. In addition, based on the sparse model used in CSPCA, an optimal weight is assigned to each of the original feature, which in turn provides the output with good interpretability. With the output of our CSPCA, we can effectively analyze the importance of each feature under the PCA criteria. The objective function is convex, and we propose an iterative algorithm to optimize it. We apply the CSPCA algorithm to feature selection and conduct extensive experiments on six different benchmark datasets. Experimental results demonstrate that the proposed algorithm outperforms state-of-the-art unsupervised feature selection algorithms.
Lower bounds on the size of semidefinite programming relaxations
Venue: arXiv cs.CC 2014
Year: 2014

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^c}$, for some constant $c > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-$O(1)$ sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX-3-SAT.
Scale-Invariant Convolutional Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

Even though convolutional neural networks (CNN) has achieved near-human performance in various computer vision tasks, its ability to tolerate scale variations is limited. The popular practise is making the model bigger first, and then train it with data augmentation using extensive scale-jittering. In this paper, we propose a scaleinvariant convolutional neural network (SiCNN), a modeldesigned to incorporate multi-scale feature exaction and classification into the network structure. SiCNN uses a multi-column architecture, with each column focusing on a particular scale. Unlike previous multi-column strategies, these columns share the same set of filter parameters by a scale transformation among them. This design deals with scale variation without blowing up the model size. Experimental results show that SiCNN detects features at various scales, and the classification result exhibits strong robustness against object scale variations.
The Application of Two-level Attention Models in Deep Convolutional Neural Network for Fine-grained Image Classification
Venue: arXiv cs.CV 2014
Year: 2014

Fine-grained classification is challenging because categories can only be discriminated by subtle and local differences. Variances in the pose, scale or rotation usually make the problem more difficult. Most fine-grained classification systems follow the pipeline of finding foreground object or object parts (where) to extract discriminative features (what). In this paper, we propose to apply visual attention to fine-grained classification task using deep neural network. Our pipeline integrates three types of attention: the bottom-up attention that propose candidate patches, the object-level top-down attention that selects relevant patches to a certain object, and the part-level top-down attention that localizes discriminative parts. We combine these attentions to train domain-specific deep nets, then use it to improve both the what and where aspects. Importantly, we avoid using expensive annotations like bounding box or part information from end-to-end. The weak supervision constraint makes our work easier to generalize. We have verified the effectiveness of the method on the subsets of ILSVRC2012 dataset and CUB200_2011 dataset. Our pipeline delivered significant improvements and achieved the best accuracy under the weakest supervision condition. The performance is competitive against other methods that rely on additional annotations.
Persistent Evidence of Local Image Properties in Generic ConvNets
Venue: arXiv cs.CV 2014
Year: 2014

Supervised training of a convolutional network for object classification should make explicit any information related to the class of objects and disregard any auxiliary information associated with the capture of the image or the variation within the object class. Does this happen in practice? Although this seems to pertain to the very final layers in the network, if we look at earlier layers we find that this is not the case. Surprisingly, strong spatial information is implicit. This paper addresses this, in particular, exploiting the image representation at the first fully connected layer, i.e. the global image descriptor which has been recently shown to be most effective in a range of visual recognition tasks. We empirically demonstrate evidences for the finding in the contexts of four different tasks: 2d landmark detection, 2d object keypoints prediction, estimation of the RGB values of input image, and recovery of semantic label of each pixel. We base our investigation on a simple framework with ridge rigression commonly across these tasks, and show results which all support our insight. Such spatial information can be used for computing correspondence of landmarks to a good accuracy, but should potentially be useful for improving the training of the convolutional nets for classification purposes.
Rational Deployment of Multiple Heuristics in IDA*
Venue: arXiv cs.AI 2014
Year: 2014

Recent advances in metareasoning for search has shown its usefulness in improving numerous search algorithms. This paper applies rational metareasoning to IDA* when several admissible heuristics are available. The obvious basic approach of taking the maximum of the heuristics is improved upon by lazy evaluation of the heuristics, resulting in a variant known as Lazy IDA*. We introduce a rational version of lazy IDA* that decides whether to compute the more expensive heuristics or to bypass it, based on a myopic expected regret estimate. Empirical evaluation in several domains supports the theoretical results, and shows that rational lazy IDA* is a state-of-the-art heuristic combination method.
Analyzing DISH for Multi-Channel MAC Protocols in Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

For long, node cooperation has been exploited as a data relaying mechanism. However, the wireless channel allows for much richer interaction between nodes. One such scenario is in a multi-channel environment, where transmitter-receiver pairs may make incorrect decisions (e.g., in selecting channels) but idle neighbors could help by sharing information to prevent undesirable consequences (e.g., data collisions). This represents a Distributed Information SHaring (DISH) mechanism for cooperation and suggests new ways of designing cooperative protocols. However, what is lacking is a theoretical understanding of this new notion of cooperation. In this paper, we view cooperation as a network resource and evaluate the availability of cooperation via a metric, $p_{co}$, the probability of obtaining cooperation. First, we analytically evaluate $p_{co}$ in the context of multi-channel multi-hop wireless networks. Second, we verify our analysis via simulations and the results show that our analysis accurately characterizes the behavior of $p_{co}$ as a function of underlying network parameters. This step also yields important insights into DISH with respect to network dynamics. Third, we investigate the correlation between $p_{co}$ and network performance in terms of collision rate, packet delay, and throughput. The results indicate a near-linear relationship, which may significantly simplify performance analysis for cooperative networks and suggests that $p_{co}$ be used as an appropriate performance indicator itself. Throughout this work, we utilize, as appropriate, three different DISH contexts --- model-based DISH, ideal DISH, and real DISH --- to explore $p_{co}$.