OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic subtrees queries revisited: the Depth First Tour Tree
Venue: arXiv cs.DS 2015
Year: 2015

In the dynamic tree problem the goal is the maintenance of an arbitrary n-vertex forest, where the trees are subject to joining and splitting by, respectively, adding and removing edges. Depending on the application, information can be associated to nodes or edges (or both), and queries might require to combine values in path or (sub)trees. In this paper we present a novel data structure, called the Depth First Tour Tree, based on a linearization of a DFS visit of the tree. Despite the simplicity of the approach, similar to the ET-Trees (based on a Euler Tour), our data structure is able to answer queries related to both paths and (sub)trees. In particular, focusing on subtree computations, we show how to customize the data structure in order to answer queries for three distinct applications: impact of the removal of an articulation point from a graph, betweenness centrality and closeness centrality of a dynamic tree.
The number of non-crossing perfect plane matchings is minimized (almost) only by point sets in convex position
Venue: arXiv cs.CG 2015
Year: 2015

It is well-known that the number of non-crossing perfect matchings of $2k$ points in convex position in the plane is $C_k$, the $k$th Catalan number. García, Noy, and Tejel proved in 2000 that for any set of $2k$ points in general position, the number of such matchings is at least $C_k$. We show that the equality holds only for sets of points in convex position, and for one exceptional configuration of $6$ points.
Pilot Reuse for Massive MIMO Transmission over Spatially Correlated Rayleigh Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

We propose pilot reuse (PR) in single cell for massive multiuser multiple-input multiple-output (MIMO) transmission to reduce the pilot overhead. For spatially correlated Rayleigh fading channels, we establish a relationship between channel spatial correlations and channel power angle spectrum when the base station antenna number tends to infinity. With this channel model, we show that sum mean square error (MSE) of channel estimation can be minimized provided that channel angle of arrival intervals of the user terminals reusing the pilots are non-overlapping, which shows feasibility of PR over spatially correlated massive MIMO channels with constrained channel angular spreads. Regarding that channel estimation performance might degrade due to PR, we also develop the closed-form robust multiuser uplink receiver and downlink precoder that minimize sum MSE of signal detection, and reveal a duality between them. Subsequently, we investigate pilot scheduling, which determines the PR pattern, under two minimum MSE related criteria, and propose a low complexity pilot scheduling algorithm which relies on the channel statistics only. Simulation results show that the proposed PR scheme provides significant performance gains over the conventional orthogonal training scheme in terms of net spectral efficiency.
The (Final) countdown
Venue: arXiv cs.AI 2015
Year: 2015

The Countdown game is one of the oldest TV show running in the world. It started broadcasting in 1972 on the french television and in 1982 on British channel 4, and it has been running since in both countries. The game, while extremely popular, never received any serious scientific attention, probably because it seems too simple at first sight. We present in this article an in-depth analysis of the numbers round of the countdown game. This includes a complexity analysis of the game, an analysis of existing algorithms, the presentation of a new algorithm that increases resolution speed by a factor of 20. It also includes some leads on how to turn the game into a more difficult one, both for a human player and for a computer, and even to transform it into a probably undecidable problem.
On the Effects of Low-Quality Training Data on Information Extraction from Clinical Reports
Venue: arXiv cs.LG 2015
Year: 2015

In the last five years there has been a flurry of work on information extraction from clinical documents, i.e., on algorithms capable of extracting, from the informal and unstructured texts that are generated during everyday clinical practice, mentions of concepts relevant to such practice. Most of this literature is about methods based on supervised learning, i.e., methods for training an information extraction system from manually annotated examples. While a lot of work has been devoted to devising learning methods that generate more and more accurate information extractors, no work has been devoted to investigating the effect of the quality of training data on the learning process. Low quality in training data often derives from the fact that the person who has annotated the data is different from the one against whose judgment the automatically annotated data must be evaluated. In this paper we test the impact of such data quality issues on the accuracy of information extraction systems as applied to the clinical domain. We do this by comparing the accuracy deriving from training data annotated by the authoritative coder (i.e., the one who has also annotated the test data, and by whose judgment we must abide), with the accuracy deriving from training data annotated by a different coder. The results indicate that, although the disagreement between the two coders (as measured on the training set) is substantial, the difference is (surprisingly enough) not always statistically significant.
Robust Adaptive Sparse Channel Estimation in the Presence of Impulsive Noises
Venue: arXiv cs.IT 2015
Year: 2015

