OpenRaiser/Intern-Atlas huggingface dataset:
Saliency Detection combining Multi-layer Integration algorithm with background prior and energy function
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose an improved mechanism for saliency detection. Firstly,based on a neoteric background prior selecting four corners of an image as background,we use color and spatial contrast with each superpixel to obtain a salinecy map(CBP). Inspired by reverse-measurement methods to improve the accuracy of measurement in Engineering,we employ the Objectness labels as foreground prior based on part of information of CBP to construct a map(OFP).Further,an original energy function is applied to optimize both of them respectively and a single-layer saliency map(SLP)is formed by merging the above twos.Finally,to deal with the scale problem,we obtain our multi-layer map(MLP) by presenting an integration algorithm to take advantage of multiple saliency maps. Quantitative and qualitative experiments on three datasets demonstrate that our method performs favorably against the state-of-the-art algorithm.
Classifier ensemble creation via false labelling
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, a novel approach to classifier ensemble creation is presented. While other ensemble creation techniques are based on careful selection of existing classifiers or preprocessing of the data, the presented approach automatically creates an optimal labelling for a number of classifiers, which are then assigned to the original data instances and fed to classifiers. The approach has been evaluated on high-dimensional biomedical datasets. The results show that the approach outperformed individual approaches in all cases.
Low-Rank Matrix Completion for Topological Interference Management by Riemannian Pursuit
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we present a flexible low-rank matrix completion (LRMC) approach for topological interference management (TIM) in the partially connected K-user interference channel. No channel state information (CSI) is required at the transmitters except the network topology information. The previous attempt on the TIM problem is mainly based on its equivalence to the index coding problem, but so far only a few index coding problems have been solved. In contrast, in this paper, we present an algorithmic approach to investigate the achievable degrees-of-freedom (DoFs) by recasting the TIM problem as an LRMC problem. Unfortunately, the resulting LRMC problem is known to be NP-hard, and the main contribution of this paper is to propose a Riemannian pursuit (RP) framework to detect the rank of the matrix to be recovered by iteratively increasing the rank. This algorithm solves a sequence of fixed-rank matrix completion problems. To address the convergence issues in the existing fixed-rank optimization methods, the quotient manifold geometry of the search space of fixed-rank matrices is exploited via Riemannian optimization. By further exploiting the structure of the low-rank matrix varieties, i.e., the closure of the set of fixed- rank matrices, we develop an efficient rank increasing strategy to find good initial points in the procedure of rank pursuit. Simulation results demonstrate that the proposed RP algorithm achieves a faster convergence rate and higher achievable DoFs for the TIM problem compared with the state-of-the-art methods.
Normal-order reduction grammars
Venue: arXiv cs.LO 2016
Year: 2016

We present an algorithm which, for given $n$, generates an unambiguous regular tree grammar defining the set of combinatory logic terms, over the set $\{S,K\}$ of primitive combinators, requiring exactly $n$ normal-order reduction steps to normalize. As a consequence of Curry and Feys's standardization theorem, our reduction grammars form a complete syntactic characterization of normalizing combinatory logic terms. Using them, we provide a recursive method of constructing ordinary generating functions counting the number of $S K$-combinators reducing in $n$ normal-order reduction steps. Finally, we investigate the size of generated grammars, giving a primitive recursive upper bound.
Fast calculation of correlations in recognition systems
Venue: arXiv cs.CV 2016
Year: 2016

Computationally efficient classification system architecture is proposed. It utilizes fast tensor-vector multiplication algorithm to apply linear operators upon input signals . The approach is applicable to wide variety of recognition system architectures ranging from single stage matched filter bank classifiers to complex neural networks with unlimited number of hidden layers.
Type Based Sign Modulation and its Application for ISI mitigation in Molecular Communication
Venue: arXiv cs.IT 2016
Year: 2016

