OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical b-Matching
Venue: arXiv cs.DS 2019
Year: 2019

A matching of a graph is a subset of edges no two of which share a common vertex, and a maximum matching is a matching of maximum cardinality. In a $b$-matching every vertex $v$ has an associated bound $b_v$, and a maximum $b$-matching is a maximum set of edges, such that every vertex $v$ appears in at most $b_v$ of them. We study an extension of this problem, termed {\em Hierarchical b-Matching}. In this extension, the vertices are arranged in a hierarchical manner. At the first level the vertices are partitioned into disjoint subsets, with a given bound for each subset. At the second level the set of these subsets is again partitioned into disjoint subsets, with a given bound for each subset, and so on. In an {\em Hierarchical b-matching} we look for a maximum set of edges, that will obey all bounds (that is, no vertex $v$ participates in more than $b_v$ edges, then all the vertices in one subset do not participate in more that that subset's bound of edges, and so on hierarchically). We propose a polynomial-time algorithm for this new problem, that works for any number of levels of this hierarchical structure.
Surface2Volume: Surface Segmentation Conforming Assemblable Volumetric Partition
Venue: arXiv cs.GR 2019
Year: 2019

Users frequently seek to fabricate objects whose outer surfaces consist of regions with different surface attributes, such as color or material. Manufacturing such objects in a single piece is often challenging or even impossible. The alternative is to partition them into single-attribute volumetric parts that can be fabricated separately and then assembled to form the target object. Facilitating this approach requires partitioning the input model into parts that conform to the surface segmentation and that can be moved apart with no collisions. We propose Surface2Volume, a partition algorithm capable of producing such assemblable parts, each of which is affiliated with a single attribute, the outer surface of whose assembly conforms to the input surface geometry and segmentation. In computing the partition we strictly enforce conformity with surface segmentation and assemblability, and optimize for ease of fabrication by minimizing part count, promoting part simplicity, and simplifying assembly sequencing. We note that computing the desired partition requires solving for three types of variables: per-part assembly trajectories, partition topology, i.e. the connectivity of the interface surfaces separating the different parts, and the geometry, or location, of these interfaces. We efficiently produce the desired partitions by addressing one type of variables at a time: first computing the assembly trajectories, then determining interface topology, and finally computing interface locations that allow parts assemblability. We algorithmically identify inputs that necessitate sequential assembly, and partition these inputs gradually by computing and disassembling a subset of assemblable parts at a time. We demonstrate our method....
CPM-sensitive AUC for CTR prediction
Venue: arXiv cs.LG 2019
Year: 2019

The prediction of click-through rate (CTR) is crucial for industrial applications, such as online advertising. AUC is a commonly used evaluation indicator for CTR models. For advertising platforms, online performance is generally evaluated by CPM. However, in practice, AUC often improves in offline evaluation, but online CPM does not. As a result, a huge waste of precious online traffic and human costs has been caused. This is because there is a gap between offline AUC and online CPM. AUC can only reflect the order on CTR, but it does not reflect the order of CTR*Bid. Moreover, the bids of different advertisements are different, so the loss of income caused by different reverse-order pair is also different. For this reason, we propose the CPM-sensitive AUC (csAUC) to solve all these problems. We also give the csAUC calculation method based on dynamic programming. It can fully support the calculation of csAUC on large-scale data in real-world applications.
Sequential modeling of Sessions using Recurrent Neural Networks for Skip Prediction
Venue: arXiv cs.IR 2019
Year: 2019

Recommender systems play an essential role in music streaming services, prominently in the form of personalized playlists. Exploring the user interactions within these listening sessions can be beneficial to understanding the user preferences in the context of a single session. In the 'Spotify Sequential Skip Prediction Challenge', WSDM, and Spotify are challenging people to understand the way users sequentially interact with music. We describe our solution approach in this paper and also state proposals for further improvements to the model. The proposed model initially generates a fixed vector representation of the session, and this additional information is incorporated into an Encoder-Decoder style architecture. This method achieved the seventh position in the competition, with a mean average accuracy of 0.604 on the test set. The solution code is available at https://github.com/sainathadapa/spotify-sequential-skip-prediction.
Network Investment Game with Wardrop Followers
Venue: arXiv cs.GT 2019
Year: 2019

We study a two-sided network investment game consisting of two sets of players, called providers and users. The game is set in two stages. In the first stage, providers aim to maximize their profit by investing in bandwidth of cloud computing services. The investments of the providers yield a set of usable services for the users. In the second stage, each user wants to process a task and therefore selects a bundle of services so as to minimize the total processing time. We assume the total processing time to be separable over the chosen services and the processing time of each service to depend on the utilization of the service and the installed bandwidth. We provide insights on how competition between providers affects the total costs of the users and show that every game on a series-parallel graph can be reduced to an equivalent single edge game when analyzing the set of subgame perfect Nash equilibria.
Latent Variable Algorithms for Multimodal Learning and Sensor Fusion
Venue: arXiv cs.LG 2019
Year: 2019

Multimodal learning has been lacking principled ways of combining information from different modalities and learning a low-dimensional manifold of meaningful representations. We study multimodal learning and sensor fusion from a latent variable perspective. We first present a regularized recurrent attention filter for sensor fusion. This algorithm can dynamically combine information from different types of sensors in a sequential decision making task. Each sensor is bonded with a modular neural network to maximize utility of its own information. A gating modular neural network dynamically generates a set of mixing weights for outputs from sensor networks by balancing utility of all sensors' information. We design a co-learning mechanism to encourage co-adaption and independent learning of each sensor at the same time, and propose a regularization based co-learning method. In the second part, we focus on recovering the manifold of latent representation. We propose a co-learning approach using probabilistic graphical model which imposes a structural prior on the generative model: multimodal variational RNN (MVRNN) model, and derive a variational lower bound for its objective functions. In the third part, we extend the siamese structure to sensor fusion for robust acoustic event detection. We perform experiments to investigate the latent representations that are extracted; works will be done in the following months. Our experiments show that the recurrent attention filter can dynamically combine different sensor inputs according to the information carried in the inputs. We consider MVRNN can identify latent representations that are useful for many downstream tasks such as speech synthesis, activity recognition, and control and planning. Both algorithms are general frameworks which can be applied to other tasks where different types of sensors are jointly used for decision making.
Chunkflow: Distributed Hybrid Cloud Processing of Large 3D Images by Convolutional Nets
Venue: arXiv cs.DC 2019
Year: 2019

It is now common to process volumetric biomedical images using 3D Convolutional Networks (ConvNets). This can be challenging for the teravoxel and even petavoxel images that are being acquired today by light or electron microscopy. Here we introduce chunkflow, a software framework for distributing ConvNet processing over local and cloud GPUs and CPUs. The image volume is divided into overlapping chunks, each chunk is processed by a ConvNet, and the results are blended together to yield the output image. The frontend submits ConvNet tasks to a cloud queue. The tasks are executed by local and cloud GPUs and CPUs. Thanks to the fault-tolerant architecture of Chunkflow, cost can be greatly reduced by utilizing cheap unstable cloud instances. Chunkflow currently supports PyTorch for GPUs and PZnet for CPUs. To illustrate its usage, a large 3D brain image from serial section electron microscopy was processed by a 3D ConvNet with a U-Net style architecture. Chunkflow provides some chunk operations for general use, and the operations can be composed flexibly in a command line interface.
Fine-Grained Named Entity Recognition using ELMo and Wikidata
Venue: arXiv cs.IR 2019
Year: 2019

Fine-grained Named Entity Recognition is a task whereby we detect and classify entity mentions to a large set of types. These types can span diverse domains such as finance, healthcare, and politics. We observe that when the type set spans several domains the accuracy of the entity detection becomes a limitation for supervised learning models. The primary reason being the lack of datasets where entity boundaries are properly annotated, whilst covering a large spectrum of entity types. Furthermore, many named entity systems suffer when considering the categorization of fine grained entity types. Our work attempts to address these issues, in part, by combining state-of-the-art deep learning models (ELMo) with an expansive knowledge base (Wikidata). Using our framework, we cross-validate our model on the 112 fine-grained entity types based on the hierarchy given from the Wiki(gold) dataset.
A formalization of forcing and the unprovability of the continuum hypothesis
Venue: arXiv cs.LO 2019
Year: 2019

We describe a formalization of forcing using Boolean-valued models in the Lean 3 theorem prover, including the fundamental theorem of forcing and a deep embedding of first-order logic with a Boolean-valued soundness theorem. As an application of our framework, we specialize our construction to the Boolean algebra of regular opens of the Cantor space $2^{ω_2 \times ω}$ and formally verify the failure of the continuum hypothesis in the resulting model.
Energy-Efficient Mobile-Edge Computation Offloading over Multiple Fading Blocks
Venue: arXiv cs.IT 2019
Year: 2019

By allowing a mobile device to offload computation-intensive tasks to a base station, mobile edge computing (MEC) is a promising solution for saving the mobile device's energy. In real applications, the offloading may span multiple fading blocks. In this paper, we investigate energy-efficient offloading over multiple fading blocks with random channel gains. An optimization problem is formulated, which optimizes the amount of data for offloading to minimize the total expected energy consumption of the mobile device. Although the formulated optimization problem is non-convex, we prove that the objective function of the problem is piecewise convex, and accordingly develop an optimal solution for the problem. Numerical results verify the correctness of our findings and the effectiveness of our proposed method.
Throughput Maximization in Two-hop DF Multiple-Relay Network with Simultaneous Wireless Information and Power Transfer
Venue: arXiv cs.IT 2019
Year: 2019

This paper investigates the end-to-end throughput maximization problem for a two-hop multiple-relay network, with relays powered by simultaneous wireless information and power transfer (SWIPT) technique. Nonlinearity of energy harvester at every relay node is taken into account and two models for approximating the nonlinearity are adopted: logistic model and linear cut-off model. Decode-and-forward (DF) is implemented, and time switching (TS) mode and power splitting (PS) mode are considered. Optimization problems are formulated for TS mode and PS mode under logistic model and linear cut-off model, respectively. End-to-end throughput is aimed to be maximized by optimizing the transmit power and bandwidth on every source-relay-destination link, and PS ratio and/or TS ratio on every relay node. Although the formulated optimization problems are all non-convex. Through a series of analysis and transformation, and with the aid of bi-level optimization and monotonic optimization, etc., we find the global optimal solution of every formulated optimization problem. In some case, a simple yet optimal solution of the formulated problem is also derived. Numerical results verify the effectiveness of our proposed methods.
Detecting Machine-Translated Paragraphs by Matching Similar Words
Venue: arXiv cs.CL 2019
Year: 2019

Machine-translated text plays an important role in modern life by smoothing communication from various communities using different languages. However, unnatural translation may lead to misunderstanding, a detector is thus needed to avoid the unfortunate mistakes. While a previous method measured the naturalness of continuous words using a N-gram language model, another method matched noncontinuous words across sentences but this method ignores such words in an individual sentence. We have developed a method matching similar words throughout the paragraph and estimating the paragraph-level coherence, that can identify machine-translated text. Experiment evaluates on 2000 English human-generated and 2000 English machine-translated paragraphs from German showing that the coherence-based method achieves high performance (accuracy = 87.0%; equal error rate = 13.0%). It is efficiently better than previous methods (best accuracy = 72.4%; equal error rate = 29.7%). Similar experiments on Dutch and Japanese obtain 89.2% and 97.9% accuracy, respectively. The results demonstrate the persistence of the proposed method in various languages with different resource levels.
Towards Combining On-Off-Policy Methods for Real-World Applications
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we point out a fundamental property of the objective in reinforcement learning, with which we can reformulate the policy gradient objective into a perceptron-like loss function, removing the need to distinguish between on and off policy training. Namely, we posit that it is sufficient to only update a policy $π$ for cases that satisfy the condition $A(\fracπμ-1)\leq0$, where $A$ is the advantage, and $μ$ is another policy. Furthermore, we show via theoretic derivation that a perceptron-like loss function matches the clipped surrogate objective for PPO. With our new formulation, the policies $π$ and $μ$ can be arbitrarily apart in theory, effectively enabling off-policy training. To examine our derivations, we can combine the on-policy PPO clipped surrogate (which we show to be equivalent with one instance of the new reformation) with the off-policy IMPALA method. We first verify the combined method on the OpenAI Gym pendulum toy problem. Next, we use our method to train a quadrotor position controller in a simulator. Our trained policy is efficient and lightweight enough to perform in a low cost micro-controller at a minimum update rate of 500 Hz. For the quadrotor, we show two experiments to verify our method and demonstrate performance: 1) hovering at a fixed position, and 2) tracking along a specific trajectory. In preliminary trials, we are also able to apply the method to a real-world quadrotor.
Super-Resolved Image Perceptual Quality Improvement via Multi-Feature Discriminators
Venue: arXiv cs.CV 2019
Year: 2019

