OpenRaiser/Intern-Atlas huggingface dataset:
Real-time Cooperative Communication for Automation over Wireless
Venue: arXiv cs.IT 2017
Year: 2017

High-performance industrial automation systems rely on tens of simultaneously active sensors and actuators and have stringent communication latency and reliability requirements. Current wireless technologies like WiFi, Bluetooth, and LTE are unable to meet these requirements, forcing the use of wired communication in industrial control systems. This paper introduces a wireless communication protocol that capitalizes on multiuser diversity and cooperative communication to achieve the ultra-reliability with a low-latency constraint. Our protocol is analyzed using the communication-theoretic delay-limited-capacity framework and compared to baseline schemes that primarily exploit frequency diversity. For a scenario inspired by an industrial printing application with thirty nodes in the control loop, 20B messages transmitted between pairs of nodes and a cycle time of $2$ ms, an idealized protocol can achieve a cycle failure probability (probability that any packet in a cycle is not successfully delivered) lower than $10^{-9}$ with nominal SNR below 5 dB in a 20MHz wide channel.
Anti-aliasing for fused filament deposition
Venue: arXiv cs.GR 2017
Year: 2017

Layered manufacturing inherently suffers from staircase defects along surfaces that are gently slopped with respect to the build direction. Reducing the slice thickness improves the situation but never resolves it completely as flat layers remain a poor approximation of the true surface in these regions. In addition, reducing the slice thickness largely increases the print time. In this work we focus on a simple yet effective technique to improve the print accuracy for layered manufacturing by filament deposition. Our method works with standard three-axis 3D filament printers (e.g. the typical, widely available 3D printers), using standard extrusion nozzles. It better reproduces the geometry of sloped surfaces without increasing the print time. Our key idea is to perform a local anti-aliasing, working at a sub-layer accuracy to produce slightly curved deposition paths and reduce approximation errors. This is inspired by Computer Graphics anti-aliasing techniques which consider sub-pixel precision to treat aliasing effects. We show that the necessary deviation in height compared to standard slicing is bounded by half the layer thickness. Therefore, the height changes remain small and plastic deposition remains reliable. We further split and order paths to minimize defects due to the extruder nozzle shape, avoiding any change to the existing hardware. We apply and analyze our approach on 3D printed examples, showing that our technique greatly improves surface accuracy and silhouette quality while keeping the print time nearly identical.
Uncertainty in Monotone Co-Design Problems
Venue: arXiv cs.RO 2017
Year: 2017

This work contributes to a compositional theory of "co-design" that allows to optimally design a robotic platform. In this framework, the user describes each subsystem as a monotone relation between "functionality" provided and "resources" required. These models can be easily composed to express the co-design constraints among different subsystems. The user then queries the model, to obtain the design with minimal resources usage, subject to a lower bound on the provided functionality. This paper concerns the introduction of uncertainty in the framework. Uncertainty has two roles: first, it allows to deal with limited knowledge of the models; second, it also can be used to generate consistent relaxations of a problem, as the computation requirements can be lowered, should the user accept some uncertainty in the answer.
Reactive Multi-Context Systems: Heterogeneous Reasoning in Dynamic Environments
Venue: arXiv cs.LO 2017
Year: 2017

Managed multi-context systems (mMCSs) allow for the integration of heterogeneous knowledge sources in a modular and very general way. They were, however, mainly designed for static scenarios and are therefore not well-suited for dynamic environments in which continuous reasoning over such heterogeneous knowledge with constantly arriving streams of data is necessary. In this paper, we introduce reactive multi-context systems (rMCSs), a framework for reactive reasoning in the presence of heterogeneous knowledge sources and data streams. We show that rMCSs are indeed well-suited for this purpose by illustrating how several typical problems arising in the context of stream reasoning can be handled using them, by showing how inconsistencies possibly occurring in the integration of multiple knowledge sources can be handled, and by arguing that the potential non-determinism of rMCSs can be avoided if needed using an alternative, more skeptical well-founded semantics instead with beneficial computational properties. We also investigate the computational complexity of various reasoning problems related to rMCSs. Finally, we discuss related work, and show that rMCSs do not only generalize mMCSs to dynamic settings, but also capture/extend relevant approaches w.r.t. dynamics in knowledge representation and stream reasoning.
Noisy Beam Alignment Techniques for Reciprocal MIMO Channels
Venue: arXiv cs.IT 2017
Year: 2017

