OpenRaiser/Intern-Atlas huggingface dataset:
Chi-squared Amplification: Identifying Hidden Hubs
Venue: arXiv cs.LG 2016
Year: 2016

We consider the following general hidden hubs model: an $n \times n$ random matrix $A$ with a subset $S$ of $k$ special rows (hubs): entries in rows outside $S$ are generated from the probability distribution $p_0 \sim N(0,σ_0^2)$; for each row in $S$, some $k$ of its entries are generated from $p_1 \sim N(0,σ_1^2)$, $σ_1>σ_0$, and the rest of the entries from $p_0$. The problem is to identify the high-degree hubs efficiently. This model includes and significantly generalizes the planted Gaussian Submatrix Model, where the special entries are all in a $k \times k$ submatrix. There are two well-known barriers: if $k\geq c\sqrt{n\ln n}$, just the row sums are sufficient to find $S$ in the general model. For the submatrix problem, this can be improved by a $\sqrt{\ln n}$ factor to $k \ge c\sqrt{n}$ by spectral methods or combinatorial methods. In the variant with $p_0=\pm 1$ (with probability $1/2$ each) and $p_1\equiv 1$, neither barrier has been broken. We give a polynomial-time algorithm to identify all the hidden hubs with high probability for $k \ge n^{0.5-δ}$ for some $δ>0$, when $σ_1^2>2σ_0^2$. The algorithm extends to the setting where planted entries might have different variances each at least as large as $σ_1^2$. We also show a nearly matching lower bound: for $σ_1^2 \le 2σ_0^2$, there is no polynomial-time Statistical Query algorithm for distinguishing between a matrix whose entries are all from $N(0,σ_0^2)$ and a matrix with $k=n^{0.5-δ}$ hidden hubs for any $δ>0$. The lower bound as well as the algorithm are related to whether the chi-squared distance of the two distributions diverges. At the critical value $σ_1^2=2σ_0^2$, we show that the general hidden hubs problem can be solved for $k\geq c\sqrt n(\ln n)^{1/4}$, improving on the naive row sum-based method.
Higher contagion and weaker ties mean anger spreads faster than joy in social media
Venue: arXiv cs.SI 2016
Year: 2016

Increasing evidence suggests that, similar to face-to-face communications, human emotions also spread in online social media. However, the mechanisms underlying this emotional contagion, for example, whether different feelings spread in unlikely ways or how the spread of emotions relates to the social network, is rarely investigated. Indeed, because of high costs and spatio-temporal limitations, explorations of this topic are challenging using conventional questionnaires or controlled experiments. Because they are collection points for natural affective responses of massive individuals, online social media sites offer an ideal proxy for tackling this issue from the perspective of computational social science. In this paper, based on the analysis of millions of tweets in Weibo, surprisingly, we find that anger is more contagious than joy, indicating that it can spark more angry follow-up tweets. Moreover, regarding dissemination in social networks, anger travels easily along weaker ties than joy, meaning that it can infiltrate different communities and break free of local traps because strangers share such content more often. Through a simple diffusion model, we reveal that greater contagion and weaker ties function cooperatively to speed up anger's spread. The diffusion of real-world events with different dominant emotions provides further testimony to the findings. To the best of our knowledge, this is the first time that quantitative long-term evidence has been presented that reveals a difference in the mechanism by which joy and anger are disseminated. Our findings shed light on both personal anger management in human communications and on controlling collective outrage in cyberspace.
An Algorithm to Realize Rate-Splitting in Gaussian Multi-access Channel
Venue: arXiv cs.IT 2016
Year: 2016

Rate Splitting Multiple Access (RSMA) is a code division multi-access technique which can achieve any base in the multi-access capacity polymatroid without high coding complexity or synchronization among the transmitting users. In this paper, a practical algorithm is proposed to compute the splitting coefficients and the successive decoding order of virtual users in Gaussian RSMA transmission. Based on the proposed algorithm, a deterministic mapping is built between the system parameters and the objective rate tuple for RSMA. As a result, the application of the RSMA technique becomes possible in current communication systems.
Speech Signal Analysis for the Estimation of Heart Rates Under Different Emotional States
Venue: arXiv cs.SD 2016
Year: 2016

A non-invasive method for the monitoring of heart activity can help to reduce the deaths caused by heart disorders such as stroke, arrhythmia and heart attack. The human voice can be considered as a biometric data that can be used for estimation of heart rate. In this paper, we propose a method for estimating the heart rate from human speech dynamically using voice signal analysis and by the development of an empirical linear predictor model. The correlation between the voice signal and heart rate are established by classifiers and prediction of the heart rates with or without emotions are done using linear models. The prediction accuracy was tested using the data collected from 15 subjects, it is about 4050 samples of speech signals and corresponding electrocardiogram samples. The proposed approach can use for early non-invasive detection of heart rate changes that can be correlated to an emotional state of the individual and also can be used as a tool for diagnosis of heart conditions in real-time situations.
Channel Estimation for Diffusive Molecular Communications
Venue: arXiv cs.IT 2016
Year: 2016

