OpenRaiser/Intern-Atlas huggingface dataset:
Ordered Dags: HypercubeSort
Venue: arXiv cs.DS 2017
Year: 2017

We generalise the insertion into a binary heap to any directed acyclic graph (DAG) with one source vertex. This lets us formulate a general method for converting any such DAG into a data structure with priority queue interface. We apply our method to a hypercube DAG to obtain a sorting algorithm of complexity $\mathcal{O}(n\log^2 (n))$. As another curious application, we derive a relationship between length of longest path and maximum degree of a vertex in a DAG.
VIDOSAT: High-dimensional Sparsifying Transform Learning for Online Video Denoising
Venue: arXiv cs.CV 2017
Year: 2017

Techniques exploiting the sparsity of images in a transform domain have been effective for various applications in image and video processing. Transform learning methods involve cheap computations and have been demonstrated to perform well in applications such as image denoising and medical image reconstruction. Recently, we proposed methods for online learning of sparsifying transforms from streaming signals, which enjoy good convergence guarantees, and involve lower computational costs than online synthesis dictionary learning. In this work, we apply online transform learning to video denoising. We present a novel framework for online video denoising based on high-dimensional sparsifying transform learning for spatio-temporal patches. The patches are constructed either from corresponding 2D patches in successive frames or using an online block matching technique. The proposed online video denoising requires little memory, and offers efficient processing. Numerical experiments compare the performance to the proposed video denoising scheme but fixing the transform to be 3D DCT, as well as prior schemes such as dictionary learning-based schemes, and the state-of-the-art VBM3D and VBM4D on several video data sets, demonstrating the promising performance of the proposed methods.
Optimal Matroid Partitioning Problems
Venue: arXiv cs.DS 2017
Year: 2017

This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set $E$ and $k$ weighted matroids $(E, \mathcal{I}_i, w_i)$, $i = 1, \dots, k$, and our task is to find a minimum partition $(I_1,\dots,I_k)$ of $E$ such that $I_i \in \mathcal{I}_i$ for all $i$. For each objective function, we give a polynomial-time algorithm or prove NP-hardness. In particular, for the case when the given weighted matroids are identical and the objective function is the sum of the maximum weight in each set (i.e., $\sum_{i=1}^k\max_{e\in I_i}w_i(e)$), we show that the problem is strongly NP-hard but admits a PTAS.
Event Identification as a Decision Process with Non-linear Representation of Text
Venue: arXiv cs.CL 2017
Year: 2017

We propose scale-free Identifier Network(sfIN), a novel model for event identification in documents. In general, sfIN first encodes a document into multi-scale memory stacks, then extracts special events via conducting multi-scale actions, which can be considered as a special type of sequence labelling. The design of large scale actions makes it more efficient processing a long document. The whole model is trained with both supervised learning and reinforcement learning.
Energy-Efficient Power and Bandwidth Allocation in an Integrated Sub-6 GHz -- Millimeter Wave System
Venue: arXiv cs.IT 2017
Year: 2017

In mobile millimeter wave (mmWave) systems, energy is a scarce resource due to the large losses in the channel and high energy usage by analog-to-digital converters (ADC), which scales with bandwidth. In this paper, we consider a communication architecture that integrates the sub-6 GHz and mmWave technologies in 5G cellular systems. In order to mitigate the energy scarcity in mmWave systems, we investigate the rate-optimal and energy-efficient physical layer resource allocation jointly across the sub-6 GHz and mmWave interfaces. First, we formulate an optimization problem in which the objective is to maximize the achievable sum rate under power constraints at the transmitter and receiver. Our formulation explicitly takes into account the energy consumption in integrated-circuit components, and assigns the optimal power and bandwidth across the interfaces. We consider the settings with no channel state information and partial channel state information at the transmitter and under high and low SNR scenarios. Second, we investigate the energy efficiency (EE) defined as the ratio between the amount of data transmitted and the corresponding incurred cost in terms of power. We use fractional programming and Dinkelbach's algorithm to solve the EE optimization problem. Our results prove that despite the availability of huge bandwidths at the mmWave interface, it may be optimal (in terms of achievable sum rate and energy efficiency) to utilize it partially. Moreover, depending on the sub-6 GHz and mmWave channel conditions and total power budget, it may be optimal to activate only one of the interfaces.
Annotation and Detection of Emotion in Text-based Dialogue Systems with CNN
Venue: arXiv cs.CL 2017
Year: 2017

