OpenRaiser/Intern-Atlas huggingface dataset:
Semantic Enrichment of Mobile Phone Data Records Using Background Knowledge
Venue: arXiv cs.AI 2015
Year: 2015

Every day, billions of mobile network events (i.e. CDRs) are generated by cellular phone operator companies. Latent in this data are inspiring insights about human actions and behaviors, the discovery of which is important because context-aware applications and services hold the key to user-driven, intelligent services, which can enhance our everyday lives such as social and economic development, urban planning, and health prevention. The major challenge in this area is that interpreting such a big stream of data requires a deep understanding of mobile network events' context through available background knowledge. This article addresses the issues in context awareness given heterogeneous and uncertain data of mobile network events missing reliable information on the context of this activity. The contribution of this research is a model from a combination of logical and statistical reasoning standpoints for enabling human activity inference in qualitative terms from open geographical data that aimed at improving the quality of human behaviors recognition tasks from CDRs. We use open geographical data, Openstreetmap (OSM), as a proxy for predicting the content of human activity in the area. The user study performed in Trento shows that predicted human activities (top level) match the survey data with around 93% overall accuracy. The extensive validation for predicting a more specific economic type of human activity performed in Barcelona, by employing credit card transaction data. The analysis identifies that appropriately normalized data on points of interest (POI) is a good proxy for predicting human economical activities, with 84% accuracy on average. So the model is proven to be efficient for predicting the context of human activity, when its total level could be efficiently observed from cell phone data records, missing contextual information however.
The Degraded Gaussian Diamond-Wiretap Channel
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we present nontrivial upper and lower bounds on the secrecy capacity of the degraded Gaussian diamond-wiretap channel and identify several ranges of channel parameters where these bounds coincide with useful intuitions. Furthermore, we investigate the effect of the presence of an eavesdropper on the capacity. We consider the following two scenarios regarding the availability of randomness: 1) a common randomness is available at the source and the two relays and 2) a randomness is available only at the source and there is no available randomness at the relays. We obtain the upper bound by taking into account the correlation between the two relay signals and the availability of randomness at each encoder. For the lower bound, we propose two types of coding schemes: 1) a decode-and-forward scheme where the relays cooperatively transmit the message and the fictitious message and 2) a partial DF scheme incorporated with multicoding in which each relay sends an independent partial message and the whole or partial fictitious message using dependent codewords.
A Hierarchical Distance-dependent Bayesian Model for Event Coreference Resolution
Venue: arXiv cs.CL 2015
Year: 2015

We present a novel hierarchical distance-dependent Bayesian model for event coreference resolution. While existing generative models for event coreference resolution are completely unsupervised, our model allows for the incorporation of pairwise distances between event mentions -- information that is widely used in supervised coreference models to guide the generative clustering processing for better event clustering both within and across documents. We model the distances between event mentions using a feature-rich learnable distance function and encode them as Bayesian priors for nonparametric clustering. Experiments on the ECB+ corpus show that our model outperforms state-of-the-art methods for both within- and cross-document event coreference resolution.
Strong Converse Exponent for Degraded Broadcast Channels at Rates outside the Capacity Region
Venue: arXiv cs.IT 2015
Year: 2015

We consider the discrete memoryless degraded broadcast channels. We prove that the error probability of decoding tends to one exponentially for rates outside the capacity region and derive an explicit lower bound of this exponent function. We shall demonstrate that the information spectrum approach is quite useful for investigating this problem.
XJ-BP: Express Journey Belief Propagation Decoding for Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

This paper presents a novel propagation (BP) based decoding algorithm for polar codes. The proposed algorithm facilitates belief propagation by utilizing the specific constituent codes that exist in the factor graph, which results in an express journey (XJ) for belief information to propagate in each decoding iteration. In addition, this XJ-BP decoder employs a novel round-trip message passing scheduling method for the increased efficiency. The proposed method simplifies min-sum (MS) BP decoder by 40.6%. Along with the round-trip scheduling, the XJ-BP algorithm reduces the computational complexity of MS BP decoding by 90.4%; this enables an energy-efficient hardware implementation of BP decoding in practice.
Converses for distributed estimation via strong data processing inequalities
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of distributed estimation, where local processors observe independent samples conditioned on a common random parameter of interest, map the observations to a finite number of bits, and send these bits to a remote estimator over independent noisy channels. We derive converse results for this problem, such as lower bounds on Bayes risk. The main technical tools include a lower bound on the Bayes risk via mutual information and small ball probability, as well as strong data processing inequalities for the relative entropy. Our results can recover and improve some existing results on distributed estimation with noiseless channels, and also capture the effect of noisy channels on the estimation performance.
Towards a better understanding and behavior recognition of inhabitants in smart cities. A public transport case
Venue: arXiv cs.CY 2015
Year: 2015

