OpenRaiser/Intern-Atlas huggingface dataset:
SciRecSys: A Recommendation System for Scientific Publication by Discovering Keyword Relationships
Venue: arXiv cs.DL 2015
Year: 2015

In this work, we propose a new approach for discovering various relationships among keywords over the scientific publications based on a Markov Chain model. It is an important problem since keywords are the basic elements for representing abstract objects such as documents, user profiles, topics and many things else. Our model is very effective since it combines four important factors in scientific publications: content, publicity, impact and randomness. Particularly, a recommendation system (called SciRecSys) has been presented to support users to efficiently find out relevant articles.
Norm-Based Capacity Control in Neural Networks
Venue: arXiv cs.LG 2015
Year: 2015

We investigate the capacity, convexity and characterization of a general family of norm-constrained feed-forward networks.
Multi-Block ADMM for Big Data Optimization in Smart Grid
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we review the parallel and distributed optimization algorithms based on alternating direction method of multipliers (ADMM) for solving "big data" optimization problem in smart grid communication networks. We first introduce the canonical formulation of the large-scale optimization problem. Next, we describe the general form of ADMM and then focus on several direct extensions and sophisticated modifications of ADMM from $2$-block to $N$-block settings to deal with the optimization problem. The iterative schemes and convergence properties of each extension/modification are given, and the implementation on large-scale computing facilities is also illustrated. Finally, we numerate several applications in power system for distributed robust state estimation, network energy management and security constrained optimal power flow problem.
Generating Multi-Sentence Lingual Descriptions of Indoor Scenes
Venue: arXiv cs.CV 2015
Year: 2015

This paper proposes a novel framework for generating lingual descriptions of indoor scenes. Whereas substantial efforts have been made to tackle this problem, previous approaches focusing primarily on generating a single sentence for each image, which is not sufficient for describing complex scenes. We attempt to go beyond this, by generating coherent descriptions with multiple sentences. Our approach is distinguished from conventional ones in several aspects: (1) a 3D visual parsing system that jointly infers objects, attributes, and relations; (2) a generative grammar learned automatically from training text; and (3) a text generation algorithm that takes into account the coherence among sentences. Experiments on the augmented NYU-v2 dataset show that our framework can generate natural descriptions with substantially higher ROGUE scores compared to those produced by the baseline.
Region-Based Rate-Control for H.264/AVC for Low Bit-Rate Applications
Venue: arXiv cs.MM 2015
Year: 2015

Rate-control plays an important role in video coding. However, in the conventional rate-control algorithms, the number and position of Macroblocks (MBs) inside one basic unit for rate-control is inflexible and predetermined. The different characteristics of the MBs are not fully considered. Also, there is no overall optimization of the coding of basic units. This paper proposes a new region-based rate-control scheme for H.264/AVC to improve the coding efficiency. The inter-frame information is explored to objectively divide one frame into multiple regions based on their rate-distortion behaviors. The MBs with the similar characteristics are classified into the same region, and the entire region instead of a single MB or a group of contiguous MBs is treated as a basic unit for rate-control. A linear rate-quantization stepsize model and a linear distortion-quantization stepsize model are proposed to accurately describe the rate-distortion characteristics for the region-based basic units. Moreover, based on the above linear models, an overall optimization model is proposed to obtain suitable Quantization Parameters (QPs) for the region-based basic units. Experimental results demonstrate that the proposed region-based rate-control approach can achieve both better subjective and objective quality by performing the rate-control adaptively with the content, compared to the conventional rate-control approaches.
Contagious Sets in Dense Graphs
Venue: arXiv cs.DM 2015
Year: 2015

