OpenRaiser/Intern-Atlas huggingface dataset:
Information-Theoretic Methods for Planning and Learning in Partially Observable Markov Decision Processes
Venue: arXiv cs.LG 2017
Year: 2017

Bounded agents are limited by intrinsic constraints on their ability to process information that is available in their sensors and memory and choose actions and memory updates. In this dissertation, we model these constraints as information-rate constraints on communication channels connecting these various internal components of the agent. We make four major contributions detailed below and many smaller contributions detailed in each section. First, we formulate the problem of optimizing the agent under both extrinsic and intrinsic constraints and develop the main tools for solving it. Second, we identify another reason for the challenging convergence properties of the optimization algorithm, which is the bifurcation structure of the update operator near phase transitions. Third, we study the special case of linear-Gaussian dynamics and quadratic cost (LQG), where the optimal solution has a particularly simple and solvable form. Fourth, we explore the learning task, where the model of the world dynamics is unknown and sample-based updates are used instead.
Uplink Performance Analysis of Dense Cellular Networks with LoS and NLoS Transmissions
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we analyse the coverage probability and the area spectral efficiency (ASE) for the uplink (UL) of dense small cell networks (SCNs) considering a practical path loss model incorporating both line-of-sight (LoS) and non-line-of-sight (NLoS) transmissions. Compared with the existing work, we adopt the following novel approaches in our study: (i) we assume a practical user association strategy (UAS) based on the smallest path loss, or equivalently the strongest received signal strength; (ii) we model the positions of both base stations (BSs) and the user equipments (UEs) as two independent Homogeneous Poisson point processes (HPPPs); and (iii) the correlation of BSs' and UEs' positions is considered, thus making our analytical results more accurate. The performance impact of LoS and NLoS transmissions on the ASE for the UL of dense SCNs is shown to be significant, both quantitatively and qualitatively, compared with existing work that does not differentiate LoS and NLoS transmissions. In particular, existing work predicted that a larger UL power compensation factor would always result in a better ASE in the practical range of BS density, i.e., 10^1-10^3 BSs/km^2. However, our results show that a smaller UL power compensation factor can greatly boost the ASE in the UL of dense SCNs, i.e., 10^2-10^3 BSs/km^2, while a larger UL power compensation factor is more suitable for sparse SCNs, i.e., 10^1-10^2 BSs/km^2.
Minimum Distance and the Minimum Weight Codewords of Schubert Codes
Venue: arXiv cs.IT 2017
Year: 2017

We consider linear codes associated to Schubert varieties in Grassmannians. A formula for the minimum distance of these codes was conjectured in 2000 and after having been established in various special cases, it was proved in 2008 by Xiang. We give an alternative proof of this formula. Further, we propose a characterization of the minimum weight codewords of Schubert codes by introducing the notion of Schubert decomposable elements of certain exterior powers. It is shown that codewords corresponding to Schubert decomposable elements are of minimum weight and also that the converse is true in many cases. A lower bound, and in some cases, an exact formula, for the number of minimum weight codewords of Schubert codes is also given. From a geometric point of view, these results correspond to determining the maximum number of $\mathbb{F}_q$-rational points that can lie on a hyperplane section of a Schubert variety in a Grassmannian with its nondegenerate embedding in a projective subspace of the Plücker projective space, and also the number of hyperplanes for which the maximum is attained.
Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs
Venue: arXiv cs.DS 2017
Year: 2017

Finding important nodes in a graph and measuring their importance is a fundamental problem in the analysis of social networks, transportation networks, biological systems, etc. Among popular such metrics are graph centrality, betweenness centrality (BC), and reach centrality (RC). These measures are also very related to classic notions like diameter and radius. Roditty and Vassilevska Williams~[STOC'13] showed that no algorithm can compute a (3/2-δ)-approximation of the diameter in sparse and unweighted graphs faster that n^{2-o(1)} time unless the widely believed strong exponential time hypothesis (SETH) is false. Abboud et al.~[SODA'15] and [SODA'16] further analyzed these problems under the recent line of research on hardness in P. They showed that in sparse and unweighted graphs (weighted for BC) none of these problems can be solved faster than n^{2-o(1)} unless some popular conjecture is false. Furthermore they ruled out a (2-δ)-approximation for RC, a (3/2-δ)-approximation for Radius and a (5/3-δ)-approximation for computing all eccentricities of a graph for any δ> 0. We extend these results to the case of unweighted graphs with constant maximum degree. Through new graph constructions we are able to obtain the same approximation and time bounds as for sparse graphs even in unweighted bounded-degree graphs. We show that no (3/2-δ) approximation of Radius or Diameter, (2-δ)-approximation of RC, (5/3-δ)-approximation of all eccentricities or exact algorithm for BC exists in time n^{2-o(1)} for such graphs and any δ> 0. This strengthens the result for BC of Abboud et al.~[SODA'16] by showing a hardness result for unweighted graphs, and follows in the footsteps of Abboud et al.~[SODA'16] and Abboud and Dahlgaard~[FOCS'16] in showing conditional lower bounds for restricted but realistic graph classes.
Learning convolutional neural network to maximize Pos@Top performance measure
Venue: arXiv cs.CV 2017
Year: 2017

