OpenRaiser/Intern-Atlas huggingface dataset:
Binary Codes for Tagging X-Ray Images via Deep De-Noising Autoencoders
Venue: arXiv cs.CV 2016
Year: 2016

A Content-Based Image Retrieval (CBIR) system which identifies similar medical images based on a query image can assist clinicians for more accurate diagnosis. The recent CBIR research trend favors the construction and use of binary codes to represent images. Deep architectures could learn the non-linear relationship among image pixels adaptively, allowing the automatic learning of high-level features from raw pixels. However, most of them require class labels, which are expensive to obtain, particularly for medical images. The methods which do not need class labels utilize a deep autoencoder for binary hashing, but the code construction involves a specific training algorithm and an ad-hoc regularization technique. In this study, we explored using a deep de-noising autoencoder (DDA), with a new unsupervised training scheme using only backpropagation and dropout, to hash images into binary codes. We conducted experiments on more than 14,000 x-ray images. By using class labels only for evaluating the retrieval results, we constructed a 16-bit DDA and a 512-bit DDA independently. Comparing to other unsupervised methods, we succeeded to obtain the lowest total error by using the 512-bit codes for retrieval via exhaustive search, and speed up 9.27 times with the use of the 16-bit codes while keeping a comparable total error. We found that our new training scheme could reduce the total retrieval error significantly by 21.9%. To further boost the image retrieval performance, we developed Radon Autoencoder Barcode (RABC) which are learned from the Radon projections of images using a de-noising autoencoder. Experimental results demonstrated its superior performance in retrieval when it was combined with DDA binary codes.
Minimizing Expected Cost Under Hard Boolean Constraints, with Applications to Quantitative Synthesis
Venue: arXiv cs.FL 2016
Year: 2016

In Boolean synthesis, we are given an LTL specification, and the goal is to construct a transducer that realizes it against an adversarial environment. Often, a specification contains both Boolean requirements that should be satisfied against an adversarial environment, and multi-valued components that refer to the quality of the satisfaction and whose expected cost we would like to minimize with respect to a probabilistic environment. In this work we study, for the first time, mean-payoff games in which the system aims at minimizing the expected cost against a probabilistic environment, while surely satisfying an $ω$-regular condition against an adversarial environment. We consider the case the $ω$-regular condition is given as a parity objective or by an LTL formula. We show that in general, optimal strategies need not exist, and moreover, the limit value cannot be approximated by finite-memory strategies. We thus focus on computing the limit-value, and give tight complexity bounds for synthesizing $ε$-optimal strategies for both finite-memory and infinite-memory strategies. We show that our game naturally arises in various contexts of synthesis with Boolean and multi-valued objectives. Beyond direct applications, in synthesis with costs and rewards to certain behaviors, it allows us to compute the minimal sensing cost of $ω$-regular specifications -- a measure of quality in which we look for a transducer that minimizes the expected number of signals that are read from the input.
Understanding Illicit Drug Use Behaviors by Mining Social Media
Venue: arXiv cs.SI 2016
Year: 2016

Drug use by people is on the rise and is of great interest to public health agencies and law enforcement agencies. As found by the National Survey on Drug Use and Health, 20 million Americans aged 12 years or older consumed illicit drugs in the past few 30 days. Given their ubiquity in everyday life, drug abuse related studies have received much and constant attention. However, most of the existing studies rely on surveys. Surveys present a fair number of problems because of their nature. Surveys on sensitive topics such as illicit drug use may not be answered truthfully by the people taking them. Selecting a representative sample to survey is another major challenge. In this paper, we explore the possibility of using big data from social media in order to understand illicit drug use behaviors. Instagram posts are collected using drug related terms by analyzing the hashtags supplied with each post. A large and dynamic dictionary of frequent illicit drug related slang is used to find these posts. These posts are studied to find common drug consumption behaviors with regard to time of day and week. Furthermore, by studying the accounts followed by the users of drug related posts, we hope to discover common interests shared by drug users.
Voting with Feet: Who are Leaving Hillary Clinton and Donald Trump?
Venue: arXiv cs.SI 2016
Year: 2016

