OpenRaiser/Intern-Atlas huggingface dataset:
Improving Named Entity Recognition for Chinese Social Media with Word Segmentation Representation Learning
Venue: arXiv cs.CL 2017
Year: 2017

Named entity recognition, and other information extraction tasks, frequently use linguistic features such as part of speech tags or chunkings. For languages where word boundaries are not readily identified in text, word segmentation is a key first step to generating features for an NER system. While using word boundary tags as features are helpful, the signals that aid in identifying these boundaries may provide richer information for an NER system. New state-of-the-art word segmentation systems use neural models to learn representations for predicting word boundaries. We show that these same representations, jointly trained with an NER system, yield significant improvements in NER for Chinese social media. In our experiments, jointly training NER and word segmentation with an LSTM-CRF model yields nearly 5% absolute improvement over previously published results.
Robotic Playing for Hierarchical Complex Skill Learning
Venue: arXiv cs.RO 2017
Year: 2017

In complex manipulation scenarios (e.g. tasks requiring complex interaction of two hands or in-hand manipulation), generalization is a hard problem. Current methods still either require a substantial amount of (supervised) training data and / or strong assumptions on both the environment and the task. In this paradigm, controllers solving these tasks tend to be complex. We propose a paradigm of maintaining simpler controllers solving the task in a small number of specific situations. In order to generalize to novel situations, the robot transforms the environment from novel situations into a situation where the solution of the task is already known. Our solution to this problem is to play with objects and use previously trained skills (basis skills). These skills can either be used for estimating or for changing the current state of the environment and are organized in skill hierarchies. The approach is evaluated in complex pick-and-place scenarios that involve complex manipulation. We further show that these skills can be learned by autonomous playing.
Optimization of Energy-Constrained Wireless Powered Communication Networks with Heterogeneous Nodes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study wireless networks where nodes have two energy sources, namely a battery and radio frequency (RF) energy harvesting circuitry. We formulate two optimization problems with different objective functions, namely maximizing the sum throughput and maximizing the minimum throughput, for enhanced fairness. Furthermore, we show the generality of the proposed system model through characterizing the conditions under which the two formulated optimization problems can be reduced to the corresponding problems of different known wireless networks, namely, conventional wireless networks (battery-powered) and wireless powered communications networks (WPCNs) with only RF energy harvesting nodes. In addition, we introduce WPCNs with two types of nodes, with and without RF energy harvesting capability, in which the nodes without RF energy harvesting are utilized to enhance the sum throughput, even beyond WPCNs with all energy harvesting nodes. We establish the convexity of all formulated problems which opens room for efficient solution using standard techniques. Our numerical results show that the two types of wireless networks, namely WPCNs with only RF energy harvesting nodes and conventional wireless networks, are considered, respectively, as lower and upper bounds on the performance of the generalized problem setting in terms of the maximum sum throughput and the maxmin throughput. Moreover, the results reveal new insights and throughput-fairness trade-offs unique to our new problem setting.
TruthDiscover: Resolving Object Conflicts on Massive Linked Data
Venue: arXiv cs.DB 2017
Year: 2017

Considerable effort has been made to increase the scale of Linked Data. However, because of the openness of the Semantic Web and the ease of extracting Linked Data from semi-structured sources (e.g., Wikipedia) and unstructured sources, many Linked Data sources often provide conflicting objects for a certain predicate of a real-world entity. Existing methods cannot be trivially extended to resolve conflicts in Linked Data because Linked Data has a scale-free property. In this demonstration, we present a novel system called TruthDiscover, to identify the truth in Linked Data with a scale-free property. First, TruthDiscover leverages the topological properties of the Source Belief Graph to estimate the priori beliefs of sources, which are utilized to smooth the trustworthiness of sources. Second, the Hidden Markov Random Field is utilized to model interdependencies among objects for estimating the trust values of objects accurately. TruthDiscover can visualize the process of resolving conflicts in Linked Data. Experiments results on four datasets show that TruthDiscover exhibits satisfactory accuracy when confronted with data having a scale-free property.
A linear algorithm for Brick Wang tiling
Venue: arXiv cs.DM 2017
Year: 2017

The Wang tiling is a classical problem in combinatorics. A major theoretical question is to find a (small) set of tiles which tiles the plane only aperiodically. In this case, resulting tilings are rather restrictive. On the other hand, Wang tiles are used as a tool to generate textures and patterns in computer graphics. In these applications, a set of tiles is normally chosen so that it tiles the plane or its sub-regions easily in many different ways. With computer graphics applications in mind, we introduce a class of such tileset, which we call sequentially permissive tilesets, and consider tiling problems with constrained boundary. We apply our methodology to a special set of Wang tiles, called Brick Wang tiles, introduced by Derouet-Jourdan et al. in 2015 to model wall patterns. We generalise their result by providing a linear algorithm to decide and solve the tiling problem for arbitrary planar regions with holes.
Projective cofactor decompositions of Boolean functions and the satisfiability problem
Venue: arXiv cs.CC 2017
Year: 2017