The idea of modern urban systems and smart cities requires monitoring and careful analysis of different signals. Such signals can originate from different sources and one of the most promising is the BTS, i.e. base transceiver station, an element of mobile carrier networks. This paper presents the fundamental problems of elicitation, classification and understanding of such signals so as to develop context-aware and pro-active systems in urban areas. These systems are characterized by the omnipresence of computing which is strongly focused on providing on-line support to users/inhabitants of smart cities. A method of analyzing selected elements of mobile phone datasets through understanding inhabitants' behavioral fingerprints to obtain smart scenarios for public transport is proposed. Some scenarios are outlined. A multi-agent system is proposed. A formalism based on graphs that allows reasoning about inhabitant behaviors is also proposed.
A New Approach to Adaptive Signal Processing
Venue: arXiv cs.SY 2015
Year: 2015

A unified linear algebraic approach to adaptive signal processing (ASP) is presented. Starting from just Ax=b, key ASP algorithms are derived in a simple, systematic, and integrated manner without requiring any background knowledge to the field. Algorithms covered are Steepest Descent, LMS, Normalized LMS, Kaczmarz, Affine Projection, RLS, Kalman filter, and MMSE/Least Square Wiener filters. By following this approach, readers will discover a synthesis; they will learn that one and only one equation is involved in all these algorithms. They will also learn that this one equation forms the basis of more advanced algorithms like reduced rank adaptive filters, extended Kalman filter, particle filters, multigrid methods, preconditioning methods, Krylov subspace methods and conjugate gradients. This will enable them to enter many sophisticated realms of modern research and development. Eventually, this one equation will not only become their passport to ASP but also to many highly specialized areas of computational science and engineering.
x.ent: R Package for Entities and Relations Extraction based on Unsupervised Learning and Document Structure
Venue: arXiv cs.CL 2015
Year: 2015

Relation extraction with accurate precision is still a challenge when processing full text databases. We propose an approach based on cooccurrence analysis in each document for which we used document organization to improve accuracy of relation extraction. This approach is implemented in a R package called \emph{x.ent}. Another facet of extraction relies on use of extracted relation into a querying system for expert end-users. Two datasets had been used. One of them gets interest from specialists of epidemiology in plant health. For this dataset usage is dedicated to plant-disease exploration through agricultural information news. An open-data platform exploits exports from \emph{x.ent} and is publicly available.
First Steps Towards a Runtime Comparison of Natural and Artificial Evolution
Venue: arXiv cs.NE 2015
Year: 2015

Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1)EA. We show that SSWM can have a moderate advantage over the (1+1)EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1)EA by taking advantage of information on the fitness gradient.
On the Minimum Distance of Array-Based Spatially-Coupled Low-Density Parity-Check Codes
Venue: arXiv cs.IT 2015
Year: 2015

An array low-density parity-check (LDPC) code is a quasi-cyclic LDPC code specified by two integers $q$ and $m$, where $q$ is an odd prime and $m \leq q$. The exact minimum distance, for small $q$ and $m$, has been calculated, and tight upper bounds on it for $m \leq 7$ have been derived. In this work, we study the minimum distance of the spatially-coupled version of these codes. In particular, several tight upper bounds on the optimal minimum distance for coupling length at least two and $m=3,4,5$, that are independent of $q$ and that are valid for all values of $q \geq q_0$ where $q_0$ depends on $m$, are presented. Furthermore, we show by exhaustive search that by carefully selecting the edge spreading or unwrapping procedure, the minimum distance (when $q$ is not very large) can be significantly increased, especially for $m=5$.
Speculative Segmented Sum for Sparse Matrix-Vector Multiplication on Heterogeneous Processors
Venue: arXiv cs.MS 2015
Year: 2015

Sparse matrix-vector multiplication (SpMV) is a central building block for scientific software and graph applications. Recently, heterogeneous processors composed of different types of cores attracted much attention because of their flexible core configuration and high energy efficiency. In this paper, we propose a compressed sparse row (CSR) format based SpMV algorithm utilizing both types of cores in a CPU-GPU heterogeneous processor. We first speculatively execute segmented sum operations on the GPU part of a heterogeneous processor and generate a possibly incorrect results. Then the CPU part of the same chip is triggered to re-arrange the predicted partial sums for a correct resulting vector. On three heterogeneous processors from Intel, AMD and nVidia, using 20 sparse matrices as a benchmark suite, the experimental results show that our method obtains significant performance improvement over the best existing CSR-based SpMV algorithms. The source code of this work is downloadable at https://github.com/bhSPARSE/Benchmark_SpMV_using_CSR
Resource requirements and speed versus geometry of unconditionally secure physical key exchanges
Venue: arXiv cs.CR 2015
Year: 2015