From a crowded field with 17 candidates, Hillary Clinton and Donald Trump have emerged as the two front-runners in the 2016 U.S. presidential campaign. The two candidates each boast more than 5 million followers on Twitter, and at the same time both have witnessed hundreds of thousands of people leave their camps. In this paper we attempt to characterize individuals who have left Hillary Clinton and Donald Trump between September 2015 and March 2016. Our study focuses on three dimensions of social demographics: social capital, gender, and age. Within each camp, we compare the characteristics of the current followers with former followers, i.e., individuals who have left since September 2015. We use the number of followers to measure social capital, and profile images to infer gender and age. For classifying gender, we train a convolutional neural network (CNN). For age, we use the Face++ API. Our study shows that for both candidates followers with more social capital are more likely to leave (or switch camps). For both candidates females make up a larger presence among unfollowers than among current followers. Somewhat surprisingly, the effect is particularly pronounced for Clinton. Lastly, middle-aged individuals are more likely to leave Trump, and the young are more likely to leave Hillary Clinton.
Closing the Gap for Makespan Scheduling via Sparsification Techniques
Venue: arXiv cs.DS 2016
Year: 2016

Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of $n$ jobs to a set of $m$ identical machines that minimizes the makespan. The problem is strongly NP-hard, and thus we do not expect a $(1+ε)$-approximation algorithm with a running time that depends polynomially on $1/ε$. Furthermore, Chen et al. [3] recently showed that a running time of $2^{(1/ε)^{1-δ}}+\text{poly}(n)$ for any $δ>0$ would imply that the Exponential Time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that try to obtain low dependencies on $1/ε$, the better of which achieves a running time of $2^{\tilde{O}(1/ε^2)}+O(n\log n)$ [11]. In this paper we obtain an algorithm with a running time of $2^{\tilde{O}(1/ε)}+O(n\log n)$, which is tight under ETH up to logarithmic factors on the exponent. Our main technical contribution is a new structural result on the configuration-IP. More precisely, we show the existence of a highly symmetric and sparse optimal solution, in which all but a constant number of machines are assigned a configuration with small support. This structure can then be exploited by integer programming techniques and enumeration. We believe that our structural result is of independent interest and should find applications to other settings. In particular, we show how the structure can be applied to the minimum makespan problem on related machines and to a larger class of objective functions on parallel machines. For all these cases we obtain an efficient PTAS with running time $2^{\tilde{O}(1/ε)} + \text{poly}(n)$.
Deterministic Performance Analysis of Subspace Methods for Cisoid Parameter Estimation
Venue: arXiv cs.IT 2016
Year: 2016

Performance analyses of subspace algorithms for cisoid parameter estimation available in the literature are predominantly of statistical nature with a focus on asymptotic$-$either in the sample size or the SNR$-$statements. This paper presents a deterministic, finite sample size, and finite-SNR performance analysis of the ESPRIT algorithm and the matrix pencil method. Our results are based, inter alia, on a new upper bound on the condition number of Vandermonde matrices with nodes inside the unit disk. This bound is obtained through a generalization of Hilbert's inequality frequently used in large sieve theory.
A Deep Hierarchical Approach to Lifelong Learning in Minecraft
Venue: arXiv cs.AI 2016
Year: 2016