Knowledge of users' emotion states helps improve human-computer interaction. In this work, we presented EmoNet, an emotion detector of Chinese daily dialogues based on deep convolutional neural networks. In order to maintain the original linguistic features, such as the order, commonly used methods like segmentation and keywords extraction were not adopted, instead we increased the depth of CNN and tried to let CNN learn inner linguistic relationships. Our main contribution is that we presented a new model and a new pipeline which can be used in multi-language environment to solve sentimental problems. Experimental results shows EmoNet has a great capacity in learning the emotion of dialogues and achieves a better result than other state of art detectors do.
Latency Aware Drone Base Station Placement in Heterogeneous Networks
Venue: arXiv cs.NI 2017
Year: 2017

Different from traditional static small cells, Drone Base Stations (DBSs) exhibit their own advantages, i.e., faster and cheaper to deploy, more flexibly reconfigured, and likely to have better communications channels owing to the presence of short-range line-of-sight links. Thus, applying DBSs into the cellular network has great potential to increase the throughput of the network and improve Quality of Service (QoS) of Mobile Users (MUs). In this paper, we focus on how to place the DBS (i.e., jointly determining the location and the association coverage of a DBS) in order to improve the QoS in terms of minimizing the total average latency ratio of MUs by considering the energy capacity limitation of the DBS. We formulate the DBS placement problem as an optimization problem and design a Latency aware dronE bAse station Placement (LEAP) algorithm to solve it efficiently. The performance of LEAP is demonstrated via simulations as compared to other two baseline methods.
Adaptive Measurement Network for CS Image Reconstruction
Venue: arXiv cs.CV 2017
Year: 2017

Conventional compressive sensing (CS) reconstruction is very slow for its characteristic of solving an optimization problem. Convolu- tional neural network can realize fast processing while achieving compa- rable results. While CS image recovery with high quality not only de- pends on good reconstruction algorithms, but also good measurements. In this paper, we propose an adaptive measurement network in which measurement is obtained by learning. The new network consists of a fully-connected layer and ReconNet. The fully-connected layer which has low-dimension output acts as measurement. We train the fully-connected layer and ReconNet simultaneously and obtain adaptive measurement. Because the adaptive measurement fits dataset better, in contrast with random Gaussian measurement matrix, under the same measuremen- t rate, it can extract the information of scene more efficiently and get better reconstruction results. Experiments show that the new network outperforms the original one.
Learning Autoencoded Radon Projections
Venue: arXiv cs.CV 2017
Year: 2017

Autoencoders have been recently used for encoding medical images. In this study, we design and validate a new framework for retrieving medical images by classifying Radon projections, compressed in the deepest layer of an autoencoder. As the autoencoder reduces the dimensionality, a multilayer perceptron (MLP) can be employed to classify the images. The integration of MLP promotes a rather shallow learning architecture which makes the training faster. We conducted a comparative study to examine the capabilities of autoencoders for different inputs such as raw images, Histogram of Oriented Gradients (HOG) and normalized Radon projections. Our framework is benchmarked on IRMA dataset containing $14,410$ x-ray images distributed across $57$ different classes. Experiments show an IRMA error of $313$ (equivalent to $\approx 82\%$ accuracy) outperforming state-of-the-art works on retrieval from IRMA dataset using autoencoders.
Skin Lesion Segmentation: U-Nets versus Clustering
Venue: arXiv cs.CV 2017
Year: 2017

