OpenRaiser/Intern-Atlas huggingface dataset:
On the Success Probability of the Box-Constrained Rounding and Babai Detectors
Venue: arXiv cs.IT 2017
Year: 2017

In communications, one frequently needs to detect a parameter vector $\hbx$ in a box from a linear model. The box-constrained rounding detector $\x^\sBR$ and Babai detector $\x^\sBB$ are often used to detect $\hbx$ due to their high probability of correct detection, which is referred to as success probability, and their high efficiency of implimentation. It is generally believed that the success probability $P^\sBR$ of $\x^\sBR$ is not larger than the success probability $P^\sBB$ of $\x^\sBB$. In this paper, we first present formulas for $P^\sBR$ and $P^\sBB$ for two different situations: $\hbx$ is deterministic and $\hbx$ is uniformly distributed over the constraint box. Then, we give a simple example to show that $P^\sBR$ may be strictly larger than $P^\sBB$ if $\hbx$ is deterministic, while we rigorously show that $P^\sBR\leq P^\sBB$ always holds if $\hbx$ is uniformly distributed over the constraint box.
Predicting Cognitive Decline with Deep Learning of Brain Metabolism and Amyloid Imaging
Venue: arXiv cs.CV 2017
Year: 2017

For effective treatment of Alzheimer disease (AD), it is important to identify subjects who are most likely to exhibit rapid cognitive decline. Herein, we developed a novel framework based on a deep convolutional neural network which can predict future cognitive decline in mild cognitive impairment (MCI) patients using flurodeoxyglucose and florbetapir positron emission tomography (PET). The architecture of the network only relies on baseline PET studies of AD and normal subjects as the training dataset. Feature extraction and complicated image preprocessing including nonlinear warping are unnecessary for our approach. Accuracy of prediction (84.2%) for conversion to AD in MCI patients outperformed conventional feature-based quantification approaches. ROC analyses revealed that performance of CNN-based approach was significantly higher than that of the conventional quantification methods (p < 0.05). Output scores of the network were strongly correlated with the longitudinal change in cognitive measurements. These results show the feasibility of deep learning as a tool for predicting disease outcome using brain images.
Certification of Compact Low-Stretch Routing Schemes
Venue: arXiv cs.DC 2017
Year: 2017

On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g., blocking the delivery of messages between some pairs of nodes, without being detected by any node. In this paper, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables. In particular, we show how to locally verify the stretch-3 routing scheme by Thorup and Zwick [SPAA 2001] by adding certificates of $\widetilde{O}(\sqrt{n})$ bits at each node in $n$-node networks, that is, by keeping the memory size of the same order of magnitude as the original routing tables. We also propose a new name-independent routing scheme using routing tables of size $\widetilde{O}(\sqrt{n})$ bits. This new routing scheme can be locally verified using certificates on $\widetilde{O}(\sqrt{n})$ bits. Its stretch is3 if using handshaking, and 5 otherwise.
Robust Smartphone App Identification Via Encrypted Network Traffic Analysis
Venue: arXiv cs.CR 2017
Year: 2017

The apps installed on a smartphone can reveal much information about a user, such as their medical conditions, sexual orientation, or religious beliefs. Additionally, the presence or absence of particular apps on a smartphone can inform an adversary who is intent on attacking the device. In this paper, we show that a passive eavesdropper can feasibly identify smartphone apps by fingerprinting the network traffic that they send. Although SSL/TLS hides the payload of packets, side-channel data such as packet size and direction is still leaked from encrypted connections. We use machine learning techniques to identify smartphone apps from this side-channel data. In addition to merely fingerprinting and identifying smartphone apps, we investigate how app fingerprints change over time, across devices and across different versions of apps. Additionally, we introduce strategies that enable our app classification system to identify and mitigate the effect of ambiguous traffic, i.e., traffic in common among apps such as advertisement traffic. We fully implemented a framework to fingerprint apps and ran a thorough set of experiments to assess its performance. We fingerprinted 110 of the most popular apps in the Google Play Store and were able to identify them six months later with up to 96% accuracy. Additionally, we show that app fingerprints persist to varying extents across devices and app versions.
Learning to Acquire Information
Venue: arXiv cs.AI 2017
Year: 2017

