OpenRaiser/Intern-Atlas huggingface dataset:
Min-Max Design of Feedback Quantizers for Netorwked Control Systems
Venue: arXiv cs.SY 2017
Year: 2017

In a networked control system, quantization is inevitable to transmit control and measurement signals. While uniform quantizers are often used in practical systems, the overloading, which is due to the limitation on the number of bits in the quantizer, may significantly degrade the control performance. In this paper, we design an overloading-free feedback quantizer based on a Delta-Sigma modulator,composed of an error feedback filter and a static quantizer. To guarantee no-overloading in the quantizer, we impose an $l_{\infty}$ norm constraint on the feedback signal in the quantizer. Then, for a prescribed $l_{\infty}$ norm constraint on the error at the system output induced by the quantizer, we design the error feedback filter that requires the minimum number of bits that achieves the constraint. Next, for a fixed number of bits for the quantizer, we investigate the achievable minimum $l_{\infty}$ norm of the error at the system output with an overloading-free quantizer. Numerical examples are provided to validate our analysis and synthesis.
ZigZag: A new approach to adaptive online learning
Venue: arXiv cs.LG 2017
Year: 2017

We develop a novel family of algorithms for the online learning setting with regret against any data sequence bounded by the empirical Rademacher complexity of that sequence. To develop a general theory of when this type of adaptive regret bound is achievable we establish a connection to the theory of decoupling inequalities for martingales in Banach spaces. When the hypothesis class is a set of linear functions bounded in some norm, such a regret bound is achievable if and only if the norm satisfies certain decoupling inequalities for martingales. Donald Burkholder's celebrated geometric characterization of decoupling inequalities (1984) states that such an inequality holds if and only if there exists a special function called a Burkholder function satisfying certain restricted concavity properties. Our online learning algorithms are efficient in terms of queries to this function. We realize our general theory by giving novel efficient algorithms for classes including lp norms, Schatten p-norms, group norms, and reproducing kernel Hilbert spaces. The empirical Rademacher complexity regret bound implies --- when used in the i.i.d. setting --- a data-dependent complexity bound for excess risk after online-to-batch conversion. To showcase the power of the empirical Rademacher complexity regret bound, we derive improved rates for a supervised learning generalization of the online learning with low rank experts task and for the online matrix prediction task. In addition to obtaining tight data-dependent regret bounds, our algorithms enjoy improved efficiency over previous techniques based on Rademacher complexity, automatically work in the infinite horizon setting, and are scale-free. To obtain such adaptive methods, we introduce novel machinery, and the resulting algorithms are not based on the standard tools of online convex optimization.
Denoising a Point Cloud for Surface Reconstruction
Venue: arXiv cs.GR 2017
Year: 2017

Surface reconstruction from an unorganized point cloud is an important problem due to its widespread applications. White noise, possibly clustered outliers, and noisy perturbation may be generated when a point cloud is sampled from a surface. Most existing methods handle limited amount of noise. We develop a method to denoise a point cloud so that the users can run their surface reconstruction codes or perform other analyses afterwards. Our experiments demonstrate that our method is computationally efficient and it has significantly better noise handling ability than several existing surface reconstruction codes.
Traffic Minimizing Caching and Latent Variable Distributions of Order Statistics
Venue: arXiv cs.NI 2017
Year: 2017

Given a statistical model for the request frequencies and sizes of data objects in a caching system, we derive the probability density of the size of the file that accounts for the largest amount of data traffic. This is equivalent to finding the required size of the cache for a caching placement that maximizes the expected byte hit ratio for given file size and popularity distributions. The file that maximizes the expected byte hit ratio is the file for which the product of its size and popularity is the highest -- thus, it is the file that incurs the greatest load on the network. We generalize this theoretical problem to cover factors and addends of arbitrary order statistics for given parent distributions. Further, we study the asymptotic behavior of these distributions. We give several factor and addend densities of widely-used distributions, and verify our results by extensive computer simulations.
Blind Demixing and Deconvolution at Near-Optimal Rate
Venue: arXiv cs.IT 2017
Year: 2017

We consider simultaneous blind deconvolution of r source signals from their noisy superposition, a problem also referred to blind demixing and deconvolution. This signal processing problem occurs in the context of the Internet of Things where a massive number of sensors sporadically communicate only short messages over unknown channels. We show that robust recovery of message and channel vectors can be achieved via convex optimization when random linear encoding using i.i.d. complex Gaussian matrices is used at the devices and the number of required measurements at the receiver scales with the degrees of freedom of the overall estimation problem. Since the scaling is linear in r our result significantly improves over recent works.
Room for improvement in automatic image description: an error analysis
Venue: arXiv cs.CL 2017
Year: 2017