An important challenge in design of modulation schemes for molecular communication is positivity of the transmission signal (only a positive concentration of molecules can be released in the environment). This restriction makes handling of the InterSymbol Interference (ISI) a challenge for molecular communication. Previous works have proposed use of chemical reactions to remove molecules from the environment, and to effectively simulate negative signals. However, the differential equation describing a diffusion-reaction process is non-linear. This precludes the possibility of using Fourier transform tools. In this paper, a solution for simulating negative signals based on the diffusion-reaction channel model is proposed. While the proposed solution does not exploit the full degrees of freedom available for signaling in a diffusion-reaction process, but its end-to-end system is a linear channel and amenable to Fourier transform analysis. Based on our solution, a modulation scheme and a precoder are introduced and shown to have a significant reduction in error probability compared to previous modulation schemes such as CSK and MCSK. The effect of various imperfections (such as quantization error) on the communication system performance are studied.
Unambiguous Prioritized Repairing of Databases
Venue: arXiv cs.DB 2016
Year: 2016

In its traditional definition, a repair of an inconsistent database is a consistent database that differs from the inconsistent one in a "minimal way". Often, repairs are not equally legitimate, as it is desired to prefer one over another; for example, one fact is regarded more reliable than another, or a more recent fact should be preferred to an earlier one. Motivated by these considerations, researchers have introduced and investigated the framework of preferred repairs, in the context of denial constraints and subset repairs. There, a priority relation between facts is lifted towards a priority relation between consistent databases, and repairs are restricted to the ones that are optimal in the lifted sense. Three notions of lifting (and optimal repairs) have been proposed: Pareto, global, and completion. In this paper we investigate the complexity of deciding whether the priority relation suffices to clean the database unambiguously, or in other words, whether there is exactly one optimal repair. We show that the different lifting semantics entail highly different complexities. Under Pareto optimality, the problem is coNP-complete, in data complexity, for every set of functional dependencies (FDs), except for the tractable case of (equivalence to) one FD per relation. Under global optimality, one FD per relation is still tractable, but we establish $Π^{p}_{2}$-completeness for a relation with two FDs. In contrast, under completion optimality the problem is solvable in polynomial time for every set of FDs. In fact, we present a polynomial-time algorithm for arbitrary conflict hypergraphs. We further show that under a general assumption of transitivity, this algorithm solves the problem even for global optimality. The algorithm is extremely simple, but its proof of correctness is quite intricate.
Millimeter Wave MIMO Channel Estimation using Overlapped Beam Patterns and Rate Adaptation
Venue: arXiv cs.IT 2016
Year: 2016

This paper is concerned with the channel estimation problem in Millimeter wave (mmWave) wireless systems with large antenna arrays. By exploiting the inherent sparse nature of the mmWave channel, we first propose a fast channel estimation (FCE) algorithm based on a novel overlapped beam pattern design, which can increase the amount of information carried by each channel measurement and thus reduce the required channel estimation time compared to the existing non-overlapped designs. We develop a maximum likelihood (ML) estimator to optimally extract the path information from the channel measurements. Then, we propose a novel rate-adaptive channel estimation (RACE) algorithm, which can dynamically adjust the number of channel measurements based on the expected probability of estimation error (PEE). The performance of both proposed algorithms is analyzed. For the FCE algorithm, an approximate closed-form expression for the PEE is derived. For the RACE algorithm, a lower bound for the minimum signal energy-to-noise ratio required for a given number of channel measurements is developed based on the Shannon-Hartley theorem. Simulation results show that the FCE algorithm significantly reduces the number of channel estimation measurements compared to the existing algorithms using non-overlapped beam patterns. By adopting the RACE algorithm, we can achieve up to a 6dB gain in signal energy-to-noise ratio for the same PEE compared to the existing algorithms.
Temporal Opinion Spam Detection by Multivariate Indicative Signals
Venue: arXiv cs.SI 2016
Year: 2016