Generative adversarial network (GAN) for image super-resolution (SR) has attracted enormous interests in recent years. However, the GAN-based SR methods only use image discriminator to distinguish SR images and high-resolution (HR) images. Image discriminator fails to discriminate images accurately since image features cannot be fully expressed. In this paper, we design a new GAN-based SR framework GAN-IMC which includes generator, image discriminator, morphological component discriminator and color discriminator. The combination of multiple feature discriminators improves the accuracy of image discrimination. Adversarial training between the generator and multi-feature discriminators forces SR images to converge with HR images in terms of data and features distribution. Moreover, in some cases, feature enhancement of salient regions is also worth considering. GAN-IMC is further optimized by weighted content loss (GAN-IMCW), which effectively restores and enhances salient regions in SR images. The effectiveness and robustness of our method are confirmed by extensive experiments on public datasets. Compared with state-of-the-art methods, the proposed method not only achieves competitive Perceptual Index (PI) and Natural Image Quality Evaluator (NIQE) values but also obtains pleasant visual perception in image edge, texture, color and salient regions.
A General Framework for Edited Video and Raw Video Summarization
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we build a general summarization framework for both of edited video and raw video summarization. Overall, our work can be divided into three folds: 1) Four models are designed to capture the properties of video summaries, i.e., containing important people and objects (importance), representative to the video content (representativeness), no similar key-shots (diversity) and smoothness of the storyline (storyness). Specifically, these models are applicable to both edited videos and raw videos. 2) A comprehensive score function is built with the weighted combination of the aforementioned four models. Note that the weights of the four models in the score function, denoted as property-weight, are learned in a supervised manner. Besides, the property-weights are learned for edited videos and raw videos, respectively. 3) The training set is constructed with both edited videos and raw videos in order to make up the lack of training data. Particularly, each training video is equipped with a pair of mixing-coefficients which can reduce the structure mess in the training set caused by the rough mixture. We test our framework on three datasets, including edited videos, short raw videos and long raw videos. Experimental results have verified the effectiveness of the proposed framework.
Joint Compressed Sensing and Manipulation of Wireless Emissions with Intelligent Surfaces
Venue: arXiv cs.ET 2019
Year: 2019

