OpenRaiser/Intern-Atlas huggingface dataset:
Intrinsic Grassmann Averages for Online Linear, Robust and Nonlinear Subspace Learning
Venue: arXiv cs.LG 2018
Year: 2018

Principal Component Analysis (PCA) and Kernel Principal Component Analysis (KPCA) are fundamental methods in machine learning for dimensionality reduction. The former is a technique for finding this approximation in finite dimensions and the latter is often in an infinite dimensional Reproducing Kernel Hilbert-space (RKHS). In this paper, we present a geometric framework for computing the principal linear subspaces in both situations as well as for the robust PCA case, that amounts to computing the intrinsic average on the space of all subspaces: the Grassmann manifold. Points on this manifold are defined as the subspaces spanned by $K$-tuples of observations. The intrinsic Grassmann average of these subspaces are shown to coincide with the principal components of the observations when they are drawn from a Gaussian distribution. We show similar results in the RKHS case and provide an efficient algorithm for computing the projection onto the this average subspace. The result is a method akin to KPCA which is substantially faster. Further, we present a novel online version of the KPCA using our geometric framework. Competitive performance of all our algorithms are demonstrated on a variety of real and synthetic data sets.
Information Elicitation for Bayesian Auctions
Venue: arXiv cs.GT 2018
Year: 2018

In this paper we design information elicitation mechanisms for Bayesian auctions. While in Bayesian mechanism design the distributions of the players' private types are often assumed to be common knowledge, information elicitation considers the situation where the players know the distributions better than the decision maker. To weaken the information assumption in Bayesian auctions, we consider an information structure where the knowledge about the distributions is arbitrarily scattered among the players. In such an unstructured information setting, we design mechanisms for unit-demand auctions and additive auctions that aggregate the players' knowledge, generating revenue that are constant approximations to the optimal Bayesian mechanisms with a common prior. Our mechanisms are 2-step dominant-strategy truthful and the revenue increases gracefully with the amount of knowledge the players collectively have.
A scikit-based Python environment for performing multi-label classification
Venue: arXiv cs.LG 2018
Year: 2018

scikit-multilearn is a Python library for performing multi-label classification. The library is compatible with the scikit/scipy ecosystem and uses sparse matrices for all internal operations. It provides native Python implementations of popular multi-label classification methods alongside a novel framework for label space partitioning and division. It includes modern algorithm adaptation methods, network-based label space division approaches, which extracts label dependency information and multi-label embedding classifiers. It provides python wrapped access to the extensive multi-label method stack from Java libraries and makes it possible to extend deep learning single-label methods for multi-label tasks. The library allows multi-label stratification and data set management. The implementation is more efficient in problem transformation than other established libraries, has good test coverage and follows PEP8. Source code and documentation can be downloaded from http://scikit.ml and also via pip. The library follows BSD licensing scheme.
Identifiability and parameter estimation of the single particle lithium-ion battery model
Venue: arXiv cs.SY 2018
Year: 2018

This paper investigates the identifiability and estimation of the parameters of the single particle model (SPM) for lithium-ion battery simulation. Identifiability is addressed both in principle and in practice. The approach begins by grouping parameters and partially non-dimensionalising the SPM to determine the maximum expected degrees of freedom in the problem. We discover that, excluding open circuit voltage, there are only six independent parameters. We then examine the structural identifiability by considering whether the transfer function of the linearised SPM is unique. It is found that the model is unique provided that the electrode open circuit voltage functions have a known non-zero gradient, the parameters are ordered, and the electrode kinetics are lumped into a single charge transfer resistance parameter. We then demonstrate the practical estimation of model parameters from measured frequency-domain experimental electrochemical impedance spectroscopy (EIS) data, and show additionally that the parametrised model provides good predictive capabilities in the time domain, exhibiting a maximum voltage error of 20 mV between model and experiment over a 10 minute dynamic discharge.
Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes
Venue: arXiv cs.IT 2018
Year: 2018

Locally recoverable (LRC) codes have recently been a focus point of research in coding theory due to their theoretical appeal and applications in distributed storage systems. In an LRC code, any erased symbol of a codeword can be recovered by accessing only a small number of other symbols. For LRC codes over a small alphabet (such as binary), the optimal rate-distance trade-off is unknown. We present several new combinatorial bounds on LRC codes including the locality-aware sphere packing and Plotkin bounds. We also develop an approach to linear programming (LP) bounds on LRC codes. The resulting LP bound gives better estimates in examples than the other upper bounds known in the literature. Further, we provide the tightest known upper bound on the rate of linear LRC codes with a given relative distance, an improvement over the previous best known bounds.
The Opacity Problem in Social Contagion
Venue: arXiv cs.SI 2018
Year: 2018