The imperative need for unconditional secure key exchange is expounded by the increasing connectivity of networks and by the increasing number and level of sophistication of cyberattacks. Two concepts that are information theoretically secure are quantum key distribution (QKD) and Kirchoff-law-Johnson-noise (KLJN). However, these concepts require a dedicated connection between hosts in peer-to-peer (P2P) networks which can be impractical and or cost prohibitive. A practical and cost effective method is to have each host share their respective cable(s) with other hosts such that two remote hosts can realize a secure key exchange without the need of an additional cable or key exchanger. In this article we analyze the cost complexities of cable, key exchangers, and time required in the star network. We mentioned the reliability of the star network and compare it with other network geometries. We also conceived a protocol and equation for the number of secure bit exchange periods needed in a star network. We then outline other network geometries and trade-off possibilities that seem interesting to explore.
Cultural Event Recognition with Visual ConvNets and Temporal Models
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents our contribution to the ChaLearn Challenge 2015 on Cultural Event Classification. The challenge in this task is to automatically classify images from 50 different cultural events. Our solution is based on the combination of visual features extracted from convolutional neural networks with temporal information using a hierarchical classifier scheme. We extract visual features from the last three fully connected layers of both CaffeNet (pretrained with ImageNet) and our fine tuned version for the ChaLearn challenge. We propose a late fusion strategy that trains a separate low-level SVM on each of the extracted neural codes. The class predictions of the low-level SVMs form the input to a higher level SVM, which gives the final event scores. We achieve our best result by adding a temporal refinement step into our classification scheme, which is applied directly to the output of each low-level SVM. Our approach penalizes high classification scores based on visual features when their time stamp does not match well an event-specific temporal distribution learned from the training and validation data. Our system achieved the second best result in the ChaLearn Challenge 2015 on Cultural Event Classification with a mean average precision of 0.767 on the test set.
LP formulations for secrecy over erasure networks with feedback
Venue: arXiv cs.IT 2015
Year: 2015

We design polynomial time schemes for secure message transmission over arbitrary networks, in the presence of an eavesdropper, and where each edge corresponds to an erasure channel with public feedback. Our schemes are described through linear programming (LP) formulations, that explicitly select (possibly different) sets of paths for key-generation and message sending. Although our LPs are not always capacity-achieving, they outperform the best known alternatives in the literature, and extend to incorporate several interesting scenaria.
The Range of Topological Effects on Communication
Venue: arXiv cs.CC 2015
Year: 2015