In recent years we have seen rapid and significant progress in automatic image description but what are the open problems in this area? Most work has been evaluated using text-based similarity metrics, which only indicate that there have been improvements, without explaining what has improved. In this paper, we present a detailed error analysis of the descriptions generated by a state-of-the-art attention-based model. Our analysis operates on two levels: first we check the descriptions for accuracy, and then we categorize the types of errors we observe in the inaccurate descriptions. We find only 20% of the descriptions are free from errors, and surprisingly that 26% are unrelated to the image. Finally, we manually correct the most frequently occurring error types (e.g. gender identification) to estimate the performance reward for addressing these errors, observing gains of 0.2--1 BLEU point per type.
How Much Spectrum is Too Much in Millimeter Wave Wireless Access
Venue: arXiv cs.IT 2017
Year: 2017

A great increase in wireless access rates might be attainable by using the large amount of spectrum available in the millimeter wave (mmWave, 30 - 300 GHz) band. However, due to higher propagation losses inherent in these frequencies, to use wider bandwidth for transmission at ranges beyond 100 meters or in non-line-of-sight (NLOS) settings may be ineffective or even counterproductive when the penalty for estimating the channel is taken into account. In this work we quantify the maximum beneficial bandwidth for mmWave transmission in some typical deployment scenarios which use pilot-based channel estimation and assume a minimum mean square error (MMSE) channel estimator at the receiver. We find that for an I.I.D. block fading model with coherence time $T_c$ and coherence bandwidth $B_c$, for transmitters and receivers equipped with a single antenna, the optimal (rate-maximizing) signal-to-noise-ratio is a constant that only depends on the product $B_cT_c$, which measures the channel coherence and equals the average number of orthogonal symbols per each independent channel coefficient. That is, for fixed channel coherence, the optimal bandwidth scales linearly with the received signal power. Under some typical deployment scenarios with both transmit and receive side beamforming, 1 GHz bandwidth can be too much.
Model Predictive Control of Voltage Source Converter in a HVDC System
Venue: arXiv cs.SY 2017
Year: 2017

Model Predictive Control (MPC) method is a class of advanced control techniques most widely applied in industry. The major advantages of the MPC are its straightforward procedure which can be applied for both linear and nonlinear system. This paper proposes the use of MPC for voltage source converter (VSC) in a high voltage direct current (HVDC) system. A MPC controller is modeled based on the state-space model of a single VSC-HVDC station including the dynamics of the main ac grid. A full scale nonlinear switching model of point-to-point connected VSC-based HVDC system is developed in Matlab/Simulink association with SimPower system to demonstrate the application of the proposed controller.
FastVentricle: Cardiac Segmentation with ENet
Venue: arXiv cs.CV 2017
Year: 2017

Cardiac Magnetic Resonance (CMR) imaging is commonly used to assess cardiac structure and function. One disadvantage of CMR is that post-processing of exams is tedious. Without automation, precise assessment of cardiac function via CMR typically requires an annotator to spend tens of minutes per case manually contouring ventricular structures. Automatic contouring can lower the required time per patient by generating contour suggestions that can be lightly modified by the annotator. Fully convolutional networks (FCNs), a variant of convolutional neural networks, have been used to rapidly advance the state-of-the-art in automated segmentation, which makes FCNs a natural choice for ventricular segmentation. However, FCNs are limited by their computational cost, which increases the monetary cost and degrades the user experience of production systems. To combat this shortcoming, we have developed the FastVentricle architecture, an FCN architecture for ventricular segmentation based on the recently developed ENet architecture. FastVentricle is 4x faster and runs with 6x less memory than the previous state-of-the-art ventricular segmentation architecture while still maintaining excellent clinical accuracy.
Belief State Planning for Autonomously Navigating Urban Intersections
Venue: arXiv cs.RO 2017
Year: 2017

Urban intersections represent a complex environment for autonomous vehicles with many sources of uncertainty. The vehicle must plan in a stochastic environment with potentially rapid changes in driver behavior. Providing an efficient strategy to navigate through urban intersections is a difficult task. This paper frames the problem of navigating unsignalized intersections as a partially observable Markov decision process (POMDP) and solves it using a Monte Carlo sampling method. Empirical results in simulation show that the resulting policy outperforms a threshold-based heuristic strategy on several relevant metrics that measure both safety and efficiency.
Incremental learning of high-level concepts by imitation
Venue: arXiv cs.AI 2017
Year: 2017