Fads, product adoption, mobs, rumors, memes, and emergent norms are diverse social contagions that have been modeled as network cascades. Empirical study of these cascades is vulnerable to what we describe as the "opacity problem": the inability to observe the critical level of peer influence required to trigger an individual's behavioral change. Even with maximal information, network cascades reveal intervals that bound critical levels of peer exposure, rather than critical values themselves. Existing practice uses interval maxima, which systematically over-estimates the social influence required for behavioral change. Simulations reveal that the over-estimation is likely common and large in magnitude. This is confirmed by an empirical study of hashtag cascades among 3.2 million Twitter users: one in five hashtag adoptions suffers critical value uncertainty due to the opacity problem. Different assumptions about these intervals lead to qualitatively different conclusions about the role of peer reinforcement in diffusion. We introduce a solution that combines identifying tightly bounded intervals with predicting uncertain critical values using node-level information.
A Window into the Soul: Biosensing in Public
Venue: arXiv cs.CY 2018
Year: 2018

Biosensed information represents an emerging class of data with the potential for massive, systematic, and remote or casual collection of personal information about people. Biosensors capture physiological signals in addition to kinesthetic data to draw intimate inferences about individuals' mental states. The proliferation of sensors makes detection, interpretation, and inference of these previously subtle - or otherwise invisible - emotional and physiological signals possible from proximate and remote locations. These sensors pose unprecedented challenges to individual privacy in public through remote, precise, and passively collected data. This paper examines the unique nature and inferential potential of biosensed data by creating a taxonomy of signals that may be collected remotely, via casual contact, or from traces left behind, and considers how these data may be collected and used to create novel privacy concerns - particularly in public. Since biosignals may often be deduced from visual data, this paper uses historic and recent photography cases to explore how social norms evolved in response to remote collection in public. A contextual integrity privacy heuristic is then used to probe the need for new norms and remedies specifically for biosensing privacy threats. This analysis examines the extensibility of relevant legal frameworks in the European Union (EU) and United States (US) as a privacy remedy, and conclude with a brief outline of possible legal or social remedies that may address privacy needs in public with biosensing technologies.
Analyzing the Weighted Nuclear Norm Minimization and Nuclear Norm Minimization based on Group Sparse Representation
Venue: arXiv cs.CV 2018
Year: 2018

Rank minimization methods have attracted considerable interest in various areas, such as computer vision and machine learning. The most representative work is nuclear norm minimization (NNM), which can recover the matrix rank exactly under some restricted and theoretical guarantee conditions. However, for many real applications, NNM is not able to approximate the matrix rank accurately, since it often tends to over-shrink the rank components. To rectify the weakness of NNM, recent advances have shown that weighted nuclear norm minimization (WNNM) can achieve a better matrix rank approximation than NNM, which heuristically set the weight being inverse to the singular values. However, it still lacks a sound mathematical explanation on why WNNM is more feasible than NNM. In this paper, we propose a scheme to analyze WNNM and NNM from the perspective of the group sparse representation. Specifically, we design an adaptive dictionary to bridge the gap between the group sparse representation and the rank minimization models. Based on this scheme, we provide a mathematical derivation to explain why WNNM is more feasible than NNM. Moreover, due to the heuristical set of the weight, WNNM sometimes pops out error in the operation of SVD, and thus we present an adaptive weight setting scheme to avoid this error. We then employ the proposed scheme on two low-level vision tasks including image denoising and image inpainting. Experimental results demonstrate that WNNM is more feasible than NNM and the proposed scheme outperforms many current state-of-the-art methods.
Succinct progress measures for solving parity games
Venue: arXiv cs.DS 2018
Year: 2018

The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear. Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right.
A Correlation-Breaking Interleaving of Polar Codes in Concatenated Systems
Venue: arXiv cs.IT 2018
Year: 2018

It is known that the bit errors of polar codes with successive cancellation (SC) decoding are coupled. However, existing concatenation schemes of polar codes with other error correction codes rarely take this coupling effect into consideration. To achieve a better error performance of concatenated systems with polar codes as inner codes, one can divide all bits in an outer block into different polar blocks to completely de-correlate the possible coupled errors in the transmitter side. We call this interleaving a blind interleaving (BI) which serves as a benchmark. Two BI schemes, termed BI-DP and BI-CDP, are proposed in the paper. To better balance performance, memory size, and the decoding delay from the de-interleaving, a novel interleaving scheme, named the correlation-breaking interleaving (CBI), is proposed. The CBI breaks the correlated information bits based on the error correlation pattern proposed and proven in this paper. The proposed CBI scheme is general in the sense that any error correction code can serve as the outer code. In this paper, Low-Density Parity-Check (LDPC) codes and BCH codes are used as two examples of the outer codes of the interleaving scheme. The CBI scheme 1) can keep the simple SC polar decoding while achieving a better error performance than the state-of-the-art (SOA) direct concatenation of polar codes with LDPC codes and BCH codes; 2) achieves a comparable error performance as the BI-DP scheme with a smaller memory size and a shorter decoding delay. Numerical results are provided to verify the performance of the BI schemes and the CBI scheme.
AP-initiated Multi-User Transmissions in IEEE 802.11ax WLANs
Venue: arXiv cs.NI 2018
Year: 2018