In molecular communication (MC) systems, the \textit{expected} number of molecules observed at the receiver over time after the instantaneous release of molecules by the transmitter is referred to as the channel impulse response (CIR). Knowledge of the CIR is needed for the design of detection and equalization schemes. In this paper, we present a training-based CIR estimation framework for MC systems which aims at estimating the CIR based on the \textit{observed} number of molecules at the receiver due to emission of a \textit{sequence} of known numbers of molecules by the transmitter. Thereby, we distinguish two scenarios depending on whether or not statistical channel knowledge is available. In particular, we derive maximum likelihood (ML) and least sum of square errors (LSSE) estimators which do not require any knowledge of the channel statistics. For the case, when statistical channel knowledge is available, the corresponding maximum a posteriori (MAP) and linear minimum mean square error (LMMSE) estimators are provided. As performance bound, we derive the classical Cramer Rao (CR) lower bound, valid for any unbiased estimator, which does not exploit statistical channel knowledge, and the Bayesian CR lower bound, valid for any unbiased estimator, which exploits statistical channel knowledge. Finally, we propose optimal and suboptimal training sequence designs for the considered MC system. Simulation results confirm the analysis and compare the performance of the proposed estimation techniques with the respective CR lower bounds.
DeepDiary: Automatic Caption Generation for Lifelogging Image Streams
Venue: arXiv cs.CV 2016
Year: 2016

Lifelogging cameras capture everyday life from a first-person perspective, but generate so much data that it is hard for users to browse and organize their image collections effectively. In this paper, we propose to use automatic image captioning algorithms to generate textual representations of these collections. We develop and explore novel techniques based on deep learning to generate captions for both individual images and image streams, using temporal consistency constraints to create summaries that are both more compact and less noisy. We evaluate our techniques with quantitative and qualitative results, and apply captioning to an image retrieval application for finding potentially private images. Our results suggest that our automatic captioning algorithms, while imperfect, may work well enough to help users manage lifelogging photo collections.
LDPC Lattice Codes for Full-Duplex Relay Channels
Venue: arXiv cs.IT 2016
Year: 2016

Low density parity check (LDPC) lattices are obtained from Construction D' and a family of nested binary LDPC codes. We consider an special case of these lattices with one binary LDPC code as underlying code. This special case of LDPC lattices can be obtained by lifting binary LDPC codes using Construction A lattices. The LDPC lattices were the first family of lattices which have efficient decoding in high dimensions. We employ the encoding and decoding of the LDPC lattices in a cooperative transmission framework. We establish two efficient shaping methods based on hypercube shaping and Voronoi shaping, to obtain LDPC lattice codes. Then, we propose the implementation of block Markov encoding for one-way and two-way relay networks using LDPC lattice codes. This entails owning an efficient method for decomposing full-rate codebook into lower rate codebooks. We apply different decomposition schemes for one-way and two-way relay channels which are the altered versions of the decomposition methods of low density lattice codes (LDLCs). Due to the lower complexity of the decoding for LDPC lattices comparing to LDLCs, the complexity of our schemes are significantly lower than the ones proposed for LDLCs. The efficiency of the proposed schemes are presented using simulation results.
Sensor Selection and Power Allocation Strategies for Energy Harvesting Wireless Sensor Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate the problem of jointly selecting a predefined number of energy-harvesting (EH) sensors and computing the optimal power allocation. The ultimate goal is to minimize the reconstruction distortion at the fusion center. This optimization problem is, unfortunately, non-convex. To circumvent that, we propose two suboptimal strategies: (i) a joint sensor selection and power allocation (JSS-EH) scheme that, we prove, is capable of iteratively finding a stationary solution of the original problem from a sequence of surrogate convex problems; and (ii) a separate sensor selection and power allocation (SS-EH) scheme, on which basis we can identify a sensible sensor selection and analytically find a power allocation policy by solving a convex problem. We also discuss the interplay between the two strategies. Performance in terms of reconstruction distortion, impact of initialization, actual subsets of selected sensors and computed power allocation policies, etc., is assessed by means of computer simulations. To that aim, an EH-agnostic sensor selection strategy, a lower bound on distortion, and an online version of the SS-EH and JSS-EH schemes are derived and used for benchmarking.
Interactive and Iterative Discovery of Entity Network Subgraphs
Venue: arXiv cs.SI 2016
Year: 2016