Future multi-input multi-output (MIMO) wireless communications systems will use beamforming as a first-step towards realizing the capacity requirements necessitated by the exponential increase in data demands. The focus of this work is on beam alignment for time-division duplexing (TDD) systems, for which we propose a number of novel algorithms. These algorithms seek to obtain good estimates of the optimal beamformer/combiner pair (which are the dominant singular vectors of the channel matrix). They are motivated by the power method, an iterative algorithm to determine eigenvalues and eigenvectors through repeated matrix multiplication. In contrast to the basic power method which considers only the most recent iteration and assumes noiseless links, the proposed techniques consider information from all the previous iterations of the algorithm and combine them in different ways. The first technique (Sequential Least-Squares method) sequentially constructs a least-squares estimate of the channel matrix, which is then used to calculate the beamformer/combiner pair estimate. The second technique (Summed Power method) aims to mitigate the effect of noise by using a linear combination of the previously tried beams to calculate the next beam, providing improved performance in the low-SNR regime (typical for mmWave systems) with minimal complexity/feedback overhead. A third technique (Least-Squares Initialized Summed Power method) combines the good performance of the first technique at the high-SNR regime with the low-complexity advantage of the second technique by priming the summed power method with initial estimates from the sequential method.
Probabilistic Saliency Estimation
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we model the salient object detection problem under a probabilistic framework encoding the boundary connectivity saliency cue and smoothness constraints in an optimization problem. We show that this problem has a closed form global optimum which estimates the salient object. We further show that along with the probabilistic framework, the proposed method also enjoys a wide range of interpretations, i.e. graph cut, diffusion maps and one-class classification. With an analysis according to these interpretations, we also find that our proposed method provides approximations to the global optimum to another criterion that integrates local/global contrast and large area saliency cues. The proposed approach achieves mostly leading performance compared to the state-of-the-art algorithms over a large set of salient object detection datasets including around 17k images for several evaluation metrics. Furthermore, the computational complexity of the proposed method is favorable/comparable to many state-of-the-art techniques.
A Cubic-Time 2-Approximation Algorithm for rSPR Distance
Venue: arXiv cs.DS 2017
Year: 2017

Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose. The problem of computing the rSPR distance of two given trees has many applications but is unfortunately NP-hard. The previously best approximation algorithm for rSPR distance achieves a ratio of 2.5 and it was open whether a better approximation algorithm for rSPR distance exists. In this paper, we answer this question in the affirmative by presenting a cubic-time approximation algorithm for rSPR distance that achieves a ratio of 2. Our algorithm is based on the new notion of key and a number of new structural lemmas. The algorithm is fairly simple and the proof of its correctness is intuitively understandable albeit complicated.
Network learning via multi-agent inverse transportation problems
Venue: arXiv cs.MA 2017
Year: 2017

Despite the ubiquity of transportation data, methods to infer the state parameters of a network either ignore sensitivity of route decisions, require route enumeration for parameterizing descriptive models of route selection, or require complex bilevel models of route assignment behavior. These limitations prevent modelers from fully exploiting ubiquitous data in monitoring transportation networks. Inverse optimization methods that capture network route choice behavior can address this gap, but they are designed to take observations of the same model to learn the parameters of that model, which is statistically inefficient (e.g. requires estimating population route and link flows). New inverse optimization models and supporting algorithms are proposed to learn the parameters of heterogeneous travelers' route behavior to infer shared network state parameters (e.g. link capacity dual prices). The inferred values are consistent with observations of each agent's optimization behavior. We prove that the method can obtain unique dual prices for a network shared by these agents in polynomial time. Four experiments are conducted. The first one, conducted on a 4-node network, verifies the methodology to obtain heterogeneous link cost parameters even when multinomial or mixed logit models would not be meaningfully estimated. The second is a parameter recovery test on the Nguyen-Dupuis network that shows that unique latent link capacity dual prices can be inferred using the proposed method. The third test on the same network demonstrates how a monitoring system in an online learning environment can be designed using this method. The last test demonstrates this learning on real data obtained from a freeway network in Queens, New York, using only real-time Google Maps queries.
Even Good Bots Fight: The Case of Wikipedia
Venue: arXiv cs.SI 2017
Year: 2017