Many automatic skin lesion diagnosis systems use segmentation as a preprocessing step to diagnose skin conditions because skin lesion shape, border irregularity, and size can influence the likelihood of malignancy. This paper presents, examines and compares two different approaches to skin lesion segmentation. The first approach uses U-Nets and introduces a histogram equalization based preprocessing step. The second approach is a C-Means clustering based approach that is much simpler to implement and faster to execute. The Jaccard Index between the algorithm output and hand segmented images by dermatologists is used to evaluate the proposed algorithms. While many recently proposed deep neural networks to segment skin lesions require a significant amount of computational power for training (i.e., computer with GPUs), the main objective of this paper is to present methods that can be used with only a CPU. This severely limits, for example, the number of training instances that can be presented to the U-Net. Comparing the two proposed algorithms, U-Nets achieved a significantly higher Jaccard Index compared to the clustering approach. Moreover, using the histogram equalization for preprocessing step significantly improved the U-Net segmentation results.
Normality of the Ehrenfeucht-Mycielski Sequence
Venue: arXiv cs.DM 2017
Year: 2017

We study the binary Ehrenfeucht Mycielski sequence seeking a balance between the number of occurrences of different binary strings. There have been numerous attempts to prove the balance conjecture of the sequence, which roughly states that 1 and 0 occur equally often in it. Our contribution is twofold. First, we study weaker forms of the conjecture proved in the past and lay out detailed proofs for many lemmas which were stated without proofs. Secondly, we extend the claim of balance to that of normality and prove a weaker form of simple normality to word length 2.
Sensor Fusion for Public Space Utilization Monitoring in a Smart City
Venue: arXiv cs.OH 2017
Year: 2017

Public space utilization is crucial for urban developers to understand how efficient a place is being occupied in order to improve existing or future infrastructures. In a smart cities approach, implementing public space monitoring with Internet-of-Things (IoT) sensors appear to be a viable solution. However, choice of sensors often is a challenging problem and often linked with scalability, coverage, energy consumption, accuracy, and privacy. To get the most from low cost sensor with aforementioned design in mind, we proposed data processing modules for capturing public space utilization with Renewable Wireless Sensor Network (RWSN) platform using pyroelectric infrared (PIR) and analog sound sensor. We first proposed a calibration process to remove false alarm of PIR sensor due to the impact of weather and environment. We then demonstrate how the sounds sensor can be processed to provide various insight of a public space. Lastly, we fused both sensors and study a particular public space utilization based on one month data to unveil its usage.
Celestial Walk: A Terminating Oblivious Walk for Convex Subdivisions
Venue: arXiv cs.DS 2017
Year: 2017

We present a new oblivious walking strategy for convex subdivisions. Our walk is faster than the straight walk and more generally applicable than the visibility walk. To prove termination of our walk we use a novel monotonically decreasing distance measure.
Computing by nowhere increasing complexity
Venue: arXiv cs.IT 2017
Year: 2017

A cellular automaton is presented whose governing rule is that the Kolmogorov complexity of a cell's neighborhood may not increase when the cell's present value is substituted for its future value. Using an approximation of this two-dimensional Kolmogorov complexity the underlying automaton is shown to be capable of simulating logic circuits. It is also shown to capture trianry logic described by a quandle, a non-associative algebraic structure. A similar automaton whose rule permits at times the increase of a cell's neighborhood complexity is shown to produce animated entities which can be used as information carriers akin to gliders in Conway's game of life.
Open Badges: A Low-Cost Toolkit for Measuring Team Communication and Dynamics
Venue: arXiv cs.HC 2017
Year: 2017

We present Open Badges, an open-source framework an toolkit for measuring and shaping face-to-face social interactions using either custom hardware devices or smart phones, and real-time web-based visualizations. Open Badges is a modular system that allows researchers to monitor and collect interaction data from people engaged in real-life social settings. In this paper we describe the technical aspects of the Open Badges project and the motivation for its creation.
Explicit MDS Codes with Complementary Duals
Venue: arXiv cs.IT 2017
Year: 2017