In the machine learning problems, the performance measure is used to evaluate the machine learning models. Recently, the number positive data points ranked at the top positions (Pos@Top) has been a popular performance measure in the machine learning community. In this paper, we propose to learn a convolutional neural network (CNN) model to maximize the Pos@Top performance measure. The CNN model is used to represent the multi-instance data point, and a classifier function is used to predict the label from the its CNN representation. We propose to minimize the loss function of Pos@Top over a training set to learn the filters of CNN and the classifier parameter. The classifier parameter vector is solved by the Lagrange multiplier method, and the filters are updated by the gradient descent method alternately in an iterative algorithm. Experiments over benchmark data sets show that the proposed method outperforms the state-of-the-art Pos@Top maximization methods.
Collaborative Learning for Language and Speaker Recognition
Venue: arXiv cs.SD 2017
Year: 2017

This paper presents a unified model to perform language and speaker recognition simultaneously and altogether. The model is based on a multi-task recurrent neural network where the output of one task is fed as the input of the other, leading to a collaborative learning framework that can improve both language and speaker recognition by borrowing information from each other. Our experiments demonstrated that the multi-task model outperforms the task-specific models on both tasks.
Joint Cell Muting and User Scheduling in Multi-Cell Networks with Temporal Fairness
Venue: arXiv cs.NI 2017
Year: 2017

A semi-centralized joint cell muting and user scheduling scheme for interference coordination in a multicell network is proposed under two different temporal fairness criteria. The main principle behind the proposed scheme is that a central entity selects a cell muting pattern out of a pattern set at a decision instant, and subsequently the un-muted base stations opportunistically schedule the users in the associated cells, both decisions made on a temporal-fair basis. Although some pattern sets are easily obtainable from static frequency reuse systems, we propose a more general pattern set construction algorithm in this paper. As for the first fairness criterion, all cells are assigned to receive the same temporal share with the ratio between the temporal share of a cell center section and that of the cell edge section is set to a fixed desired value for all cells. The second fairness criterion is based on the max-min temporal fairness for which the temporal share of the network-wide worst-case user is maximized. Numerical results are provided to validate the effectiveness of the proposed scheme for both criteria. The impact of choice of the cell muting pattern set is also studied through numerical examples for various cellular topologies.
Anytime Discovery of a Diverse Set of Patterns with Monte Carlo Tree Search
Venue: arXiv cs.DS 2017
Year: 2017

The discovery of patterns that accurately discriminate one class label from another remains a challenging data mining task. Subgroup discovery (SD) is one of the frameworks that enables to elicit such interesting hypotheses from labeled data. A question remains fairly open: How to select an accurate heuristic search technique when exhaustive enumeration of the pattern space is infeasible? Existing approaches make use of beam-search, sampling and genetic algorithms for discovering a pattern set that is non-redundant and of high quality w.r.t. a pattern quality measure. We argue that such approaches produce pattern sets that lack of diversity: Only few patterns of high quality, and different enough, are discovered. Our main contribution is then to formally define pattern mining as a game and to solve it with Monte Carlo tree search (MCTS). It can be seen as an exhaustive search guided by random simulations which can be stopped early (limited budget) by virtue of its best-first search property. We show through a comprehensive set of experiments how MCTS enables the anytime discovery of a diverse pattern set of high quality. It outperforms other approaches when dealing with a large pattern search space and for different quality measures. Thanks to its genericity, our MCTS settings can be used for SD but also for many other pattern mining tasks.
Linking Behavior in the PER Coauthorship Network
Venue: arXiv cs.DL 2017
Year: 2017

