OpenRaiser/Intern-Atlas huggingface dataset:
Low Algorithmic Complexity Entropy-deceiving Graphs
Venue: arXiv cs.IT 2017
Year: 2017

In estimating the complexity of objects, in particular of graphs, it is common practice to rely on graph- and information-theoretic measures. Here, using integer sequences with properties such as Borel normality, we explain how these measures are not independent of the way in which an object, such as a graph, can be described or observed. From observations that can reconstruct the same graph and are therefore essentially translations of the same description, we will see that when applying a computable measure such as Shannon Entropy, not only is it necessary to pre-select a feature of interest where there is one, and to make an arbitrary selection where there is not, but also that more general properties, such as the causal likelihood of a graph as a measure (opposed to randomness), can be largely misrepresented by computable measures such as Entropy and Entropy rate. We introduce recursive and non-recursive (uncomputable) graphs and graph constructions based on these integer sequences, whose different lossless descriptions have disparate Entropy values, thereby enabling the study and exploration of a measure's range of applications and demonstrating the weaknesses of computable measures of complexity.
Towards Instance Optimal Bounds for Best Arm Identification
Venue: arXiv cs.LG 2017
Year: 2017

In the classical best arm identification (Best-$1$-Arm) problem, we are given $n$ stochastic bandit arms, each associated with a reward distribution with an unknown mean. We would like to identify the arm with the largest mean with probability at least $1-δ$, using as few samples as possible. Understanding the sample complexity of Best-$1$-Arm has attracted significant attention since the last decade. However, the exact sample complexity of the problem is still unknown. Recently, Chen and Li made the gap-entropy conjecture concerning the instance sample complexity of Best-$1$-Arm. Given an instance $I$, let $μ_{[i]}$ be the $i$th largest mean and $Δ_{[i]}=μ_{[1]}-μ_{[i]}$ be the corresponding gap. $H(I)=\sum_{i=2}^nΔ_{[i]}^{-2}$ is the complexity of the instance. The gap-entropy conjecture states that $Ω\left(H(I)\cdot\left(\lnδ^{-1}+\mathsf{Ent}(I)\right)\right)$ is an instance lower bound, where $\mathsf{Ent}(I)$ is an entropy-like term determined by the gaps, and there is a $δ$-correct algorithm for Best-$1$-Arm with sample complexity $O\left(H(I)\cdot\left(\lnδ^{-1}+\mathsf{Ent}(I)\right)+Δ_{[2]}^{-2}\ln\lnΔ_{[2]}^{-1}\right)$. If the conjecture is true, we would have a complete understanding of the instance-wise sample complexity of Best-$1$-Arm. We make significant progress towards the resolution of the gap-entropy conjecture. For the upper bound, we provide a highly nontrivial algorithm which requires \[O\left(H(I)\cdot\left(\lnδ^{-1} +\mathsf{Ent}(I)\right)+Δ_{[2]}^{-2}\ln\lnΔ_{[2]}^{-1}\mathrm{polylog}(n,δ^{-1})\right)\] samples in expectation. For the lower bound, we show that for any Gaussian Best-$1$-Arm instance with gaps of the form $2^{-k}$, any $δ$-correct monotone algorithm requires $Ω\left(H(I)\cdot\left(\lnδ^{-1} + \mathsf{Ent}(I)\right)\right)$ samples in expectation.
A Systematic Identification and Analysis of Scientists on Twitter
Venue: arXiv cs.DL 2017
Year: 2017

