OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Polygon Clouds: Representation and Compression for VR/AR
Venue: arXiv cs.GR 2017
Year: 2017

We introduce the {\em polygon cloud}, also known as a polygon set or {\em soup}, as a compressible representation of 3D geometry (including its attributes, such as color texture) intermediate between polygonal meshes and point clouds. Dynamic or time-varying polygon clouds, like dynamic polygonal meshes and dynamic point clouds, can take advantage of temporal redundancy for compression, if certain challenges are addressed. In this paper, we propose methods for compressing both static and dynamic polygon clouds, specifically triangle clouds. We compare triangle clouds to both triangle meshes and point clouds in terms of compression, for live captured dynamic colored geometry. We find that triangle clouds can be compressed nearly as well as triangle meshes, while being far more robust to noise and other structures typically found in live captures, which violate the assumption of a smooth surface manifold, such as lines, points, and ragged boundaries. We also find that triangle clouds can be used to compress point clouds with significantly better performance than previously demonstrated point cloud compression methods. In particular, for intra-frame coding of geometry, our method improves upon octree-based intra-frame coding by a factor of 5-10 in bit rate. Inter-frame coding improves this by another factor of 2-5. Overall, our dynamic triangle cloud compression improves over the previous state-of-the-art in dynamic point cloud compression by 33\% or more.
Congestion Control for Network-Aware Telehaptic Communication
Venue: arXiv cs.NI 2017
Year: 2017

Telehaptic applications involve delay-sensitive multimedia communication between remote locations with distinct Quality of Service (QoS) requirements for different media components. These QoS constraints pose a variety of challenges, especially when the communication occurs over a shared network, with unknown and time-varying cross-traffic. In this work, we propose a transport layer congestion control protocol for telehaptic applications operating over shared networks, termed as dynamic packetization module (DPM). DPM is a lossless, network-aware protocol which tunes the telehaptic packetization rate based on the level of congestion in the network. To monitor the network congestion, we devise a novel network feedback module, which communicates the end-to-end delays encountered by the telehaptic packets to the respective transmitters with negligible overhead. Via extensive simulations, we show that DPM meets the QoS requirements of telehaptic applications over a wide range of network cross-traffic conditions. We also report qualitative results of a real-time telepottery experiment with several human subjects, which reveal that DPM preserves the quality of telehaptic activity even under heavily congested network scenarios. Finally, we compare the performance of DPM with several previously proposed telehaptic communication protocols and demonstrate that DPM outperforms these protocols.
Error bounds for approximations with deep ReLU networks
Venue: arXiv cs.LG 2017
Year: 2017

We study expressive power of shallow and deep neural networks with piece-wise linear activation functions. We establish new rigorous upper and lower bounds for the network complexity in the setting of approximations in Sobolev spaces. In particular, we prove that deep ReLU networks more efficiently approximate smooth functions than shallow networks. In the case of approximations of 1D Lipschitz functions we describe adaptive depth-6 network architectures more efficient than the standard shallow architecture.
Efficiency and Budget Balance in General Quasi-linear Domains
Venue: arXiv cs.GT 2017
Year: 2017

We study efficiency and budget balance for designing mechanisms in general quasi-linear domains. Green and Laffont (1979) proved that one cannot generically achieve both. We consider strategyproof budget-balanced mechanisms that are approximately efficient. For deterministic mechanisms, we show that a strategyproof and budget-balanced mechanism must have a sink agent whose valuation function is ignored in selecting an alternative, and she is compensated with the payments made by the other agents. We assume the valuations of the agents come from a bounded open interval. Using this result, we find a tight lower bound on the inefficiencies of strategyproof, budget-balanced mechanisms in this domain. The bound shows that the inefficiency asymptotically disappears when the number of agents is large---a result close in spirit to Green and Laffont (1979, Theorem 9.4). However, our results provide worst-case bounds and the best possible rate of convergence. Next, we consider minimizing any convex combination of inefficiency and budget imbalance. We show that if the valuations are unrestricted, no deterministic mechanism can do asymptotically better than minimizing inefficiency alone. Finally, we investigate randomized mechanisms and provide improved lower bounds on expected inefficiency. We give a tight lower bound for an interesting class of strategyproof, budget-balanced, randomized mechanisms. We also use an optimization-based approach---in the spirit of automated mechanism design---to provide a lower bound on the minimum achievable inefficiency of any randomized mechanism. Experiments with real data from two applications show that the inefficiency for a simple randomized mechanism is 5--100 times smaller than the worst case. This relative difference increases with the number of agents.
Validation of Twitter opinion trends with national polling aggregates: Hillary Clinton vs Donald Trump
Venue: arXiv cs.SI 2017
Year: 2017

