OpenRaiser/Intern-Atlas huggingface dataset:
The TUM LapChole dataset for the M2CAI 2016 workflow challenge
Venue: arXiv cs.CV 2017
Year: 2017

In this technical report we present our collected dataset of laparoscopic cholecystectomies (LapChole). Laparoscopic videos of a total of 20 surgeries were recorded and annotated with surgical phase labels, of which 15 were randomly pre-determined as training data, while the remaining 5 videos are selected as test data. This dataset was later included as part of the M2CAI 2016 workflow detection challenge during MICCAI 2016 in Athens.
Improving Sampling from Generative Autoencoders with Markov Chains
Venue: arXiv cs.LG 2017
Year: 2017

We focus on generative autoencoders, such as variational or adversarial autoencoders, which jointly learn a generative model alongside an inference model. Generative autoencoders are those which are trained to softly enforce a prior on the latent distribution learned by the inference model. We call the distribution to which the inference model maps observed samples, the learned latent distribution, which may not be consistent with the prior. We formulate a Markov chain Monte Carlo (MCMC) sampling process, equivalent to iteratively decoding and encoding, which allows us to sample from the learned latent distribution. Since, the generative model learns to map from the learned latent distribution, rather than the prior, we may use MCMC to improve the quality of samples drawn from the generative model, especially when the learned latent distribution is far from the prior. Using MCMC sampling, we are able to reveal previously unseen differences between generative autoencoders trained either with or without a denoising criterion.
A Polynomial-time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs
Venue: arXiv cs.DS 2017
Year: 2017

A directed multigraph is said vulnerable if it can generate Braess paradox in Traffic Networks. In this paper, we give a graph-theoretic characterisation of vulnerable directed multigraphs; analogous results appeared in the literature only for undirected multigraphs and for a specific family of directed multigraphs. The proof of our characterisation also provides an algorithm that checks if a multigraph is vulnerable in O(|V| |E|^2); this is the first polynomial time algorithm that checks vulnerability for general directed multigraphs. The resulting algorithm also contributes to another well known problem, i.e. the directed subgraph homeomorphism problem without node mapping, by providing another pattern graph for which a polynomial time algorithm exists.
Design of an Ultra-Efficient Reversible Full Adder-Subtractor in Quantum-dot Cellular Automata
Venue: arXiv cs.ET 2017
Year: 2017

By the progressive scaling of the feature size and power consumption in VLSI chips the part of energy dissipated due to information loss in irreversible computations will become a serious limitation in the near future. Quantum-dot cellular automata (QCA) is an emerging nanotechnology with extremely low energy dissipation which facilitates new computation paradigms such as reversible computing. In this paper a novel reversible full adder-subtractor circuit based on QCA is proposed. Our proposed design is implemented using only one layer and does not require any rotated cells which significantly improves the manufacturability of the design. In addition, it improves the cell count, area and total energy dissipation by almost 45% and 50% and 48%, respectively, as compared to the existing QCA-based single-layer and multilayer reversible full adders.
Efficient Construction of Polar Codes
Venue: arXiv cs.IT 2017
Year: 2017

The construction of polar codes for channels other than BECs requires sorting of all bit channels and then selecting the best $K$ of them for a block length $N=2^n$. In this paper, two types of partial orders (PO) of polar codes are incorporated in the construction process to decrease the required computations. Three sets, corresponding to the good bit channels ($\mathcal{I}$), the frozen bit channels ($\mathcal{F}$), and the undetermined bit channels ($\mathcal{U}$), are selected by applying PO relations. The POs are channel independent and are therefore universal for all binary-input discrete memoryless channels. For a given specific channel, a new process, called Dimension Reduction (DR), is proposed in this paper to further reduce the size of $\mathcal{U}$. Our studies show that for $N=10$ and the code rate $R=0.5$ (being the worst code rate), incorporating PO relations alone can determine 50% of the bit channels ($|\mathcal{I}| + |\mathcal{F}| \approx N/2$). With our proposed DR, this number of the determined bit channels goes up to 82%, which brings a significant reduction of computations in the construction of polar codes.
From Node Embedding To Community Embedding
Venue: arXiv cs.SI 2017
Year: 2017