Nowadays, robots become a companion in everyday life. To be well-accepted by humans, robots should efficiently understand meanings of their partners' motions and body language, and respond accordingly. Learning concepts by imitation brings them this ability in a user-friendly way. This paper presents a fast and robust model for Incremental Learning of Concepts by Imitation (ILoCI). In ILoCI, observed multimodal spatio-temporal demonstrations are incrementally abstracted and generalized based on both their perceptual and functional similarities during the imitation. In this method, perceptually similar demonstrations are abstracted by a dynamic model of mirror neuron system. An incremental method is proposed to learn their functional similarities through a limited number of interactions with the teacher. Learning all concepts together by the proposed memory rehearsal enables robot to utilize the common structural relations among concepts which not only expedites the learning process especially at the initial stages, but also improves the generalization ability and the robustness against discrepancies between observed demonstrations. Performance of ILoCI is assessed using standard LASA handwriting benchmark data set. The results show efficiency of ILoCI in concept acquisition, recognition and generation in addition to its robustness against variability in demonstrations.
Control of Asynchronous Imitation Dynamics on Networks
Venue: arXiv cs.GT 2017
Year: 2017

Imitation is widely observed in populations of decision-making agents. Using our recent convergence results for asynchronous imitation dynamics on networks, we consider how such networks can be efficiently driven to a desired equilibrium state by offering payoff incentives for using a certain strategy, either uniformly or targeted to individuals. In particular, if for each available strategy, agents playing that strategy receive maximum payoff when their neighbors play that same strategy, we show that providing incentives to agents in a network that is at equilibrium will result in convergence to a unique new equilibrium. For the case when a uniform incentive can be offered to all agents, this result allows the computation of the optimal incentive using a binary search algorithm. When incentives can be targeted to individual agents, we propose an algorithm to select which agents should be chosen based on iteratively maximizing a ratio of the number of agents who adopt the desired strategy to the payoff incentive required to get those agents to do so. Simulations demonstrate that the proposed algorithm computes near-optimal targeted payoff incentives for a range of networks and payoff distributions in coordination games.
Optimizing Differentiable Relaxations of Coreference Evaluation Metrics
Venue: arXiv cs.CL 2017
Year: 2017

Coreference evaluation metrics are hard to optimize directly as they are non-differentiable functions, not easily decomposable into elementary decisions. Consequently, most approaches optimize objectives only indirectly related to the end goal, resulting in suboptimal performance. Instead, we propose a differentiable relaxation that lends itself to gradient-based optimisation, thus bypassing the need for reinforcement learning or heuristic modification of cross-entropy. We show that by modifying the training objective of a competitive neural coreference system, we obtain a substantial gain in performance. This suggests that our approach can be regarded as a viable alternative to using reinforcement learning or more computationally expensive imitation learning.
Lean From Thy Neighbor: Stochastic & Adversarial Bandits in a Network
Venue: arXiv cs.LG 2017
Year: 2017

An individual's decisions are often guided by those of his or her peers, i.e., neighbors in a social network. Presumably, being privy to the experiences of others aids in learning and decision making, but how much advantage does an individual gain by observing her neighbors? Such problems make appearances in sociology and economics and, in this paper, we present a novel model to capture such decision-making processes and appeal to the classical multi-armed bandit framework to analyze it. Each individual, in addition to her own actions, can observe the actions and rewards obtained by her neighbors, and can use all of this information in order to minimize her own regret. We provide algorithms for this setting, both for stochastic and adversarial bandits, and show that their regret smoothly interpolates between the regret in the classical bandit setting and that of the full-information setting as a function of the neighbors' exploration. In the stochastic setting the additional information must simply be incorporated into the usual estimation of the rewards, while in the adversarial setting this is attained by constructing a new unbiased estimator for the rewards and appropriately bounding the amount of additional information provided by the neighbors. These algorithms are optimal up to log factors; despite the fact that the agents act independently and selfishly, this implies that it is an approximate Nash equilibria for all agents to use our algorithms. Further, we show via empirical simulations that our algorithms, often significantly, outperform existing algorithms that one could apply to this setting.
Additive Spanners and Distance Oracles in Quadratic Time
Venue: arXiv cs.DS 2017
Year: 2017

