OpenRaiser/Intern-Atlas huggingface dataset:
Graph-Community Detection for Cross-Document Topic Segment Relationship Identification
Venue: arXiv cs.CL 2016
Year: 2016

In this paper we propose a graph-community detection approach to identify cross-document relationships at the topic segment level. Given a set of related documents, we automatically find these relationships by clustering segments with similar content (topics). In this context, we study how different weighting mechanisms influence the discovery of word communities that relate to the different topics found in the documents. Finally, we test different mapping functions to assign topic segments to word communities, determining which topic segments are considered equivalent. By performing this task it is possible to enable efficient multi-document browsing, since when a user finds relevant content in one document we can provide access to similar topics in other documents. We deploy our approach in two different scenarios. One is an educational scenario where equivalence relationships between learning materials need to be found. The other consists of a series of dialogs in a social context where students discuss commonplace topics. Results show that our proposed approach better discovered equivalence relationships in learning material documents and obtained close results in the social speech domain, where the best performing approach was a clustering technique.
DCNNs on a Diet: Sampling Strategies for Reducing the Training Set Size
Venue: arXiv cs.CV 2016
Year: 2016

Large-scale supervised classification algorithms, especially those based on deep convolutional neural networks (DCNNs), require vast amounts of training data to achieve state-of-the-art performance. Decreasing this data requirement would significantly speed up the training process and possibly improve generalization. Motivated by this objective, we consider the task of adaptively finding concise training subsets which will be iteratively presented to the learner. We use convex optimization methods, based on an objective criterion and feedback from the current performance of the classifier, to efficiently identify informative samples to train on. We propose an algorithm to decompose the optimization problem into smaller per-class problems, which can be solved in parallel. We test our approach on standard classification tasks and demonstrate its effectiveness in decreasing the training set size without compromising performance. We also show that our approach can make the classifier more robust in the presence of label noise and class imbalance.
Viral Search algorithm
Venue: arXiv cs.NE 2016
Year: 2016

The article, after a brief introduction on genetic algorithms and their functioning, presents a kind of genetic algorithm called Viral Search. We present the key concepts, we formally derive the algorithm and we perform numerical tests designed to illustrate the potential and limits.
Using Fuzzy Logic to Leverage HTML Markup for Web Page Representation
Venue: arXiv cs.IR 2016
Year: 2016

The selection of a suitable document representation approach plays a crucial role in the performance of a document clustering task. Being able to pick out representative words within a document can lead to substantial improvements in document clustering. In the case of web documents, the HTML markup that defines the layout of the content provides additional structural information that can be further exploited to identify representative words. In this paper we introduce a fuzzy term weighing approach that makes the most of the HTML structure for document clustering. We set forth and build on the hypothesis that a good representation can take advantage of how humans skim through documents to extract the most representative words. The authors of web pages make use of HTML tags to convey the most important message of a web page through page elements that attract the readers' attention, such as page titles or emphasized elements. We define a set of criteria to exploit the information provided by these page elements, and introduce a fuzzy combination of these criteria that we evaluate within the context of a web page clustering task. Our proposed approach, called Abstract Fuzzy Combination of Criteria (AFCC), can adapt to datasets whose features are distributed differently, achieving good results compared to other similar fuzzy logic based approaches and TF-IDF across different datasets.
Adversarial Perturbations Against Deep Neural Networks for Malware Classification
Venue: arXiv cs.CR 2016
Year: 2016

Deep neural networks, like many other machine learning models, have recently been shown to lack robustness against adversarially crafted inputs. These inputs are derived from regular inputs by minor yet carefully selected perturbations that deceive machine learning models into desired misclassifications. Existing work in this emerging field was largely specific to the domain of image classification, since the high-entropy of images can be conveniently manipulated without changing the images' overall visual appearance. Yet, it remains unclear how such attacks translate to more security-sensitive applications such as malware detection - which may pose significant challenges in sample generation and arguably grave consequences for failure. In this paper, we show how to construct highly-effective adversarial sample crafting attacks for neural networks used as malware classifiers. The application domain of malware classification introduces additional constraints in the adversarial sample crafting problem when compared to the computer vision domain: (i) continuous, differentiable input domains are replaced by discrete, often binary inputs; and (ii) the loose condition of leaving visual appearance unchanged is replaced by requiring equivalent functional behavior. We demonstrate the feasibility of these attacks on many different instances of malware classifiers that we trained using the DREBIN Android malware data set. We furthermore evaluate to which extent potential defensive mechanisms against adversarial crafting can be leveraged to the setting of malware classification. While feature reduction did not prove to have a positive impact, distillation and re-training on adversarially crafted samples show promising results.
Outer Bounds on the Storage-Repair Bandwidth Tradeoff of Exact-Repair Regenerating Codes
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, three outer bounds on the normalized storage-repair bandwidth (S-RB) tradeoff of regenerating codes having parameter set $\{(n,k,d),(α,β)\}$ under the exact-repair (ER) setting are presented. The first outer bound is applicable for every parameter set $(n,k,d)$ and in conjunction with a code construction known as {\em improved layered codes}, it characterizes the normalized ER tradeoff for the case $(n,k=3,d=n-1)$. It establishes a non-vanishing gap between the ER and functional-repair (FR) tradeoffs for every $(n,k,d)$. The second bound is an improvement upon an existing bound due to Mohajer et al. and is tighter than the first bound, in a regime away from the Minimum Storage Regeneraing (MSR) point. The third bound is for the case of $k=d$, under the linear setting. This outer bound matches with the achievable region of {\em layered codes} thereby characterizing the normalized ER tradeoff of linear ER codes when $k=d=n-1$.
Shallow Discourse Parsing Using Distributed Argument Representations and Bayesian Optimization
Venue: arXiv cs.CL 2016
Year: 2016