We propose a lifelong learning system that has the ability to reuse and transfer knowledge from one task to another while efficiently retaining the previously learned knowledge-base. Knowledge is transferred by learning reusable skills to solve tasks in Minecraft, a popular video game which is an unsolved and high-dimensional lifelong learning problem. These reusable skills, which we refer to as Deep Skill Networks, are then incorporated into our novel Hierarchical Deep Reinforcement Learning Network (H-DRLN) architecture using two techniques: (1) a deep skill array and (2) skill distillation, our novel variation of policy distillation (Rusu et. al. 2015) for learning skills. Skill distillation enables the HDRLN to efficiently retain knowledge and therefore scale in lifelong learning, by accumulating knowledge and encapsulating multiple reusable skills into a single distilled network. The H-DRLN exhibits superior performance and lower learning sample complexity compared to the regular Deep Q Network (Mnih et. al. 2015) in sub-domains of Minecraft.
Impact of Mobility on the Sum Rate of NB-OFDMA Based Mobile IoT Networks
Venue: arXiv cs.IT 2016
Year: 2016

In future Internet of Things (IoT) networks, the explosive growth of mobile devices compel us to reconsider the effectiveness of the current frequency-division multiple access (FDMA) schemes. Devices' differentiated mobility features and diversified scattering environments make it more complicated to characterize the multi-user interference. In this paper, we thoroughly analyze the impacts of devices' mobility on the inter-sub-carrier interference (ICI) in an IoT system based on the 3GPP narrow-band orthogonal frequency-division multiple access (NB-OFDMA) protocol, and obtain the relationship between the system sum-rate and devices' mobility. Our results may shed some lights on the system design under the mobile scenarios.
Compressed-domain visual saliency models: A comparative study
Venue: arXiv cs.MM 2016
Year: 2016

Computational modeling of visual saliency has become an important research problem in recent years, with applications in video quality estimation, video compression, object tracking, retargeting, summarization, and so on. While most visual saliency models for dynamic scenes operate on raw video, several models have been developed for use with compressed-domain information such as motion vectors and transform coefficients. This paper presents a comparative study of eleven such models as well as two high-performing pixel-domain saliency models on two eye-tracking datasets using several comparison metrics. The results indicate that highly accurate saliency estimation is possible based only on a partially decoded video bitstream. The strategies that have shown success in compressed-domain saliency modeling are highlighted, and certain challenges are identified as potential avenues for further improvement.
Fast approximation algorithms for $p$-centres in large $δ$-hyperbolic graphs
Venue: arXiv cs.DS 2016
Year: 2016

We provide a quasilinear time algorithm for the $p$-center problem with an additive error less than or equal to 3 times the input graph's hyperbolic constant. Specifically, for the graph $G=(V,E)$ with $n$ vertices, $m$ edges and hyperbolic constant $δ$, we construct an algorithm for $p$-centers in time $O(p(δ+1)(n+m)\log(n))$ with radius not exceeding $r_p + δ$ when $p \leq 2$ and $r_p + 3δ$ when $p \geq 3$, where $r_p$ are the optimal radii. Prior work identified $p$-centers with accuracy $r_p+δ$ but with time complexity $O((n^3\log n + n^2m)\log(diam(G)))$ which is impractical for large graphs.
Degree and Sensitivity: tails of two distributions
Venue: arXiv cs.CC 2016
Year: 2016

The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree poly(s). The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Further, we show that improving the bound to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets, and present an approach towards proving this conjecture.
Estimating Weighted Matchings in $o(n)$ Space
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of estimating the weight of a maximum weighted matching of a weighted graph $G(V,E)$ whose edges are revealed in a streaming fashion. We develop a reduction from the maximum weighted matching problem to the maximum cardinality matching problem that only doubles the approximation factor of a streaming algorithm developed for the maximum cardinality matching problem. Our results hold for the insertion-only and the dynamic (i.e, insertion and deletion) edge-arrival streaming models. The previous best-known reduction is due to Bury and Schwiegelshohn (ESA 2015) who develop an algorithm whose approximation guarantee scales by a polynomial factor. As an application, we obtain improved estimators for weighted planar graphs and, more generally, for weighted bounded-arboricity graphs, by feeding into our reduction the recent estimators due to Esfandiari et al. (SODA 2015) and to Chitnis et al. (SODA 2016). In particular, we obtain a $(48+ε)$-approximation estimator for the weight of a maximum weighted matching in planar graphs.
Subjective Assessment of H.264 Compressed Stereoscopic Video
Venue: arXiv cs.MM 2016
Year: 2016