We study the activation process in undirected graphs known as bootstrap percolation: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it had at least r active neighbors, for a threshold r that is identical for all vertices. A contagious set is a vertex set whose activation results with the entire graph being active. Let m(G,r) be the size of a smallest contagious set in a graph G on n vertices. We examine density conditions that ensure m(G,r) = r for all r >= 2. With respect to the minimum degree, we prove that such a smallest possible contagious set is guaranteed to exist if and only if G has minimum degree at least (k-1)/k * n. Moreover, we study the speed with which the activation spreads and provide tight upper bounds on the number of rounds it takes until all nodes are activated in such a graph. We also investigate what average degree asserts the existence of small contagious sets. For n >= k >= r, we denote by M(n,k,r) the maximum number of edges in an n-vertex graph G satisfying m(G,r)>k. We determine the precise value of M(n,k,2) and M(n,k,k), assuming that n is sufficiently large compared to k.
An Online Convex Optimization Approach to Blackwell's Approachability
Venue: arXiv cs.GT 2015
Year: 2015

The notion of approachability in repeated games with vector payoffs was introduced by Blackwell in the 1950s, along with geometric conditions for approachability and corresponding strategies that rely on computing {\em steering directions} as projections from the current average payoff vector to the (convex) target set. Recently, Abernethy, Batlett and Hazan (2011) proposed a class of approachability algorithms that rely on the no-regret properties of Online Linear Programming for computing a suitable sequence of steering directions. This is first carried out for target sets that are convex cones, and then generalized to any convex set by embedding it in a higher-dimensional convex cone. In this paper we present a more direct formulation that relies on the support function of the set, along with suitable Online Convex Optimization algorithms, which leads to a general class of approachability algorithms. We further show that Blackwell's original algorithm and its convergence follow as a special case.
Multi-Server Coded Caching
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider multiple cache-enabled clients connected to multiple servers through an intermediate network. We design several topology-aware coding strategies for such networks. Based on topology richness of the intermediate network, and types of coding operations at internal nodes, we define three classes of networks, namely, dedicated, flexible, and linear networks. For each class, we propose an achievable coding scheme, analyze its coding delay, and also, compare it with an information theoretic lower bound. For flexible networks, we show that our scheme is order-optimal in terms of coding delay and, interestingly, the optimal memory-delay curve is achieved in certain regimes. In general, our results suggest that, in case of networks with multiple servers, type of network topology can be exploited to reduce service delay.
On Defining SPARQL with Boolean Tensor Algebra
Venue: arXiv cs.DB 2015
Year: 2015

The Resource Description Framework (RDF) represents information as subject-predicate-object triples. These triples are commonly interpreted as a directed labelled graph. We propose an alternative approach, interpreting the data as a 3-way Boolean tensor. We show how SPARQL queries - the standard queries for RDF - can be expressed as elementary operations in Boolean algebra, giving us a complete re-interpretation of RDF and SPARQL. We show how the Boolean tensor interpretation allows for new optimizations and analyses of the complexity of SPARQL queries. For example, estimating the size of the results for different join queries becomes much simpler.
From Data Fusion to Knowledge Fusion
Venue: arXiv cs.DB 2015
Year: 2015

The task of {\em data fusion} is to identify the true values of data items (eg, the true date of birth for {\em Tom Cruise}) among multiple observed values drawn from different sources (eg, Web sites) of varying (and unknown) reliability. A recent survey\cite{LDL+12} has provided a detailed comparison of various fusion methods on Deep Web data. In this paper, we study the applicability and limitations of different fusion techniques on a more challenging problem: {\em knowledge fusion}. Knowledge fusion identifies true subject-predicate-object triples extracted by multiple information extractors from multiple information sources. These extractors perform the tasks of entity linkage and schema alignment, thus introducing an additional source of noise that is quite different from that traditionally considered in the data fusion literature, which only focuses on factual errors in the original sources. We adapt state-of-the-art data fusion techniques and apply them to a knowledge base with 1.6B unique knowledge triples extracted by 12 extractors from over 1B Web pages, which is three orders of magnitude larger than the data sets used in previous data fusion papers. We show great promise of the data fusion approaches in solving the knowledge fusion problem, and suggest interesting research directions through a detailed error analysis of the methods.
CLP(H): Constraint Logic Programming for Hedges
Venue: arXiv cs.LO 2015
Year: 2015