Next-generation 802.11ax WLANs will make extensive use of multi-user communications in both downlink (DL) and uplink (UL) directions to achieve high and efficient spectrum utilization in scenarios with many user stations per access point. It will become possible with the support of multi-user (MU) multiple input, multiple output (MIMO) and orthogonal frequency division multiple access (OFDMA) transmissions. In this paper, we first overview the novel characteristics introduced by IEEE 802.11ax to implement AP-initiated OFDMA and MU-MIMO transmissions in both downlink and uplink directions. Namely, we describe the changes made at the physical layer and at the medium access control layer to support OFDMA, the use of \emph{trigger frames} to schedule uplink multi-user transmissions, and the new \emph{multi-user RTS/CTS mechanism} to protect large multi-user transmissions from collisions. Then, in order to study the achievable throughput of an 802.11ax network, we use both mathematical analysis and simulations to numerically quantify the benefits of MU transmissions and the impact of 802.11ax overheads on the WLAN saturation throughput. Results show the advantages of MU transmissions in scenarios with many user stations, also providing some novel insights on the conditions in which 802.11ax WLANs are able to maximize their performance, such as the existence of an optimal number of active user stations in terms of throughput, or the need to provide strict prioritization to AP-initiated MU transmissions to avoid collisions with user stations.
Cover Time in Edge-Uniform Stochastically-Evolving Graphs
Venue: arXiv cs.DC 2018
Year: 2018

We define a general model of stochastically-evolving graphs, namely the \emph{Edge-Uniform Stochastically-Evolving Graphs}. In this model, each possible edge of an underlying general static graph evolves independently being either alive or dead at each discrete time step of evolution following a (Markovian) stochastic rule. The stochastic rule is identical for each possible edge and may depend on the past $k \ge 0$ observations of the edge's state. We examine two kinds of random walks for a single agent taking place in such a dynamic graph: (i) The \emph{Random Walk with a Delay} (\emph{RWD}), where at each step the agent chooses (uniformly at random) an incident possible edge, i.e., an incident edge in the underlying static graph, and then it waits till the edge becomes alive to traverse it. (ii) The more natural \emph{Random Walk on what is Available} (\emph{RWA}) where the agent only looks at alive incident edges at each time step and traverses one of them uniformly at random. Our study is on bounding the \emph{cover time}, i.e., the expected time until each node is visited at least once by the agent. For \emph{RWD}, we provide a first upper bound for the cases $k = 0, 1$ by correlating \emph{RWD} with a simple random walk on a static graph. Moreover, we present a modified electrical network theory capturing the $k = 0$ case. For \emph{RWA}, we derive some first bounds for the case $k = 0$, by reducing \emph{RWA} to an \emph{RWD}-equivalent walk with a modified delay. Further, we also provide a framework, which is shown to compute the exact value of the cover time for a general family of stochastically-evolving graphs in exponential time. Finally, we conduct experiments on the cover time of \emph{RWA} in Edge-Uniform graphs and compare the experimental findings with our theoretical bounds.
Deep Stochastic Configuration Networks with Universal Approximation Property
Venue: arXiv cs.LG 2018
Year: 2018

This paper develops a randomized approach for incrementally building deep neural networks, where a supervisory mechanism is proposed to constrain the random assignment of the weights and biases, and all the hidden layers have direct links to the output layer. A fundamental result on the universal approximation property is established for such a class of randomized leaner models, namely deep stochastic configuration networks (DeepSCNs). A learning algorithm is presented to implement DeepSCNs with either specific architecture or self-organization. The read-out weights attached with all direct links from each hidden layer to the output layer are evaluated by the least squares method. Given a set of training examples, DeepSCNs can speedily produce a learning representation, that is, a collection of random basis functions with the cascaded inputs together with the read-out weights. An empirical study on a function approximation is carried out to demonstrate some properties of the proposed deep learner model.
Pricing average price advertising options when underlying spot market prices are discontinuous
Venue: arXiv cs.GT 2018
Year: 2018