The tremendous growth in 3D (stereo) imaging and display technologies has led to stereoscopic content (video and image) becoming increasingly popular. However, both the subjective and the objective evaluation of stereoscopic video content has not kept pace with the rapid growth of the content. Further, the availability of standard stereoscopic video databases is also quite limited. In this work, we attempt to alleviate these shortcomings. We present a stereoscopic video database and its subjective evaluation. We have created a database containing a set of 144 distorted videos. We limit our attention to H.264 compression artifacts. The distorted videos were generated using 6 uncompressed pristine videos of left and right views originally created by Goldmann et al. at EPFL [1]. Further, 19 subjects participated in the subjective assessment task. Based on the subjective study, we have formulated a relation between the 2D and stereoscopic subjective scores as a function of compression rate and depth range. We have also evaluated the performance of popular 2D and 3D image/video quality assessment (I/VQA) algorithms on our database.
Delay-Optimal Computation Task Scheduling for Mobile-Edge Computing Systems
Venue: arXiv cs.IT 2016
Year: 2016

Mobile-edge computing (MEC) emerges as a promising paradigm to improve the quality of computation experience for mobile devices. Nevertheless, the design of computation task scheduling policies for MEC systems inevitably encounters a challenging two-timescale stochastic optimization problem. Specifically, in the larger timescale, whether to execute a task locally at the mobile device or to offload a task to the MEC server for cloud computing should be decided, while in the smaller timescale, the transmission policy for the task input data should adapt to the channel side information. In this paper, we adopt a Markov decision process approach to handle this problem, where the computation tasks are scheduled based on the queueing state of the task buffer, the execution state of the local processing unit, as well as the state of the transmission unit. By analyzing the average delay of each task and the average power consumption at the mobile device, we formulate a power-constrained delay minimization problem, and propose an efficient one-dimensional search algorithm to find the optimal task scheduling policy. Simulation results are provided to demonstrate the capability of the proposed optimal stochastic task scheduling policy in achieving a shorter average execution delay compared to the baseline policies.
Incompatibility of Efficiency and Strategyproofness in the Random Assignment Setting with Indifferences
Venue: arXiv cs.GT 2016
Year: 2016

A fundamental resource allocation setting is the random assignment problem in which agents express preferences over objects that are then randomly allocated to the agents. In 2001, Bogomolnaia and Moulin presented the probabilistic serial (PS) mechanism that is an anonymous, neutral, Pareto optimal, and weak strategyproof mechanism when the preferences are considered with respect to stochastic dominance. The result holds when agents have strict preferences over individual objects. It has been an open problem whether there exists a mechanism that satisfies the same properties when agents may have indifference among the objects. We show that for this more general domain, there exists no extension of PS that is ex post efficient and weak strategyproof. The result is surprising because it does not even require additional symmetry or fairness conditions such as anonymity, neutrality, or equal treatment of equals. Our result further demonstrates that the lack of weak SD-strategyproofness of the extended PS mechanism of Katta and Sethuraman (2006) is not a design flaw of extended PS but is due to an inherent incompatibility of efficiency and strategyproofness of PS in the full preference domain.
Bounds on the Error Probability of Raptor Codes
Venue: arXiv cs.IT 2016
Year: 2016

In this paper q-ary Raptor codes under ML decoding are considered. An upper bound on the probability of decoding failure is derived using the weight enumerator of the outer code, or its expected weight enumerator if the outer code is drawn randomly from some ensemble of codes. The bound is shown to be tight by means of simulations. This bound provides a new insight into Raptor codes since it shows how Raptor codes can be analyzed similarly to a classical fixed-rate serial concatenation.
Compress Voice Transference over low Signal Strength in Satellite Communication
Venue: arXiv cs.MM 2016
Year: 2016