We continue the study of communication cost of computing functions when inputs are distributed among $k$ processors, each of which is located at one vertex of a network/graph called a terminal. Every other node of the network also has a processor, with no input. The communication is point-to-point and the cost is the total number of bits exchanged by the protocol, in the worst case, on all edges. Chattopadhyay, Radhakrishnan and Rudra (FOCS'14) recently initiated a study of the effect of topology of the network on the total communication cost using tools from $L_1$ embeddings. Their techniques provided tight bounds for simple functions like Element-Distinctness (ED), which depend on the 1-median of the graph. This work addresses two other kinds of natural functions. We show that for a large class of natural functions like Set-Disjointness the communication cost is essentially $n$ times the cost of the optimal Steiner tree connecting the terminals. Further, we show for natural composed functions like $\text{ED} \circ \text{XOR}$ and $\text{XOR} \circ \text{ED}$, the naive protocols suggested by their definition is optimal for general networks. Interestingly, the bounds for these functions depend on more involved topological parameters that are a combination of Steiner tree and 1-median costs. To obtain our results, we use some new tools in addition to ones used in Chattopadhyay et. al. These include (i) viewing the communication constraints via a linear program; (ii) using tools from the theory of tree embeddings to prove topology sensitive direct sum results that handle the case of composed functions and (iii) representing the communication constraints of certain problems as a family of collection of multiway cuts, where each multiway cut simulates the hardness of computing the function on the star topology.
WxBS: Wide Baseline Stereo Generalizations
Venue: arXiv cs.CV 2015
Year: 2015

We have presented a new problem -- the wide multiple baseline stereo (WxBS) -- which considers matching of images that simultaneously differ in more than one image acquisition factor such as viewpoint, illumination, sensor type or where object appearance changes significantly, e.g. over time. A new dataset with the ground truth for evaluation of matching algorithms has been introduced and will be made public. We have extensively tested a large set of popular and recent detectors and descriptors and show than the combination of RootSIFT and HalfRootSIFT as descriptors with MSER and Hessian-Affine detectors works best for many different nuisance factors. We show that simple adaptive thresholding improves Hessian-Affine, DoG, MSER (and possibly other) detectors and allows to use them on infrared and low contrast images. A novel matching algorithm for addressing the WxBS problem has been introduced. We have shown experimentally that the WxBS-M matcher dominantes the state-of-the-art methods both on both the new and existing datasets.
Leveraging disjoint communities for detecting overlapping community structure
Venue: arXiv cs.SI 2015
Year: 2015

Network communities represent mesoscopic structure for understanding the organization of real-world networks, where nodes often belong to multiple communities and form overlapping community structure in the network. Due to non-triviality in finding the exact boundary of such overlapping communities, this problem has become challenging, and therefore huge effort has been devoted to detect overlapping communities from the network. In this paper, we present PVOC (Permanence based Vertex-replication algorithm for Overlapping Community detection), a two-stage framework to detect overlapping community structure. We build on a novel observation that non-overlapping community structure detected by a standard disjoint community detection algorithm from a network has high resemblance with its actual overlapping community structure, except the overlapping part. Based on this observation, we posit that there is perhaps no need of building yet another overlapping community finding algorithm; but one can efficiently manipulate the output of any existing disjoint community finding algorithm to obtain the required overlapping structure. We propose a new post-processing technique that by combining with any existing disjoint community detection algorithm, can suitably process each vertex using a new vertex-based metric, called permanence, and thereby finds out overlapping candidates with their community memberships. Experimental results on both synthetic and large real-world networks show that PVOC significantly outperforms six state-of-the-art overlapping community detection algorithms in terms of high similarity of the output with the ground-truth structure. Thus our framework not only finds meaningful overlapping communities from the network, but also allows us to put an end to the constant effort of building yet another overlapping community detection algorithm.
Handling oversampling in dynamic networks using link prediction
Venue: arXiv cs.SI 2015
Year: 2015

Oversampling is a common characteristic of data representing dynamic networks. It introduces noise into representations of dynamic networks, but there has been little work so far to compensate for it. Oversampling can affect the quality of many important algorithmic problems on dynamic networks, including link prediction. Link prediction seeks to predict edges that will be added to the network given previous snapshots. We show that not only does oversampling affect the quality of link prediction, but that we can use link prediction to recover from the effects of oversampling. We also introduce a novel generative model of noise in dynamic networks that represents oversampling. We demonstrate the results of our approach on both synthetic and real-world data.
Lower Bounds for the Size of Nondeterministic Circuits
Venue: arXiv cs.CC 2015
Year: 2015

Nondeterministic circuits are a nondeterministic computation model in circuit complexity theory. In this paper, we prove a $3(n-1)$ lower bound for the size of nondeterministic $U_2$-circuits computing the parity function. It is known that the minimum size of (deterministic) $U_2$-circuits computing the parity function exactly equals $3(n-1)$. Thus, our result means that nondeterministic computation is useless to compute the parity function by $U_2$-circuits and cannot reduce the size from $3(n-1)$. To the best of our knowledge, this is the first nontrivial lower bound for the size of nondeterministic circuits (including formulas, constant depth circuits, and so on) with unlimited nondeterminism for an explicit Boolean function. We also discuss an approach to proving lower bounds for the size of deterministic circuits via lower bounds for the size of nondeterministic restricted circuits.
Massive MIMO Full-Duplex Relaying with Optimal Power Allocation for Independent Multipairs
Venue: arXiv cs.IT 2015
Year: 2015

With the help of an in-band full-duplex relay station, it is possible to simultaneously transmit and receive signals from multiple users. The performance of such system can be greatly increased when the relay station is equipped with a large number of antennas on both transmitter and receiver sides. In this paper, we exploit the use of massive arrays to effectively suppress the loopback interference (LI) of a decode-and-forward relay (DF) and evaluate the performance of the end-to-end (e2e) transmission. This paper assumes imperfect channel state information is available at the relay and designs a minimum mean-square error (MMSE) filter to mitigate the interference. Subsequently, we adopt zero-forcing (ZF) filters for both detection and beamforming. The performance of such system is evaluated in terms of bit error rate (BER) at both relay and destinations, and an optimal choice for the transmission power at the relay is shown. We then propose a complexity efficient optimal power allocation (OPA) algorithm that, using the channel statistics, computes the minimum power that satisfies the rate constraints of each pair. The results obtained via simulation show that when both MMSE filtering and OPA method are used, better values for the energy efficiency are attained.