Metrics derived from Twitter and other social media---often referred to as altmetrics---are increasingly used to estimate the broader social impacts of scholarship. Such efforts, however, may produce highly misleading results, as the entities that participate in conversations about science on these platforms are largely unknown. For instance, if altmetric activities are generated mainly by scientists, does it really capture broader social impacts of science? Here we present a systematic approach to identifying and analyzing scientists on Twitter. Our method can identify scientists across many disciplines, without relying on external bibliographic data, and be easily adapted to identify other stakeholder groups in science. We investigate the demographics, sharing behaviors, and interconnectivity of the identified scientists. We find that Twitter has been employed by scholars across the disciplinary spectrum, with an over-representation of social and computer and information scientists; under-representation of mathematical, physical, and life scientists; and a better representation of women compared to scholarly publishing. Analysis of the sharing of URLs reveals a distinct imprint of scholarly sites, yet only a small fraction of shared URLs are science-related. We find an assortative mixing with respect to disciplines in the networks between scientists, suggesting the maintenance of disciplinary walls in social media. Our work contributes to the literature both methodologically and conceptually---we provide new methods for disambiguating and identifying particular actors on social media and describing the behaviors of scientists, thus providing foundational information for the construction and use of indicators on the basis of social media metrics.
Fast binary embeddings with Gaussian circulant matrices: improved bounds
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of encoding a finite set of vectors into a small number of bits while approximately retaining information on the angular distances between the vectors. By deriving improved variance bounds related to binary Gaussian circulant embeddings, we largely fix a gap in the proof of the best known fast binary embedding method. Our bounds also show that well-spreadness assumptions on the data vectors, which were needed in earlier work on variance bounds, are unnecessary. In addition, we propose a new binary embedding with a faster running time on sparse data.
On-line Joint Limit Avoidance for Torque Controlled Robots by Joint Space Parametrization
Venue: arXiv cs.RO 2017
Year: 2017

This paper proposes control laws ensuring the stabilization of a time-varying desired joint trajectory, as well as joint limit avoidance, in the case of fully-actuated manipulators. The key idea is to perform a parametrization of the feasible joint space in terms of exogenous states. It follows that the control of these states allows for joint limit avoidance. One of the main outcomes of this paper is that position terms in control laws are replaced by parametrized terms, where joint limits must be avoided. Stability and convergence of time-varying reference trajectories obtained with the proposed method are demonstrated to be in the sense of Lyapunov. The introduced control laws are verified by carrying out experiments on two degrees-of-freedom of the humanoid robot iCub.
Recurrent Neural Networks With Limited Numerical Precision
Venue: arXiv cs.NE 2017
Year: 2017

Recurrent Neural Networks (RNNs) produce state-of-art performance on many machine learning tasks but their demand on resources in terms of memory and computational power are often high. Therefore, there is a great interest in optimizing the computations performed with these models especially when considering development of specialized low-power hardware for deep networks. One way of reducing the computational needs is to limit the numerical precision of the network weights and biases. This has led to different proposed rounding methods which have been applied so far to only Convolutional Neural Networks and Fully-Connected Networks. This paper addresses the question of how to best reduce weight precision during training in the case of RNNs. We present results from the use of different stochastic and deterministic reduced precision training methods applied to three major RNN types which are then tested on several datasets. The results show that the weight binarization methods do not work with the RNNs. However, the stochastic and deterministic ternarization, and pow2-ternarization methods gave rise to low-precision RNNs that produce similar and even higher accuracy on certain datasets therefore providing a path towards training more efficient implementations of RNNs in specialized hardware.
Learning an Optimization Algorithm through Human Design Iterations
Venue: arXiv cs.LG 2017
Year: 2017

Solving optimal design problems through crowdsourcing faces a dilemma: On one hand, human beings have been shown to be more effective than algorithms at searching for good solutions of certain real-world problems with high-dimensional or discrete solution spaces; on the other hand, the cost of setting up crowdsourcing environments, the uncertainty in the crowd's domain-specific competence, and the lack of commitment of the crowd, all contribute to the lack of real-world application of design crowdsourcing. We are thus motivated to investigate a solution-searching mechanism where an optimization algorithm is tuned based on human demonstrations on solution searching, so that the search can be continued after human participants abandon the problem. To do so, we model the iterative search process as a Bayesian Optimization (BO) algorithm, and propose an inverse BO (IBO) algorithm to find the maximum likelihood estimators of the BO parameters based on human solutions. We show through a vehicle design and control problem that the search performance of BO can be improved by recovering its parameters based on an effective human search. Thus, IBO has the potential to improve the success rate of design crowdsourcing activities, by requiring only good search strategies instead of good solutions from the crowd.
System Reliability, Fault Tolerance and Design Metrics Tradeoffs in the Distributed Minority and Majority Voting Based Redundancy Scheme
Venue: arXiv cs.AR 2017
Year: 2017