In 1964, Massey introduced a class of codes with complementary duals which are called Linear Complimentary Dual (LCD for short) codes. He showed that LCD codes have applications in communication system, side-channel attack (SCA) and so on. LCD codes have been extensively studied in literature. On the other hand, MDS codes form an optimal family of classical codes which have wide applications in both theory and practice. The main purpose of this paper is to give an explicit construction of several classes of LCD MDS codes, using tools from algebraic function fields. We exemplify this construction and obtain several classes of explicit LCD MDS codes for the odd characteristic case.
Quantitative Perspectives on Fifty Years of the Journal of the History of Biology
Venue: arXiv cs.DL 2017
Year: 2017

Journal of the History of Biology provides a fifty-year long record for examining the evolution of the history of biology as a scholarly discipline. In this paper, we present a new dataset and preliminary quantitative analysis of the thematic content of JHB from the perspectives of geography, organisms, and thematic fields. The geographic diversity of authors whose work appears in JHB has increased steadily since 1968, but the geographic coverage of the content of JHB articles remains strongly lopsided toward the United States, United Kingdom, and western Europe and has diversified much less dramatically over time. The taxonomic diversity of organisms discussed in JHB increased steadily between 1968 and the late 1990s but declined in later years, mirroring broader patterns of diversification previously reported in the biomedical research literature. Finally, we used a combination of topic modeling and nonlinear dimensionality reduction techniques to develop a model of multi-article fields within JHB. We found evidence for directional changes in the representation of fields on multiple scales. The diversity of JHB with regard to the representation of thematic fields has increased overall, with most of that diversification occurring in recent years. Drawing on the dataset generated in the course of this analysis, as well as web services in the emerging digital history and philosophy of science ecosystem, we have developed an interactive web platform for exploring the content of JHB, and we provide a brief overview of the platform in this article. As a whole, the data and analyses presented here provide a starting-place for further critical reflection on the evolution of the history of biology over the past half-century.
Resource Scheduling for Mixed Traffic Types with Scalable TTI in Dynamic TDD Systems
Venue: arXiv cs.NI 2017
Year: 2017

This paper analyses the performance benefits of a user-centric scheduling approach, exploiting the flexibility of both dynamic time division duplex (TDD) and a variable transmission time interval (TTI), where the downlink to uplink ratio and TTI duration can be adapted to the traffic load. The formulation of the joint optimisation problem takes into consideration the individual requirements of each single user in terms of sustainable latency and desired throughput, thus implementing a real user-centric scheduling approach. Moreover, the developed solution is evaluated in a scenario with mixed traffic types, mobile broadband (MBB) and mission critical communications (MCC), showing remarkable performance enhancement of the proposed scheme over baseline dynamic TDD schemes with a fixed TTI in terms of both achievable throughput of the MBB users and guaranteed latency for the MCC users.
Complexity of Edge Monitoring on Some Graph Classes
Venue: arXiv cs.DM 2017
Year: 2017

In this paper, we study the complexity of the edge monitoring problem. A vertex $v$ monitors an edge $e$ if both extremities together with $v$ form a triangle in the graph. Given a graph $G=(V,E)$ and a weight function on edges $c$ where $c(e)$ is the number of monitors that needs the edge $e$, the problem is to seek a minimum subset of monitors $S$ such that every edge $e$ in the graph is monitored by at least $c(e)$ vertices in $S$. In this paper, we study the edge monitoring problem on several graph classes such as complete graphs, block graphs, cographs, split graphs, interval graphs and planar graphs. We also generalize the problem by adding weights on vertices.
A User-Centric System for Verified Identities on the Bitcoin Blockchain
Venue: arXiv cs.CR 2017
Year: 2017

We present an identity management scheme built into the Bitcoin blockchain, allowing for identities that are as indelible as the blockchain itself. Moreover, we take advantage of Bitcoin's decentralized nature to facilitate a shared control between users and identity providers, allowing users to directly manage their own identities, fluidly coordinating identities from different providers, even as identity providers can revoke identities and impose controls.
Codes Endowed With the Rank Metric
Venue: arXiv cs.IT 2017
Year: 2017