This paper describes the Georgia Tech team's approach to the CoNLL-2016 supplementary evaluation on discourse relation sense classification. We use long short-term memories (LSTM) to induce distributed representations of each argument, and then combine these representations with surface features in a neural network. The architecture of the neural network is determined by Bayesian hyperparameter search.
Efficient adaptation of complex-valued noiselet sensing matrices for compressed single-pixel imaging
Venue: arXiv cs.CV 2016
Year: 2016

Minimal mutual coherence of discrete noiselets and Haar wavelets makes this pair of bases an essential choice for the measurement and compression matrices in compressed-sensing-based single-pixel detectors. In this paper we propose an efficient way of using complex-valued and non-binary noiselet functions for object sampling in single-pixel cameras with binary spatial light modulators and incoherent illumination. The proposed method allows to determine m complex noiselet coefficients from m+1 binary sampling measurements. Further, we introduce a modification to the complex fast noiselet transform, which enables computationally-efficient real-time generation of the binary noiselet-based patterns using efficient integer calculations on bundled patterns. The proposed method is verified experimentally with a single-pixel camera system using a binary spatial light modulator.
Settling the complexity of computing approximate two-player Nash equilibria
Venue: arXiv cs.CC 2016
Year: 2016

We prove that there exists a constant $ε>0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $ε$-approximate Nash equilibrium in a two-player (nXn) game requires quasi-polynomial time, $n^{\log^{1-o(1)} n}$. This matches (up to the o(1) term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD. En route, we also prove new hardness results for computing Nash equilibria in games with many players. In particular, we show that computing an $ε$-approximate Nash equilibrium in a game with n players requires $2^{Ω(n)}$ oracle queries to the payoff tensors. This resolves an open problem posed by Hart and Nisan [HN13], Babichenko [Bab14], and Chen et al. [CCT15]. In fact, our results for n-player games are stronger: they hold with respect to the $(ε,δ)$-WeakNash relaxation recently introduced by Babichenko et al. [BPR16].
Wireless Information and Power Transfer Design for Energy Cooperation Distributed Antenna Systems
Venue: arXiv cs.IT 2016
Year: 2016

Distributed antenna systems (DAS) have been widely implemented in state-of-the-art cellular communication systems to cover dead spots. Recent studies have also indicated that DAS have advantages in wireless energy transfer (WET). In this paper, we study simultaneous wireless information and power transfer (SWIPT) for a multiple-input single-output (MISO) DAS in the downlink which consists of arbitrarily distributed remote antenna units (RAUs). In order to save the energy cost, we adopt energy cooperation of energy harvesting (EH) and two-way energy flows to let the RAUs trade their harvested energy through the smart grid network. Under individual EH constraints, per-RAU power constraints and various smart grid considerations, we investigate a power management strategy that determines how to utilize the stochastically spatially distributed harvested energy at the RAUs and how to trade the energy with the smart grid simultaneously to supply maximum wireless information transfer (WIT) with a minimum WET constraint for a receiver adopting power splitting (PS). Our analysis shows that the optimal design can be achieved in two steps. The first step is to maximize a new objective that can simultaneously maximize both WET and WIT, considering both the smart grid profitable and smart grid neutral cases. For the grid-profitable case, we derive the optimal full power strategy and provide a closed-form result to see under what condition this strategy is used. On the other hand, for the grid-neutral case, we illustrate that the optimal power policy has a double-threshold structure and present an optimal allocation strategy. The second step is then to solve the whole problem by obtaining the splitting power ratio based on the minimum WET constraint. Simulation results are provided to evaluate the performance under various settings and characterize the double-threshold structure.
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs
Venue: arXiv cs.DS 2016
Year: 2016

We present space-efficient algorithms for computing cut vertices in a given graph with $n$ vertices and $m$ edges in linear time using $O(n+\min\{m,n\log \log n\})$ bits. With the same time and using $O(n+m)$ bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in $O(n\log \log n)$ time using $O(n)$ bits.
Adapting to unknown noise level in sparse deconvolution
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study sparse spike deconvolution over the space of complex-valued measures when the input measure is a finite sum of Dirac masses. We introduce a modified version of the Beurling Lasso (BLasso), a semi-definite program that we refer to as the Concomitant Beurling Lasso (CBLasso). This new procedure estimates the target measure and the unknown noise level simultaneously. Contrary to previous estimators in the literature, theory holds for a tuning parameter that depends only on the sample size, so that it can be used for unknown noise level problems. Consistent noise level estimation is standardly proved. As for Radon measure estimation, theoretical guarantees match the previous state-of-the-art results in Super-Resolution regarding minimax prediction and localization. The proofs are based on a bound on the noise level given by a new tail estimate of the supremum of a stationary non-Gaussian process through the Rice method.
Probabilistic Interpretation for Correntropy with Complex Data
Venue: arXiv cs.IT 2016
Year: 2016

Recent studies have demonstrated that correntropy is an efficient tool for analyzing higher-order statistical moments in nonGaussian noise environments. Although it has been used with complex data, some adaptations were then necessary without deriving a generic form so that similarities between complex random variables can be aggregated. This paper presents a novel probabilistic interpretation for correntropy using complex-valued data called complex correntropy. An analytical recursive solution for the maximum complex correntropy criterion (MCCC) is introduced as based on the fixedpoint solution. This technique is applied to a simple system identification case study, as the results demonstrate prominent advantages regarding the proposed cost function if compared to the complex recursive least squares (RLS) algorithm. By using such probabilistic interpretation, correntropy can be applied to solve several problems involving complex data in a more straightforward way.
A Survey of Satisfiability Modulo Theory
Venue: arXiv cs.LO 2016
Year: 2016

Satisfiability modulo theory (SMT) consists in testing the satisfiability of first-order formulas over linear integer or real arithmetic, or other theories. In this survey, we explain the combination of propositional satisfiability and decision procedures for conjunctions known as DPLL(T), and the alternative "natural domain" approaches. We also cover quantifiers, Craig interpolants, polynomial arithmetic, and how SMT solvers are used in automated software analysis.
2D Time-frequency interference modelling using stochastic geometry for performance evaluation in Low-Power Wide-Area Networks
Venue: arXiv cs.NI 2016
Year: 2016

In wireless networks, interferences between trans- missions are modelled either in time or frequency domain. In this article, we jointly analyze interferences in the time- frequency domain using a stochastic geometry model assuming the total time-frequency resources to be a two-dimensional plane and transmissions from Internet of Things (IoT) devices time- frequency patterns on this plane. To evaluate the interference, we quantify the overlap between the information packets: provided that the overlap is not too strong, the packets are not necessarily lost due to capture effect. This flexible model can be used for multiple medium access scenarios and is especially adapted to the random time-frequency access schemes used in Low-Power Wide-Area Networks (LPWANs). By characterizing the outage probability and throughput, our approach permits to evaluate the performance of two representative LPWA technologies Sigfox{\textsuperscript \textregistered} and LoRaWA{\textsuperscript \textregistered}.
Locality based Core Selection for Multicore Shared Tree Multicasting
Venue: arXiv cs.NI 2016
Year: 2016

Multicasting can be done in two different ways: source based tree approach and shared tree approach. Protocols such as Core Based Tree (CBT), Protocol Independent Multicasting Sparse Mode (PIM-SM) use shared tree approach. Shared tree approach is preferred over source-based tree approach because in the later construction of minimum cost tree per source is needed unlike a single shared tree in the former approach. In this paper, we present a candidate core selection approach for shared tree multicasting so that in a multicast session different senders can select different cores from the candidate core set based on the senders' physical locations to allow an efficient multicore multicasting approach.
Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
Venue: arXiv cs.IT 2016
Year: 2016

We study the question of reconstructing two signals $f$ and $g$ from their convolution $y = f\ast g$. This problem, known as {\em blind deconvolution}, pervades many areas of science and technology, including astronomy, medical imaging, optics, and wireless communications. A key challenge of this intricate non-convex optimization problem is that it might exhibit many local minima. We present an efficient numerical algorithm that is guaranteed to recover the exact solution, when the number of measurements is (up to log-factors) slightly larger than the information-theoretical minimum, and under reasonable conditions on $f$ and $g$. The proposed regularized gradient descent algorithm converges at a geometric rate and is provably robust in the presence of noise. To the best of our knowledge, our algorithm is the first blind deconvolution algorithm that is numerically efficient, robust against noise, and comes with rigorous recovery guarantees under certain subspace conditions. Moreover, numerical experiments do not only provide empirical verification of our theory, but they also demonstrate that our method yields excellent performance even in situations beyond our theoretical framework.
The Edit Distance Transducer in Action: The University of Cambridge English-German System at WMT16
Venue: arXiv cs.CL 2016
Year: 2016

This paper presents the University of Cambridge submission to WMT16. Motivated by the complementary nature of syntactical machine translation and neural machine translation (NMT), we exploit the synergies of Hiero and NMT in different combination schemes. Starting out with a simple neural lattice rescoring approach, we show that the Hiero lattices are often too narrow for NMT ensembles. Therefore, instead of a hard restriction of the NMT search space to the lattice, we propose to loosely couple NMT and Hiero by composition with a modified version of the edit distance transducer. The loose combination outperforms lattice rescoring, especially when using multiple NMT systems in an ensemble.
Inscribed Matter Communication: Part I
Venue: arXiv cs.ET 2016
Year: 2016

We provide a fundamental treatment of the molecular communication channel wherein "inscribed matter" is transmitted across a spatial gap to provide reliable signaling between a sender and receiver. Inscribed matter is defined as an ensemble of "tokens" (molecules, objects, and so on) and is inspired, at least partially, by biological systems where groups of individually constructed discrete particles ranging from molecules through membrane-bound structures containing molecules to viruses and organisms are released by a source and travel to a target -- for example, morphogens or semiochemicals diffuse from one cell, tissue or organism diffuse to another. For identical tokens that are neither lost nor modified, we consider messages encoded using three candidate communication schemes: a) token timing (timed release), b) token payload (composition), and c) token timing plus payload. We provide capacity bounds for each scheme and discuss their relative utility. We find that under not unreasonable assumptions, megabit per second rates could be supported at femtoWatt transmitter powers. Since quantities such as token concentration or bin-counting are derivatives of token arrival timing, individual token timing undergirds all molecular communication techniques. Thus, our modeling and results about the physics of efficient token-based information transfer can inform investigations of diverse theoretical and practical problems in engineering and biology. This work, Part I, focuses on the information theoretic bounds on capacity. Part II develops some of the mathematical and information-theoretic ideas that support the bounds presented here.
HEMI: Hyperedge Majority Influence Maximization
Venue: arXiv cs.SI 2016
Year: 2016