Most of the existing graph embedding methods focus on nodes, which aim to output a vector representation for each node in the graph such that two nodes being "close" on the graph are close too in the low-dimensional space. Despite the success of embedding individual nodes for graph analytics, we notice that an important concept of embedding communities (i.e., groups of nodes) is missing. Embedding communities is useful, not only for supporting various community-level applications, but also to help preserve community structure in graph embedding. In fact, we see community embedding as providing a higher-order proximity to define the node closeness, whereas most of the popular graph embedding methods focus on first-order and/or second-order proximities. To learn the community embedding, we hinge upon the insight that community embedding and node embedding reinforce with each other. As a result, we propose ComEmbed, the first community embedding method, which jointly optimizes the community embedding and node embedding together. We evaluate ComEmbed on real-world data sets. We show it outperforms the state-of-the-art baselines in both tasks of node classification and community prediction.
RNN Approaches to Text Normalization: A Challenge
Venue: arXiv cs.CL 2017
Year: 2017

This paper presents a challenge to the community: given a large corpus of written text aligned to its normalized spoken form, train an RNN to learn the correct normalization function. We present a data set of general text where the normalizations were generated using an existing text normalization component of a text-to-speech system. This data set will be released open-source in the near future. We also present our own experiments with this data set with a variety of different RNN architectures. While some of the architectures do in fact produce very good results when measured in terms of overall accuracy, the errors that are produced are problematic, since they would convey completely the wrong message if such a system were deployed in a speech application. On the other hand, we show that a simple FST-based filter can mitigate those errors, and achieve a level of accuracy not achievable by the RNN alone. Though our conclusions are largely negative on this point, we are actually not arguing that the text normalization problem is intractable using an pure RNN approach, merely that it is not going to be something that can be solved merely by having huge amounts of annotated text data and feeding that to a general RNN model. And when we open-source our data, we will be providing a novel data set for sequence-to-sequence modeling in the hopes that the the community can find better solutions. The data used in this work have been released and are available at: https://github.com/rwsproat/text-normalization-data
LoRea: A Backscatter Architecture that Achieves a Long Communication Range
Venue: arXiv cs.NI 2017
Year: 2017

There is the long-standing assumption that radio communication in the range of hundreds of meters needs to consume mWs of power at the transmitting device. In this paper, we demonstrate that this is not necessarily the case for some devices equipped with backscatter radios. We present LoRea an architecture consisting of a tag, a reader and multiple carrier generators that overcomes the power, cost and range limitations of existing systems such as Computational Radio Frequency Identification~(CRFID). LoRea achieves this by: First, generating narrow-band backscatter transmissions that improve receiver sensitivity. Second, mitigating self-interference without the complex designs employed on RFID readers by keeping carrier signal and backscattered signal apart in frequency. Finally, decoupling carrier generation from the reader and using devices such as WiFi routers and sensor nodes as a source of the carrier signal. An off-the-shelf implementation of LoRea costs 70 USD, a drastic reduction in price considering commercial RFID readers cost 2000 USD. LoRea's range scales with the carrier strength, and proximity to the carrier source and achieves a maximum range of 3.4 kilometre when the tag is located at 1 meter distance from a 28 dBm carrier source while consuming 70 microwatts at the tag. When the tag is equidistant from the carrier source and the receiver, we can communicate upto 75 meter, a significant improvement over existing RFID readers.
Semi-Supervised Radio Signal Identification
Venue: arXiv cs.LG 2017
Year: 2017

