OpenRaiser/Intern-Atlas huggingface dataset:
A Data-Driven Approach to Pre-Operative Evaluation of Lung Cancer Patients
Venue: arXiv cs.CY 2017
Year: 2017

Lung cancer is the number one cause of cancer deaths. Many early stage lung cancer patients have resectable tumors; however, their cardiopulmonary function needs to be properly evaluated before they are deemed operative candidates. Consequently, a subset of such patients is asked to undergo standard pulmonary function tests, such as cardiopulmonary exercise tests (CPET) or stair climbs, to have their pulmonary function evaluated. The standard tests are expensive, labor intensive, and sometimes ineffective due to co-morbidities, such as limited mobility. Recovering patients would benefit greatly from a device that can be worn at home, is simple to use, and is relatively inexpensive. Using advances in information technology, the goal is to design a continuous, inexpensive, mobile and patient-centric mechanism for evaluation of a patient's pulmonary function. A light mobile mask is designed, fitted with CO2, O2, flow volume, and accelerometer sensors and tested on 18 subjects performing 15 minute exercises. The data collected from the device is stored in a cloud service and machine learning algorithms are used to train and predict a user's activity .Several classification techniques are compared - K Nearest Neighbor, Random Forest, Support Vector Machine, Artificial Neural Network, and Naive Bayes. One useful area of interest involves comparing a patient's predicted activity levels, especially using only breath data, to that of a normal person's, using the classification models.
Towards a new Framework linking knowledge management systems and organizational agility : an empirical study
Venue: arXiv cs.CY 2017
Year: 2017

The amount of data has exploded over the last ten years. Data is captured and shared from personal devices, transactional operations, sensors, social media and other sources. Firms should, thus, be able to explore the new opportunities and rapidly seize them by developing the corresponding capabilities. In our work, we focus on two emerging dynamic capabilities: Absorptive capacity and organizational agility. We propose a new theoretical Framework based on the previous literature linking the use of knowledge management systems and organizational agility by highlighting the mediating role of absorptive capacity. In addition, we carried out an empirical study based on a survey to support and validate the proposed Framework. The main findings of this study are presented.
Fast Label Extraction in the CDAWG
Venue: arXiv cs.DS 2017
Year: 2017

The compact directed acyclic word graph (CDAWG) of a string $T$ of length $n$ takes space proportional just to the number $e$ of right extensions of the maximal repeats of $T$, and it is thus an appealing index for highly repetitive datasets, like collections of genomes from similar species, in which $e$ grows significantly more slowly than $n$. We reduce from $O(m\log{\log{n}})$ to $O(m)$ the time needed to count the number of occurrences of a pattern of length $m$, using an existing data structure that takes an amount of space proportional to the size of the CDAWG. This implies a reduction from $O(m\log{\log{n}}+\mathtt{occ})$ to $O(m+\mathtt{occ})$ in the time needed to locate all the $\mathtt{occ}$ occurrences of the pattern. We also reduce from $O(k\log{\log{n}})$ to $O(k)$ the time needed to read the $k$ characters of the label of an edge of the suffix tree of $T$, and we reduce from $O(m\log{\log{n}})$ to $O(m)$ the time needed to compute the matching statistics between a query of length $m$ and $T$, using an existing representation of the suffix tree based on the CDAWG. All such improvements derive from extracting the label of a vertex or of an arc of the CDAWG using a straight-line program induced by the reversed CDAWG.
Digital Domain Power Division Multiplexed Dual Polarization Coherent Optical OFDM Transmission
Venue: arXiv cs.IT 2017
Year: 2017