Programmable, intelligent surfaces can manipulate electromagnetic waves impinging upon them, producing arbitrarily shaped reflection, refraction and diffraction, to the benefit of wireless users. Moreover, in their recent form of HyperSurfaces, they have acquired inter-networking capabilities, enabling the Internet of Material Properties with immense potential in wireless communications. However, as with any system with inputs and outputs, accurate sensing of the impinging wave attributes is imperative for programming HyperSurfaces to obtain a required response. Related solutions include field nano-sensors embedded within HyperSurfaces to perform minute measurements over the area of the HyperSurface, as well as external sensing systems. The present work proposes a sensing system that can operate without such additional hardware. The novel scheme programs the HyperSurface to perform compressed sensing of the impinging wave via simple one-antenna power measurements. The HyperSurface can jointly be programmed for both wave sensing and wave manipulation duties at the same time. Evaluation via simulations validates the concept and highlight its promising potential.
A Large-scale Varying-view RGB-D Action Dataset for Arbitrary-view Human Action Recognition
Venue: arXiv cs.CV 2019
Year: 2019

Current researches of action recognition mainly focus on single-view and multi-view recognition, which can hardly satisfies the requirements of human-robot interaction (HRI) applications to recognize actions from arbitrary views. The lack of datasets also sets up barriers. To provide data for arbitrary-view action recognition, we newly collect a large-scale RGB-D action dataset for arbitrary-view action analysis, including RGB videos, depth and skeleton sequences. The dataset includes action samples captured in 8 fixed viewpoints and varying-view sequences which covers the entire 360 degree view angles. In total, 118 persons are invited to act 40 action categories, and 25,600 video samples are collected. Our dataset involves more participants, more viewpoints and a large number of samples. More importantly, it is the first dataset containing the entire 360 degree varying-view sequences. The dataset provides sufficient data for multi-view, cross-view and arbitrary-view action analysis. Besides, we propose a View-guided Skeleton CNN (VS-CNN) to tackle the problem of arbitrary-view action recognition. Experiment results show that the VS-CNN achieves superior performance.
Layer Dynamics of Linearised Neural Nets
Venue: arXiv cs.LG 2019
Year: 2019

