OpenRaiser/Intern-Atlas huggingface dataset:
On the Complexity of Estimating Renyi Divergences
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies the complexity of estimating Renyi divergences of discrete distributions: $p$ observed from samples and the baseline distribution $q$ known \emph{a priori}. Extending the results of Acharya et al. (SODA'15) on estimating Renyi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Renyi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on \emph{events occurring unlikely} in $q$, and is unbounded in general (no matter what an estimation technique is used). For any divergence of order bigger than $1$, we provide upper and lower bounds on the number of samples dependent on probabilities of $p$ and $q$. We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of $q$ are non-negligible. This gives theoretical insights into heuristics used in applied papers to handle numerical instability, which occurs for small probabilities of $q$. Our result explains that small probabilities should be handled with care not only because of numerical issues, but also because of a blow up in sample complexity.
Arbitrary Beam Synthesis of Different Hybrid Beamforming Systems
Venue: arXiv cs.IT 2017
Year: 2017

For future mmWave mobile communication systems the use of analog/hybrid beamforming is envisioned be a key as- pect. The synthesis of beams is a key technology of enable the best possible operation during beamsearch, data transmission and MU MIMO operation. The developed method for synthesizing beams is based on previous work in radar technology considering only phase array antennas. With this technique it is possible to generate a desired beam of any shape with the constraints of the desired target transceiver antenna frontend. It is not constraint to a certain antenna array geometry, but can handle 1d, 2d and even 3d antenna array geometries like cylindric arrays. The numerical examples show that the method can synthesize beams by considering a user defined tradeoff between gain, transition width and passband ripples.
Social media marketing analytics : a multicultural approach applied to the beauty \& cosmetic sector
Venue: arXiv cs.SI 2017
Year: 2017

We present in this paper a multicultural approach to social media marketing analytics, applied in two Facebook brand pages: French (individualistic culture, the country home of the brand) versus Saudi Arabian (collectivistic culture, one of its country hosts), which are published by an internationalbeauty \& cosmetics firm. Using social network analysis and content analysis, we identify the most popular posts and the most influential users within these two brand pages and highlight the different communities emerging from brand and users interactions. These communities seem to be culture oriented when they are constructed around socialization branded posts and product-line oriented when advertising branded posts are concerned.
Downlink and Uplink Decoupling in Two-Tier Heterogeneous Networks with Multi-Antenna Base Stations
Venue: arXiv cs.IT 2017
Year: 2017

In order to improve the uplink performance of future cellular networks, the idea to decouple the downlink (DL) and uplink (UL) association has recently been shown to provide significant gain in terms of both coverage and rate performance. However, all the work is limited to SISO network. Therefore, to study the gain provided by the DL and UL decoupling in multi-antenna base stations (BSs) setup, we study a two tier heterogeneous network consisting of multi-antenna BSs, and single antenna user equipments (UEs). We use maximal ratio combining (MRC) as a linear receiver at the BSs and using tools from stochastic geometry, we derive tractable expressions for both signal to interference ratio (SIR) coverage probability and rate coverage probability. We observe that as the disparity in the beamforming gain of both tiers increases, the gain in term of SIR coverage probability provided by the decoupled association over non-decoupled association decreases. We further observe that when there is asymmetry in the number of antennas of both tier, then we need further biasing towards femto-tier on the top of decoupled association to balance the load and get optimal rate coverage probability.
An Algebraic-Combinatorial Proof Technique for the GM-MDS Conjecture
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the problem of designing maximum distance separable (MDS) codes over small fields with constraints on the support of their generator matrices. For any given $m\times n$ binary matrix $M$, the GM-MDS conjecture, due to Dau et al., states that if $M$ satisfies the so-called MDS condition, then for any field $\mathbb{F}$ of size $q\geq n+m-1$, there exists an $[n,m]_q$ MDS code whose generator matrix $G$, with entries in $\mathbb{F}$, fits $M$ (i.e., $M$ is the support matrix of $G$). Despite all the attempts by the coding theory community, this conjecture remains still open in general. It was shown, independently by Yan et al. and Dau et al., that the GM-MDS conjecture holds if the following conjecture, referred to as the TM-MDS conjecture, holds: if $M$ satisfies the MDS condition, then the determinant of a transformation matrix $T$, such that $TV$ fits $M$, is not identically zero, where $V$ is a Vandermonde matrix with distinct parameters. In this work, we generalize the TM-MDS conjecture, and present an algebraic-combinatorial approach based on polynomial-degree reduction for proving this conjecture. Our proof technique's strength is based primarily on reducing inherent combinatorics in the proof. We demonstrate the strength of our technique by proving the TM-MDS conjecture for the cases where the number of rows ($m$) of $M$ is upper bounded by $5$. For this class of special cases of $M$ where the only additional constraint is on $m$, only cases with $m\leq 4$ were previously proven theoretically, and the previously used proof techniques are not applicable to cases with $m > 4$.
Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of multi-message private information retrieval (MPIR) from $N$ non-communicating replicated databases. In MPIR, the user is interested in retrieving $P$ messages out of $M$ stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR $C_s^P$ is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol. For the case $P \geq \frac{M}{2}$, we determine the exact sum capacity of MPIR as $C_s^P=\frac{1}{1+\frac{M-P}{PN}}$. The achievable scheme in this case is based on downloading MDS-coded mixtures of all messages. For $P \leq \frac{M}{2}$, we develop lower and upper bounds for all $M,P,N$. These bounds match if the total number of messages $M$ is an integer multiple of the number of desired messages $P$, i.e., $\frac{M}{P} \in \mathbb{N}$. In this case, $C_s^P=\frac{1-\frac{1}{N}}{1-(\frac{1}{N})^{M/P}}$. The achievable scheme in this case generalizes the single-message capacity achieving scheme to have unbalanced number of stages per round of download. For all the remaining cases, the difference between the lower and upper bound is at most $0.0082$, which occurs for $M=5$, $P=2$, $N=2$. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes.
Underpinnings of Digital-photo interaction in Computer-mediated platforms
Venue: arXiv cs.HC 2017
Year: 2017

This dissertation is based on five empirical research articles investigating the different latent factors that motivate and hinder the process of digital-photo interaction in computer-mediated platforms. Study I examine the current practices surrounding digital photos in the context of personal photo repositories (N=15). Study II investigates the gratifications and impeding factors associated with photo-tagging activity on Facebook (N=67). Study III develops and tests an instrument for understanding the gratifications of Facebook photo-sharing (N=368). Study IV examines the impact of various aspects of privacy in relation to photo-sharing intentions on Facebook (N=378). Finally, study V investigates the age and gender differences regarding various aspects of privacy and trust in the context of photo-sharing activity on Facebook (N=378). The dissertation reveals the following findings: First, lack of "social features" is one of the essential reasons for non-acceptance of tagging feature in standalone photo management applications. Second, photo-sharing and photo-tagging adoption and popularity can be attributed to various factors such as affection, attention, communication, disclosure, habit, information sharing, self-expression, socialization, and social influence. Third, age, gender, and activity influence photo-sharing and photo-tagging gratifications. Fourth, in the context of Facebook photo-sharing, various aspects of privacy significantly impact users trust and activity and consequently photo-sharing intentions. Fifth, women and young Facebook users are significantly more concerned about the privacy of their shared photos. Sixth, privacy-protective measures are significantly exercised more by young Facebook users, yet they exhibit more trust and a higher level of activity on Facebook.
Model-driven Scheduling for Distributed Stream Processing Systems
Venue: arXiv cs.DC 2017
Year: 2017

Distributed Stream Processing frameworks are being commonly used with the evolution of Internet of Things(IoT). These frameworks are designed to adapt to the dynamic input message rate by scaling in/out.Apache Storm, originally developed by Twitter is a widely used stream processing engine while others includes Flink, Spark streaming. For running the streaming applications successfully there is need to know the optimal resource requirement, as over-estimation of resources adds extra cost.So we need some strategy to come up with the optimal resource requirement for a given streaming application. In this article, we propose a model-driven approach for scheduling streaming applications that effectively utilizes a priori knowledge of the applications to provide predictable scheduling behavior. Specifically, we use application performance models to offer reliable estimates of the resource allocation required. Further, this intuition also drives resource mapping, and helps narrow the estimated and actual dataflow performance and resource utilization. Together, this model-driven scheduling approach gives a predictable application performance and resource utilization behavior for executing a given DSPS application at a target input stream rate on distributed resources.
Unobtrusive Deferred Update Stabilization for Efficient Geo-Replication
Venue: arXiv cs.DC 2017
Year: 2017

In this paper we propose a novel approach to manage the throughput vs latency tradeoff that emerges when managing updates in geo-replicated systems. Our approach consists in allowing full concurrency when processing local updates and using a deferred local serialisation procedure before shipping updates to remote datacenters. This strategy allows to implement inexpensive mechanisms to ensure system consistency requirements while avoiding intrusive effects on update operations, a major performance limitation of previous systems. We have implemented our approach as a variant of Riak KV. Our extensive evaluation shows that we outperform sequencer-based approaches by almost an order of magnitude in the maximum achievable throughput. Furthermore, unlike previous sequencer-free solutions, our approach reaches nearly optimal remote update visibility latencies without limiting throughput.
Multiuser Communication Based on the DFT Eigenstructure
Venue: arXiv cs.IT 2017
Year: 2017

The eigenstructure of the discrete Fourier transform (DFT) is examined and new systematic procedures to generate eigenvectors of the unitary DFT are proposed. DFT eigenvectors are suggested as user signatures for data communication over the real adder channel (RAC). The proposed multiuser communication system over the 2-user RAC is detailed.
A General Framework for Evaluating Callout Mechanisms in Repeated Auctions
Venue: arXiv cs.GT 2017
Year: 2017

Motivated by online display ad exchanges, we study a setting in which an exchange repeatedly interacts with bidders who have quota, making decisions about which subsets of bidders are called to participate in ad-slot-specific auctions. A bidder with quota cannot respond to more than a certain number of calls per second. In practice, random throttling is the principal solution by which these constraints are enforced. Given the repeated nature of the interaction with its bidders, the exchange has access to data containing information about each bidder's segments of interest. This information can be utilized to design smarter callout mechanisms --- with the potential of improving the exchange's long-term revenue. In this work, we present a general framework for evaluating and comparing the performance of various callout mechanisms using historical auction data only. To measure the impact of a callout mechanism on long-term revenue, we propose a strategic model that captures the repeated interaction between the exchange and bidders. Our model leads us to two metrics for performance: immediate revenue impact and social welfare. Next we present an empirical framework for estimating these two metrics from historical data. For the baseline to compare against, we consider random throttling, as well as a greedy algorithm with certain theoretical guarantees. We propose several natural callout mechanisms and investigate them through our framework on both synthetic and real auction data. We characterize the conditions under which each heuristic performs well and show that, in addition to being computationally faster, in practice our heuristics consistently and significantly outperform the baselines.
Capacity Bounds on the Downlink of Symmetric, Multi-Relay, Single Receiver C-RAN Networks
Venue: arXiv cs.IT 2017
Year: 2017

The downlink of symmetric Cloud Radio Access Networks (C-RANs) with multiple relays and a single receiver is studied. Lower and upper bounds are derived on the capacity. The lower bound is achieved by Marton's coding which facilitates dependence among the multiple-access channel inputs. The upper bound uses Ozarow's technique to augment the system with an auxiliary random variable. The bounds are studied over scalar Gaussian C-RANs and are shown to meet and characterize the capacity for interesting regimes of operation.
The Effect of Different Writing Tasks on Linguistic Style: A Case Study of the ROC Story Cloze Task
Venue: arXiv cs.CL 2017
Year: 2017

A writer's style depends not just on personal traits but also on her intent and mental state. In this paper, we show how variants of the same writing task can lead to measurable differences in writing style. We present a case study based on the story cloze task (Mostafazadeh et al., 2016a), where annotators were assigned similar writing tasks with different constraints: (1) writing an entire story, (2) adding a story ending for a given story context, and (3) adding an incoherent ending to a story. We show that a simple linear classifier informed by stylistic features is able to successfully distinguish among the three cases, without even looking at the story context. In addition, combining our stylistic features with language model predictions reaches state of the art performance on the story cloze challenge. Our results demonstrate that different task framings can dramatically affect the way people write.
The Meta Distribution of the SIR for Cellular Networks with Power Control
Venue: arXiv cs.IT 2017
Year: 2017

The meta distribution of the signal-to-interference ratio (SIR) provides fine-grained information about the performance of individual links in a wireless network. This paper focuses on the analysis of the meta distribution of the SIR for both the cellular network uplink and downlink with fractional power control. For the uplink scenario, an approximation of the interfering user point process with a non-homogeneous Poisson point process is used. The moments of the meta distribution for both scenarios are calculated. Some bounds, the analytical expression, the mean local delay, and the beta approximation of the meta distribution are provided. The results give interesting insights into the effect of the power control in both the uplink and downlink. Detailed simulations show that the approximations made in the analysis are well justified.
Measures of Threaded Discussion Properties
Venue: arXiv cs.CY 2017
Year: 2017

In this paper, we present a set of measures to quantify certain properties of threaded discussions, which are ubiquitous in online learn-ing platforms. In particular, we address how to measure the redundancy of posts, the compactness of topics, and the degree of hierarchy in sub-threads. This preliminary work would very much benefit from discussion and serves as a starting point for ultimately creating optimal structures of threaded discussions depending on the context.
Sparse Algorithm for Robust LSSVM in Primal Space
Venue: arXiv cs.LG 2017
Year: 2017

As enjoying the closed form solution, least squares support vector machine (LSSVM) has been widely used for classification and regression problems having the comparable performance with other types of SVMs. However, LSSVM has two drawbacks: sensitive to outliers and lacking sparseness. Robust LSSVM (R-LSSVM) overcomes the first partly via nonconvex truncated loss function, but the current algorithms for R-LSSVM with the dense solution are faced with the second drawback and are inefficient for training large-scale problems. In this paper, we interpret the robustness of R-LSSVM from a re-weighted viewpoint and give a primal R-LSSVM by the representer theorem. The new model may have sparse solution if the corresponding kernel matrix has low rank. Then approximating the kernel matrix by a low-rank matrix and smoothing the loss function by entropy penalty function, we propose a convergent sparse R-LSSVM (SR-LSSVM) algorithm to achieve the sparse solution of primal R-LSSVM, which overcomes two drawbacks of LSSVM simultaneously. The proposed algorithm has lower complexity than the existing algorithms and is very efficient for training large-scale problems. Many experimental results illustrate that SR-LSSVM can achieve better or comparable performance with less training time than related algorithms, especially for training large scale problems.
An Efficient Global Algorithm for Single-Group Multicast Beamforming
Venue: arXiv cs.IT 2017
Year: 2017

Consider the single-group multicast beamforming problem, where multiple users receive the same data stream simultaneously from a single transmitter. The problem is NP-hard and all existing algorithms for the problem either find suboptimal approximate or local stationary solutions. In this paper, we propose an efficient branch-and-bound algorithm for the problem that is guaranteed to find its global solution. To the best of our knowledge, our proposed algorithm is the first tailored global algorithm for the single-group multicast beamforming problem. Simulation results show that our proposed algorithm is computationally efficient (albeit its theoretical worst-case iteration complexity is exponential with respect to the number of receivers) and it significantly outperforms a state-of-the-art general-purpose global optimization solver called Baron. Our proposed algorithm provides an important benchmark for performance evaluation of existing algorithms for the same problem. By using it as the benchmark, we show that two state-of-the-art algorithms, semidefinite relaxation algorithm and successive linear approximation algorithm, work well when the problem dimension (i.e., the number of antennas at the transmitter and the number of receivers) is small but their performance deteriorates quickly as the problem dimension increases.
Vulnerability of D2D Communications from Interconnected Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

In this paper, we study how rumors in Online Social Networks (OSNs) may impact the performance of device-to-device (D2D) communication. As D2D is a new technology, people may choose not to use it when believed in rumors of its negative impacts. Thus, the cellular network with underlaying D2D is vulnerable to OSNs as rumors in OSNs may decrement the throughput of the cellular network in popular content delivery scenarios. To analyze the vulnerability, we introduce the problem of finding the most critical nodes in the OSN such that the throughput of a content delivery scenario is minimized when a rumor starts from those nodes. We then propose an efficient solution to the critical nodes detection problem. The severity of such vulnerability is supported by extensive experiments in various simulation settings, from which we observe up to $40\%$ reduction in network throughput.
An Implementation of Faster RCNN with Study for Region Sampling
Venue: arXiv cs.CV 2017
Year: 2017

We adapted the join-training scheme of Faster RCNN framework from Caffe to TensorFlow as a baseline implementation for object detection. Our code is made publicly available. This report documents the simplifications made to the original pipeline, with justifications from ablation analysis on both PASCAL VOC 2007 and COCO 2014. We further investigated the role of non-maximal suppression (NMS) in selecting regions-of-interest (RoIs) for region classification, and found that a biased sampling toward small regions helps performance and can achieve on-par mAP to NMS-based sampling when converged sufficiently.
Refining StreamBED Through Expert Interviews, Design Feedback, and a Low Fidelity Prototype
Venue: arXiv cs.HC 2017
Year: 2017

StreamBED is an embodied VR training for citizen scientists to make qualitative stream assessments. Early findings garnered positive feedback about training qualitative assessment using a virtual representation of different stream spaces, but presented field-specific challenges; novice biologists had trouble interpreting qualitative protocols, and needed substantive guidance to look for and interpret environment cues. In order to address these issues in the redesign, this work uses research through design (RTD) methods to consider feedback from expert stream biologists, firsthand stream monitoring experience, discussions with education and game designers, and feedback from a low fidelity prototype. The qualitative findings found that training should facilitate personal narratives, maximize realism, and should use social dynamics to scaffold learning.
Transfer from Multiple Linear Predictive State Representations (PSR)
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we tackle the problem of transferring policy from multiple partially observable source environments to a partially observable target environment modeled as predictive state representation. This is an entirely new approach with no previous work, other than the case of transfer in fully observable domains. We develop algorithms to successfully achieve policy transfer when we have the model of both the source and target tasks and discuss in detail their performance and shortcomings. These algorithms could be a starting point for the field of transfer learning in partial observability.