Capacity is the eternal pursuit for communication systems due to the overwhelming demand of bandwidth hungry applications. As the backbone infrastructure of modern communication networks, the optical fiber transmission system undergoes a significant capacity growth over decades by exploiting available physical dimensions (time, frequency, quadrature, polarization and space) of the optical carrier for multiplexing. For each dimension, stringent orthogonality must be guaranteed for perfect separation of independent multiplexed signals. To catch up with the ever-increasing capacity requirement, it is therefore interesting and important to develop new multiplexing methodologies relaxing the orthogonal constraint thus achieving better spectral efficiency and more flexibility of frequency reuse. Inspired by the idea of non-orthogonal multiple access (NOMA) scheme, here we propose a digital domain power division multiplexed (PDM) transmission technology which is fully compatible with current dual polarization (DP) coherent optical communication system. The coherent optical orthogonal frequency division multiplexing (CO-OFDM) modulation has been employed owing to its great superiority on high spectral efficiency, flexible coding, ease of channel estimation and robustness against fiber dispersion. And a PDM-DP-CO-OFDM has been theoretically and experimentally demonstrated with 100Gb/s wavelength division multiplexing (WDM) transmission over 1440km standard single mode fibers (SSMFs). Two baseband quadrature phase shift keying (QPSK) OFDM signals are overlaid together with different power levels. After IQ modulation, polarization multiplexing and long distance fiber transmission, the PDM-DP-CO-OFDM signal has been successfully recovered in the typical polarization diversity coherent receiver by successive interference cancellation (SIC) algorithm.
Positioning for Visible Light Communication System Exploiting Multipath Reflections
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we introduce a new uplink visible light indoor positioning system that estimates the position of the users in the network-side of a visible light communications (VLC) system. This technique takes advantage of the diffuse components of the uplink channel impulse response for positioning, which has been considered as a destructive noise in existing visible light communication positioning literature. Exploiting the line of sight (LOS) component, the most significant diffusive component of the channel (the second power peak (SPP)), and the delay time between LOS and SPP, we present a proof of concept analysis for positioning using fixed reference points, i.e. uplink photodetectors (PDs). Simulation results show the root mean square (RMS) positioning accuracy of 25 cm and 5 cm for one and 4 PDs scenarios, respectively.
On Generalized Optimal Hard Decision Fusion
Venue: arXiv cs.IT 2017
Year: 2017

In this letter, we formulate a generalized decision fusion problem (GDFP) for sensing with centralized hard decision fusion. We show that various new and existing decision fusion rules are special cases of the proposed GDFP. We then relate our problem to the classical $0-1$ Knapsack problem (KP). Consequently, we apply dynamic programming to solve the exponentially complex GDFP in polynomial time. Numerical results are presented to verify the effectiveness of the proposed solution.
Robust Detection of Random Events with Spatially Correlated Data in Wireless Sensor Networks via Distributed Compressive Sensing
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we exploit the theory of compressive sensing to perform detection of a random source in a dense sensor network. When the sensors are densely deployed, observations at adjacent sensors are highly correlated while those corresponding to distant sensors are less correlated. Thus, the covariance matrix of the concatenated observation vector of all the sensors at any given time can be sparse where the sparse structure depends on the network topology and the correlation model. Exploiting the sparsity structure of the covariance matrix, we develop a robust nonparametric detector to detect the presence of the random event using a compressed version of the data collected at the distributed nodes. We employ the multiple access channel (MAC) model with distributed random projections for sensors to transmit observations so that a compressed version of the observations is available at the fusion center. Detection is performed by constructing a decision statistic based on the covariance information of uncompressed data which is estimated using compressed data. The proposed approach does not require any knowledge of the noise parameter to set the threshold, and is also robust when the distributed random projection matrices become sparse.
Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Graphs with Bounded Highway Dimension
Venue: arXiv cs.DS 2017
Year: 2017