The distributed minority and majority voting based redundancy (DMMR) scheme was recently proposed as an efficient alternative to the conventional N-modular redundancy (NMR) scheme for the physical design of mission/safety-critical circuits and systems. The DMMR scheme enables significant improvements in fault tolerance and design metrics compared to the NMR scheme albeit at the expense of a slight decrease in the system reliability. In this context, this paper studies the system reliability, fault tolerance and design metrics tradeoffs in the DMMR scheme compared to the NMR scheme when the majority logic group of the DMMR scheme is increased in size relative to the minority logic group. Some example DMMR and NMR systems were realized using a 32/28nm CMOS process and compared. The results show that 5-of-M DMMR systems have a similar or better fault tolerance whilst requiring similar or fewer function modules than their counterpart NMR systems and simultaneously achieve optimizations in design metrics. Nevertheless, 3-of-M DMMR systems have the upper hand with respect to fault tolerance and design metrics optimizations than the comparable NMR and 5-of-M DMMR systems. With regard to system reliability, NMR systems are closely followed by 5-of-M DMMR systems which are closely followed by 3-of-M DMMR systems. The verdict is 3-of-M DMMR systems are preferable to implement higher levels of redundancy from a combined system reliability, fault tolerance and design metrics perspective to realize mission/safety-critical circuits and systems.
Full-Duplex Backscatter Interference Networks Based on Time-Hopping Spread Spectrum
Venue: arXiv cs.IT 2017
Year: 2017

Future Internet-of-Things (IoT) is expected to wirelessly connect billions of low-complexity devices. For wireless information transfer (WIT) in IoT, high density of IoT devices and their ad hoc communication result in strong interference which acts as a bottleneck on WIT. Furthermore, battery replacement for the massive number of IoT devices is difficult if not infeasible, making wireless energy transfer (WET) desirable. This motivates: (i) the design of full-duplex WIT to reduce latency and enable efficient spectrum utilization, and (ii) the implementation of passive IoT devices using backscatter antennas that enable WET from one device (reader) to another (tag). However, the resultant increase in the density of simultaneous links exacerbates the interference issue. This issue is addressed in this paper by proposing the design of full-duplex backscatter communication (BackCom) networks, where a novel multiple-access scheme based on time-hopping spread-spectrum (TH-SS) is designed to enable both one-way WET and two-way WIT in coexisting backscatter reader-tag links. Comprehensive performance analysis of BackCom networks is presented in this paper, including forward/backward bit-error rates and WET efficiency and outage probabilities, which accounts for energy harvesting at tags, non-coherent and coherent detection at tags and readers, respectively, and the effects of asynchronous transmissions.
Improving Correlation with Human Judgments by Integrating Semantic Similarity with Second--Order Vectors
Venue: arXiv cs.CL 2017
Year: 2017

Vector space methods that measure semantic similarity and relatedness often rely on distributional information such as co--occurrence frequencies or statistical measures of association to weight the importance of particular co--occurrences. In this paper, we extend these methods by incorporating a measure of semantic similarity based on a human curated taxonomy into a second--order vector representation. This results in a measure of semantic relatedness that combines both the contextual information available in a corpus--based vector space representation with the semantic knowledge found in a biomedical ontology. Our results show that incorporating semantic similarity into a second order co--occurrence matrices improves correlation with human judgments for both similarity and relatedness, and that our method compares favorably to various different word embedding methods that have recently been evaluated on the same reference standards we have used.
Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
Venue: arXiv cs.NA 2017
Year: 2017