Online consumer reviews reflect the testimonials of real people, unlike advertisements. As such, they have critical impact on potential consumers, and indirectly on businesses. According to a Harvard study (Luca 2011), +1 rise in star-rating increases revenue by 5-9%. Problematically, such financial incentives have created a market for spammers to fabricate reviews, to unjustly promote or demote businesses, activities known as opinion spam (Jindal and Liu 2008). A vast majority of existing work on this problem have formulations based on static review data, with respective techniques operating in an offline fashion. Spam campaigns, however, are intended to make most impact during their course. Abnormal events triggered by spammers' activities could be masked in the load of future events, which static analysis would fail to identify. In this work, we approach the opinion spam problem with a temporal formulation. Specifically, we monitor a list of carefully selected indicative signals of opinion spam over time and design efficient techniques to both detect and characterize abnormal events in real-time. Experiments on datasets from two different review sites show that our approach is fast, effective, and practical to be deployed in real-world systems.
#greysanatomy vs. #yankees: Demographics and Hashtag Use on Twitter
Venue: arXiv cs.SI 2016
Year: 2016

Demographics, in particular, gender, age, and race, are a key predictor of human behavior. Despite the significant effect that demographics plays, most scientific studies using online social media do not consider this factor, mainly due to the lack of such information. In this work, we use state-of-the-art face analysis software to infer gender, age, and race from profile images of 350K Twitter users from New York. For the period from November 1, 2014 to October 31, 2015, we study which hashtags are used by different demographic groups. Though we find considerable overlap for the most popular hashtags, there are also many group-specific hashtags.
Two Tales of the World: Comparison of Widely Used World News Datasets GDELT and EventRegistry
Venue: arXiv cs.DL 2016
Year: 2016

In this work, we compare GDELT and Event Registry, which monitor news articles worldwide and provide big data to researchers regarding scale, news sources, and news geography. We found significant differences in scale and news sources, but surprisingly, we observed high similarity in news geography between the two datasets.
Distributed Multi-Task Learning with Shared Representation
Venue: arXiv cs.LG 2016
Year: 2016

We study the problem of distributed multi-task learning with shared representation, where each machine aims to learn a separate, but related, task in an unknown shared low-dimensional subspaces, i.e. when the predictor matrix has low rank. We consider a setting where each task is handled by a different machine, with samples for the task available locally on the machine, and study communication-efficient methods for exploiting the shared structure.
Online Sparse Linear Regression
Venue: arXiv cs.LG 2016
Year: 2016

We consider the online sparse linear regression problem, which is the problem of sequentially making predictions observing only a limited number of features in each round, to minimize regret with respect to the best sparse linear regressor, where prediction accuracy is measured by square loss. We give an inefficient algorithm that obtains regret bounded by $\tilde{O}(\sqrt{T})$ after $T$ prediction rounds. We complement this result by showing that no algorithm running in polynomial time per iteration can achieve regret bounded by $O(T^{1-δ})$ for any constant $δ> 0$ unless $\text{NP} \subseteq \text{BPP}$. This computational hardness result resolves an open problem presented in COLT 2014 (Kale, 2014) and also posed by Zolghadr et al. (2013). This hardness result holds even if the algorithm is allowed to access more features than the best sparse linear regressor up to a logarithmic factor in the dimension.
Local Partial Clique Covers for Index Coding
Venue: arXiv cs.IT 2016
Year: 2016

Index coding, or broadcasting with side information, is a network coding problem of most fundamental importance. In this problem, given a directed graph, each vertex represents a user with a need of information, and the neighborhood of each vertex represents the side information availability to that user. The aim is to find an encoding to minimum number of bits (optimal rate) that, when broadcasted, will be sufficient to the need of every user. Not only the optimal rate is intractable, but it is also very hard to characterize with some other well-studied graph parameter or with a simpler formulation, such as a linear program. Recently there have been a series of works that address this question and provide explicit schemes for index coding as the optimal value of a linear program with rate given by well-studied properties such as local chromatic number or partial clique-covering number. There has been a recent attempt to combine these existing notions of local chromatic number and partial clique covering into a unified notion denoted as the local partial clique cover (Arbabjolfaei and Kim, 2014). We present a generalized novel upper-bound (encoding scheme) - in the form of the minimum value of a linear program - for optimal index coding. Our bound also combines the notions of local chromatic number and partial clique covering into a new definition of the local partial clique cover, which outperforms both the previous bounds, as well as beats the previous attempt to combination. Further, we look at the upper bound derived recently by Thapa et al., 2015, and extend their $n$-$\mathsf{GIC}$ (Generalized Interlinked Cycle) construction to $(k,n)$-$\mathsf{GIC}$ graphs, which are a generalization of $k$-partial cliques.
Batched Lazy Decision Trees
Venue: arXiv cs.LG 2016
Year: 2016