In recent years, there has been a huge increase in the number of bots online, varying from Web crawlers for search engines, to chatbots for online customer service, spambots on social media, and content-editing bots in online collaboration communities. The online world has turned into an ecosystem of bots. However, our knowledge of how these automated agents are interacting with each other is rather poor. Bots are predictable automatons that do not have the capacity for emotions, meaning-making, creativity, and sociality and it is hence natural to expect interactions between bots to be relatively predictable and uneventful. In this article, we analyze the interactions between bots that edit articles on Wikipedia. We track the extent to which bots undid each other's edits over the period 2001-2010, model how pairs of bots interact over time, and identify different types of interaction trajectories. We find that, although Wikipedia bots are intended to support the encyclopedia, they often undo each other's edits and these sterile "fights" may sometimes continue for years. Unlike humans on Wikipedia, bots' interactions tend to occur over longer periods of time and to be more reciprocated. Yet, just like humans, bots in different cultural environments may behave differently. Our research suggests that even relatively "dumb" bots may give rise to complex interactions, and this carries important implications for Artificial Intelligence research. Understanding what affects bot-bot interactions is crucial for managing social media well, providing adequate cyber-security, and designing well functioning autonomous vehicles.
An overview of gradient descent optimization algorithms
Venue: arXiv cs.LG 2017
Year: 2017

Gradient descent optimization algorithms, while increasingly popular, are often used as black-box optimizers, as practical explanations of their strengths and weaknesses are hard to come by. This article aims to provide the reader with intuitions with regard to the behaviour of different algorithms that will allow her to put them to use. In the course of this overview, we look at different variants of gradient descent, summarize challenges, introduce the most common optimization algorithms, review architectures in a parallel and distributed setting, and investigate additional strategies for optimizing gradient descent.
Distant Supervision for Relation Extraction beyond the Sentence Boundary
Venue: arXiv cs.CL 2017
Year: 2017

The growing demand for structured knowledge has led to great interest in relation extraction, especially in cases with limited supervision. However, existing distance supervision approaches only extract relations expressed in single sentences. In general, cross-sentence relation extraction is under-explored, even in the supervised-learning setting. In this paper, we propose the first approach for applying distant supervision to cross- sentence relation extraction. At the core of our approach is a graph representation that can incorporate both standard dependencies and discourse relations, thus providing a unifying way to model relations within and across sentences. We extract features from multiple paths in this graph, increasing accuracy and robustness when confronted with linguistic variation and analysis error. Experiments on an important extraction task for precision medicine show that our approach can learn an accurate cross-sentence extractor, using only a small existing knowledge base and unlabeled text from biomedical research articles. Compared to the existing distant supervision paradigm, our approach extracted twice as many relations at similar precision, thus demonstrating the prevalence of cross-sentence relations and the promise of our approach.
Variants of the Entropy Power Inequality
Venue: arXiv cs.IT 2017
Year: 2017

An extension of the entropy power inequality to the form $N_r^α(X+Y) \geq N_r^α(X) + N_r^α(Y)$ with arbitrary independent summands $X$ and $Y$ in $\mathbb{R}^n$ is obtained for the Rényi entropy and powers $α\geq (r+1)/2$.
Low Complexity Multiply Accumulate Unit for Weight-Sharing Convolutional Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

Convolutional Neural Networks (CNNs) are one of the most successful deep machine learning technologies for processing image, voice and video data. CNNs require large amounts of processing capacity and memory, which can exceed the resources of low power mobile and embedded systems. Several designs for hardware accelerators have been proposed for CNNs which typically contain large numbers of Multiply Accumulate (MAC) units. One approach to reducing data sizes and memory traffic in CNN accelerators is "weight sharing", where the full range of values in a trained CNN are put in bins and the bin index is stored instead of the original weight value. In this paper we propose a novel MAC circuit that exploits binning in weight-sharing CNNs. Rather than computing the MAC directly we instead count the frequency of each weight and place it in a bin. We then compute the accumulated value in a subsequent multiply phase. This allows hardware multipliers in the MAC circuit to be replaced with adders and selection logic. Experiments show that for the same clock speed our approach results in fewer gates, smaller logic, and reduced power.
Select-Additive Learning: Improving Generalization in Multimodal Sentiment Analysis
Venue: arXiv cs.CL 2017
Year: 2017

Multimodal sentiment analysis is drawing an increasing amount of attention these days. It enables mining of opinions in video reviews which are now available aplenty on online platforms. However, multimodal sentiment analysis has only a few high-quality data sets annotated for training machine learning algorithms. These limited resources restrict the generalizability of models, where, for example, the unique characteristics of a few speakers (e.g., wearing glasses) may become a confounding factor for the sentiment classification task. In this paper, we propose a Select-Additive Learning (SAL) procedure that improves the generalizability of trained neural networks for multimodal sentiment analysis. In our experiments, we show that our SAL approach improves prediction accuracy significantly in all three modalities (verbal, acoustic, visual), as well as in their fusion. Our results show that SAL, even when trained on one dataset, achieves good generalization across two new test datasets.
Converting Basic D3 Charts into Reusable Style Templates
Venue: arXiv cs.HC 2017
Year: 2017