Radio emitter recognition in dense multi-user environments is an important tool for optimizing spectrum utilization, identifying and minimizing interference, and enforcing spectrum policy. Radio data is readily available and easy to obtain from an antenna, but labeled and curated data is often scarce making supervised learning strategies difficult and time consuming in practice. We demonstrate that semi-supervised learning techniques can be used to scale learning beyond supervised datasets, allowing for discerning and recalling new radio signals by using sparse signal representations based on both unsupervised and supervised methods for nonlinear feature learning and clustering methods.
Per-Server Dominant-Share Fairness (PS-DSF): A Multi-Resource Fair Allocation Mechanism for Heterogeneous Servers
Venue: arXiv cs.DC 2017
Year: 2017

Users of cloud computing platforms pose different types of demands for multiple resources on servers (physical or virtual machines). Besides differences in their resource capacities, servers may be additionally heterogeneous in their ability to service users - certain users' tasks may only be serviced by a subset of the servers. We identify important shortcomings in existing multi-resource fair allocation mechanisms - Dominant Resource Fairness (DRF) and its follow up work - when used in such environments. We develop a new fair allocation mechanism called Per-Server Dominant-Share Fairness (PS-DSF) which we show offers all desirable sharing properties that DRF is able to offer in the case of a single "resource pool" (i.e., if the resources of all servers were pooled together into one hypothetical server). We evaluate the performance of PS-DSF through simulations. Our evaluation shows the enhanced efficiency of PS-DSF compared to the existing allocation mechanisms. We argue how our proposed allocation mechanism is applicable in cloud computing networks and especially large scale data-centers.
Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review
Venue: arXiv cs.LG 2017
Year: 2017

The paper characterizes classes of functions for which deep learning can be exponentially better than shallow learning. Deep convolutional networks are a special case of these conditions, though weight sharing is not the main reason for their exponential advantage.
All or nothing: toward a promise problem dichotomy for constraint problems
Venue: arXiv cs.CC 2017
Year: 2017

A finite constraint language $\mathscr{R}$ is a finite set of relations over some finite domain $A$. We show that intractability of the constraint satisfaction problem $\operatorname{CSP}(\mathscr{R})$ can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions: where instances are guaranteed to either have no solutions at all, or to be $k$-robustly satisfiable (for any fixed $k$), meaning that every "reasonable" partial instantiation on~$k$ variables extends to a solution. For example, subject to the assumption $\texttt{P}\neq \texttt{NP}$, then for any~$k$, we show that there is no polynomial time algorithm that can distinguish non-$3$-colourable graphs, from those for which any reasonable $3$-colouring of any $k$ of the vertices can extend to a full $3$-colouring. Our main result shows that an analogous statement holds for all known intractable constraint problems over fixed finite constraint languages.
Classifying unavoidable Tverberg partitions
Venue: arXiv cs.CG 2017
Year: 2017

Let $T(d,r) = (r-1)(d+1)+1$ be the parameter in Tverberg's theorem, and call a partition $\mathcal I$ of $\{1,2,\ldots,T(d,r)\}$ into $r$ parts a "Tverberg type". We say that $\mathcal I$ "occurs" in an ordered point sequence $P$ if $P$ contains a subsequence $P'$ of $T(d,r)$ points such that the partition of $P'$ that is order-isomorphic to $\mathcal I$ is a Tverberg partition. We say that $\mathcal I$ is "unavoidable" if it occurs in every sufficiently long point sequence. In this paper we study the problem of determining which Tverberg types are unavoidable. We conjecture a complete characterization of the unavoidable Tverberg types, and we prove some cases of our conjecture for $d\le 4$. Along the way, we study the avoidability of many other geometric predicates. Our techniques also yield a large family of $T(d,r)$-point sets for which the number of Tverberg partitions is exactly $(r-1)!^d$. This lends further support for Sierksma's conjecture on the number of Tverberg partitions.
Out-of-Band Radiation from Large Antenna Arrays
Venue: arXiv cs.IT 2017
Year: 2017