We introduce a batched lazy algorithm for supervised classification using decision trees. It avoids unnecessary visits to irrelevant nodes when it is used to make predictions with either eagerly or lazily trained decision trees. A set of experiments demonstrate that the proposed algorithm can outperform both the conventional and lazy decision tree algorithms in terms of computation time as well as memory consumption, without compromising accuracy.
Network-wide Packet Behavior Identification and Private Network Function Outsourcing
Venue: arXiv cs.NI 2016
Year: 2016

Identifying the network-wide forwarding behaviors of a packet is essential for many network management applications. We present AP Classifier, a control plane tool for packet be- havior identification. Experiments show that the processing speed of AP Classifier is faster than existing tools by at least an order of magnitude. Furthermore, AP Classifier uses very small memory and is able to support real-time updates. We also present a network function outsource framework with AP Classifier which can provide security properties.
A Tangible Volume for Portable 3D Interaction
Venue: arXiv cs.HC 2016
Year: 2016

We present a new approach to achieve tangible object manipulation with a single, fully portable and self-contained device. Our solution is based on the concept of a "tangible volume". We turn a tangible object into a handheld fish-tank display. The tangible volume represents a volume of space that can be freely manipulated within a virtual scene. This volume can be positioned onto virtual objects to directly grasp them, and to manipulate them in 3D space. We investigate this concept through two user studies. The first study evaluates the intuitiveness of using a tangible volume for grasping and manipulating virtual objects. The second study evaluates the effects of the limited field of view on spatial awareness. Finally, we present a generalization of this concept to other forms of interaction through the surface of the volume.
Study and evaluation of an Irregular Graph Algorithm on Multicore and GPU Processor Architectures
Venue: arXiv cs.DC 2016
Year: 2016