Measuring and forecasting opinion trends from real-time social media is a long-standing goal of big-data analytics. Despite its importance, there has been no conclusive scientific evidence so far that social media activity can capture the opinion of the general population. Here we develop a method to infer the opinion of Twitter users regarding the candidates of the 2016 US Presidential Election by using a combination of statistical physics of complex networks and machine learning based on hashtags co-occurrence to develop an in-domain training set approaching 1 million tweets. We investigate the social networks formed by the interactions among millions of Twitter users and infer the support of each user to the presidential candidates. The resulting Twitter trends follow the New York Times National Polling Average, which represents an aggregate of hundreds of independent traditional polls, with remarkable accuracy. Moreover, the Twitter opinion trend precedes the aggregated NYT polls by 10 days, showing that Twitter can be an early signal of global opinion trends. Our analytics unleash the power of Twitter to uncover social trends from elections, brands to political movements, and at a fraction of the cost of national polls.
RedThreads: An Interface for Application-level Fault Detection/Correction through Adaptive Redundant Multithreading
Venue: arXiv cs.DC 2017
Year: 2017

In the presence of accelerated fault rates, which are projected to be the norm on future exascale systems, it will become increasingly difficult for high-performance computing (HPC) applications to accomplish useful computation. Due to the fault-oblivious nature of current HPC programming paradigms and execution environments, HPC applications are insufficiently equipped to deal with errors. We believe that HPC applications should be enabled with capabilities to actively search for and correct errors in their computations. The redundant multithreading (RMT) approach offers lightweight replicated execution streams of program instructions within the context of a single application process. However, the use of complete redundancy incurs significant overhead to the application performance. In this paper we present RedThreads, an interface that provides application-level fault detection and correction based on RMT, but applies the thread-level redundancy adaptively. We describe the RedThreads syntax and semantics, and the supporting compiler infrastructure and runtime system. Our approach enables application programmers to scope the extent of redundant computation. Additionally, the runtime system permits the use of RMT to be dynamically enabled, or disabled, based on the resiliency needs of the application and the state of the system. Our experimental results demonstrate how adaptive RMT exploits programmer insight and runtime inference to dynamically navigate the trade-off space between an application's resilience coverage and the associated performance overhead of redundant computation.
Utilizing High-level Visual Feature for Indoor Shopping Mall Navigation
Venue: arXiv cs.CV 2017
Year: 2017

Towards robust and convenient indoor shopping mall navigation, we propose a novel learning-based scheme to utilize the high-level visual information from the storefront images captured by personal devices of users. Specifically, we decompose the visual navigation problem into localization and map generation respectively. Given a storefront input image, a novel feature fusion scheme (denoted as FusionNet) is proposed by fusing the distinguishing DNN-based appearance feature and text feature for robust recognition of store brands, which serves for accurate localization. Regarding the map generation, we convert the user-captured indicator map of the shopping mall into a topological map by parsing the stores and their connectivity. Experimental results conducted on the real shopping malls demonstrate that the proposed system achieves robust localization and precise map generation, enabling accurate navigation.
Morphology Generation for Statistical Machine Translation using Deep Learning Techniques
Venue: arXiv cs.CL 2017
Year: 2017

Morphology in unbalanced languages remains a big challenge in the context of machine translation. In this paper, we propose to de-couple machine translation from morphology generation in order to better deal with the problem. We investigate the morphology simplification with a reasonable trade-off between expected gain and generation complexity. For the Chinese-Spanish task, optimum morphological simplification is in gender and number. For this purpose, we design a new classification architecture which, compared to other standard machine learning techniques, obtains the best results. This proposed neural-based architecture consists of several layers: an embedding, a convolutional followed by a recurrent neural network and, finally, ends with sigmoid and softmax layers. We obtain classification results over 98% accuracy in gender classification, over 93% in number classification, and an overall translation improvement of 0.7 METEOR.
Fully Character-Level Neural Machine Translation without Explicit Segmentation
Venue: arXiv cs.CL 2017
Year: 2017

Most existing machine translation systems operate at the level of words, relying on explicit segmentation to extract tokens. We introduce a neural machine translation (NMT) model that maps a source character sequence to a target character sequence without any segmentation. We employ a character-level convolutional network with max-pooling at the encoder to reduce the length of source representation, allowing the model to be trained at a speed comparable to subword-level models while capturing local regularities. Our character-to-character model outperforms a recently proposed baseline with a subword-level encoder on WMT'15 DE-EN and CS-EN, and gives comparable performance on FI-EN and RU-EN. We then demonstrate that it is possible to share a single character-level encoder across multiple languages by training a model on a many-to-one translation task. In this multilingual setting, the character-level encoder significantly outperforms the subword-level encoder on all the language pairs. We observe that on CS-EN, FI-EN and RU-EN, the quality of the multilingual character-level translation even surpasses the models specifically trained on that language pair alone, both in terms of BLEU score and human judgment.
Differential Inequalities in Multi-Agent Coordination and Opinion Dynamics Modeling
Venue: arXiv cs.SY 2017
Year: 2017