This paper presents the comparison of compression algorithms for voice transferring method over SMS in satellite communication. Voice transferring method over SMS is useful in situations when signal strength is low and due to poor signal strength voice call connection is not possible to initiate or signal dropped during voice call. This method has one serious flaw that it produces large number of SMS while converting voice into SMS. Such issue is catered to some extend by employing any compression algorithm. In this paper our major aim is to find best compression scheme for said method, for that purpose we compare 6 different types of compression algorithms which are; LZW (Lempel-Ziv-Welch), Huffman coding, PPM (Prediction by partial matching), Arithmetic Coding (AC), BWT (Burrows-Wheeler-Transform), LZMA (Lempel-Ziv-Markov chain). This comparison shows that PPM compression method offers better compression ratio and produce small number of SMS. For experimentation we use Thuraya SG-2520 satellite phone. Moreover, we develop an application using J2ME platform[Ref:a]. We tested that application more than 100 times and then we compare the result in terms of compression ratio of each algorithm and number of connected SMS produce after each compression method. The result of this study will help developers to choose better compression scheme for their respective applications. http://www.learnrnd.com/news.php?id=ISSUES_IN_MOLECULAR_COMMUNICATIONS
Mutual Transformation of Information and Knowledge
Venue: arXiv cs.AI 2016
Year: 2016

Information and knowledge are transformable into each other. Information transformation into knowledge by the example of rule generation from OWL (Web Ontology Language) ontology has been shown during the development of the SWES (Semantic Web Expert System). The SWES is expected as an expert system for searching OWL ontologies from the Web, generating rules from the found ontologies and supplementing the SWES knowledge base with these rules. The purpose of this paper is to show knowledge transformation into information by the example of ontology generation from rules.
An Accelerometer Based Calculator for Visually Impaired People Using Mobile Devices
Venue: arXiv cs.HC 2016
Year: 2016

Recent trend of touch-screen devices produces an accessibility barrier for visually impaired people. On the other hand, these devices come with sensors such as accelerometer. This calls for new approaches to human computer interface (HCI). In this study, our aim is to find an alternative approach to classify 20 different hand gestures captured by iPhone 3GS's built-in accelerometer and make high accuracy on user-independent classifications using Dynamic Time Warping (DTW) with dynamic warping window sizes. 20 gestures with 1,100 gesture data are collected from 15 normal-visioned people. This data set is used for training. Experiment-1 based on this data set produced an accuracy rate of 96.7~\%. In order for visually impaired people to use the system, a gesture recognition based "talking" calculator is implemented. In Experiment-2, 4 visually impaired end-users used the calculator and obtained 95.5~\% accuracy rate among 17 gestures with 720 gesture data totally. Contributions of the techniques to the end result is also investigated. Dynamic warping window size is found to be the most effective one. The data and the code is available.
An Appropriate Sensor Distribution Technique in Wireless Sensor Networks
Venue: arXiv cs.NI 2016
Year: 2016

Wireless Sensor Network (WSN) is pertinent to many applications with varied network parameters. Sensor node placement in the application region whether it is indoor or outdoor is a major task as well as plays very remarkable role in the network performance. Node placement is carried out according to the region where it is applied, either deterministic or non deterministic. Because of the need for different sensing probability or detection probability, same approach of sensor placement may not be suited for all the applications. Some of the applications are well formed and give better performance with the uniform distribution of sensors but few need intense distribution of nodes in particular sensitive places especially those applications meant for intrusion detection. An application which needs high level intrusion detection and a suitable sensor distribution methodology, known as Half-Normal Distribution (Half-Gaussian) based deployment, have been set forth in this paper. We have also discussed the theoretical comparison for detection probability with the uniform distribution in terms of number of sensor nodes.