Given a CNF formula $F$, we present a new algorithm for deciding the satisfiability (SAT) of $F$ and computing all solutions of assignments. The algorithm is based on the concept of \emph{cofactors} known in the literature. This paper is a fallout of the previous work by authors on Boolean satisfiability \cite{sul1, sul2,sude}, however the algorithm is essentially independent of the orthogonal expansion concept over which previous papers were based. The algorithm selects a single concrete cofactor recursively by projecting the search space to the set which satisfies a CNF in the formula. This cofactor is called \emph{projective cofactor}. The advantage of such a computation is that it recursively decomposes the satisfiability problem into independent sub-problems at every selection of a projective cofactor. This leads to a parallel algorithm for deciding satisfiability and computing all solutions of a satisfiable formula.
Splines and Wavelets on Circulant Graphs
Venue: arXiv cs.DM 2017
Year: 2017

We present novel families of wavelets and associated filterbanks for the analysis and representation of functions defined on circulant graphs. In this work, we leverage the inherent vanishing moment property of the circulant graph Laplacian operator, and by extension, the e-graph Laplacian, which is established as a parameterization of the former with respect to the degree per node, for the design of vertex-localized and critically-sampled higher-order graph (e-)spline wavelet filterbanks, which can reproduce and annihilate classes of (exponential) polynomial signals on circulant graphs. In addition, we discuss similarities and analogies of the detected properties and resulting constructions with splines and spline wavelets in the Euclidean domain. Ultimately, we consider generalizations to arbitrary graphs in the form of graph approximations, with focus on graph product decompositions. In particular, we proceed to show how the use of graph products facilitates a multi-dimensional extension of the proposed constructions and properties.
Dynamic Modularity Approach to Adaptive Inner/Outer Loop Control of Robotic Systems
Venue: arXiv cs.SY 2017
Year: 2017

Modern applications of robotics typically involve a robot control system with an inner PI (proportional-integral) or PID (proportional-integral-derivative) control loop and an outer user-specified control loop. The existing outer loop controllers, however, do not take into consideration the dynamic effects of robots and their effectiveness relies on the ad hoc assumption that the inner PI or PID control loop is fast enough, and other torque-based control algorithms cannot be implemented in robotics with closed architecture. This paper investigates the adaptive control of robotic systems with an inner/outer loop structure, taking into full account the effects of the dynamics and the system uncertainties, and both the task-space control and joint-space control are considered. We propose a dynamic modularity approach to resolve this issue, and a class of adaptive outer loop control schemes is proposed and their role is to dynamically generate the joint velocity (or position) command for the low-level joint servoing loop. Without relying on the ad hoc assumption that the joint servoing is fast enough or the modification of the low-level joint controller structure, we rigorously show that the proposed outer loop controllers can ensure the stability and convergence of the closed-loop system. We also propose the outer loop versions of several standard joint-space direct/composite adaptive controllers for rigid or flexible-joint robots, and a promising conclusion may be that most torque-based adaptive controllers for robots can be designed to fit the inner/outer loop structure by using the new definition of the joint velocity (or position) command. Simulation results are provided to show the performance of various adaptive outer loop controllers, using a three-DOF (degree-of-freedom) manipulator, and experiment results using the UR10 robotic system are also presented.
Learning Dexterous Manipulation for a Soft Robotic Hand from Human Demonstration
Venue: arXiv cs.LG 2017
Year: 2017

Dexterous multi-fingered hands can accomplish fine manipulation behaviors that are infeasible with simple robotic grippers. However, sophisticated multi-fingered hands are often expensive and fragile. Low-cost soft hands offer an appealing alternative to more conventional devices, but present considerable challenges in sensing and actuation, making them difficult to apply to more complex manipulation tasks. In this paper, we describe an approach to learning from demonstration that can be used to train soft robotic hands to perform dexterous manipulation tasks. Our method uses object-centric demonstrations, where a human demonstrates the desired motion of manipulated objects with their own hands, and the robot autonomously learns to imitate these demonstrations using reinforcement learning. We propose a novel algorithm that allows us to blend and select a subset of the most feasible demonstrations to learn to imitate on the hardware, which we use with an extension of the guided policy search framework to use multiple demonstrations to learn generalizable neural network policies. We demonstrate our approach on the RBO Hand 2, with learned motor skills for turning a valve, manipulating an abacus, and grasping.
Weakly-Supervised Semantic Segmentation using Motion Cues
Venue: arXiv cs.CV 2017
Year: 2017