Graph mining to extract interesting components has been studied in various guises, e.g., communities, dense subgraphs, cliques. However, most existing works are based on notions of frequency and connectivity and do not capture subjective interestingness from a user's viewpoint. Furthermore, existing approaches to mine graphs are not interactive and cannot incorporate user feedbacks in any natural manner. In this paper, we address these gaps by proposing a graph maximum entropy model to discover surprising connected subgraph patterns from entity graphs. This model is embedded in an interactive visualization framework to enable human-in-the-loop, model-guided data exploration. Using case studies on real datasets, we demonstrate how interactions between users and the maximum entropy model lead to faster and explainable conclusions.
Capturing Lombardi Flow in Orthogonal Drawings by Minimizing the Number of Segments
Venue: arXiv cs.DM 2016
Year: 2016

Inspired by the artwork of Mark Lombardi, we study the problem of constructing orthogonal drawings where a small number of horizontal and vertical line segments covers all vertices. We study two problems on orthogonal drawings of planar graphs, one that minimizes the total number of line segments and another that minimizes the number of line segments that cover all the vertices. We show that the first problem can be solved by a non-trivial modification of the flow-network orthogonal bend-minimization algorithm of Tamassia, resulting in a polynomial-time algorithm. We show that the second problem is NP-hard even for planar graphs with maximum degree 3. Given this result, we then address this second optimization problem for trees and series-parallel graphs with maximum degree 3. For both graph classes, we give polynomial-time algorithms for upward orthogonal drawings with the minimum number of segments covering the vertices.
Reed-Solomon and Concatenated Codes with Applications in Space Communication
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we provide a detailed description of Reed-Solomon (RS) codes, the most important algorithms for decoding them, and their use in concatenated coding systems for space applications. In the current literature there is scattered information regarding the bit-level implementation of such codes for either space systems or any other type of application. Consequently, we start with a general overview of the channel coding systems used in space communications and then we focus in the finest details. We first present a detailed description of the required algebra of RS codes with detailed examples. Next, the steps of the encoding and decoding algorithms are described with detail and again with additional examples. Next, we focus on a particularly important class of concatenated encoders/decoders namely the Consultative Committee for Space Data Systems (CCSDS) concatenated coding system that uses RS as the outer code, and a convolutional inner code. Finally, we perform a thorough performance evaluation of the presented codes under the AWGN channel model.
Machine Learning-augmented Predictive Modeling of Turbulent Separated Flows over Airfoils
Venue: arXiv cs.CE 2016
Year: 2016

A modeling paradigm is developed to augment predictive models of turbulence by effectively utilizing limited data generated from physical experiments. The key components of our approach involve inverse modeling to infer the spatial distribution of model discrepancies, and, machine learning to reconstruct discrepancy information from a large number of inverse problems into corrective model forms. We apply the methodology to turbulent flows over airfoils involving flow separation. Model augmentations are developed for the Spalart Allmaras (SA) model using adjoint-based full field inference on experimentally measured lift coefficient data. When these model forms are reconstructed using neural networks (NN) and embedded within a standard solver, we show that much improved predictions in lift can be obtained for geometries and flow conditions that were not used to train the model. The NN-augmented SA model also predicts surface pressures extremely well. Portability of this approach is demonstrated by confirming that predictive improvements are preserved when the augmentation is embedded in a different commercial finite-element solver. The broader vision is that by incorporating data that can reveal the form of the innate model discrepancy, the applicability of data-driven turbulence models can be extended to more general flows.
Almost Perfect Privacy for Additive Gaussian Privacy Filters
Venue: arXiv cs.IT 2016
Year: 2016

We study the maximal mutual information about a random variable $Y$ (representing non-private information) displayed through an additive Gaussian channel when guaranteeing that only $ε$ bits of information is leaked about a random variable $X$ (representing private information) that is correlated with $Y$. Denoting this quantity by $g_ε(X,Y)$, we show that for perfect privacy, i.e., $ε=0$, one has $g_0(X,Y)=0$ for any pair of absolutely continuous random variables $(X,Y)$ and then derive a second-order approximation for $g_ε(X,Y)$ for small $ε$. This approximation is shown to be related to the strong data processing inequality for mutual information under suitable conditions on the joint distribution $P_{XY}$. Next, motivated by an operational interpretation of data privacy, we formulate the privacy-utility tradeoff in the same setup using estimation-theoretic quantities and obtain explicit bounds for this tradeoff when $ε$ is sufficiently small using the approximation formula derived for $g_ε(X,Y)$.
Julia Implementation of the Dynamic Distributed Dimensional Data Model
Venue: arXiv cs.MS 2016
Year: 2016

Julia is a new language for writing data analysis programs that are easy to implement and run at high performance. Similarly, the Dynamic Distributed Dimensional Data Model (D4M) aims to clarify data analysis operations while retaining strong performance. D4M accomplishes these goals through a composable, unified data model on associative arrays. In this work, we present an implementation of D4M in Julia and describe how it enables and facilitates data analysis. Several experiments showcase scalable performance in our new Julia version as compared to the original Matlab implementation.
Viewpoint and Topic Modeling of Current Events
Venue: arXiv cs.CL 2016
Year: 2016