Machine learning and data mining algorithms are becoming increasingly important in analyzing large volume, multi-relational and multi--modal datasets, which are often conveniently represented as multiway arrays or tensors. It is therefore timely and valuable for the multidisciplinary research community to review tensor decompositions and tensor networks as emerging tools for large-scale data analysis and data mining. We provide the mathematical and graphical representations and interpretation of tensor networks, with the main focus on the Tucker and Tensor Train (TT) decompositions and their extensions or generalizations. Keywords: Tensor networks, Function-related tensors, CP decomposition, Tucker models, tensor train (TT) decompositions, matrix product states (MPS), matrix product operators (MPO), basic tensor operations, multiway component analysis, multilinear blind source separation, tensor completion, linear/multilinear dimensionality reduction, large-scale optimization problems, symmetric eigenvalue decomposition (EVD), PCA/SVD, huge systems of linear equations, pseudo-inverse of very large matrices, Lasso and Canonical Correlation Analysis (CCA) (This is Part 1)
Succinct data-structure for nearest colored node in a tree
Venue: arXiv cs.DS 2017
Year: 2017

We give a succinct data-structure that stores a tree with colors on the nodes. Given a node x and a color alpha, the structure finds the nearest node to x with color alpha. This results improves the $O(n\log n)$-bits structure of Gawrychowski et al.~[CPM 2016].
Public Wi-Fi Monetization via Advertising
Venue: arXiv cs.GT 2017
Year: 2017

The proliferation of public Wi-Fi hotspots has brought new business potentials for Wi-Fi networks, which carry a significant amount of global mobile data traffic today. In this paper, we propose a novel Wi-Fi monetization model for venue owners (VOs) deploying public Wi-Fi hotspots, where the VOs can generate revenue by providing two different Wi-Fi access schemes for mobile users (MUs): (i) the premium access, in which MUs directly pay VOs for their Wi-Fi usage, and (ii) the advertising sponsored access, in which MUs watch advertisements in exchange of the free usage of Wi-Fi. VOs sell their ad spaces to advertisers (ADs) via an ad platform, and share the ADs' payments with the ad platform. We formulate the economic interactions among the ad platform, VOs, MUs, and ADs as a three-stage Stackelberg game. In Stage I, the ad platform announces its advertising revenue sharing policy. In Stage II, VOs determine the Wi-Fi prices (for MUs) and advertising prices (for ADs). In Stage III, MUs make access choices and ADs purchase advertising spaces. We analyze the sub-game perfect equilibrium (SPE) of the proposed game systematically, and our analysis shows the following useful observations. First, the ad platform's advertising revenue sharing policy in Stage I will affect only the VOs' Wi-Fi prices but not the VOs' advertising prices in Stage II. Second, both the VOs' Wi-Fi prices and advertising prices are non-decreasing in the advertising concentration level and non-increasing in the MU visiting frequency. Numerical results further show that the VOs are capable of generating large revenues through mainly providing one type of Wi-Fi access (the premium access or advertising sponsored access), depending on their advertising concentration levels and MU visiting frequencies.
A Consumer-Centric Market for Database Computation in the Cloud
Venue: arXiv cs.DB 2017
Year: 2017