Fully convolutional neural networks (FCNNs) trained on a large number of images with strong pixel-level annotations have become the new state of the art for the semantic segmentation task. While there have been recent attempts to learn FCNNs from image-level weak annotations, they need additional constraints, such as the size of an object, to obtain reasonable performance. To address this issue, we present motion-CNN (M-CNN), a novel FCNN framework which incorporates motion cues and is learned from video-level weak annotations. Our learning scheme to train the network uses motion segments as soft constraints, thereby handling noisy motion information. When trained on weakly-annotated videos, our method outperforms the state-of-the-art EM-Adapt approach on the PASCAL VOC 2012 image segmentation benchmark. We also demonstrate that the performance of M-CNN learned with 150 weak video annotations is on par with state-of-the-art weakly-supervised methods trained with thousands of images. Finally, M-CNN substantially outperforms recent approaches in a related task of video co-localization on the YouTube-Objects dataset.
On Delay-Optimal Scheduling in Queueing Systems with Replications
Venue: arXiv cs.PF 2017
Year: 2017

In modern computer systems, jobs are divided into short tasks and executed in parallel. Empirical observations in practical systems suggest that the task service times are highly random and the job service time is bottlenecked by the slowest straggling task. One common solution for straggler mitigation is to replicate a task on multiple servers and wait for one replica of the task to finish early. The delay performance of replications depends heavily on the scheduling decisions of when to replicate, which servers to replicate on, and which job to serve first. So far, little is understood on how to optimize these scheduling decisions for minimizing the delay to complete the jobs. In this paper, we present a comprehensive study on delay-optimal scheduling of replications in both centralized and distributed multi-server systems. Low-complexity scheduling policies are designed and are proven to be delay-optimal or near delay-optimal in stochastic ordering among all causal and non-preemptive policies. These theoretical results are established for general system settings and delay metrics that allow for arbitrary arrival processes, arbitrary job sizes, arbitrary due times, and heterogeneous servers with data locality constraints. Novel sample-path tools are developed to prove these results.
Dynamics, Control, and Estimation for Aerial Robots Tethered by Cables or Bars
Venue: arXiv cs.RO 2017
Year: 2017

We consider the problem of controlling an aerial robot connected to the ground by a passive cable or a passive rigid link. We provide a thorough characterization of this nonlinear dynamical robotic system in terms of fundamental properties such as differential flatness, controllability, and observability. We prove that the robotic system is differentially flat with respect to two output pairs: elevation of the link and attitude of the vehicle; elevation of the link and longitudinal link force (e.g., cable tension, or bar compression). We show the design of an almost globally convergent nonlinear observer of the full state that resorts only to an onboard accelerometer and a gyroscope. We also design two almost globally convergent nonlinear controllers to track any sufficiently smooth time-varying trajectory of the two output pairs. Finally we numerically test the robustness of the proposed method in several far-from-nominal conditions: nonlinear cross-coupling effects, parameter deviations, measurements noise and non ideal actuators.
Approximate Personalized PageRank on Dynamic Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We propose and analyze two algorithms for maintaining approximate Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added or deleted. Our algorithms are natural dynamic versions of two known local variations of power iteration. One, Forward Push, propagates probability mass forwards along edges from a source node, while the other, Reverse Push, propagates local changes backwards along edges from a target. In both variations, we maintain an invariant between two vectors, and when an edge is updated, our algorithm first modifies the vectors to restore the invariant, then performs any needed local push operations to restore accuracy. For Reverse Push, we prove that for an arbitrary directed graph in a random edge model, or for an arbitrary undirected graph, given a uniformly random target node $t$, the cost to maintain a PPR vector to $t$ of additive error $\varepsilon$ as $k$ edges are updated is $O(k + \bar{d} / \varepsilon)$, where $\bar{d}$ is the average degree of the graph. This is $O(1)$ work per update, plus the cost of computing a reverse vector once on a static graph. For Forward Push, we show that on an arbitrary undirected graph, given a uniformly random start node $s$, the cost to maintain a PPR vector from $s$ of degree-normalized error $\varepsilon$ as $k$ edges are updated is $O(k + 1 / \varepsilon)$, which is again $O(1)$ per update plus the cost of computing a PPR vector once on a static graph.
Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements
Venue: arXiv cs.IT 2017
Year: 2017

We investigate recovery of nonnegative vectors from non-adaptive compressive measurements in the presence of noise of unknown power. In the absence of noise, existing results in the literature identify properties of the measurement that assure uniqueness in the non-negative orthant. By linking such uniqueness results to nullspace properties, we deduce uniform and robust compressed sensing guarantees for nonnegative least squares. No l1-regularization is required. As an important proof of principle, we establish that m x n random i.i.d. 0/1-valued Bernoulli matrices obey the required conditions with overwhelming probability provided that m=O(slog(n/s)). We achieve this by establishing the robust nullspace property for random 0/1-matrices - a novel result in its own right. Our analysis is motivated by applications in wireless network activity detection.
Identification via the Broadcast Channel
Venue: arXiv cs.IT 2017
Year: 2017