There are multiple sides to every story, and while statistical topic models have been highly successful at topically summarizing the stories in corpora of text documents, they do not explicitly address the issue of learning the different sides, the viewpoints, expressed in the documents. In this paper, we show how these viewpoints can be learned completely unsupervised and represented in a human interpretable form. We use a novel approach of applying CorrLDA2 for this purpose, which learns topic-viewpoint relations that can be used to form groups of topics, where each group represents a viewpoint. A corpus of documents about the Israeli-Palestinian conflict is then used to demonstrate how a Palestinian and an Israeli viewpoint can be learned. By leveraging the magnitudes and signs of the feature weights of a linear SVM, we introduce a principled method to evaluate associations between topics and viewpoints. With this, we demonstrate, both quantitatively and qualitatively, that the learned topic groups are contextually coherent, and form consistently correct topic-viewpoint associations.
Are wearable devices ready for HTTPS? Measuring the cost of secure communication protocols on wearable devices
Venue: arXiv cs.CR 2016
Year: 2016

The majority of available wearable devices require communication with Internet servers for data analysis and storage, and rely on a paired smartphone to enable secure communication. However, wearable devices are mostly equipped with WiFi network interfaces, enabling direct communication with the Internet. Secure communication protocols should then run on these wearables itself, yet it is not clear if they can be efficiently supported. In this paper, we show that wearable devices are ready for direct and secure Internet communication by means of experiments with both controlled and Internet servers. We observe that the overall energy consumption and communication delay can be reduced with direct Internet connection via WiFi from wearables compared to using smartphones as relays via Bluetooth. We also show that the additional HTTPS cost caused by TLS handshake and encryption is closely related to number of parallel connections, and has the same relative impact on wearables and smartphones.
Generating Synthetic Data for Text Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Generating synthetic images is an art which emulates the natural process of image generation in a closest possible manner. In this work, we exploit such a framework for data generation in handwritten domain. We render synthetic data using open source fonts and incorporate data augmentation schemes. As part of this work, we release 9M synthetic handwritten word image corpus which could be useful for training deep network architectures and advancing the performance in handwritten word spotting and recognition tasks.
Transitive Hashing Network for Heterogeneous Multimedia Retrieval
Venue: arXiv cs.CV 2016
Year: 2016

Hashing has been widely applied to large-scale multimedia retrieval due to the storage and retrieval efficiency. Cross-modal hashing enables efficient retrieval from database of one modality in response to a query of another modality. Existing work on cross-modal hashing assumes heterogeneous relationship across modalities for hash function learning. In this paper, we relax the strong assumption by only requiring such heterogeneous relationship in an auxiliary dataset different from the query/database domain. We craft a hybrid deep architecture to simultaneously learn the cross-modal correlation from the auxiliary dataset, and align the dataset distributions between the auxiliary dataset and the query/database domain, which generates transitive hash codes for heterogeneous multimedia retrieval. Extensive experiments exhibit that the proposed approach yields state of the art multimedia retrieval performance on public datasets, i.e. NUS-WIDE, ImageNet-YahooQA.
Self-contained NoSQL Resources for Cross-Domain RDF
Venue: arXiv cs.DB 2016
Year: 2016

Cross-domain knowledge bases such as DBpedia, Freebase and YAGO have emerged as encyclopedic hubs in the Web of Linked Data. Despite enabling several practical applications in the Semantic Web, the large-scale, schema-free nature of such graphs often precludes research groups from employing them widely as evaluation test cases for entity resolution and instance-based ontology alignment applications. Although the ground-truth linkages between the three knowledge bases above are available, they are not amenable to resource-limited applications. One reason is that the ground-truth files are not self-contained, meaning that a researcher must usually perform a series of expensive joins (typically in MapReduce) to obtain usable information sets. In this paper, we upload several publicly licensed data resources to the public cloud and use simple Hadoop clusters to compile, and make accessible, three cross-domain self-contained test cases involving linked instances from DBpedia, Freebase and YAGO. Self-containment is enabled by virtue of a simple NoSQL JSON-like serialization format. Potential applications for these resources, particularly related to testing transfer learning research hypotheses, are also briefly described.
An Improved Algorithm for Diameter-Optimally Augmenting Paths in a Metric Space
Venue: arXiv cs.DS 2016
Year: 2016

Let $P$ be a path graph of $n$ vertices embedded in a metric space. We consider the problem of adding a new edge to $P$ such that the diameter of the resulting graph is minimized. Previously (in ICALP 2015) the problem was solved in $O(n\log^3 n)$ time. In this paper, based on new observations and different algorithmic techniques, we present an $O(n\log n)$ time algorithm.