OpenRaiser/Intern-Atlas huggingface dataset:
Discovering and Characterizing Mobility Patterns in Urban Spaces: A Study of Manhattan Taxi Data
Venue: arXiv cs.SI 2016
Year: 2016

Nowadays, human movement in urban spaces can be traced digitally in many cases. It can be observed that movement patterns are not constant, but vary across time and space. In this work,we characterize such spatio-temporal patterns with an innovative combination of two separate approaches that have been utilized for studying human mobility in the past. First, by using non-negative tensor factorization (NTF), we are able to cluster human behavior based on spatio-temporal dimensions. Second, for understanding these clusters, we propose to use HypTrails, a Bayesian approach for expressing and comparing hypotheses about human trails. To formalize hypotheses we utilize data that is publicly available on the Web, namely Foursquare data and census data provided by an open data platform. By applying this combination of approaches to taxi data in Manhattan, we can discover and explain different patterns in human mobility that cannot be identified in a collective analysis. As one example, we can find a group of taxi rides that end at locations with a high number of party venues (according to Foursquare) on weekend nights. Overall, our work demonstrates that human mobility is not one-dimensional but rather contains different facets both in time and space which we explain by utilizing online data. The findings of this paper argue for a more fine-grained analysis of human mobility in order to make more informed decisions for e.g., enhancing urban structures, tailored traffic control and location-based recommender systems.
Semantic Word Clusters Using Signed Normalized Graph Cuts
Venue: arXiv cs.CL 2016
Year: 2016

Vector space representations of words capture many aspects of word similarity, but such methods tend to make vector spaces in which antonyms (as well as synonyms) are close to each other. We present a new signed spectral normalized graph cut algorithm, signed clustering, that overlays existing thesauri upon distributionally derived vector representations of words, so that antonym relationships between word pairs are represented by negative weights. Our signed clustering algorithm produces clusters of words which simultaneously capture distributional and synonym relations. We evaluate these clusters against the SimLex-999 dataset (Hill et al.,2014) of human judgments of word pair similarities, and also show the benefit of using our clusters to predict the sentiment of a given text.
Hierarchical Latent Word Clustering
Venue: arXiv cs.CL 2016
Year: 2016

This paper presents a new Bayesian non-parametric model by extending the usage of Hierarchical Dirichlet Allocation to extract tree structured word clusters from text data. The inference algorithm of the model collects words in a cluster if they share similar distribution over documents. In our experiments, we observed meaningful hierarchical structures on NIPS corpus and radiology reports collected from public repositories.
Alternative Authentication in the Wild
Venue: arXiv cs.HC 2016
Year: 2016

Alphanumeric authentication routinely fails to regulate access to resources with the required stringency, primarily due to usability issues. Initial deployment did not reveal the problems of passwords, deep and profound flaws only emerged once passwords were deployed in the wild. The need for a replacement is widely acknowledged yet despite over a decade of research into knowledge-based alternatives, few, if any, have been adopted by industry. Alternatives are unconvincing for three primary reasons. The first is that alternatives are rarely investigated beyond the initial proposal, with only the results from a constrained lab test provided to convince adopters of their viability. The second is that alternatives are seldom tested realistically where the authenticator mediates access to something of value. The third is that the testing rarely varies the device or context beyond that initially targeted. In the modern world different devices are used across a variety of contexts. What works well in one context may easily fail in another. Consequently, the contribution of this paper is an "in the wild" evaluation of an alternative authentication mechanism that had demonstrated promise in its lab evaluation. In the field test the mechanism was deployed to actual users to regulate access to an application in a context beyond that initially proposed. The performance of the mechanism is reported and discussed. We conclude by reflecting on the value of field evaluations of alternative authentication mechanisms.
Data-driven Rank Breaking for Efficient Rank Aggregation
Venue: arXiv cs.LG 2016
Year: 2016

Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. Rank-breaking is a common practice to reduce the computational complexity of learning the global ranking. The individual preferences are broken into pairwise comparisons and applied to efficient algorithms tailored for independent paired comparisons. However, due to the ignored dependencies in the data, naive rank-breaking approaches can result in inconsistent estimates. The key idea to produce accurate and consistent estimates is to treat the pairwise comparisons unequally, depending on the topology of the collected data. In this paper, we provide the optimal rank-breaking estimator, which not only achieves consistency but also achieves the best error bound. This allows us to characterize the fundamental tradeoff between accuracy and complexity. Further, the analysis identifies how the accuracy depends on the spectral gap of a corresponding comparison graph.
Interference-Aware Decoupled Cell Association in Device-to-Device based 5G Networks
Venue: arXiv cs.NI 2016
Year: 2016