Advertising options have been recently studied as a special type of guaranteed contracts in online advertising, which are an alternative sales mechanism to real-time auctions. An advertising option is a contract which gives its buyer a right but not obligation to enter into transactions to purchase page views or link clicks at one or multiple pre-specified prices in a specific future period. Different from typical guaranteed contracts, the option buyer pays a lower upfront fee but can have greater flexibility and more control of advertising. Many studies on advertising options so far have been restricted to the situations where the option payoff is determined by the underlying spot market price at a specific time point and the price evolution over time is assumed to be continuous. The former leads to a biased calculation of option payoff and the latter is invalid empirically for many online advertising slots. This paper addresses these two limitations by proposing a new advertising option pricing framework. First, the option payoff is calculated based on an average price over a specific future period. Therefore, the option becomes path-dependent. The average price is measured by the power mean, which contains several existing option payoff functions as its special cases. Second, jump-diffusion stochastic models are used to describe the movement of the underlying spot market price, which incorporate several important statistical properties including jumps and spikes, non-normality, and absence of autocorrelations. A general option pricing algorithm is obtained based on Monte Carlo simulation. In addition, an explicit pricing formula is derived for the case when the option payoff is based on the geometric mean. This pricing formula is also a generalized version of several other option pricing models discussed in related studies.
Stochastic Approximation for Canonical Correlation Analysis
Venue: arXiv cs.LG 2018
Year: 2018

We propose novel first-order stochastic approximation algorithms for canonical correlation analysis (CCA). Algorithms presented are instances of inexact matrix stochastic gradient (MSG) and inexact matrix exponentiated gradient (MEG), and achieve $ε$-suboptimality in the population objective in $\operatorname{poly}(\frac{1}ε)$ iterations. We also consider practical variants of the proposed algorithms and compare them with other methods for CCA both theoretically and empirically.
Proactive Resource Management for LTE in Unlicensed Spectrum: A Deep Learning Perspective
Venue: arXiv cs.IT 2018
Year: 2018

LTE in unlicensed spectrum using licensed assisted access LTE (LTE-LAA) is a promising approach to overcome the wireless spectrum scarcity. However, to reap the benefits of LTE-LAA, a fair coexistence mechanism with other incumbent WiFi deployments is required. In this paper, a novel deep learning approach is proposed for modeling the resource allocation problem of LTE-LAA small base stations (SBSs). The proposed approach enables multiple SBSs to proactively perform dynamic channel selection, carrier aggregation, and fractional spectrum access while guaranteeing fairness with existing WiFi networks and other LTE-LAA operators. Adopting a proactive coexistence mechanism enables future delay-tolerant LTE-LAA data demands to be served within a given prediction window ahead of their actual arrival time thus avoiding the underutilization of the unlicensed spectrum during off-peak hours while maximizing the total served LTE-LAA traffic load. To this end, a noncooperative game model is formulated in which SBSs are modeled as Homo Egualis agents that aim at predicting a sequence of future actions and thus achieving long-term equal weighted fairness with WLAN and other LTE-LAA operators over a given time horizon. The proposed deep learning algorithm is then shown to reach a mixed-strategy Nash equilibrium (NE), when it converges. Simulation results using real data traces show that the proposed scheme can yield up to 28% and 11% gains over a conventional reactive approach and a proportional fair coexistence mechanism, respectively. The results also show that the proposed framework prevents WiFi performance degradation for a densely deployed LTE-LAA network.
Adaptive Bidirectional Backpropagation: Towards Biologically Plausible Error Signal Transmission in Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

The back-propagation (BP) algorithm has been considered the de-facto method for training deep neural networks. It back-propagates errors from the output layer to the hidden layers in an exact manner using the transpose of the feedforward weights. However, it has been argued that this is not biologically plausible because back-propagating error signals with the exact incoming weights are not considered possible in biological neural systems. In this work, we propose a biologically plausible paradigm of neural architecture based on related literature in neuroscience and asymmetric BP-like methods. Specifically, we propose two bidirectional learning algorithms with trainable feedforward and feedback weights. The feedforward weights are used to relay activations from the inputs to target outputs. The feedback weights pass the error signals from the output layer to the hidden layers. Different from other asymmetric BP-like methods, the feedback weights are also plastic in our framework and are trained to approximate the forward activations. Preliminary results show that our models outperform other asymmetric BP-like methods on the MNIST and the CIFAR-10 datasets.
Optimal Energy Beamforming under Per-Antenna Power Constraint
Venue: arXiv cs.IT 2018
Year: 2018

Energy beamforming (EB) is a key technique to enhance the efficiency of wireless power transfer (WPT). In this paper, we study the optimal EB under per-antenna power constraint (PAC) which is more practical than the conventional sum-power constraint (SPC). We consider a multi antenna energy transmitter (ET) with PAC that broadcasts wireless energy to multiple randomly placed energy receivers (ER)s within its cell area. We consider sum energy maximization problem with PAC and provide the optimal solution structure for the general case. This optimal structure implies that sending one energy beam is optimal under PAC which means that the rank of transmit covariance matrix is one similar to SPC. We also derive closed-form solutions for two special cases and propose two sub-optimal solutions for general case, which performs very close to optimal beamforming.