There is considerable long-term interest in understanding the dynamics of collaboration networks, and how these networks form and evolve over time. Most of the work done on the dynamics of social networks focuses on well-established communities. Work examining emerging social networks is rarer, simply because data is difficult to obtain in real time. In this paper, we use thirty years of data from an emerging scientific community to look at that crucial early stage in the development of a social network. We show that when the field was very young, islands of individual researchers labored in relative isolation, and the coauthorship network was disconnected. Thirty years later, rather than a cluster of individuals, we find a true collaborative community, bound together by a robust collaboration network. However, this change did not take place gradually\textemdash the network remained a loose assortment of isolated individuals until the mid-2000s, when those smaller parts suddenly knit themselves together into a single whole. In the rest of this paper, we consider the role of three factors in these observed structural changes: growth, changes in social norms, and the introduction of institutions such as field-specific conferences and journals. We have data from the very earliest years of the field, a period which includes the introduction of two different institutions: the first field-specific conference, and the first field-specific journals. We also identify two relevant behavioral shifts: a discrete increase in coauthorship coincident with the first conference, and a shift among established authors away from collaborating with outsiders, towards collaborating with each other. The interaction of these factors gives us insight into the formation of collaboration networks more broadly.
Radial Velocity Retrieval for Multichannel SAR Moving Targets with Time-Space Doppler De-ambiguity
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, with respect to multichannel synthetic aperture radars (SAR), we first formulate the problems of Doppler ambiguities on the radial velocity (RV) estimation of a ground moving target in range-compressed domain, range-Doppler domain and image domain, respectively. It is revealed that in these problems, a cascaded time-space Doppler ambiguity (CTSDA) may encounter, i.e., time domain Doppler ambiguity (TDDA) in each channel arises first and then spatial domain Doppler ambiguity (SDDA) among multi-channels arises second. Accordingly, the multichannel SAR systems with different parameters are investigated in three different cases with diverse Doppler ambiguity properties, and a multi-frequency SAR is then proposed to obtain the RV estimation by solving the ambiguity problem based on Chinese remainder theorem (CRT). In the first two cases, the ambiguity problem can be solved by the existing closed-form robust CRT. In the third case, it is found that the problem is different from the conventional CRT problems and we call it a double remaindering problem in this paper. We then propose a sufficient condition under which the double remaindering problem, i.e., the CTSDA, can also be solved by the closed-form robust CRT. When the sufficient condition is not satisfied for a multi-channel SAR, a searching based method is proposed. Finally, some results of numerical experiments are provided to demonstrate the effectiveness of the proposed methods.
Square-root algorithms for maximum correntropy estimation of linear discrete-time systems in presence of non-Gaussian noise
Venue: arXiv cs.SY 2017
Year: 2017

Recent developments in the realm of state estimation of stochastic dynamic systems in the presence of non-Gaussian noise have induced a new methodology called the maximum correntropy filtering. The filters designed under the maximum correntropy criterion (MCC) utilize a similarity measure (or correntropy) between two random variables as a cost function. They are shown to improve the estimators' robustness against outliers or impulsive noises. In this paper we explore the numerical stability of linear filtering technique proposed recently under the MCC approach. The resulted estimator is called the maximum correntropy criterion Kalman filter (MCC-KF). The purpose of this study is two-fold. First, the previously derived MCC-KF equations are revise and the related Kalman-like equality conditions are proved. Based on this theoretical finding, we improve the MCC-KF technique in the sense that the new method possesses a better estimation quality with the reduced computational cost compared with the previously proposed MCC-KF variant. Second, we devise some square-root implementations for the newly-designed improved estimator. The square-root algorithms are well known to be inherently more stable than the conventional Kalman-like implementations, which process the full error covariance matrix in each iteration step of the filter. Additionally, following the latest achievements in the KF community, all square-root algorithms are formulated here in the so-called array form. All the MCC-KF variants developed in this paper are demonstrated to outperform the previously proposed MCC-KF version in two numerical examples.
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
Venue: arXiv cs.CC 2017
Year: 2017

Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this assumption that $\mathbf{BPL} \subseteq \bigcap_{α> 0} \mathbf{DSPACE}(\log^{1 + α} n)$. We strengthen the theorem to an equivalence by considering two generalizations of the concept of a pseudorandom generator against logspace. A targeted pseudorandom generator against logspace takes as input a short uniform random seed and a finite automaton; it outputs a long bitstring that looks random to that particular automaton. A simulation advice generator for logspace stretches a small uniform random seed into a long advice string; the requirement is that there is some logspace algorithm that, given a finite automaton and this advice string, simulates the automaton reading a long uniform random input. We prove that $\bigcap_{α> 0} \mathbf{promise\mbox{-}BPSPACE}(\log^{1 + α} n) = \bigcap_{α> 0} \mathbf{promise\mbox{-}DSPACE}(\log^{1 + α} n)$ if and only if for every targeted pseudorandom generator against logspace, there is a simulation advice generator for logspace with similar parameters. Finally, we observe that in a certain uniform setting (namely, if we only worry about sequences of automata that can be generated in logspace), targeted pseudorandom generators against logspace can be transformed into simulation advice generators with similar parameters.
Adversary Resistant Deep Neural Networks with an Application to Malware Detection
Venue: arXiv cs.LG 2017
Year: 2017