The concept of bounded highway dimension was developed to capture observed properties of the metrics of road networks. We show that a graph with bounded highway dimension, for any vertex, can be embedded into a a graph of bounded treewidth in such a way that the distance between $u$ and $v$ is preserved up to an additive error of $ε$ times the distance from $u$ or $v$ to the selected vertex. We show that this theorem yields a PTAS for Bounded-Capacity Vehicle Routing in graphs of bounded highway dimension. In this problem, the input specifies a depot and a set of clients, each with a location and demand; the output is a set of depot-to-depot tours, where each client is visited by some tour and each tour covers at most $Q$ units of client demand. Our PTAS can be extended to handle penalties for unvisited clients. We extend this embedding result to handle a set $S$ of distinguished vertices. The treewidth depends on $|S|$, and the distance between $u$ and $v$ is preserved up to an additive error of $ε$ times the distance from $u$ and $v$ to $S$. This embedding result implies a PTAS for Multiple Depot Bounded-Capacity Vehicle Routing: the tours can go from one depot to another. The embedding result also implies that, for fixed $k$, there is a PTAS for $k$-Center in graphs of bounded highway dimension. In this problem, the goal is to minimize $d$ such that there exist $k$ vertices (the centers) such that every vertex is within distance $d$ of some center. Similarly, for fixed $k$, there is a PTAS for $k$-Median in graphs of bounded highway dimension. In this problem, the goal is to minimize the sum of distances to the $k$ centers.
A Preamble Collision Resolution Scheme via Tagged Preambles for Cellular IoT/M2M Communications
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a preamble (PA) collision resolution (PACR) scheme based on multiple timing advance (TA) values captured via tagged PAs. In the proposed PACR scheme, tags are embedded in random access (RA) PAs and multiple TA values are captured for a single detected PA during a tag detection procedure. The proposed PACR scheme significantly improves RA success probability for stationary machine nodes since the nodes using collided PAs can successfully complete the corresponding RAs using exclusive data resource blocks.
Unsupervised Motion Artifact Detection in Wrist-Measured Electrodermal Activity Data
Venue: arXiv cs.HC 2017
Year: 2017

One of the main benefits of a wrist-worn computer is its ability to collect a variety of physiological data in a minimally intrusive manner. Among these data, electrodermal activity (EDA) is readily collected and provides a window into a person's emotional and sympathetic responses. EDA data collected using a wearable wristband are easily influenced by motion artifacts (MAs) that may significantly distort the data and degrade the quality of analyses performed on the data if not identified and removed. Prior work has demonstrated that MAs can be successfully detected using supervised machine learning algorithms on a small data set collected in a lab setting. In this paper, we demonstrate that unsupervised learning algorithms perform competitively with supervised algorithms for detecting MAs on EDA data collected in both a lab-based setting and a real-world setting comprising about 23 hours of data. We also find, somewhat surprisingly, that incorporating accelerometer data as well as EDA improves detection accuracy only slightly for supervised algorithms and significantly degrades the accuracy of unsupervised algorithms.
Fast calculation of entropy with Zhang's estimator
Venue: arXiv cs.CL 2017
Year: 2017

Entropy is a fundamental property of a repertoire. Here, we present an efficient algorithm to estimate the entropy of types with the help of Zhang's estimator. The algorithm takes advantage of the fact that the number of different frequencies in a text is in general much smaller than the number of types. We justify the convenience of the algorithm by means of an analysis of the statistical properties of texts from more than 1000 languages. Our work opens up various possibilities for future research.
Practical Adversarial Combinatorial Bandit Algorithm via Compression of Decision Sets
Venue: arXiv cs.DS 2017
Year: 2017

We consider the adversarial combinatorial multi-armed bandit (CMAB) problem, whose decision set can be exponentially large with respect to the number of given arms. To avoid dealing with such large decision sets directly, we propose an algorithm performed on a zero-suppressed binary decision diagram (ZDD), which is a compressed representation of the decision set. The proposed algorithm achieves either $O(T^{2/3})$ regret with high probability or $O(\sqrt{T})$ expected regret as the any-time guarantee, where $T$ is the number of past rounds. Typically, our algorithm works efficiently for CMAB problems defined on networks. Experimental results show that our algorithm is applicable to various large adversarial CMAB instances including adaptive routing problems on real-world networks.
Can string kernels pass the test of time in Native Language Identification?
Venue: arXiv cs.CL 2017
Year: 2017