Let $G$ be an unweighted, undirected graph. An additive $k$-spanner of $G$ is a subgraph $H$ that approximates all distances between pairs of nodes up to an additive error of $+k$, that is, it satisfies $d_H(u,v) \le d_G(u,v)+k$ for all nodes $u,v$, where $d$ is the shortest path distance. We give a deterministic algorithm that constructs an additive $O\!\left(1\right)$-spanner with $O\!\left(n^{4/3}\right)$ edges in $O\!\left(n^2\right)$ time. This should be compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010] giving an additive $6$-spanner with $O\!\left(n^{4/3}\log^3 n\right)$ edges in expected time $O\!\left(n^2\log^2 n\right)$. An $(α,β)$-approximate distance oracle for $G$ is a data structure that supports the following distance queries between pairs of nodes in $G$. Given two nodes $u$, $v$ it can in constant time compute a distance estimate $\tilde{d}$ that satisfies $d \le \tilde{d} \le αd + β$ where $d$ is the distance between $u$ and $v$ in $G$. Sommer [ICALP 2016] gave a randomized Monte Carlo $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\text{poly} \log n\right)$ in expected time $O\!\left(n^2\text{poly} \log n\right)$. As an application of the additive $O(1)$-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\right)$ in time $O\!\left(n^2\right)$. This also implies an algorithm that in $O\!\left(n^2\right)$ gives approximate distance for all pairs of nodes in $G$ improving on the $O\!\left(n^2 \log n\right)$ algorithm by Baswana and Kavitha [SICOMP 2010].
Neural Machine Translation Model with a Large Vocabulary Selected by Branching Entropy
Venue: arXiv cs.CL 2017
Year: 2017

Neural machine translation (NMT), a new approach to machine translation, has achieved promising results comparable to those of traditional approaches such as statistical machine translation (SMT). Despite its recent success, NMT cannot handle a larger vocabulary because the training complexity and decoding complexity proportionally increase with the number of target words. This problem becomes even more serious when translating patent documents, which contain many technical terms that are observed infrequently. In this paper, we propose to select phrases that contain out-of-vocabulary words using the statistical approach of branching entropy. This allows the proposed NMT system to be applied to a translation task of any language pair without any language-specific knowledge about technical term identification. The selected phrases are then replaced with tokens during training and post-translated by the phrase translation table of SMT. Evaluation on Japanese-to-Chinese, Chinese-to-Japanese, Japanese-to-English and English-to-Japanese patent sentence translation proved the effectiveness of phrases selected with branching entropy, where the proposed NMT model achieves a substantial improvement over a baseline NMT model without our proposed technique. Moreover, the number of translation errors of under-translation by the baseline NMT model without our proposed technique reduces to around half by the proposed NMT model.
Translation of Patent Sentences with a Large Vocabulary of Technical Terms Using Neural Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

Neural machine translation (NMT), a new approach to machine translation, has achieved promising results comparable to those of traditional approaches such as statistical machine translation (SMT). Despite its recent success, NMT cannot handle a larger vocabulary because training complexity and decoding complexity proportionally increase with the number of target words. This problem becomes even more serious when translating patent documents, which contain many technical terms that are observed infrequently. In NMTs, words that are out of vocabulary are represented by a single unknown token. In this paper, we propose a method that enables NMT to translate patent sentences comprising a large vocabulary of technical terms. We train an NMT system on bilingual data wherein technical terms are replaced with technical term tokens; this allows it to translate most of the source sentences except technical terms. Further, we use it as a decoder to translate source sentences with technical term tokens and replace the tokens with technical term translations using SMT. We also use it to rerank the 1,000-best SMT translations on the basis of the average of the SMT score and that of the NMT rescoring of the translated sentences with technical term tokens. Our experiments on Japanese-Chinese patent sentences show that the proposed NMT system achieves a substantial improvement of up to 3.1 BLEU points and 2.3 RIBES points over traditional SMT systems and an improvement of approximately 0.6 BLEU points and 0.8 RIBES points over an equivalent NMT system without our proposed technique.
NEXT: A Neural Network Framework for Next POI Recommendation
Venue: arXiv cs.IR 2017
Year: 2017

The task of next POI recommendation has been studied extensively in recent years. However, developing an unified recommendation framework to incorporate multiple factors associated with both POIs and users remains challenging, because of the heterogeneity nature of these information. Further, effective mechanisms to handle cold-start and endow the system with interpretability are also difficult topics. Inspired by the recent success of neural networks in many areas, in this paper, we present a simple but effective neural network framework for next POI recommendation, named NEXT. NEXT is an unified framework to learn the hidden intent regarding user's next move, by incorporating different factors in an unified manner. Specifically, in NEXT, we incorporate meta-data information and two kinds of temporal contexts (i.e., time interval and visit time). To leverage sequential relations and geographical influence, we propose to adopt DeepWalk, a network representation learning technique, to encode such knowledge. We evaluate the effectiveness of NEXT against state-of-the-art alternatives and neural networks based solutions. Experimental results over three publicly available datasets demonstrate that NEXT significantly outperforms baselines in real-time next POI recommendation. Further experiments demonstrate the superiority of NEXT in handling cold-start. More importantly, we show that NEXT provides meaningful explanation of the dimensions in hidden intent space.