Broadband wireless channels usually have the sparse nature. Based on the assumption of Gaussian noise model, adaptive filtering algorithms for reconstruction sparse channels were proposed to take advantage of channel sparsity. However, impulsive noises are often existed in many advance broadband communications systems. These conventional algorithms are vulnerable to deteriorate due to interference of impulsive noise. In this paper, sign least mean square algorithm (SLMS) based robust sparse adaptive filtering algorithms are proposed for estimating channels as well as for mitigating impulsive noise. By using different sparsity-inducing penalty functions, i.e., zero-attracting (ZA), reweighted ZA (RZA), reweighted L1-norm (RL1) and Lp-norm (LP), the proposed SLMS algorithms are termed as SLMS-ZA, SLMS-RZA, LSMS-RL1 and SLMS-LP. Simulation results are given to validate the proposed algorithms.
NeuroSVM: A Graphical User Interface for Identification of Liver Patients
Venue: arXiv cs.LG 2015
Year: 2015

Diagnosis of liver infection at preliminary stage is important for better treatment. In todays scenario devices like sensors are used for detection of infections. Accurate classification techniques are required for automatic identification of disease samples. In this context, this study utilizes data mining approaches for classification of liver patients from healthy individuals. Four algorithms (Naive Bayes, Bagging, Random forest and SVM) were implemented for classification using R platform. Further to improve the accuracy of classification a hybrid NeuroSVM model was developed using SVM and feed-forward artificial neural network (ANN). The hybrid model was tested for its performance using statistical parameters like root mean square error (RMSE) and mean absolute percentage error (MAPE). The model resulted in a prediction accuracy of 98.83%. The results suggested that development of hybrid model improved the accuracy of prediction. To serve the medicinal community for prediction of liver disease among patients, a graphical user interface (GUI) has been developed using R. The GUI is deployed as a package in local repository of R platform for users to perform prediction.
Time and space optimality of rotor-router graph exploration
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of exploration of an anonymous, port-labeled, undirected graph with $n$ nodes and $m$ edges and diameter $D$, by a single mobile agent. Initially the agent does not know the graph topology nor any of the global parameters. Moreover, the agent does not know the incoming port when entering to a vertex. Each vertex is endowed with memory that can be read and modified by the agent upon its visit to that node. However the agent has no operational memory i.e., it cannot carry any state while traversing an edge. In such a model at least $\log_2 d$ bits are needed at each vertex of degree $d$ for the agent to be able to traverse each graph edge. This number of bits is always sufficient to explore any graph in time $O(mD)$ using algorithm Rotor-Router. We show that even if the available node memory is unlimited then time $Ω(n^3)$ is sometimes required for any algorithm. This shows that Rotor-Router is asymptotically optimal in the worst-case graphs. Secondly we show that for the case of the path the Rotor-Router attains exactly optimal time.
Positive Inductive-Recursive Definitions
Venue: arXiv cs.LO 2015
Year: 2015