Cell association in cellular networks is an important aspect that impacts network capacity and eventually quality of experience. The scope of this work is to investigate the different and generalized cell association (CAS) strategies for Device-to-Device (D2D) communications in a cellular network infrastructure. To realize this, we optimize D2D-based cell association by using the notion of uplink and downlink decoupling that was proven to offer significant performance gains. We propose an integer linear programming (ILP) optimization framework to achieve efficient D2D cell association that minimizes the interference caused by D2D devices onto cellular communications in the uplink as well as improve the D2D resource utilization efficiency. Simulation results based on Vodafone's LTE field trial network in a dense urban scenario highlight the performance gains and render this proposal a candidate design approach for future 5G networks.
On Structured Sparsity of Phonological Posteriors for Linguistic Parsing
Venue: arXiv cs.CL 2016
Year: 2016

The speech signal conveys information on different time scales from short time scale or segmental, associated to phonological and phonetic information to long time scale or supra segmental, associated to syllabic and prosodic information. Linguistic and neurocognitive studies recognize the phonological classes at segmental level as the essential and invariant representations used in speech temporal organization. In the context of speech processing, a deep neural network (DNN) is an effective computational method to infer the probability of individual phonological classes from a short segment of speech signal. A vector of all phonological class probabilities is referred to as phonological posterior. There are only very few classes comprising a short term speech signal; hence, the phonological posterior is a sparse vector. Although the phonological posteriors are estimated at segmental level, we claim that they convey supra-segmental information. Specifically, we demonstrate that phonological posteriors are indicative of syllabic and prosodic events. Building on findings from converging linguistic evidence on the gestural model of Articulatory Phonology as well as the neural basis of speech perception, we hypothesize that phonological posteriors convey properties of linguistic classes at multiple time scales, and this information is embedded in their support (index) of active coefficients. To verify this hypothesis, we obtain a binary representation of phonological posteriors at the segmental level which is referred to as first-order sparsity structure; the high-order structures are obtained by the concatenation of first-order binary vectors. It is then confirmed that the classification of supra-segmental linguistic events, the problem known as linguistic parsing, can be achieved with high accuracy using asimple binary pattern matching of first-order or high-order structures.
On the Capacity of Multilevel NAND Flash Memory Channels
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we initiate a first information-theoretic study on multilevel NAND flash memory channels with intercell interference. More specifically, for a multilevel NAND flash memory channel under mild assumptions, we first prove that such a channel is indecomposable and it features asymptotic equipartition property; we then further prove that stationary processes achieve its information capacity, and consequently, as its order tends to infinity, its Markov capacity converges to its information capacity; eventually, we establish that its operational capacity is equal to its information capacity. Our results suggest that it is highly plausible to apply the ideas and techniques in the computation of the capacity of finite-state channels, which are relatively better explored, to that of the capacity of multilevel NAND flash memory channels.
Can Negligible Cooperation Increase Network Reliability?
Venue: arXiv cs.IT 2016
Year: 2016

In network cooperation strategies, nodes work together with the aim of increasing transmission rates or reliability. This paper demonstrates that enabling cooperation between the transmitters of a two-user multiple access channel, via a cooperation facilitator that has access to both messages, always results in a network whose maximal- and average-error sum-capacities are the same---even when those capacities differ in the absence of cooperation and the information shared with the encoders is negligible. From this result, it follows that if a multiple access channel with no transmitter cooperation has different maximal- and average-error sum-capacities, then the maximal-error sum-capacity of the network consisting of this channel and a cooperation facilitator is not continuous with respect to the output edge capacities of the facilitator. This shows that there exist networks where sharing even a negligible number of bits per channel use with the encoders yields a non-negligible benefit.
Active Sensing of Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

This paper develops an active sensing method to estimate the relative weight (or trust) agents place on their neighbors' information in a social network. The model used for the regression is based on the steady state equation in the linear DeGroot model under the influence of stubborn agents, i.e., agents whose opinions are not influenced by their neighbors. This method can be viewed as a \emph{social RADAR}, where the stubborn agents excite the system and the latter can be estimated through the reverberation observed from the analysis of the agents' opinions. The social network sensing problem can be interpreted as a blind compressed sensing problem with a sparse measurement matrix. We prove that the network structure will be revealed when a sufficient number of stubborn agents independently influence a number of ordinary (non-stubborn) agents. We investigate the scenario with a deterministic or randomized DeGroot model and propose a consistent estimator of the steady states for the latter scenario. Simulation results on synthetic and real world networks support our findings.
A Beta-Beta Achievability Bound with Applications
Venue: arXiv cs.IT 2016
Year: 2016