One area of Computing applications which poses significant challenge of performance scalability on Chip Multiprocessors(CMP's) are Irregular applications. Such applications have very little computation and unpredictable memory access patterns making them memory-bound in contrast to compute-bound applications. Since the gap between processor and memory performance continues to exist, difficulty to hide and decrease this gap is one of the important factors which results in poor performance of these applications on CMP's. The goal of this thesis is to overcome many such challenges posed during performance acceleration of an irregular graph algorithm called Triad Census. We accelerated the Triad Census algorithm on two significantly different Chip Multiprocessors: Dual-socket Intel Xeon Multicore (8 hardware threads per socket) and 240-processor core NVIDIA Tesla C1060 GPGPU(128 hardware threads per core). The experimental results obtained on Intel Multicore Xeon system shows performance speedups (w.r.t baseline sequential) of maximum 56x , average 33x and minimum 8.3x for real world graph data sets. On NVIDIA Tesla C1060 GPGPU, we were able to match almost equally the Multicore results - 58.4x maximum, 32.8x average and 4.2x minimum speedups w.r.t baseline sequential. In terms of raw performance, for the graph data set called Patents network, our results on Intel Xeon Multicore(16 hw threads) were 1.27x times faster than previous results on Cray XMT(16 hw threads) while results achieved on GPGPU were comparatively slower(0.72x). To the best of our knowledge, this algorithm has only been accelerated on supercomputer class computer named Cray XMT and no work exists that demonstrates performance evaluation and comparison of this algorithm on relatively lower-cost Multicore and GPGPU based platforms.
The Rise of Social Botnets: Attacks and Countermeasures
Venue: arXiv cs.SI 2016
Year: 2016

Online social networks (OSNs) are increasingly threatened by social bots which are software-controlled OSN accounts that mimic human users with malicious intentions. A social botnet refers to a group of social bots under the control of a single botmaster, which collaborate to conduct malicious behavior while mimicking the interactions among normal OSN users to reduce their individual risk of being detected. We demonstrate the effectiveness and advantages of exploiting a social botnet for spam distribution and digital-influence manipulation through real experiments on Twitter and also trace-driven simulations. We also propose the corresponding countermeasures and evaluate their effectiveness. Our results can help understand the potentially detrimental effects of social botnets and help OSNs improve their bot(net) detection systems.
megaman: Manifold Learning with Millions of points
Venue: arXiv cs.LG 2016
Year: 2016

Manifold Learning is a class of algorithms seeking a low-dimensional non-linear representation of high-dimensional data. Thus manifold learning algorithms are, at least in theory, most applicable to high-dimensional data and sample sizes to enable accurate estimation of the manifold. Despite this, most existing manifold learning implementations are not particularly scalable. Here we present a Python package that implements a variety of manifold learning algorithms in a modular and scalable fashion, using fast approximate neighbors searches and fast sparse eigendecompositions. The package incorporates theoretical advances in manifold learning, such as the unbiased Laplacian estimator and the estimation of the embedding distortion by the Riemannian metric method. In benchmarks, even on a single-core desktop computer, our code embeds millions of data points in minutes, and takes just 200 minutes to embed the main sample of galaxy spectra from the Sloan Digital Sky Survey --- consisting of 0.6 million samples in 3750-dimensions --- a task which has not previously been possible.
Leveraging Crowd for Game-based Learning: A Case Study of Privacy Education Game Design and Evaluation by Crowdsourcing
Venue: arXiv cs.CY 2016
Year: 2016

As the Internet grows in importance, it is vital to develop methods and techniques for educating end-users to improve their awareness of online privacy. Web-based education tools have been proven effective in many domains and have been increasingly adopted by many online professional and educational services. However, the design and development of Web-based education tools for online privacy is still in the early stage. The traditional solutions always involve privacy experts who have sophisticated expertise. Such involvement can make the tool development costly. Furthermore, it is not clear how inspiring and effective these education tools are to general users of varying backgrounds, specially to novice users who have rarely dealt with online privacy issues before. In this paper, we design, develop, and evaluate a game-based privacy learning system by leveraging the wisdom of a crowd of non-experts on Amazon Mechanic Turk. Empirical study demonstrates that the crowd can provide high-quality ideas of designing and developing a practical, educational privacy learning game.
A Novel Design of Linear Phase Non-uniform Digital Filter Banks
Venue: arXiv cs.IT 2016
Year: 2016

In many applications such as wireless communications and subband adaptive filtering, we need to design non-uniform filter banks (NUFB), which may lead to better performances and reduced hardware complexity when compared to uniform filter bank. NUFB satisfying linear phase property for all the constituent filters, are desirable in applications such as speech and image processing and in communication. This paper proposes a novel design of non-uniform modified discrete fourier transform filter bank (MDFT FB). Here, each non-uniform channel is obtained by merging the nearby channels of a uniform MDFT FB. The reported works of non-uniform cosine modulated filter banks (CMFBs) do not satisfy linear phase property for all the constituent filters. In this work, we introduce the design of a non-uniform MDFT FB which satisfies linear phase property for all the constituent filters. The proposed design of the non-uniform MDFT FB is checked utilizing the alias cancellation among the channels, distortion and flatness condition of the channels. A condition is derived to find the channels when merged with adjacent channels, will cause aliasing in M channels. In the design and implementation of the proposed non-uniform MDFT FB, the structure of the uniform MDFT filter bank is preserved and hence all the advantages of MDFT FB over the DFT filter bank, are guaranteed. Hence without increasing the design complexity, the non-uniform MDFT FB is designed.