Beyond its highly publicized victories in Go, there have been numerous successful applications of deep learning in information retrieval, computer vision and speech recognition. In cybersecurity, an increasing number of companies have become excited about the potential of deep learning, and have started to use it for various security incidents, the most popular being malware detection. These companies assert that deep learning (DL) could help turn the tide in the battle against malware infections. However, deep neural networks (DNNs) are vulnerable to adversarial samples, a flaw that plagues most if not all statistical learning models. Recent research has demonstrated that those with malicious intent can easily circumvent deep learning-powered malware detection by exploiting this flaw. In order to address this problem, previous work has developed various defense mechanisms that either augmenting training data or enhance model's complexity. However, after a thorough analysis of the fundamental flaw in DNNs, we discover that the effectiveness of current defenses is limited and, more importantly, cannot provide theoretical guarantees as to their robustness against adversarial sampled-based attacks. As such, we propose a new adversary resistant technique that obstructs attackers from constructing impactful adversarial samples by randomly nullifying features within samples. In this work, we evaluate our proposed technique against a real world dataset with 14,679 malware variants and 17,399 benign programs. We theoretically validate the robustness of our technique, and empirically show that our technique significantly boosts DNN robustness to adversarial samples while maintaining high accuracy in classification. To demonstrate the general applicability of our proposed method, we also conduct experiments using the MNIST and CIFAR-10 datasets, generally used in image recognition research.
Generalized Inverse Classification
Venue: arXiv cs.LG 2017
Year: 2017

Inverse classification is the process of perturbing an instance in a meaningful way such that it is more likely to conform to a specific class. Historical methods that address such a problem are often framed to leverage only a single classifier, or specific set of classifiers. These works are often accompanied by naive assumptions. In this work we propose generalized inverse classification (GIC), which avoids restricting the classification model that can be used. We incorporate this formulation into a refined framework in which GIC takes place. Under this framework, GIC operates on features that are immediately actionable. Each change incurs an individual cost, either linear or non-linear. Such changes are subjected to occur within a specified level of cumulative change (budget). Furthermore, our framework incorporates the estimation of features that change as a consequence of direct actions taken (indirectly changeable features). To solve such a problem, we propose three real-valued heuristic-based methods and two sensitivity analysis-based comparison methods, each of which is evaluated on two freely available real-world datasets. Our results demonstrate the validity and benefits of our formulation, framework, and methods.
Energy-Efficient Beam Coordination Strategies with Rate Dependent Processing Power
Venue: arXiv cs.IT 2017
Year: 2017

This paper proposes energy-efficient coordinated beamforming strategies for multi-cell multi-user multiple-input single-output system. We consider a practical power consumption model, where part of the consumed power depends on the base station or user specific data rates due to coding, decoding and backhaul. This is different from the existing approaches where the base station power consumption has been assumed to be a convex or linear function of the transmit powers. Two optimization criteria are considered, namely network energy efficiency maximization and weighted sum energy efficiency maximization. We develop successive convex approximation based algorithms to tackle these difficult nonconvex problems. We further propose decentralized implementations for the considered problems, in which base stations perform parallel and distributed computation based on local channel state information and limited backhaul information exchange. The decentralized approaches admit closed-form solutions and can be implemented without invoking a generic external convex solver. We also show an example of the pilot contamination effect on the energy efficiency using a heuristic pilot allocation strategy. The numerical results are provided to demonstrate that the rate dependent power consumption has a large impact on the system energy efficiency, and, thus, has to be taken into account when devising energy-efficient transmission strategies. The significant gains of the proposed algorithms over the conventional low-complexity beamforming algorithms are also illustrated.
Spectral partitioning in equitable graphs
Venue: arXiv cs.SI 2017
Year: 2017

Graph partitioning problems emerge in a wide variety of complex systems, ranging from biology to finance, but can be rigorously analyzed and solved only for a few graph ensembles. Here, an ensemble of equitable graphs, i.e. random graphs with a block-regular structure, is studied, for which analytical results can be obtained. In particular, the spectral density of this ensemble is computed exactly for a modular and bipartite structure. Kesten-McKay's law for random regular graphs is found analytically to apply also for modular and bipartite structures when blocks are homogeneous. Exact solution to graph partitioning for two equal-sized communities is proposed and verified numerically, and a conjecture on the absence of an efficient recovery detectability transition in equitable graphs is suggested. Final discussion summarizes results and outlines their relevance for the solution of graph partitioning problems in other graph ensembles, in particular for the study of detectability thresholds and resolution limits in stochastic block models.