A channel coding achievability bound expressed in terms of the ratio between two Neyman-Pearson $β$ functions is proposed. This bound is the dual of a converse bound established earlier by Polyanskiy and Verdú (2014). The new bound turns out to simplify considerably the analysis in situations where the channel output distribution is not a product distribution, for example due to a cost constraint or a structural constraint (such as orthogonality or constant composition) on the channel inputs. Connections to existing bounds in the literature are discussed. The bound is then used to derive 1) an achievability bound on the channel dispersion of additive non-Gaussian noise channels with random Gaussian codebooks, 2) the channel dispersion of the exponential-noise channel, 3) a second-order expansion for the minimum energy per bit of an AWGN channel, and 4) a lower bound on the maximum coding rate of a multiple-input multiple-output Rayleigh-fading channel with perfect channel state information at the receiver, which is the tightest known achievability result.
Agile-SD: A Linux-based TCP Congestion Control Algorithm for Supporting High-speed and Short-distance Networks
Venue: arXiv cs.NI 2016
Year: 2016

Recently, high-speed and short-distance networks are widely deployed and their necessity is rapidly increasing everyday. This type of networks is used in several network applications; such as Local Area Networks (LAN) and Data Center Networks (DCN). In LANs and DCNs, high-speed and short-distance networks are commonly deployed to connect between computing and storage elements in order to provide rapid services. Indeed, the overall performance of such networks is significantly influenced by the Congestion Control Algorithm (CCA) which suffers from the problem of bandwidth under-utilization, especially if the applied buffer regime is very small. In this paper, a novel loss-based CCA tailored for high-speed and Short-Distance (SD) networks, namely Agile-SD, has been proposed. The main contribution of the proposed CCA is to implement the mechanism of agility factor. Further, intensive simulation experiments have been carried out to evaluate the performance of Agile-SD compared to Compound and Cubic which are the default CCAs of the most commonly used operating systems. The results of the simulation experiments show that the proposed CCA outperforms the compared CCAs in terms of average throughput, loss ratio and fairness, especially when a small buffer is applied. Moreover, Agile-SD shows lower sensitivity to the buffer size change and packet error rate variation which increases its efficiency.
Polar Codes for Broadcast Channels with Receiver Message Side Information and Noncausal State Available at the Encoder
Venue: arXiv cs.IT 2016
Year: 2016

In this paper polar codes are proposed for two receiver broadcast channels with receiver message side information (BCSI) and noncausal state available at the encoder, referred to as BCSI with noncausal state for short, where the two receivers know a priori the private messages intended for each other. This channel generalizes BCSI with common message and Gelfand-Pinsker problem and has applications in cellular communication systems. We establish an achievable rate region for BCSI with noncausal state and show that it is strictly larger than the straightforward extension of the Gelfand-Pinsker result. To achieve the established rate region with polar coding, we present polar codes for the general Gelfand-Pinsker problem, which adopts chaining construction and utilizes causal information to pre-transmit the frozen bits. It is also shown that causal information is necessary to pre-transmit the frozen bits. Based on the result of Gelfand-Pinsker problem, we use the chaining construction method to design polar codes for BCSI with noncausal state. The difficulty is that there are multiple chains sharing common information bit indices. To avoid value assignment conflicts, a nontrivial polarization alignment scheme is presented. It is shown that the proposed rate region is tight for degraded BCSI with noncausal state.
Semantic Place Descriptors for Classification and Map Discovery
Venue: arXiv cs.IR 2016
Year: 2016

Urban environments develop complex, non-obvious structures that are often hard to represent in the form of maps or guides. Finding the right place to go often requires intimate familiarity with the location in question and cannot easily be deduced by visitors. In this work, we exploit large-scale samples of usage information, in the form of mobile phone traces and geo-tagged Twitter messages in order to automatically explore and annotate city maps via kernel density estimation. Our experiments are based on one year's worth of mobile phone activity collected by Nokia's Mobile Data Challenge (MDC). We show that usage information can be a strong predictor of semantic place categories, allowing us to automatically annotate maps based on the behavior of the local user base.
Power Consumption Modeling and Prediction in a Hybrid CPU-GPU-MIC Supercomputer (preliminary version)
Venue: arXiv cs.DC 2016
Year: 2016

Power consumption is a major obstacle for High Performance Computing (HPC) systems in their quest towards the holy grail of ExaFLOP performance. Significant advances in power efficiency have to be made before this goal can be attained and accurate modeling is an essential step towards power efficiency by optimizing system operating parameters to match dynamic energy needs. In this paper we present a study of power consumption by jobs in Eurora, a hybrid CPU-GPU-MIC system installed at the largest Italian data center. Using data from a dedicated monitoring framework, we build a data-driven model of power consumption for each user in the system and use it to predict the power requirements of future jobs. We are able to achieve good prediction results for over 80% of the users in the system. For the remaining users, we identify possible reasons why prediction performance is not as good. Possible applications for our predictive modeling results include scheduling optimization, power-aware billing and system-scale power modeling. All the scripts used for the study have been made available on GitHub.
Business Process Modeling and Execution -- A Compiler for Distributed Microservices
Venue: arXiv cs.SE 2016
Year: 2016