In this work, we consider the problem of influence maximization on a hypergraph. We first extend the Independent Cascade (IC) model to hypergraphs, and prove that the traditional influence maximization problem remains submodular. We then present a variant of the influence maximization problem (HEMI) where one seeks to maximize the number of hyperedges, a majority of whose nodes are influenced. We prove that HEMI is non-submodular under the diffusion model proposed.
Average Shortest Path Length of Graphs of Diameter 3
Venue: arXiv cs.DM 2016
Year: 2016

A network topology with low average shortest path length (ASPL) provides efficient data transmission while the number of nodes and the number of links incident to each node are often limited due to physical constraints. In this paper, we consider the construction of low ASPL graphs under these constraints by using stochastic local search (SLS) algorithms. Since the ASPL cannot be calculated efficiently, the ASPL is not suitable for the evaluation function of SLS algorithms. We first derive an equality and bounds for the ASPL of graphs of diameter 3. Then, we propose use the simpliest upper bound represented by the number of triangles and squares in the graph as an evaluation function for graphs of diameter 3. We show that the proposed evaluation function can be evaluated in O(1) time as the number of nodes and the maximum degree tend to infinity by using some data tables. By using the simulated annealing with the proposed evaluation function, we construct low ASPL regular graphs of diameter 3 with 10 000 nodes.
Leadership Network and Team Performance in Interactive Contests
Venue: arXiv cs.SI 2016
Year: 2016

Over the years, the concept of leadership has experienced a paradigm shift - from solitary leader (centralized leadership) to de-centralized leadership or distributed leadership. This paper explores the idea that centralized leadership, as earlier suggested, negatively impacts team performance. I applied the hypothesis to cricket, a sport in which leaders play an important role in team's success. I generated batting partnership network and evaluated the central-most player in the team, applying tools of social network analysis. Analyzing 3420 matches in one day international cricket and 1979 Test matches involving 10 teams, I examined the impact of centralized leadership in outcome of a contest. I observed that the odds for winning a one day international match under centralized leadership is 30% higher than the odds for winning under de-centralized leadership. In both forms of cricket (Test and one day international ), I failed to find evidence that distributed leadership is associated with higher team performance. These results suggest important implications for cricket administrators in development and management of working teams.