CLP(H) is an instantiation of the general constraint logic programming scheme with the constraint domain of hedges. Hedges are finite sequences of unranked terms, built over variadic function symbols and three kinds of variables: for terms, for hedges, and for function symbols. Constraints involve equations between unranked terms and atoms for regular hedge language membership. We study algebraic semantics of CLP(H) programs, define a sound, terminating, and incomplete constraint solver, investigate two fragments of constraints for which the solver returns a complete set of solutions, and describe classes of programs that generate such constraints.
The lambda mechanism in lambda calculus and in other calculi
Venue: arXiv cs.PL 2015
Year: 2015

A comparison of Landin's form of lambda calculus with Church's shows that, independently of the lambda calculus, there exists a mechanism for converting functions with arguments indexed by variables to the usual kind of function where the arguments are indexed numerically. We call this the "lambda mechanism" and show how it can be used in other calculi. In first-order predicate logic it can be used to define new functions and new predicates in terms of existing ones. In a purely imperative programming language it can be used to provide an Algol-like procedure facility.
Robotic Wireless Networks in a Narrow Alley: A Game Theoretic Approach
Venue: arXiv cs.RO 2015
Year: 2015

There are many situations where vehicles may compete with each other to maximize their respective utilities.We consider a narrow alley where two groups, eastbound and westbound, of autonomous vehicles are heading toward each of their destination to minimize their travel distance. However, if the two groups approach the road simultaneously, it will be blocked. The main goal of this paper is to investigate how wireless communications among the vehicles can lead the solution near to Pareto optimum. In addition, we implemented such a vehicular test-bed, composed of networked robots that have an infrared sensor, a DC motor, and a wireless communication module: ZigBee (IEEE 802.15.4).
FPGA Implementation of the CAR Model of the Cochlea
Venue: arXiv cs.NE 2015
Year: 2015

The front end of the human auditory system, the cochlea, converts sound signals from the outside world into neural impulses transmitted along the auditory pathway for further processing. The cochlea senses and separates sound in a nonlinear active fashion, exhibiting remarkable sensitivity and frequency discrimination. Although several electronic models of the cochlea have been proposed and implemented, none of these are able to reproduce all the characteristics of the cochlea, including large dynamic range, large gain and sharp tuning at low sound levels, and low gain and broad tuning at intense sound levels. Here, we implement the Cascade of Asymmetric Resonators (CAR) model of the cochlea on an FPGA. CAR represents the basilar membrane filter in the Cascade of Asymmetric Resonators with Fast-Acting Compression (CAR-FAC) cochlear model. CAR-FAC is a neuromorphic model of hearing based on a pole-zero filter cascade model of auditory filtering. It uses simple nonlinear extensions of conventional digital filter stages that are well suited to FPGA implementations, so that we are able to implement up to 1224 cochlear sections on Virtex-6 FPGA to process sound data in real time. The FPGA implementation of the electronic cochlea described here may be used as a front-end sound analyser for various machine-hearing applications.
Personalising Mobile Advertising Based on Users Installed Apps
Venue: arXiv cs.CY 2015
Year: 2015

Mobile advertising is a billion pound industry that is rapidly expanding. The success of an advert is measured based on how users interact with it. In this paper we investigate whether the application of unsupervised learning and association rule mining could be used to enable personalised targeting of mobile adverts with the aim of increasing the interaction rate. Over May and June 2014 we recorded advert interactions such as tapping the advert or watching the whole advert video along with the set of apps a user has installed at the time of the interaction. Based on the apps that the users have installed we applied k-means clustering to profile the users into one of ten classes. Due to the large number of apps considered we implemented dimension reduction to reduced the app feature space by mapping the apps to their iTunes category and clustered users based on the percentage of their apps that correspond to each iTunes app category. The clustering was externally validated by investigating differences between the way the ten profiles interact with the various adverts genres (lifestyle, finance and entertainment adverts). In addition association rule mining was performed to find whether the time of the day that the advert is served and the number of apps a user has installed makes certain profiles more likely to interact with the advert genres. The results showed there were clear differences in the way the profiles interact with the different advert genres and the results of this paper suggest that mobile advert targeting would improve the frequency that users interact with an advert.
An $\mathcal{O}(n\log n)$ projection operator for weighted $\ell_1$-norm regularization with sum constraint
Venue: arXiv cs.LG 2015
Year: 2015