In this paper, we propose to rethink the dominant logic of how to model business processes. We think that an actor based approach supports in a much better way the fundamental nature of business processes. We present a proposal for a compiler architecture to model and execute business processes as a set of communicating microservices that are hosted on a general purpose virtual machine for distributed execution.
On the decomposition of Generalized Additive Independence models
Venue: arXiv cs.DM 2016
Year: 2016

The GAI (Generalized Additive Independence) model proposed by Fishburn is a generalization of the additive utility model, which need not satisfy mutual preferential independence. Its great generality makes however its application and study difficult. We consider a significant subclass of GAI models, namely the discrete 2-additive GAI models, and provide for this class a decomposition into nonnegative monotone terms. This decomposition allows a reduction from exponential to quadratic complexity in any optimization problem involving discrete 2-additive models, making them usable in practice.
Gaussian Approximation for the Downlink Interference in Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper derives Gaussian approximation bounds for the standardized aggregate wireless interference (AWI) in the downlink of K-tier heterogeneous cellular networks when base stations in each tier are distributed over the plane according to a (possibly non-homogeneous) Poisson process. The proposed methodology is general enough to account for general bounded path-loss models and fading statistics. The deviations of the distribution of the standardized AWI from the standard normal distribution are measured in terms of the Kolmogorov-Smirnov distance. An explicit expression bounding the Kolmogorov-Smirnov distance between these two distributions is obtained as a function of a broad range of network parameters such as per-tier transmission power levels, base station locations, fading statistics and the path-loss model. A simulation study is performed to corroborate the analytical results. In particular, a good statistical match between the standardized AWI distribution and its normal approximation occurs even for moderately dense heterogeneous cellular networks. These results are expected to have important ramifications on the characterization of performance upper and lower bounds for emerging 5G network architectures.
Geometric-Algebra LMS Adaptive Filter and its Application to Rotation Estimation
Venue: arXiv cs.CV 2016
Year: 2016

This paper exploits Geometric (Clifford) Algebra (GA) theory in order to devise and introduce a new adaptive filtering strategy. From a least-squares cost function, the gradient is calculated following results from Geometric Calculus (GC), the extension of GA to handle differential and integral calculus. The novel GA least-mean-squares (GA-LMS) adaptive filter, which inherits properties from standard adaptive filters and from GA, is developed to recursively estimate a rotor (multivector), a hypercomplex quantity able to describe rotations in any dimension. The adaptive filter (AF) performance is assessed via a 3D point-clouds registration problem, which contains a rotation estimation step. Calculating the AF computational complexity suggests that it can contribute to reduce the cost of a full-blown 3D registration algorithm, especially when the number of points to be processed grows. Moreover, the employed GA/GC framework allows for easily applying the resulting filter to estimating rotors in higher dimensions.
Topological descriptors for 3D surface analysis
Venue: arXiv cs.CV 2016
Year: 2016

We investigate topological descriptors for 3D surface analysis, i.e. the classification of surfaces according to their geometric fine structure. On a dataset of high-resolution 3D surface reconstructions we compute persistence diagrams for a 2D cubical filtration. In the next step we investigate different topological descriptors and measure their ability to discriminate structurally different 3D surface patches. We evaluate their sensitivity to different parameters and compare the performance of the resulting topological descriptors to alternative (non-topological) descriptors. We present a comprehensive evaluation that shows that topological descriptors are (i) robust, (ii) yield state-of-the-art performance for the task of 3D surface analysis and (iii) improve classification performance when combined with non-topological descriptors.
On the Latent Variable Interpretation in Sum-Product Networks
Venue: arXiv cs.AI 2016
Year: 2016

One of the central themes in Sum-Product networks (SPNs) is the interpretation of sum nodes as marginalized latent variables (LVs). This interpretation yields an increased syntactic or semantic structure, allows the application of the EM algorithm and to efficiently perform MPE inference. In literature, the LV interpretation was justified by explicitly introducing the indicator variables corresponding to the LVs' states. However, as pointed out in this paper, this approach is in conflict with the completeness condition in SPNs and does not fully specify the probabilistic model. We propose a remedy for this problem by modifying the original approach for introducing the LVs, which we call SPN augmentation. We discuss conditional independencies in augmented SPNs, formally establish the probabilistic interpretation of the sum-weights and give an interpretation of augmented SPNs as Bayesian networks. Based on these results, we find a sound derivation of the EM algorithm for SPNs. Furthermore, the Viterbi-style algorithm for MPE proposed in literature was never proven to be correct. We show that this is indeed a correct algorithm, when applied to selective SPNs, and in particular when applied to augmented SPNs. Our theoretical results are confirmed in experiments on synthetic data and 103 real-world datasets.