A new theory of data types which allows for the definition of types as initial algebras of certain functors Fam(C) -> Fam(C) is presented. This theory, which we call positive inductive-recursive definitions, is a generalisation of Dybjer and Setzer's theory of inductive-recursive definitions within which C had to be discrete -- our work can therefore be seen as lifting this restriction. This is a substantial endeavour as we need to not only introduce a type of codes for such data types (as in Dybjer and Setzer's work), but also a type of morphisms between such codes (which was not needed in Dybjer and Setzer's development). We show how these codes are interpreted as functors on Fam(C) and how these morphisms of codes are interpreted as natural transformations between such functors. We then give an application of positive inductive-recursive definitions to the theory of nested data types and we give concrete examples of recursive functions defined on universes by using their elimination principle. Finally we justify the existence of positive inductive-recursive definitions by adapting Dybjer and Setzer's set-theoretic model to our setting.
Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks
Venue: arXiv cs.AI 2015
Year: 2015

One long-term goal of machine learning research is to produce methods that are applicable to reasoning and natural language, in particular building an intelligent dialogue agent. To measure progress towards that goal, we argue for the usefulness of a set of proxy tasks that evaluate reading comprehension via question answering. Our tasks measure understanding in several ways: whether a system is able to answer questions via chaining facts, simple induction, deduction and many more. The tasks are designed to be prerequisites for any system that aims to be capable of conversing with a human. We believe many existing learning systems can currently not solve them, and hence our aim is to classify these tasks into skill sets, so that researchers can identify (and then rectify) the failings of their systems. We also extend and improve the recently introduced Memory Networks model, and show it is able to solve some, but not all, of the tasks.
Interpreting "altmetrics": viewing acts on social media through the lens of citation and social theories
Venue: arXiv cs.DL 2015
Year: 2015

More than 30 years after Cronin's seminal paper on "the need for a theory of citing" (Cronin, 1981), the metrics community is once again in need of a new theory, this time one for so-called "altmetrics". Altmetrics, short for alternative (to citation) metrics -- and as such a misnomer -- refers to a new group of metrics based (largely) on social media events relating to scholarly communication. As current definitions of altmetrics are shaped and limited by active platforms, technical possibilities, and business models of aggregators such as Altmetric.com, ImpactStory, PLOS, and Plum Analytics, and as such constantly changing, this work refrains from defining an umbrella term for these very heterogeneous new metrics. Instead a framework is presented that describes acts leading to (online) events on which the metrics are based. These activities occur in the context of social media, such as discussing on Twitter or saving to Mendeley, as well as downloading and citing. The framework groups various types of acts into three categories -- accessing, appraising, and applying -- and provides examples of actions that lead to visibility and traceability online. To improve the understanding of the acts, which result in online events from which metrics are collected, select citation and social theories are used to interpret the phenomena being measured. Citation theories are used because the new metrics based on these events are supposed to replace or complement citations as indicators of impact. Social theories, on the other hand, are discussed because there is an inherent social aspect to the measurements.
Efficient Synthesis of Room Acoustics via Scattering Delay Networks
Venue: arXiv cs.SD 2015
Year: 2015

An acoustic reverberator consisting of a network of delay lines connected via scattering junctions is proposed. All parameters of the reverberator are derived from physical properties of the enclosure it simulates. It allows for simulation of unequal and frequency-dependent wall absorption, as well as directional sources and microphones. The reverberator renders the first-order reflections exactly, while making progressively coarser approximations of higher-order reflections. The rate of energy decay is close to that obtained with the image method (IM) and consistent with the predictions of Sabine and Eyring equations. The time evolution of the normalized echo density, which was previously shown to be correlated with the perceived texture of reverberation, is also close to that of IM. However, its computational complexity is one to two orders of magnitude lower, comparable to the computational complexity of a feedback delay network (FDN), and its memory requirements are negligible.
Location Identification of Power Line Outages Using PMU Measurements with Bad Data
Venue: arXiv cs.SY 2015
Year: 2015

The use of phasor angle measurements provided by phasor measurement units (PMUs) in fault detection is regarded as a promising method in identifying locations of power line outages. However, communication errors or system malfunctions may introduce errors to the measurements and thus yield bad data. Most of the existing methods on line outage identification fail to consider such error. This paper develops a framework for identifying multiple power line outages based on the PMUs' measurements in the presence of bad data. In particular, we design an algorithm to identify locations of line outage and recover the faulty measurements simultaneously. The proposed algorithm does not require any prior information on the number of line outages and the noise variance. Case studies carried out on test systems of different sizes validate the effectiveness and efficiency of the proposed approach.
Bimodal logics with a `weakly connected' component without the finite model property
Venue: arXiv cs.LO 2015
Year: 2015

There are two known general results on the finite model property (fmp) of commutators [L,L'] (bimodal logics with commuting and confluent modalities). If L is finitely axiomatisable by modal formulas having universal Horn first-order correspondents, then both [L,K] and [L,S5] are determined by classes of frames that admit filtration, and so have the fmp. On the negative side, if both L and L' are determined by transitive frames and have frames of arbitrarily large depth, then [L,L'] does not have the fmp. In this paper we show that commutators with a `weakly connected' component often lack the fmp. Our results imply that the above positive result does not generalise to universally axiomatisable component logics, and even commutators without `transitive' components such as [K.3,K] can lack the fmp. We also generalise the above negative result to cases where one of the component logics has frames of depth one only, such as [S4.3,S5] and the decidable product logic S4.3xS5. We also show cases when already half of commutativity is enough to force infinite frames.
On predictability of rare events leveraging social media: a machine learning perspective
Venue: arXiv cs.SI 2015
Year: 2015

Information extracted from social media streams has been leveraged to forecast the outcome of a large number of real-world events, from political elections to stock market fluctuations. An increasing amount of studies demonstrates how the analysis of social media conversations provides cheap access to the wisdom of the crowd. However, extents and contexts in which such forecasting power can be effectively leveraged are still unverified at least in a systematic way. It is also unclear how social-media-based predictions compare to those based on alternative information sources. To address these issues, here we develop a machine learning framework that leverages social media streams to automatically identify and predict the outcomes of soccer matches. We focus in particular on matches in which at least one of the possible outcomes is deemed as highly unlikely by professional bookmakers. We argue that sport events offer a systematic approach for testing the predictive power of social media, and allow to compare such power against the rigorous baselines set by external sources. Despite such strict baselines, our framework yields above 8% marginal profit when used to inform simple betting strategies. The system is based on real-time sentiment analysis and exploits data collected immediately before the games, allowing for informed bets. We discuss the rationale behind our approach, describe the learning framework, its prediction performance and the return it provides as compared to a set of betting strategies. To test our framework we use both historical Twitter data from the 2014 FIFA World Cup games, and real-time Twitter data collected by monitoring the conversations about all soccer matches of four major European tournaments (FA Premier League, Serie A, La Liga, and Bundesliga), and the 2014 UEFA Champions League, during the period between Oct. 25th 2014 and Nov. 26th 2014.
Spatio-temporal Video Parsing for Abnormality Detection
Venue: arXiv cs.CV 2015
Year: 2015

Abnormality detection in video poses particular challenges due to the infinite size of the class of all irregular objects and behaviors. Thus no (or by far not enough) abnormal training samples are available and we need to find abnormalities in test data without actually knowing what they are. Nevertheless, the prevailing concept of the field is to directly search for individual abnormal local patches or image regions independent of another. To address this problem, we propose a method for joint detection of abnormalities in videos by spatio-temporal video parsing. The goal of video parsing is to find a set of indispensable normal spatio-temporal object hypotheses that jointly explain all the foreground of a video, while, at the same time, being supported by normal training samples. Consequently, we avoid a direct detection of abnormalities and discover them indirectly as those hypotheses which are needed for covering the foreground without finding an explanation for themselves by normal samples. Abnormalities are localized by MAP inference in a graphical model and we solve it efficiently by formulating it as a convex optimization problem. We experimentally evaluate our approach on several challenging benchmark sets, improving over the state-of-the-art on all standard benchmarks both in terms of abnormality classification and localization.
CSMA-SIC: Carrier Sensing with Successive Interference Cancellation
Venue: arXiv cs.NI 2015
Year: 2015

Successive interference cancellation (SIC) is a physical layer technique that enables the decoders to decode multiple simultaneously transmitted signals. The complicated model of SIC requires careful design of the MAC protocol and accurate adjustment of transmission parameters. We propose a new MAC protocol, known as CSMA-SIC, that employs the multi-packet reception capability of SIC. The proposed protocol adjusts the transmission probabilities to achieve throughput optimality.
Bibliometrics/Citation networks
Venue: arXiv cs.DL 2015
Year: 2015

In addition to shaping social networks, for example, in terms of co-authorship relations, scientific communications induce and reproduce cognitive structures. Scientific literature is intellectually organized in terms of disciplines and specialties; these structures are reproduced and networked reflexively by making references to the authors, concepts and texts embedded in these literatures. The concept of a cognitive structure was introduced in social network analysis (SNA) in 1987 by David Krackhardt, but the focus in SNA has hitherto been on cognition as a psychological attribute of human agency. In bibliometrics, and in science and technology studies (STS) more generally, socio-cognitive structures refer to intellectual organization at the supra-individual level. This intellectual organization emerges and is reproduced by the collectives of authors who are organized not only in terms of inter-personal relations, but also more abstractly in terms of codes of communication that are field-specific. Citations can serve as indicators of this codification process.
Call Admission Control based on Adaptive Bandwidth Allocation for Multi-Class Services in Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

Due to the fact that Quality of Service (QoS) requirements are not as stringent for non-real-time traffic types, as opposed to real-time traffic, more calls can be accommodated by releasing some bandwidth from the existing non-real-time traffic calls. If the released bandwidth to accept a handover call is larger than to accept a new call, then the probability of dropping a call is smaller than the probability of blocking a call. In this paper we propose an efficient Call Admission Control (CAC) that relies on adaptive multi-level bandwidth-allocation scheme for non-real-time calls. The features of the scheme allow reduction of the call dropping probability along with the increase of the bandwidth utilization. The numerical results show that the proposed scheme is able to attain negligible handover call dropping probability without sacrificing bandwidth utilization.
Bandit Convex Optimization: sqrt{T} Regret in One Dimension
Venue: arXiv cs.LG 2015
Year: 2015

We analyze the minimax regret of the adversarial bandit convex optimization problem. Focusing on the one-dimensional case, we prove that the minimax regret is $\widetildeΘ(\sqrt{T})$ and partially resolve a decade-old open problem. Our analysis is non-constructive, as we do not present a concrete algorithm that attains this regret rate. Instead, we use minimax duality to reduce the problem to a Bayesian setting, where the convex loss functions are drawn from a worst-case distribution, and then we solve the Bayesian version of the problem with a variant of Thompson Sampling. Our analysis features a novel use of convexity, formalized as a "local-to-global" property of convex functions, that may be of independent interest.
Unique Factorization and Controllability of Tail-Biting Trellis Realizations via Controller Granule Decompositions
Venue: arXiv cs.IT 2015
Year: 2015

The Conti-Boston factorization theorem (CBFT) for linear tail-biting trellis realizations is extended to group realizations with a new and simpler proof, based on a controller granule decomposition of the behavior and known controllability results for group realizations. Further controllability results are given; e.g., a trellis realization is controllable if and only if its top (controllability) granule is trivial.