We describe a machine learning approach for the 2017 shared task on Native Language Identification (NLI). The proposed approach combines several kernels using multiple kernel learning. While most of our kernels are based on character p-grams (also known as n-grams) extracted from essays or speech transcripts, we also use a kernel based on i-vectors, a low-dimensional representation of audio recordings, provided by the shared task organizers. For the learning stage, we choose Kernel Discriminant Analysis (KDA) over Kernel Ridge Regression (KRR), because the former classifier obtains better results than the latter one on the development set. In our previous work, we have used a similar machine learning approach to achieve state-of-the-art NLI results. The goal of this paper is to demonstrate that our shallow and simple approach based on string kernels (with minor improvements) can pass the test of time and reach state-of-the-art performance in the 2017 NLI shared task, despite the recent advances in natural language processing. We participated in all three tracks, in which the competitors were allowed to use only the essays (essay track), only the speech transcripts (speech track), or both (fusion track). Using only the data provided by the organizers for training our models, we have reached a macro F1 score of 86.95% in the closed essay track, a macro F1 score of 87.55% in the closed speech track, and a macro F1 score of 93.19% in the closed fusion track. With these scores, our team (UnibucKernel) ranked in the first group of teams in all three tracks, while attaining the best scores in the speech and the fusion tracks.
A Harmony Search Based Wrapper Feature Selection Method for Holistic Bangla word Recognition
Venue: arXiv cs.CV 2017
Year: 2017

A lot of search approaches have been explored for the selection of features in pattern classification domain in order to discover significant subset of the features which produces better accuracy. In this paper, we introduced a Harmony Search (HS) algorithm based feature selection method for feature dimensionality reduction in handwritten Bangla word recognition problem. This algorithm has been implemented to reduce the feature dimensionality of a technique described in one of our previous papers by S. Bhowmik et al.[1]. In the said paper, a set of 65 elliptical features were computed for handwritten Bangla word recognition purpose and a recognition accuracy of 81.37% was achieved using Multi Layer Perceptron (MLP) classifier. In the present work, a subset containing 48 features (approximately 75% of said feature vector) has been selected by HS based wrapper feature selection method which produces an accuracy rate of 90.29%. Reasonable outcomes also validates that the introduced algorithm utilizes optimal number of features while showing higher classification accuracies when compared to two standard evolutionary algorithms like Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and statistical feature dimensionality reduction technique like Principal Component Analysis (PCA). This confirms the suitability of HS algorithm to the holistic handwritten word recognition problem.
Men Are from Mars, Women Are from Venus: Evaluation and Modelling of Verbal Associations
Venue: arXiv cs.CL 2017
Year: 2017

We present a quantitative analysis of human word association pairs and study the types of relations presented in the associations. We put our main focus on the correlation between response types and respondent characteristics such as occupation and gender by contrasting syntagmatic and paradigmatic associations. Finally, we propose a personalised distributed word association model and show the importance of incorporating demographic factors into the models commonly used in natural language processing.
MST in O(1) Rounds of the Congested Clique
Venue: arXiv cs.DC 2017
Year: 2017