Despite the phenomenal success of deep learning in recent years, there remains a gap in understanding the fundamental mechanics of neural nets. More research is focussed on handcrafting complex and larger networks, and the design decisions are often ad-hoc and based on intuition. Some recent research has aimed to demystify the learning dynamics in neural nets by attempting to build a theory from first principles, such as characterising the non-linear dynamics of specialised \textit{linear} deep neural nets (such as orthogonal networks). In this work, we expand and derive properties of learning dynamics respected by general multi-layer linear neural nets. Although an over-parameterisation of a single layer linear network, linear multi-layer neural nets offer interesting insights that explain how learning dynamics proceed in small pockets of the data space. We show in particular that multiple layers in linear nets grow at approximately the same rate, and there are distinct phases of learning with markedly different layer growth. We then apply a linearisation process to a general RelU neural net and show how nonlinearity breaks down the growth symmetry observed in liner neural nets. Overall, our work can be viewed as an initial step in building a theory for understanding the effect of layer design on the learning dynamics from first principles.
Faster Algorithms for All Pairs Non-decreasing Paths Problem
Venue: arXiv cs.DS 2019
Year: 2019

In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time $\tilde{O}(n^{\frac{3 + ω}{2}}) = \tilde{O}(n^{2.686})$. Here $n$ is the number of vertices, and $ω< 2.373$ is the exponent of time complexity of fast matrix multiplication [Williams 2012, Le Gall 2014]. This matches the current best upper bound for $(\max, \min)$-matrix product [Duan, Pettie 2009] which is reducible to APNP. Thus, further improvement for APNP will imply a faster algorithm for $(\max, \min)$-matrix product. The previous best upper bound for APNP on weighted digraphs was $\tilde{O}(n^{\frac{1}{2}(3 + \frac{3 - ω}{ω+ 1} + ω)}) = \tilde{O}(n^{2.78})$ [Duan, Gu, Zhang 2018]. We also show an $\tilde{O}(n^2)$ time algorithm for APNP in undirected graphs which also reaches optimal within logarithmic factors.