Co-existing wireless systems, which share a common spectrum, need to mitigate out-of-band (OOB) radiation to avoid excessive interference. For legacy systems, OOB radiation is well understood and is commonly handled by digital precompensation techniques. When using large arrays, however, new phenomena and hardware limitations have to be considered. First, signals can be radiated directionally, which might focus the OOB radiation. Second, low-complexity hardware is used for cost reasons, which increases the relative amount of OOB radiation. Given that massive MIMO and millimeter wave communication rely on base stations with a large number of antennas, the spatial behavior of OOB radiation from large arrays will have significant implications for the hardware requirements of future base stations. We show that, if the OOB radiation is beamformed, its array gain is never larger than that of the in-band signal. In many cases, the OOB radiation is close to isotropic even when the in-band signal is highly directive. With the same total radiated power, the OOB radiation from large arrays is therefore never more severe than from a legacy system with the same adjacent-channel-leakage ratio. Further, the OOB radiation is less detrimental than from a legacy system since the high array gain of the in-band signal allows large arrays to radiate less total power than legacy systems. We also show how OOB radiation from large arrays varies with location in static propagation environments and how these effects vanish when averaged over the small-scale fading. Since a higher relative amount of OOB radiation can be tolerated for large arrays, the linearity requirement can be relaxed as compared to legacy systems. Specifically, less stringent linearity requirements on each transmitter makes it possible to build large arrays from low-complexity hardware.
Using Hover to Compromise the Confidentiality of User Input on Android
Venue: arXiv cs.CR 2017
Year: 2017

We show that the new hover (floating touch) technology, available in a number of today's smartphone models, can be abused by any Android application running with a common SYSTEM_ALERT_WINDOW permission to record all touchscreen input into other applications. Leveraging this attack, a malicious application running on the system is therefore able to profile user's behavior, capture sensitive input such as passwords and PINs as well as record all user's social interactions. To evaluate our attack we implemented Hoover, a proof-of-concept malicious application that runs in the system background and records all input to foreground applications. We evaluated Hoover with 40 users, across two different Android devices and two input methods, stylus and finger. In the case of touchscreen input by finger, Hoover estimated the positions of users' clicks within an error of 100 pixels and keyboard input with an accuracy of 79%. Hoover captured users' input by stylus even more accurately, estimating users' clicks within 2 pixels and keyboard input with an accuracy of 98%. We discuss ways of mitigating this attack and show that this cannot be done by simply restricting access to permissions or imposing additional cognitive load on the users since this would significantly constrain the intended use of the hover technology.
Twenty (simple) questions
Venue: arXiv cs.DM 2017
Year: 2017

A basic combinatorial interpretation of Shannon's entropy function is via the "20 questions" game. This cooperative game is played by two players, Alice and Bob: Alice picks a distribution $π$ over the numbers $\{1,\ldots,n\}$, and announces it to Bob. She then chooses a number $x$ according to $π$, and Bob attempts to identify $x$ using as few Yes/No queries as possible, on average. An optimal strategy for the "20 questions" game is given by a Huffman code for $π$: Bob's questions reveal the codeword for $x$ bit by bit. This strategy finds $x$ using fewer than $H(π)+1$ questions on average. However, the questions asked by Bob could be arbitrary. In this paper, we investigate the following question: Are there restricted sets of questions that match the performance of Huffman codes, either exactly or approximately? Our first main result shows that for every distribution $π$, Bob has a strategy that uses only questions of the form "$x < c$?" and "$x = c$?", and uncovers $x$ using at most $H(π)+1$ questions on average, matching the performance of Huffman codes in this sense. We also give a natural set of $O(rn^{1/r})$ questions that achieve a performance of at most $H(π)+r$, and show that $Ω(rn^{1/r})$ questions are required to achieve such a guarantee. Our second main result gives a set $\mathcal{Q}$ of $1.25^{n+o(n)}$ questions such that for every distribution $π$, Bob can implement an optimal strategy for $π$ using only questions from $\mathcal{Q}$. We also show that $1.25^{n-o(n)}$ questions are needed, for infinitely many $n$. If we allow a small slack of $r$ over the optimal strategy, then roughly $(rn)^{Θ(1/r)}$ questions are necessary and sufficient.
Recover Subjective Quality Scores from Noisy Measurements
Venue: arXiv cs.MM 2017
Year: 2017