We present a distributed randomized algorithm finding Minimum Spanning Tree (MST) of a given graph in O(1) rounds, with high probability, in the Congested Clique model. The input graph in the Congested Clique model is a graph of n nodes, where each node initially knows only its incident edges. The communication graph is a clique with limited edge bandwidth: each two nodes (not necessarily neighbours in the input graph) can exchange $O(\log n)$ bits. As in previous works, the key part of the MST algorithm is an efficient Connected Components (CC) algorithm. However, unlike the former approaches, we do not aim at simulating the standard Boruvka algorithm, at least at initial stages of the CC algorithm. Instead, we develop a new technique which combines connected components of sample sparse subgraphs of the input graph in order to accelerate the process of uncovering connected components of the original input graph. More specifically, we develop a sparsification technique which reduces an initial CC problem in $O(1)$ rounds to its two restricted instances. The former instance has a graph with maximal degree $O(\log \log n)$ as the input -- here our sample-combining technique helps. In the latter instance, a partition of the input graph into $O(n/\log \log n)$ connected components is known. This gives an opportunity to apply previous algorithms to determine connected components in $O(1)$ rounds. Our result addresses the problem from and the $O(\log \log n)$ algorithm of Lotker et al. [SPAA 2003; SICOMP 2005], improves over previous $O(\log* n)$ algorithm of Ghaffari et al. [PODC 2016] and $O(\log \log \log n)$ algorithm of Hegeman et al. [PODC 2015] . It also determines $Θ(1)$ round complexity in the congested clique for MST, as well as other graph problems, including bipartiteness, cut verification, s-t connectivity and cycle containment.
Measurement and Analysis of UDP Traffic over Wi-Fi and GPRS
Venue: arXiv cs.NI 2017
Year: 2017

With the increasing usage of mobile devices to ubiquitously access heterogeneous applications in wireless Internet, the measurement and analysis of Internet traffic has become a key research area. In this paper, we present the results of our measurements for VBR traffic over UDP in 802.11g and GPRS networks. We focus on Inter-Packet Arrival Time (IPRT) and Inter-Packet Transmission Delay (IPTD) and observe that the later has a significant impact on the round trip delay. Numerical parameters for Weibull, Exponential and Normal distribution in order to represent such traffic are also presented.
Rational Points on the Unit Sphere: Approximation Complexity and Practical Constructions
Venue: arXiv cs.CG 2017
Year: 2017

Each non-zero point in $\mathbb{R}^d$ identifies a closest point $x$ on the unit sphere $\mathbb{S}^{d-1}$. We are interested in computing an $ε$-approximation $y \in \mathbb{Q}^d$ for $x$, that is exactly on $\mathbb{S}^{d-1}$ and has low bit size. We revise lower bounds on rational approximations and provide explicit, spherical instances. We prove that floating-point numbers can only provide trivial solutions to the sphere equation in $\mathbb{R}^2$ and $\mathbb{R}^3$. Moreover, we show how to construct a rational point with denominators of at most $10(d-1)/\varepsilon^2$ for any given $ε\in \left(0,\tfrac 1 8\right]$, improving on a previous result. The method further benefits from algorithms for simultaneous Diophantine approximation. Our open-source implementation and experiments demonstrate the practicality of our approach in the context of massive data sets Geo-referenced by latitude and longitude values.
Self-organized Hierarchical Softmax
Venue: arXiv cs.CL 2017
Year: 2017

We propose a new self-organizing hierarchical softmax formulation for neural-network-based language models over large vocabularies. Instead of using a predefined hierarchical structure, our approach is capable of learning word clusters with clear syntactical and semantic meaning during the language model training process. We provide experiments on standard benchmarks for language modeling and sentence compression tasks. We find that this approach is as fast as other efficient softmax approximations, while achieving comparable or even better performance relative to similar full softmax models.
Robust Rigid Point Registration based on Convolution of Adaptive Gaussian Mixture Models
Venue: arXiv cs.CV 2017
Year: 2017

Matching 3D rigid point clouds in complex environments robustly and accurately is still a core technique used in many applications. This paper proposes a new architecture combining error estimation from sample covariances and dual global probability alignment based on the convolution of adaptive Gaussian Mixture Models (GMM) from point clouds. Firstly, a novel adaptive GMM is defined using probability distributions from the corresponding points. Then rigid point cloud alignment is performed by maximizing the global probability from the convolution of dual adaptive GMMs in the whole 2D or 3D space, which can be efficiently optimized and has a large zone of accurate convergence. Thousands of trials have been conducted on 200 models from public 2D and 3D datasets to demonstrate superior robustness and accuracy in complex environments with unpredictable noise, outliers, occlusion, initial rotation, shape and missing points.