Distributed algorithms of multi-agent coordination have attracted substantial attention from the research community; the simplest and most thoroughly studied of them are consensus protocols in the form of differential or difference equations over general time-varying weighted graphs. These graphs are usually characterized algebraically by their associated Laplacian matrices. Network algorithms with similar algebraic graph theoretic structures, called being of Laplacian-type in this paper, also arise in other related multi-agent control problems, such as aggregation and containment control, target surrounding, distributed optimization and modeling of opinion evolution in social groups. In spite of their similarities, each of such algorithms has often been studied using separate mathematical techniques. In this paper, a novel approach is offered, allowing a unified and elegant way to examine many Laplacian-type algorithms for multi-agent coordination. This approach is based on the analysis of some differential or difference inequalities that have to be satisfied by the some "outputs" of the agents (e.g. the distances to the desired set in aggregation problems). Although such inequalities may have many unbounded solutions, under natural graphic connectivity conditions all their bounded solutions converge (and even reach consensus), entailing the convergence of the corresponding distributed algorithms. In the theory of differential equations the absence of bounded non-convergent solutions is referred to as the equation's dichotomy. In this paper, we establish the dichotomy criteria of Laplacian-type differential and difference inequalities and show that these criteria enable one to extend a number of recent results, concerned with Laplacian-type algorithms for multi-agent coordination and modeling opinion formation in social groups.
Computing All Distinct Squares in Linear Time for Integer Alphabets
Venue: arXiv cs.DS 2017
Year: 2017

Given a string on an integer alphabet, we present an algorithm that computes the set of all distinct squares belonging to this string in time linear to the string length. As an application, we show how to compute the tree topology of the minimal augmented suffix tree in linear time. Asides from that, we elaborate an algorithm computing the longest previous table in a succinct representation using compressed working space.
Fused DNN: A deep neural network fusion approach to fast and robust pedestrian detection
Venue: arXiv cs.CV 2017
Year: 2017

We propose a deep neural network fusion architecture for fast and robust pedestrian detection. The proposed network fusion architecture allows for parallel processing of multiple networks for speed. A single shot deep convolutional network is trained as a object detector to generate all possible pedestrian candidates of different sizes and occlusions. This network outputs a large variety of pedestrian candidates to cover the majority of ground-truth pedestrians while also introducing a large number of false positives. Next, multiple deep neural networks are used in parallel for further refinement of these pedestrian candidates. We introduce a soft-rejection based network fusion method to fuse the soft metrics from all networks together to generate the final confidence scores. Our method performs better than existing state-of-the-arts, especially when detecting small-size and occluded pedestrians. Furthermore, we propose a method for integrating pixel-wise semantic segmentation network into the network fusion architecture as a reinforcement to the pedestrian detector. The approach outperforms state-of-the-art methods on most protocols on Caltech Pedestrian dataset, with significant boosts on several protocols. It is also faster than all other methods.
Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-dimension
Venue: arXiv cs.CG 2017
Year: 2017

We consider the problem of finding a small hitting set in an {\it infinite} range space $\cF=(Q,\cR)$ of bounded VC-dimension. We show that, under reasonably general assumptions, the infinite dimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any $δ>0$, a set of size $O(s_{\cF}(z^*_\cF))$ that hits $(1-δ)$-fraction of $\cR$ (with respect to a given measure) in time proportional to $\log(\frac{1}δ)$, where $s_{\cF}(\frac{1}ε)$ is the size of the smallest $ε$-net the range space admits, and $z^*_{\cF}$ is the value of the {\it fractional} optimal solution. This {\it exponentially} improves upon previous results which achieve the same approximation guarantees with running time proportional to $\poly(\frac{1}δ)$. Our assumptions hold, for instance, in the case when the range space represents the {\it visibility} regions of a polygon in $\RR^2$, giving thus a deterministic polynomial time $O(\log z^*_{\cF})$-approximation algorithm for guarding $(1-δ)$-fraction of the area of any given simple polygon, with running time proportional to $\polylog(\frac{1}δ)$.
Improved approximation for two dimensional strip packing with polynomial bounded width
Venue: arXiv cs.DS 2017
Year: 2017

We study the well-known two-dimensional strip packing problem. Given is a set of rectangular axis-parallel items and a strip of width $W$ with infinite height. The objective is to find a packing of these items into the strip, which minimizes the packing height. Lately, it has been shown that the lower bound of $3/2$ of the absolute approximation ratio can be beaten when we allow a pseudo-polynomial running-time of type $(n W)^{f(1/\varepsilon)}$. If $W$ is polynomially bounded by the number of items, this is a polynomial running-time. We present a pseudo-polynomial algorithm with approximation ratio $4/3 +\varepsilon$ and running time $(n W)^{1/\varepsilon^{\mathcal{O}(2^{1/\varepsilon})}}$.
Forward Stochastic Reachability Analysis for Uncontrolled Linear Systems using Fourier Transforms
Venue: arXiv cs.SY 2017
Year: 2017