We provide a simple and efficient algorithm for the projection operator for weighted $\ell_1$-norm regularization subject to a sum constraint, together with an elementary proof. The implementation of the proposed algorithm can be downloaded from the author's homepage.
Efficient Computation of the Characteristic Polynomial of a Threshold Graph
Venue: arXiv cs.DS 2015
Year: 2015

An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chvátal and Hammer, as well as by Henderson and Zalcstein in 1977. A threshold graph is obtained from a one vertex graph by repeatedly adding either an isolated vertex or a dominating vertex, which is a vertex adjacent to all the other vertices. Threshold graphs are special kinds of cographs, which themselves are special kinds of graphs of clique-width 2. We obtain a running time of $O(n \log^2 n)$ for computing the characteristic polynomial, while the previously fastest algorithm ran in quadratic time. Keywords: Efficient Algorithms, Threshold Graphs, Characteristic Polynomial.
Polynomial kernelization for removing induced claws and diamonds
Venue: arXiv cs.DS 2015
Year: 2015

A graph is called (claw,diamond)-free if it contains neither a claw (a $K_{1,3}$) nor a diamond (a $K_4$ with an edge removed) as an induced subgraph. Equivalently, (claw,diamond)-free graphs can be characterized as line graphs of triangle-free graphs, or as linear dominoes, i.e., graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique. In this paper we consider the parameterized complexity of the (claw,diamond)-free Edge Deletion problem, where given a graph $G$ and a parameter $k$, the question is whether one can remove at most $k$ edges from $G$ to obtain a (claw,diamond)-free graph. Our main result is that this problem admits a polynomial kernel. We complement this finding by proving that, even on instances with maximum degree $6$, the problem is NP-complete and cannot be solved in time $2^{o(k)}\cdot |V(G)|^{O(1)}$ unless the Exponential Time Hypothesis fail
On Using Synthetic Social Media Stimuli in an Emergency Preparedness Functional Exercise
Venue: arXiv cs.SI 2015
Year: 2015

This paper details the creation and use of a massive (over 32,000 messages) artificially constructed 'Twitter' microblog stream for a regional emergency preparedness functional exercise. By combining microblog conversion, manual production, and a control set, we created a web based information stream providing valid, misleading, and irrelevant information to public information officers (PIOs) representing hospitals, fire departments, the local Red Cross, and city and county government officials. PIOs searched, monitored, and (through conventional channels) verified potentially acionable information that could then be redistributed through a personalized screen name. Our case study of a key PIO reveals several capabilities that social media can support, including event detection, the distribution of information between functions within the emergency response community, and the distribution of messages to the public. We suggest that training as well as information filtering tools are necessary to realize the potential of social media in both emergencies and exercises.
Grouping and Recognition of Dot Patterns with Straight Offset Polygons
Venue: arXiv cs.CV 2015
Year: 2015

When the boundary of a familiar object is shown by a series of isolated dots, humans can often recognize the object with ease. This ability can be sustained with addition of distracting dots around the object. However, such capability has not been reproduced algorithmically on computers. We introduce a new algorithm that groups a set of dots into multiple non-disjoint subsets. It connects the dots into a spanning tree using the proximity cue. It then applies the straight polygon transformation to an initial polygon derived from the spanning tree. The straight polygon divides the space into polygons recursively and each polygon can be viewed as grouping of a subset of the dots. The number of polygons generated is O($n$). We also introduce simple shape selection and recognition algorithms that can be applied to the grouping result. We used both natural and synthetic images to show effectiveness of these algorithms.
Context Forest for efficient object detection with large mixture models
Venue: arXiv cs.CV 2015
Year: 2015