We review the main results of the theory of rank-metric codes, with emphasis on their combinatorial properties. We study their duality theory and MacWilliams identities, comparing in particular rank-metric codes in vector and matrix representation. We then investigate the combinatorial structure of MRD codes and optimal anticodes in the rank metric, describing how they relate to each other.
Grasping Unknown Objects in Clutter by Superquadric Representation
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, a quick and efficient method is presented for grasping unknown objects in clutter. The grasping method relies on real-time superquadric (SQ) representation of partial view objects and incomplete object modelling, well suited for unknown symmetric objects in cluttered scenarios which is followed by optimized antipodal grasping. The incomplete object models are processed through a mirroring algorithm that assumes symmetry to first create an approximate complete model and then fit for SQ representation. The grasping algorithm is designed for maximum force balance and stability, taking advantage of the quick retrieval of dimension and surface curvature information from the SQ parameters. The pose of the SQs with respect to the direction of gravity is calculated and used together with the parameters of the SQs and specification of the gripper, to select the best direction of approach and contact points. The SQ fitting method has been tested on custom datasets containing objects in isolation as well as in clutter. The grasping algorithm is evaluated on a PR2 and real time results are presented. Initial results indicate that though the method is based on simplistic shape information, it outperforms other learning based grasping algorithms that also work in clutter in terms of time-efficiency and accuracy.
DiffuserCam: Lensless Single-exposure 3D Imaging
Venue: arXiv cs.CV 2017
Year: 2017

We demonstrate a compact and easy-to-build computational camera for single-shot 3D imaging. Our lensless system consists solely of a diffuser placed in front of a standard image sensor. Every point within the volumetric field-of-view projects a unique pseudorandom pattern of caustics on the sensor. By using a physical approximation and simple calibration scheme, we solve the large-scale inverse problem in a computationally efficient way. The caustic patterns enable compressed sensing, which exploits sparsity in the sample to solve for more 3D voxels than pixels on the 2D sensor. Our 3D voxel grid is chosen to match the experimentally measured two-point optical resolution across the field-of-view, resulting in 100 million voxels being reconstructed from a single 1.3 megapixel image. However, the effective resolution varies significantly with scene content. Because this effect is common to a wide range of computational cameras, we provide new theory for analyzing resolution in such systems.
Classical and Quantum Evaluation Codes at the Trace Roots
Venue: arXiv cs.IT 2017
Year: 2017

We introduce a new class of evaluation linear codes by evaluating polynomials at the roots of a suitable trace function. We give conditions for self-orthogonality of these codes and their subfield-subcodes with respect to the Hermitian inner product. They allow us to construct stabilizer quantum codes over several finite fields which substantially improve the codes in the literature and that are records at [http://www.codetables.de] for the binary case. Moreover, we obtain several classical linear codes over the field $\mathbb{F}_4$ which are records at [http://www.codetables.de].
A study of Thompson Sampling with Parameter h
Venue: arXiv cs.LG 2017
Year: 2017

Thompson Sampling algorithm is a well known Bayesian algorithm for solving stochastic multi-armed bandit. At each time step the algorithm chooses each arm with probability proportional to it being the current best arm. We modify the strategy by introducing a paramter h which alters the importance of the probability of an arm being the current best arm. We show that the optimality of Thompson sampling is robust to this perturbation within a range of parameter values for two arm bandits.
Learnable Explicit Density for Continuous Latent Space and Variational Inference
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we study two aspects of the variational autoencoder (VAE): the prior distribution over the latent variables and its corresponding posterior. First, we decompose the learning of VAEs into layerwise density estimation, and argue that having a flexible prior is beneficial to both sample generation and inference. Second, we analyze the family of inverse autoregressive flows (inverse AF) and show that with further improvement, inverse AF could be used as universal approximation to any complicated posterior. Our analysis results in a unified approach to parameterizing a VAE, without the need to restrict ourselves to use factorial Gaussians in the latent real space.