We propose a scalable method for forward stochastic reachability analysis for uncontrolled linear systems with affine disturbance. Our method uses Fourier transforms to efficiently compute the forward stochastic reach probability measure (density) and the forward stochastic reach set. This method is applicable to systems with bounded or unbounded disturbance sets. We also examine the convexity properties of the forward stochastic reach set and its probability density. Motivated by the problem of a robot attempting to capture a stochastically moving, non-adversarial target, we demonstrate our method on two simple examples. Where traditional approaches provide approximations, our method provides exact analytical expressions for the densities and probability of capture.
Joint CoMP-Cell Selection and Resource Allocation with Fronthaul-Constrained C-RAN
Venue: arXiv cs.IT 2017
Year: 2017

Cloud-based Radio Access Network (C-RAN) is a promising architecture for future cellular networks, in which Baseband Units (BBUs) are placed at a centralized location, with capacity-constrained fronthaul connected to multiple distributed Remote Radio Units (RRHs) that are far away from the BBUs. The centralization of signal processing enables the flexibility for coordinated multi-point transmission (CoMP) to meet high traffic demand of users. We investigate how to jointly optimize CoMP-cell selection and base station resource allocation so as to enhance the quality of service (QoS), subject to the fronthaul capacity constraint in orthogonal frequency-division multiple access (OFDMA) based C-RAN. The problem is proved to be NP-hard in this paper. To deal with the computational complexity, we derive a partial optimality condition as the foundation for designing a cell-selection algorithm. Besides, we provide a solution method of the optimum of the time-frequency resource allocation problem without loss of fairness on the QoS enhancement of all users. The simulations show good performance of the proposed algorithms for jointly optimizing the cell selection and resource allocation in a C-RAN, with respect to QoS.
Bsmooth: Learning from user feedback to disambiguate query terms in interactive data retrieval
Venue: arXiv cs.DB 2017
Year: 2017

There is great interest in supporting imprecise queries (e.g., keyword search or natural language queries) over databases today. To support such queries, the database system is typically required to disambiguate parts of the user-specified query against the database, using whatever resources are intrinsically available to it (the database schema, data values distributions, natural language models etc). Often, systems will also have a user-interaction log available, which can serve as an extrinsic resource to supplement their model based on their own intrinsic resources. This leads to a problem of how best to combine the system's prior ranking with insight derived from the user-interaction log. Statistical inference techniques such as maximum likelihood or Bayesian updates from a subjective prior turn out not to apply in a straightforward way due to possible noise from user search behavior and to encoding biases endemic to the system's models. In this paper, we address such learning problem in interactive data retrieval, with specific focus on type classification for user-specified query terms. We develop a novel Bayesian smoothing algorithm, Bsmooth, which is simple, fast, flexible and accurate. We analytically establish some desirable properties and show, through experiments against an independent benchmark, that the addition of such a learning layer performs much better than standard methods.
Local max-cut in smoothed polynomial time
Venue: arXiv cs.DS 2017
Year: 2017

In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass, but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem, for which no polynomial time method is known. In a breakthrough paper, Etscheid and Röglin proved that the smoothed complexity of local max-cut is quasi-polynomial, i.e., if arbitrary bounded weights are randomly perturbed, a local maximum can be found in $n^{O(\log n)}$ steps. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding local optima for max-cut is much easier than solving it.
An Efficient Uplink Multi-Connectivity Scheme for 5G mmWave Control Plane Applications
Venue: arXiv cs.NI 2017
Year: 2017

The millimeter wave (mmWave) frequencies offer the potential of orders of magnitude increases in capacity for next-generation cellular systems. However, links in mmWave networks are susceptible to blockage and may suffer from rapid variations in quality. Connectivity to multiple cells - at mmWave and/or traditional frequencies - is considered essential for robust communication. One of the challenges in supporting multi-connectivity in mmWaves is the requirement for the network to track the direction of each link in addition to its power and timing. To address this challenge, we implement a novel uplink measurement system that, with the joint help of a local coordinator operating in the legacy band, guarantees continuous monitoring of the channel propagation conditions and allows for the design of efficient control plane applications, including handover, beam tracking and initial access. We show that an uplink-based multi-connectivity approach enables less consuming, better performing, faster and more stable cell selection and scheduling decisions with respect to a traditional downlink-based standalone scheme. Moreover, we argue that the presented framework guarantees (i) efficient tracking of the user in the presence of the channel dynamics expected at mmWaves, and (ii) fast reaction to situations in which the primary propagation path is blocked or not available.