The identification (ID) capacity region of the two-receiver broadcast channel (BC) is shown to be the set of rate-pairs for which, for some distribution on the channel input, each receiver's ID rate does not exceed the mutual information between the channel input and the channel output that it observes. Moreover, the capacity region's interior is achieved by codes with deterministic encoders. The results are obtained under the average-error criterion, which requires that each receiver reliably identify its message whenever the message intended for the other receiver is drawn at random. They hold also for channels whose transmission capacity region is to-date unknown. Key to the proof is a new ID code construction for the single-user channel. Extensions to the BC with one-sided feedback and the three-receiver BC are also discussed: inner bounds on their ID capacity regions are obtained, and those are shown to be in some cases tight.
Continuous 3D Label Stereo Matching using Local Expansion Moves
Venue: arXiv cs.CV 2017
Year: 2017

We present an accurate stereo matching method using local expansion moves based on graph cuts. This new move-making scheme is used to efficiently infer per-pixel 3D plane labels on a pairwise Markov random field (MRF) that effectively combines recently proposed slanted patch matching and curvature regularization terms. The local expansion moves are presented as many alpha-expansions defined for small grid regions. The local expansion moves extend traditional expansion moves by two ways: localization and spatial propagation. By localization, we use different candidate alpha-labels according to the locations of local alpha-expansions. By spatial propagation, we design our local alpha-expansions to propagate currently assigned labels for nearby regions. With this localization and spatial propagation, our method can efficiently infer MRF models with a continuous label space using randomized search. Our method has several advantages over previous approaches that are based on fusion moves or belief propagation; it produces submodular moves deriving a subproblem optimality; it helps find good, smooth, piecewise linear disparity maps; it is suitable for parallelization; it can use cost-volume filtering techniques for accelerating the matching cost computations. Even using a simple pairwise MRF, our method is shown to have best performance in the Middlebury stereo benchmark V2 and V3.
Mathematical Harmony Analysis
Venue: arXiv cs.SD 2017
Year: 2017

Musical chords, harmonies or melodies in Just Intonation have note frequencies which are described by a base frequency multiplied by rational numbers. For any local section, these notes can be converted to some base frequency multiplied by whole positive numbers. The structure of the chord can be analysed mathematically by finding functions which are unchanged upon chord transposition. These functions are are denoted invariant, and are important for understanding the structure of harmony. Each chord described by whole numbers has a greatest common divisor, GCD, and a lowest common multiple, LCM. The ratio of these is denoted Complexity which is a positive whole number. The set of divisors of Complexity give a subset of a p limit tone lattice and have both a natural ordering and a multiplicative structure. The position and orientation of the original chord, on the ordered set or on the lattice, give rise to many other invariant functions including measures for otonality and utonality. Other invariant functions can be constructed from: ratios between note pairs, prime projections, weighted chords which incorporate loudness. Given a set of conditions described by invariant functions, algorithms can be developed to find all scales or chords meeting those conditions, allowing the classification of consonant harmonies up to specified limits.
Phoenix: A Self-Optimizing Chess Engine
Venue: arXiv cs.AI 2017
Year: 2017

Since the advent of computers, many tasks which required humans to spend a lot of time and energy have been trivialized by the computers' ability to perform repetitive tasks extremely quickly. Playing chess is one such task. It was one of the first games which was `solved' using AI. With the advent of deep learning, chess playing agents can surpass human ability with relative ease. However algorithms using deep learning must learn millions of parameters. This work looks at the game of chess through the lens of genetic algorithms. We train a genetic player from scratch using only a handful of learnable parameters. We use Multi-Niche Crowding to optimize positional Value Tables (PVTs) which are used extensively in chess engines to evaluate the goodness of a position. With a very simple setup and after only 1000 generations of evolution, the player reaches the level of an International Master.
Unsupervised Learning of Visual Representations by Solving Jigsaw Puzzles
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we study the problem of image representation learning without human annotation. By following the principles of self-supervision, we build a convolutional neural network (CNN) that can be trained to solve Jigsaw puzzles as a pretext task, which requires no manual labeling, and then later repurposed to solve object classification and detection. To maintain the compatibility across tasks we introduce the context-free network (CFN), a siamese-ennead CNN. The CFN takes image tiles as input and explicitly limits the receptive field (or context) of its early processing units to one tile at a time. We show that the CFN includes fewer parameters than AlexNet while preserving the same semantic learning capabilities. By training the CFN to solve Jigsaw puzzles, we learn both a feature mapping of object parts as well as their correct spatial arrangement. Our experimental evaluations show that the learned features capture semantically relevant content. Our proposed method for learning visual representations outperforms state of the art methods in several transfer learning benchmarks.