We consider the problem of diagnosis where a set of simple observations are used to infer a potentially complex hidden hypothesis. Finding the optimal subset of observations is intractable in general, thus we focus on the problem of active diagnosis, where the agent selects the next most-informative observation based on the results of previous observations. We show that under the assumption of uniform observation entropy, one can build an implication model which directly predicts the outcome of the potential next observation conditioned on the results of past observations, and selects the observation with the maximum entropy. This approach enjoys reduced computation complexity by bypassing the complicated hypothesis space, and can be trained on observation data alone, learning how to query without knowledge of the hidden hypothesis.
Cell-Probe Lower Bounds from Online Communication Complexity
Venue: arXiv cs.DS 2017
Year: 2017

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players, Bob, his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result each time before the next piece is revealed to Bob. This model has a closer and more natural correspondence to dynamic data structures than classic communication models do, and hence presents a new perspective on data structures. We first present a tight lower bound for the online set intersection problem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. We then apply the online communication model to prove data structure lower bounds for two dynamic data structure problems: the Group Range problem and the Dynamic Connectivity problem for forests. Both of the problems admit a worst case $O(\log n)$-time data structure. Using online communication complexity, we prove a tight cell-probe lower bound for each: spending $o(\log n)$ (even amortized) time per operation results in at best an $\exp(-δ^2 n)$ probability of correctly answering a $(1/2+δ)$-fraction of the $n$ queries.
Improving Context Aware Language Models
Venue: arXiv cs.CL 2017
Year: 2017

Increased adaptability of RNN language models leads to improved predictions that benefit many applications. However, current methods do not take full advantage of the RNN structure. We show that the most widely-used approach to adaptation (concatenating the context with the word embedding at the input to the recurrent layer) is outperformed by a model that has some low-cost improvements: adaptation of both the hidden and output layers. and a feature hashing bias term to capture context idiosyncrasies. Experiments on language modeling and classification tasks using three different corpora demonstrate the advantages of the proposed techniques.
A 3D fully convolutional neural network and a random walker to segment the esophagus in CT
Venue: arXiv cs.CV 2017
Year: 2017