The availability of public computing resources in the cloud has revolutionized data analysis, but requesting cloud resources often involves complex decisions for consumers. Under the current pricing mechanisms, cloud service providers offer several service options and charge consumers based on the resources they use. Before they can decide which cloud resources to request, consumers have to estimate the completion time and cost of their computational tasks for different service options and possibly for different service providers. This estimation is challenging even for expert cloud users. We propose a new market-based framework for pricing computational tasks in the cloud. Our framework introduces an agent between consumers and cloud providers. The agent takes data and computational tasks from users, estimates time and cost for evaluating the tasks, and returns to consumers contracts that specify the price and completion time. Our framework can be applied directly to existing cloud markets without altering the way cloud providers offer and price services. In addition, it simplifies cloud use for consumers by allowing them to compare contracts, rather than choose resources directly. We present design, analytical, and algorithmic contributions focusing on pricing computation contracts, analyzing their properties, and optimizing them in complex workflows. We conduct an experimental evaluation of our market framework over a real-world cloud service and demonstrate empirically that our market ensures three key properties: competitiveness, fairness, and resilience. Finally, we present a fine-grained pricing mechanism for complex workflows and show that it can increase agent profits by more than an order of magnitude in some cases.
Generating realistic scaled complex networks
Venue: arXiv cs.SI 2017
Year: 2017

Research on generative models is a central project in the emerging field of network science, and it studies how statistical patterns found in real networks could be generated by formal rules. Output from these generative models is then the basis for designing and evaluating computational methods on networks, and for verification and simulation studies. During the last two decades, a variety of models has been proposed with an ultimate goal of achieving comprehensive realism for the generated networks. In this study, we (a) introduce a new generator, termed ReCoN; (b) explore how ReCoN and some existing models can be fitted to an original network to produce a structurally similar replica, (c) use ReCoN to produce networks much larger than the original exemplar, and finally (d) discuss open problems and promising research directions. In a comparative experimental study, we find that ReCoN is often superior to many other state-of-the-art network generation methods. We argue that ReCoN is a scalable and effective tool for modeling a given network while preserving important properties at both micro- and macroscopic scales, and for scaling the exemplar data by orders of magnitude in size.
What can (partition) logic contribute to information theory?
Venue: arXiv cs.IT 2017
Year: 2017

Logical probability theory was developed as a quantitative measure based on Boole's logic of subsets. But information theory was developed into a mature theory by Claude Shannon with no such connection to logic. A recent development in logic changes this situation. In category theory, the notion of a subset is dual to the notion of a quotient set or partition, and recently the logic of partitions has been developed in a parallel relationship to the Boolean logic of subsets (subset logic is usually mis-specified as the special case of propositional logic). What then is the quantitative measure based on partition logic in the same sense that logical probability theory is based on subset logic? It is a measure of information that is named "logical entropy" in view of that logical basis. This paper develops the notion of logical entropy and the basic notions of the resulting logical information theory. Then an extensive comparison is made with the corresponding notions based on Shannon entropy.
Large-Scale Multi-Antenna Multi-Sine Wireless Power Transfer
Venue: arXiv cs.IT 2017
Year: 2017

Wireless Power Transfer (WPT) is expected to be a technology reshaping the landscape of low-power applications such as the Internet of Things, Radio Frequency identification (RFID) networks, etc. Although there has been some progress towards multi-antenna multi-sine WPT design, the large-scale design of WPT, reminiscent of massive MIMO in communications, remains an open challenge. In this paper, we derive efficient multiuser algorithms based on a generalizable optimization framework, in order to design transmit sinewaves that maximize the weighted-sum/minimum rectenna output DC voltage. The study highlights the significant effect of the nonlinearity introduced by the rectification process on the design of waveforms in multiuser systems. Interestingly, in the single-user case, the optimal spatial domain beamforming, obtained prior to the frequency domain power allocation optimization, turns out to be Maximum Ratio Transmission (MRT). In contrast, in the general weighted sum criterion maximization problem, the spatial domain beamforming optimization and the frequency domain power allocation optimization are coupled. Assuming channel hardening, low-complexity algorithms are proposed based on asymptotic analysis, to maximize the two criteria. The structure of the asymptotically optimal spatial domain precoder can be found prior to the optimization. The performance of the proposed algorithms is evaluated. Numerical results confirm the inefficiency of the linear model-based design for the single and multi-user scenarios. It is also shown that as nonlinear model-based designs, the proposed algorithms can benefit from an increasing number of sinewaves.