We present a technique for converting a basic D3 chart into a reusable style template. Then, given a new data source we can apply the style template to generate a chart that depicts the new data, but in the style of the template. To construct the style template we first deconstruct the input D3 chart to recover its underlying structure: the data, the marks and the mappings that describe how the marks encode the data. We then rank the perceptual effectiveness of the deconstructed mappings. To apply the resulting style template to a new data source we first obtain importance ranks for each new data field. We then adjust the template mappings to depict the source data by matching the most important data fields to the most perceptually effective mappings. We show how the style templates can be applied to source data in the form of either a data table or another D3 chart. While our implementation focuses on generating templates for basic chart types (e.g. variants of bar charts, line charts, dot plots, scatterplots, etc.), these are the most commonly used chart types today. Users can easily find such basic D3 charts on the Web, turn them into templates, and immediately see how their own data would look in the visual style (e.g. colors, shapes, fonts, etc.) of the templates. We demonstrate the effectiveness of our approach by applying a diverse set of style templates to a variety of source datasets.
Better than Counting Seconds: Identifying Fallers among Healthy Elderly using Fusion of Accelerometer Features and Dual-Task Timed Up and Go
Venue: arXiv cs.CY 2017
Year: 2017

Devices and sensors for identification of fallers can be used to implement actions to prevent falls and to allow the elderly to live an independent life while reducing the long-term care costs. In this study we aimed to investigate the accuracy of Timed Up and Go test, for fallers' identification, using fusion of features extracted from accelerometer data. Single and dual tasks TUG (manual and cognitive) were performed by a final sample (94% power) of 36 community dwelling healthy older persons (18 fallers paired with 18 non-fallers) while they wear a single triaxial accelerometer at waist with sampling rate of 200Hz. The segmentation of the TUG different trials and its comparative analysis allows to better discriminate fallers from non-fallers, while conventional functional tests fail to do so. In addition, we show that the fusion of features improve the discrimination power, achieving AUC of 0.84 (Sensitivity=Specificity=0.83, 95% CI 0.62-0.91), and demonstrating the clinical relevance of the study. We concluded that features extracted from segmented TUG trials acquired with dual tasks has potential to improve performance when identifying fallers via accelerometer sensors, which can improve TUG accuracy for clinical and epidemiological applications.
Online Learning of Combinatorial Objects via Extended Formulation
Venue: arXiv cs.LG 2017
Year: 2017

The standard techniques for online learning of combinatorial objects perform multiplicative updates followed by projections into the convex hull of all the objects. However, this methodology can be expensive if the convex hull contains many facets. For example, the convex hull of $n$-symbol Huffman trees is known to have exponentially many facets (Maurras et al., 2010). We get around this difficulty by exploiting extended formulations (Kaibel, 2011), which encode the polytope of combinatorial objects in a higher dimensional "extended" space with only polynomially many facets. We develop a general framework for converting extended formulations into efficient online algorithms with good relative loss bounds. We present applications of our framework to online learning of Huffman trees and permutations. The regret bounds of the resulting algorithms are within a factor of $O(\sqrt{\log(n)})$ of the state-of-the-art specialized algorithms for permutations, and depending on the loss regimes, improve on or match the state-of-the-art for Huffman trees. Our method is general and can be applied to other combinatorial objects.
Multilinear Grammar: Ranks and Interpretations
Venue: arXiv cs.CL 2017
Year: 2017

Multilinear Grammar provides a framework for integrating the many different syntagmatic structures of language into a coherent semiotically based Rank Interpretation Architecture, with default linear grammars at each rank. The architecture defines a Sui Generis Condition on ranks, from discourse through utterance and phrasal structures to the word, with its sub-ranks of morphology and phonology. Each rank has unique structures and its own semantic-pragmatic and prosodic-phonetic interpretation models. Default computational models for each rank are proposed, based on a Procedural Plausibility Condition: incremental processing in linear time with finite working memory. We suggest that the Rank Interpretation Architecture and its multilinear properties provide systematic design features of human languages, contrasting with unordered lists of key properties or single structural properties at one rank, such as recursion, which have previously been been put forward as language design features. The framework provides a realistic background for the gradual development of complexity in the phylogeny and ontogeny of language, and clarifies a range of challenges for the evaluation of realistic linguistic theories and applications. The empirical objective of the paper is to demonstrate unique multilinear properties at each rank and thereby motivate the Multilinear Grammar and Rank Interpretation Architecture framework as a coherent approach to capturing the complexity of human languages in the simplest possible way.