Precise delineation of organs at risk (OAR) is a crucial task in radiotherapy treatment planning, which aims at delivering high dose to the tumour while sparing healthy tissues. In recent years algorithms showed high performance and the possibility to automate this task for many OAR. However, for some OAR precise delineation remains challenging. The esophagus with a versatile shape and poor contrast is among these structures. To tackle these issues we propose a 3D fully (convolutional neural network (CNN) driven random walk (RW) approach to automatically segment the esophagus on CT. First, a soft probability map is generated by the CNN. Then an active contour model (ACM) is fitted on the probability map to get a first estimation of the center line. The outputs of the CNN and ACM are then used in addition to CT Hounsfield values to drive the RW. Evaluation and training was done on 50 CTs with peer reviewed esophagus contours. Results were assessed regarding spatial overlap and shape similarities. The generated contours showed a mean Dice coefficient of 0.76, an average symmetric square distance of 1.36 mm and an average Hausdorff distance of 11.68 compared to the reference. These figures translate into a very good agreement with the reference contours and an increase in accuracy compared to other methods. We show that by employing a CNN accurate estimations of esophagus location can be obtained and refined by a post processing RW step. One of the main advantages compared to previous methods is that our network performs convolutions in a 3D manner, fully exploiting the 3D spatial context and performing an efficient and precise volume-wise prediction. The whole segmentation process is fully automatic and yields esophagus delineations in very good agreement with the used gold standard, showing that it can compete with previously published methods.
SFCSD: A Self-Feedback Correction System for DNS Based on Active and Passive Measurement
Venue: arXiv cs.NI 2017
Year: 2017

Domain Name System (DNS), one of the important infrastructure in the Internet, was vulnerable to attacks, for the DNS designer didn't take security issues into consideration at the beginning. The defects of DNS may lead to users' failure of access to the websites, what's worse, users might suffer a huge economic loss. In order to correct the DNS wrong resource records, we propose a Self-Feedback Correction System for DNS (SFCSD), which can find and track a large number of common websites' domain name and IP address correct correspondences to provide users with a real-time auto-updated correct (IP, Domain) binary tuple list. By matching specific strings with SSL, DNS and HTTP traffic passively, filtering with the CDN CNAME and non-homepage URL feature strings, verifying with webpage fingerprint algorithm, SFCSD obtains a large number of highly possibly correct IP addresses to make an active manual correction in the end. Its self-feedback mechanism can expand search range and improve performance. Experiments show that, SFCSD can achieve 94.3% precision and 93.07% recall rate with the optimal threshold selection in the test dataset. It has 8Gbps processing speed stand-alone to find almost 1000 possibly correct (IP, Domain) per day for the each specific string and to correct almost 200.
Context-based Object Viewpoint Estimation: A 2D Relational Approach
Venue: arXiv cs.CV 2017
Year: 2017

The task of object viewpoint estimation has been a challenge since the early days of computer vision. To estimate the viewpoint (or pose) of an object, people have mostly looked at object intrinsic features, such as shape or appearance. Surprisingly, informative features provided by other, extrinsic elements in the scene, have so far mostly been ignored. At the same time, contextual cues have been proven to be of great benefit for related tasks such as object detection or action recognition. In this paper, we explore how information from other objects in the scene can be exploited for viewpoint estimation. In particular, we look at object configurations by following a relational neighbor-based approach for reasoning about object relations. We show that, starting from noisy object detections and viewpoint estimates, exploiting the estimated viewpoint and location of other objects in the scene can lead to improved object viewpoint predictions. Experiments on the KITTI dataset demonstrate that object configurations can indeed be used as a complementary cue to appearance-based viewpoint estimation. Our analysis reveals that the proposed context-based method can improve object viewpoint estimation by reducing specific types of viewpoint estimation errors commonly made by methods that only consider local information. Moreover, considering contextual information produces superior performance in scenes where a high number of object instances occur. Finally, our results suggest that, following a cautious relational neighbor formulation brings improvements over its aggressive counterpart for the task of object viewpoint estimation.
Scientific Article Summarization Using Citation-Context and Article's Discourse Structure
Venue: arXiv cs.CL 2017
Year: 2017

We propose a summarization approach for scientific articles which takes advantage of citation-context and the document discourse model. While citations have been previously used in generating scientific summaries, they lack the related context from the referenced article and therefore do not accurately reflect the article's content. Our method overcomes the problem of inconsistency between the citation summary and the article's content by providing context for each citation. We also leverage the inherent scientific article's discourse for producing better summaries. We show that our proposed method effectively improves over existing summarization approaches (greater than 30% improvement over the best performing baseline) in terms of \textsc{Rouge} scores on TAC2014 scientific summarization dataset. While the dataset we use for evaluation is in the biomedical domain, most of our approaches are general and therefore adaptable to other domains.
A hybrid spatial data mining approach based on fuzzy topological relations and MOSES evolutionary algorithm
Venue: arXiv cs.AI 2017
Year: 2017

Making high-quality decisions in strategic spatial planning is heavily dependent on extracting knowledge from vast amounts of data. Although many decision-making problems like developing urban areas require such perception and reasoning, existing methods in this field usually neglect the deep knowledge mined from geographic databases and are based on pure statistical methods. Due to the large volume of data gathered in spatial databases, and the uncertainty of spatial objects, mining association rules for high-level knowledge representation is a challenging task. Few algorithms manage geographical and non-geographical data using topological relations. In this paper, a novel approach for spatial data mining based on the MOSES evolutionary framework is presented which improves the classic genetic programming approach. A hybrid architecture called GGeo is proposed to apply the MOSES mining rules considering fuzzy topological relations from spatial data. The uncertainty and fuzziness aspects are addressed using an enriched model of topological relations by fuzzy region connection calculus. Moreover, to overcome the problem of time-consuming fuzzy topological relationships calculations, this a novel data pre-processing method is offered. GGeo analyses and learns from geographical and non-geographical data and uses topological and distance parameters, and returns a series of arithmetic-spatial formulas as classification rules. The proposed approach is resistant to noisy data, and all its stages run in parallel to increase speed. This approach may be used in different spatial data classification problems as well as representing an appropriate method of data analysis and economic policy making.
Select and Permute: An Improved Online Framework for Scheduling to Minimize Weighted Completion Time
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we introduce a new online scheduling framework for minimizing total weighted completion time in a general setting. The framework is inspired by the work of Hall et al. [Mathematics of Operations Research, Vol 22(3):513-544, 1997] and Garg et al. [Proc. of Foundations of Software Technology and Theoretical Computer Science, pp. 96-107, 2007], who show how to convert an offline approximation to an online scheme. Our framework uses two offline approximation algorithms (one for the simpler problem of scheduling without release times, and another for the minimum unscheduled weight problem) to create an online algorithm with provably good competitive ratios. We illustrate multiple applications of this method that yield improved competitive ratios. Our framework gives algorithms with the best or only known competitive ratios for the concurrent open shop, coflow, and concurrent cluster models. We also introduce a randomized variant of our framework based on the ideas of Chakrabarti et al. [Proc. of International Colloquium on Automata, Languages, and Programming, pp. 646-657, 1996] and use it to achieve improved competitive ratios for these same problems.
Continuous monitoring of $\ell_p$ norms in data streams
Venue: arXiv cs.DS 2017
Year: 2017

In insertion-only streaming, one sees a sequence of indices $a_1, a_2, \ldots, a_m\in [n]$. The stream defines a sequence of $m$ frequency vectors $x^{(1)},\ldots,x^{(m)}\in\mathbb{R}^n$ with $(x^{(t)})_i = |\{j : j\in[t], a_j = i\}|$. That is, $x^{(t)}$ is the frequency vector after seeing the first $t$ items in the stream. Much work in the streaming literature focuses on estimating some function $f(x^{(m)})$. Many applications though require obtaining estimates at time $t$ of $f(x^{(t)})$, for every $t\in[m]$. Naively this guarantee is obtained by devising an algorithm with failure probability $\ll 1/m$, then performing a union bound over all stream updates to guarantee that all $m$ estimates are simultaneously accurate with good probability. When $f(x)$ is some $\ell_p$ norm of $x$, recent works have shown that this union bound is wasteful and better space complexity is possible for the continuous monitoring problem, with the strongest known results being for $p=2$ [HTY14, BCIW16, BCINWW17]. In this work, we improve the state of the art for all $0<p<2$, which we obtain via a novel analysis of Indyk's $p$-stable sketch [Indyk06].
A dynamic resource allocation decision model for IT security
Venue: arXiv cs.CR 2017
Year: 2017

Today, with the continued growth in using information and communication technologies (ICT) for business purposes, business organizations become increasingly dependent on their information systems. Thus, they need to protect them from the different attacks exploiting their vulnerabilities. To do so, the organization has to use security technologies, which may be proactive or reactive ones. Each security technology has a relative cost and addresses specific vulnerabilities. Therefore, the organization has to put in place the appropriate security technologies set that minimizes the information system s vulnerabilities with a minimal cost. This bi objective problem will be considered as a resources allocation problem (RAP) where security technologies represent the resources to be allocated. However, the set of vulnerabilities may change, periodically, with the continual appearance of new ones. Therefore, the security technologies set should be flexible to face these changes, in real time, and the problem becomes a dynamic one. In this paper, we propose a harmony search based algorithm to solve the bi objective dynamic resource allocation decision model. This approach was compared to a genetic algorithm and provided good results.
Subspace Tracking Algorithms for Millimeter Wave MIMO Channel Estimation with Hybrid Beamforming
Venue: arXiv cs.IT 2017
Year: 2017

This paper proposes the use of subspace tracking algorithms for performing MIMO channel estimation at millimeter wave (mmWave) frequencies. Using a subspace approach, we develop a protocol enabling the estimation of the right (resp. left) singular vectors at the transmitter (resp. receiver) side; then, we adapt the projection approximation subspace tracking with deflation (PASTd) and the orthogonal Oja (OOJA) algorithms to our framework and obtain two channel estimation algorithms. The hybrid analog/digital nature of the beamformer is also explicitly taken into account at the algorithm design stage. Numerical results show that the proposed estimation algorithms are effective, and that they perform better than two relevant competing alternatives available in the open literature.
Large-Scale Sleep Condition Analysis Using Selfies from Social Media
Venue: arXiv cs.SI 2017
Year: 2017

Sleep condition is closely related to an individual's health. Poor sleep conditions such as sleep disorder and sleep deprivation affect one's daily performance, and may also cause many chronic diseases. Many efforts have been devoted to monitoring people's sleep conditions. However, traditional methodologies require sophisticated equipment and consume a significant amount of time. In this paper, we attempt to develop a novel way to predict individual's sleep condition via scrutinizing facial cues as doctors would. Rather than measuring the sleep condition directly, we measure the sleep-deprived fatigue which indirectly reflects the sleep condition. Our method can predict a sleep-deprived fatigue rate based on a selfie provided by a subject. This rate is used to indicate the sleep condition. To gain deeper insights of human sleep conditions, we collected around 100,000 faces from selfies posted on Twitter and Instagram, and identified their age, gender, and race using automatic algorithms. Next, we investigated the sleep condition distributions with respect to age, gender, and race. Our study suggests among the age groups, fatigue percentage of the 0-20 youth and adolescent group is the highest, implying that poor sleep condition is more prevalent in this age group. For gender, the fatigue percentage of females is higher than that of males, implying that more females are suffering from sleep issues than males. Among ethnic groups, the fatigue percentage in Caucasian is the highest followed by Asian and African American.
A Real-Time Framework for Task Assignment in Hyperlocal Spatial Crowdsourcing
Venue: arXiv cs.DB 2017
Year: 2017

Spatial Crowdsourcing (SC) is a novel platform that engages individuals in the act of collecting various types of spatial data. This method of data collection can significantly reduce cost and turnover time, and is particularly useful in urban environmental sensing, where traditional means fail to provide fine-grained field data. In this study, we introduce hyperlocal spatial crowdsourcing, where all workers who are located within the spatiotemporal vicinity of a task are eligible to perform the task, e.g., reporting the precipitation level at their area and time. In this setting, there is often a budget constraint, either for every time period or for the entire campaign, on the number of workers to activate to perform tasks. The challenge is thus to maximize the number of assigned tasks under the budget constraint, despite the dynamic arrivals of workers and tasks. We introduce a taxonomy of several problem variants, such as budget-per-time-period vs. budget-per-campaign and binary-utility vs. distance-based-utility. We study the hardness of the task assignment problem in the offline setting and propose online heuristics which exploits the spatial and temporal knowledge acquired over time. Our experiments are conducted with spatial crowdsourcing workloads generated by the SCAWG tool and extensive results show the effectiveness and efficiency of our proposed solutions.