Simple quality metrics such as PSNR are known to not correlate well with subjective quality when tested across a wide spectrum of video content or quality regime. Recently, efforts have been made in designing objective quality metrics trained on subjective data (e.g. VMAF), demonstrating better correlation with video quality perceived by human. Clearly, the accuracy of such a metric heavily depends on the quality of the subjective data that it is trained on. In this paper, we propose a new approach to recover subjective quality scores from noisy raw measurements, using maximum likelihood estimation, by jointly estimating the subjective quality of impaired videos, the bias and consistency of test subjects, and the ambiguity of video contents all together. We also derive closed-from expression for the confidence interval of each estimate. Compared to previous methods which partially exploit the subjective information, our approach is able to exploit the information in full, yielding tighter confidence interval and better handling of outliers without the need for z-scoring or subject rejection. It also handles missing data more gracefully. Finally, as side information, it provides interesting insights on the test subjects and video contents.
Algorithmic Discrepancy Beyond Partial Coloring
Venue: arXiv cs.DS 2017
Year: 2017

The partial coloring method is one of the most powerful and widely used method in combinatorial discrepancy problems. However, in many cases it leads to sub-optimal bounds as the partial coloring step must be iterated a logarithmic number of times, and the errors can add up in an adversarial way. We give a new and general algorithmic framework that overcomes the limitations of the partial coloring method and can be applied in a black-box manner to various problems. Using this framework, we give new improved bounds and algorithms for several classic problems in discrepancy. In particular, for Tusnady's problem, we give an improved $O(\log^2 n)$ bound for discrepancy of axis-parallel rectangles and more generally an $O_d(\log^dn)$ bound for $d$-dimensional boxes in $\mathbb{R}^d$. Previously, even non-constructively, the best bounds were $O(\log^{2.5} n)$ and $O_d(\log^{d+0.5}n)$ respectively. Similarly, for the Steinitz problem we give the first algorithm that matches the best known non-constructive bounds due to Banaszczyk [Banaszczyk 2012] in the $\ell_\infty$ case, and improves the previous algorithmic bounds substantially in the $\ell_2$ case. Our framework is based upon a substantial generalization of the techniques developed recently in the context of the Komlós discrepancy problem [BDG16].
Hierarchical Question Answering for Long Documents
Venue: arXiv cs.CL 2017
Year: 2017

We present a framework for question answering that can efficiently scale to longer documents while maintaining or even improving performance of state-of-the-art models. While most successful approaches for reading comprehension rely on recurrent neural networks (RNNs), running them over long documents is prohibitively slow because it is difficult to parallelize over sequences. Inspired by how people first skim the document, identify relevant parts, and carefully read these parts to produce an answer, we combine a coarse, fast model for selecting relevant sentences and a more expensive RNN for producing the answer from those sentences. We treat sentence selection as a latent variable trained jointly from the answer only using reinforcement learning. Experiments demonstrate the state of the art performance on a challenging subset of the Wikireading and on a new dataset, while speeding up the model by 3.5x-6.7x.
AC-BLSTM: Asymmetric Convolutional Bidirectional LSTM Networks for Text Classification
Venue: arXiv cs.CL 2017
Year: 2017

Recently deeplearning models have been shown to be capable of making remarkable performance in sentences and documents classification tasks. In this work, we propose a novel framework called AC-BLSTM for modeling sentences and documents, which combines the asymmetric convolution neural network (ACNN) with the Bidirectional Long Short-Term Memory network (BLSTM). Experiment results demonstrate that our model achieves state-of-the-art results on five tasks, including sentiment analysis, question type classification, and subjectivity classification. In order to further improve the performance of AC-BLSTM, we propose a semi-supervised learning framework called G-AC-BLSTM for text classification by combining the generative model with AC-BLSTM.