We present Context Forest (ConF), a technique for predicting properties of the objects in an image based on its global appearance. Compared to standard nearest-neighbour techniques, ConF is more accurate, fast and memory efficient. We train ConF to predict which aspects of an object class are likely to appear in a given image (e.g. which viewpoint). This enables to speed-up multi-component object detectors, by automatically selecting the most relevant components to run on that image. This is particularly useful for detectors trained from large datasets, which typically need many components to fully absorb the data and reach their peak performance. ConF provides a speed-up of 2x for the DPM detector [1] and of 10x for the EE-SVM detector [2]. To show ConF's generality, we also train it to predict at which locations objects are likely to appear in an image. Incorporating this information in the detector score improves mAP performance by about 2% by removing false positive detections in unlikely locations.
Deployment Issues for Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we examine a number of deployment issues which arise from practical considerations in massive multiple-input-multiple-output (MIMO) systems. We show both spatial correlation and line-of-sight (LOS) introduce an interference component to the system which causes non-orthogonality between user channels. Distributing the antennas into multiple clusters is shown to reduce spatial correlation and improve performance. Furthermore, due to its ability to minimize interference, zero forcing (ZF) precoding performs well in massive MIMO systems compared to matched filter (MF) precoding which suffers large penalties. However, the noise component in the ZF signal-to-noise-ratio (SNR) increases significantly in the case of imperfect transmit channel state information (CSI).
IMAC: Impulsive-mitigation adaptive sparse channel estimation based on Gaussian-mixture model
Venue: arXiv cs.IT 2015
Year: 2015

Broadband frequency-selective fading channels usually have the inherent sparse nature. By exploiting the sparsity, adaptive sparse channel estimation (ASCE) methods, e.g., reweighted L1-norm least mean square (RL1-LMS), could bring a performance gain if additive noise satisfying Gaussian assumption. In real communication environments, however, channel estimation performance is often deteriorated by unexpected non-Gaussian noises which include conventional Gaussian noises and impulsive interferences. To design stable communication systems, hence, it is urgent to develop advanced channel estimation methods to remove the impulsive interference and to exploit channel sparsity simultaneously. In this paper, robust impulsive-mitigation adaptive sparse channel estimation (IMAC) method is proposed for solving aforementioned technical issues. Specifically, first of all, the non-Gaussian noise model is described by Gaussian mixture model (GMM). Secondly, cost function of reweighted L1-norm penalized least absolute error standard (RL1-LAE) algorithm is constructed. Then, RL1-LAE algorithm is derived for realizing IMAC method. Finally, representative simulation results are provided to corroborate the studies.
How to Round Subspaces: A New Spectral Clustering Algorithm
Venue: arXiv cs.DS 2015
Year: 2015

A basic problem in spectral clustering is the following. If a solution obtained from the spectral relaxation is close to an integral solution, is it possible to find this integral solution even though they might be in completely different basis? In this paper, we propose a new spectral clustering algorithm. It can recover a $k$-partition such that the subspace corresponding to the span of its indicator vectors is $O(\sqrt{opt})$ close to the original subspace in spectral norm with $opt$ being the minimum possible ($opt \le 1$ always). Moreover our algorithm does not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a $k$-partition closer than $o(k \cdot opt)$. We present two applications for our algorithm. First one finds a disjoint union of bounded degree expanders which approximate a given graph in spectral norm. The second one is for approximating the sparsest $k$-partition in a graph where each cluster have expansion at most $ϕ_k$ provided $ϕ_k \le O(λ_{k+1})$ where $λ_{k+1}$ is the $(k+1)^{st}$ eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required $ϕ_k \le O(λ_{k+1}/k)$.