OpenRaiser/Intern-Atlas huggingface dataset:
Online Sensor Hallucination via Knowledge Distillation for Multimodal Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

We deal with the problem of information fusion driven satellite image/scene classification and propose a generic hallucination architecture considering that all the available sensor information are present during training while some of the image modalities may be absent while testing. It is well-known that different sensors are capable of capturing complementary information for a given geographical area and a classification module incorporating information from all the sources are expected to produce an improved performance as compared to considering only a subset of the modalities. However, the classical classifier systems inherently require all the features used to train the module to be present for the test instances as well, which may not always be possible for typical remote sensing applications (say, disaster management). As a remedy, we provide a robust solution in terms of a hallucination module that can approximate the missing modalities from the available ones during the decision-making stage. In order to ensure better knowledge transfer during modality hallucination, we explicitly incorporate concepts of knowledge distillation for the purpose of exploring the privileged (side) information in our framework and subsequently introduce an intuitive modular training approach. The proposed network is evaluated extensively on a large-scale corpus of PAN-MS image pairs (scene recognition) as well as on a benchmark hyperspectral image dataset (image classification) where we follow different experimental scenarios and find that the proposed hallucination based module indeed is capable of capturing the multi-source information, albeit the explicit absence of some of the sensor information, and aid in improved scene characterization.
Efficient Convolutional Neural Network for FMCW Radar Based Hand Gesture Recognition
Venue: arXiv cs.HC 2019
Year: 2019

FMCW radar could detect object's range, speed and Angleof-Arrival, advantages are robust to bad weather, good range resolution, and good speed resolution. In this paper, we consider the FMCW radar as a novel interacting interface on laptop. We merge sequences of object's range, speed, azimuth information into single input, then feed to a convolution neural network to learn spatial and temporal patterns. Our model achieved 96% accuracy on test set and real-time test.
One-Exact Approximate Pareto Sets
Venue: arXiv cs.DS 2019
Year: 2019

Papadimitriou and Yannakakis show that the polynomial-time solvability of a certain singleobjective problem determines the class of multiobjective optimization problems that admit a polynomial-time computable $(1+\varepsilon, \dots , 1+\varepsilon)$-approximate Pareto set (also called an $\varepsilon$-Pareto set). Similarly, in this article, we characterize the class of problems having a polynomial-time computable approximate $\varepsilon$-Pareto set that is exact in one objective by the efficient solvability of an appropriate singleobjective problem. This class includes important problems such as multiobjective shortest path and spanning tree, and the approximation guarantee we provide is, in general, best possible. Furthermore, for biobjective problems from this class, we provide an algorithm that computes a one-exact $\varepsilon$-Pareto set of cardinality at most twice the cardinality of a smallest such set and show that this factor of 2 is best possible. For three or more objective functions, however, we prove that no constant-factor approximation on the size of the set can be obtained efficiently.
Parallel and Scalable Precise Clustering for Homologous Protein Discovery
Venue: arXiv cs.DC 2019
Year: 2019

This paper presents a new, parallel implementation of clustering and demonstrates its utility in greatly speeding up the process of identifying homologous proteins. Clustering is a technique to reduce the number of comparison needed to find similar pairs in a set of $n$ elements such as protein sequences. Precise clustering ensures that each pair of similar elements appears together in at least one cluster, so that similarities can be identified by all-to-all comparison in each cluster rather than on the full set. This paper introduces ClusterMerge, a new algorithm for precise clustering that uses transitive relationships among the elements to enable parallel and scalable implementations of this approach. We apply ClusterMerge to the important problem of finding similar amino acid sequences in a collection of proteins. ClusterMerge identifies 99.8% of similar pairs found by a full $O(n^2)$ comparison, with only half as many operations. More importantly, ClusterMerge is highly amenable to parallel and distributed computation. Our implementation achieves a speedup of 604$\times$ on 768 cores (1400$\times$ faster than a comparable single-threaded clustering implementation), a strong scaling efficiency of 90%, and a weak scaling efficiency of nearly 100%.
Classical Chinese Sentence Segmentation for Tomb Biographies of Tang Dynasty
Venue: arXiv cs.CL 2019
Year: 2019

Tomb biographies of the Tang dynasty provide invaluable information about Chinese history. The original biographies are classical Chinese texts which contain neither word boundaries nor sentence boundaries. Relying on three published books of tomb biographies of the Tang dynasty, we investigated the effectiveness of employing machine-learning methods for algorithmically identifying the pauses and terminals of sentences in the biographies. We consider the segmentation task as a classification problem. Chinese characters that are and are not followed by a punctuation mark are classified into two categories. We applied a machine-learning-based mechanism, the conditional random fields (CRF), to classify the characters (and words) in the texts, and we studied the contributions of selected types of lexical information to the resulting quality of the segmentation recommendations. This proposal presented at the DH 2018 conference discussed some of the basic experiments and their evaluations. By considering the contextual information and employing the heuristics provided by experts of Chinese literature, we achieved F1 measures that were better than 80%. More complex experiments that employ deep neural networks helped us further improve the results in recent work.
How big can style be? Addressing high dimensionality for recommending with style
Venue: arXiv cs.IR 2019
Year: 2019

Using embeddings as representations of products is quite commonplace in recommender systems, either by extracting the semantic embeddings of text descriptions, user sessions, collaborative relationships, or product images. In this paper, we present an approach to extract style embeddings for using in fashion recommender systems, with a special focus on style information such as textures, prints, material, etc. The main issue of using such a type of embeddings is its high dimensionality. So, we propose feature reduction solutions alongside the investigation of its influence in the overall task of recommending products of the same style based on their main image. The feature reduction we propose allows for reducing the embedding vector from 600k features to 512, leading to a memory reduction of 99.91\% without critically compromising the quality of the recommendations.
Downlink Analysis for the Typical Cell in Poisson Cellular Networks
Venue: arXiv cs.IT 2019
Year: 2019

Owing to its unparalleled tractability, the Poisson point process (PPP) has emerged as a popular model for the analysis of cellular networks. Considering a stationary point process of users, which is independent of the base station (BS) point process, it is well known that the typical user does not lie in the typical cell and thus it may not truly represent the typical cell performance. Inspired by this observation, we present a construction that allows a direct characterization of the downlink performance of the typical cell. For this, we present an exact downlink analysis for the 1-D case and a remarkably accurate approximation for the 2-D case. Several useful insights about the differences and similarities in the two viewpoints (typical user vs. typical cell) are also provided.
Initialization for Network Embedding: A Graph Partition Approach
Venue: arXiv cs.SI 2019
Year: 2019

Network embedding has been intensively studied in the literature and widely used in various applications, such as link prediction and node classification. While previous work focus on the design of new algorithms or are tailored for various problem settings, the discussion of initialization strategies in the learning process is often missed. In this work, we address this important issue of initialization for network embedding that could dramatically improve the performance of the algorithms on both effectiveness and efficiency. Specifically, we first exploit the graph partition technique that divides the graph into several disjoint subsets, and then construct an abstract graph based on the partitions. We obtain the initialization of the embedding for each node in the graph by computing the network embedding on the abstract graph, which is much smaller than the input graph, and then propagating the embedding among the nodes in the input graph. With extensive experiments on various datasets, we demonstrate that our initialization technique significantly improves the performance of the state-of-the-art algorithms on the evaluations of link prediction and node classification by up to 7.76% and 8.74% respectively. Besides, we show that the technique of initialization reduces the running time of the state-of-the-arts by at least 20%.
Explainable Video Action Reasoning via Prior Knowledge and State Transitions
Venue: arXiv cs.CV 2019
Year: 2019

Human action analysis and understanding in videos is an important and challenging task. Although substantial progress has been made in past years, the explainability of existing methods is still limited. In this work, we propose a novel action reasoning framework that uses prior knowledge to explain semantic-level observations of video state changes. Our method takes advantage of both classical reasoning and modern deep learning approaches. Specifically, prior knowledge is defined as the information of a target video domain, including a set of objects, attributes and relationships in the target video domain, as well as relevant actions defined by the temporal attribute and relationship changes (i.e. state transitions). Given a video sequence, we first generate a scene graph on each frame to represent concerned objects, attributes and relationships. Then those scene graphs are linked by tracking objects across frames to form a spatio-temporal graph (also called video graph), which represents semantic-level video states. Finally, by sequentially examining each state transition in the video graph, our method can detect and explain how those actions are executed with prior knowledge, just like the logical manner of thinking by humans. Compared to previous works, the action reasoning results of our method can be explained by both logical rules and semantic-level observations of video content changes. Besides, the proposed method can be used to detect multiple concurrent actions with detailed information, such as who (particular objects), when (time), where (object locations) and how (what kind of changes). Experiments on a re-annotated dataset CAD-120 show the effectiveness of our method.
Modular Verification of Autonomous Space Robotics
Venue: arXiv cs.SE 2019
Year: 2019

Ensuring that autonomous space robot control software behaves as it should is crucial, particularly as software failure in space often equates to mission failure and could potentially endanger nearby astronauts and costly equipment. To minimise mission failure caused by software errors, we can utilise a variety of tools and techniques to verify that the software behaves as intended. In particular, distinct nodes in a robotic system often require different verification techniques to ensure that they behave as expected. This paper introduces a method for integrating the various verification techniques that are applied to robotic software, via a First-Order Logic (FOL) specification that captures each node's assumptions and guarantees. These FOL specifications are then used to guide the verification of the individual nodes, be it by testing or the use of a formal method. We also outline a way of measuring our confidence in the verification of the entire system in terms of the verification techniques used.
A Semantic Schema for Data Quality Management in a Multi-Tenant Data Platform
Venue: arXiv cs.SE 2019
Year: 2019

Schibsted Media Group is a global marketplace company with presence in more than 20 countries. It is undergoing a digital transformation to convert data silos to a multi-tenant system based on a common data platform. Good data quality based on a common schema on the semantic level is essential for building successful data-driven products across marketplaces. To solve this challenge, we developed the data quality tooling based on a semantic schema management system to support schema evolution with versioning, testing and transformation. It can monitor the data quality requirements for different applications and handle incoming data consisting of multiple schema versions. Today the system is operating in production and processes over one billion events per day for over 100 applications.
Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines
Venue: arXiv cs.CC 2019
Year: 2019

The logical depth of a {\em reversible} Turing machine equals the shortest running time of a shortest program for it. This is applied to show that the result in L.F. Antunes, A. Souto, and P.M.B. Vitányi, On the Rate of Decrease in Logical Depth, Theor. Comput. Sci., 702(2017), 60--64 is valid notwithstanding the error noted in Corrigendum P.M.B. Vitányi, Corrigendum to "On the rate of decrease in logical depth" by L.F. Antunes, A. Souto, and P.M.B. Vitányi [Theoret. Comput. Sci. 702 (2017) 60--64], {\em Theoret. Comput. Sci.}, https://doi.org/10.1016/j.tcs.2018.07.009 . /
Topology optimization for 3D thin-walled structures with adaptive meshing
Venue: arXiv cs.CE 2019
Year: 2019

This paper presents a density-based topology optimization method for designing 3D thin-walled structures with adaptive meshing. Uniform wall thickness is achieved by simultaneously constraining the minimum and maximum feature sizes using Helmholtz partial differential equations (PDE). The PDE-based constraints do not require information about neighbor cells and therefore can readily be integrated with an adaptive meshing scheme. This effectively enables the 3D topology optimization of thin-walled structures with a desktop PC, by significantly reducing computation in large void regions that appear during optimization. The uniform feature size constraint, when applied to 3D structures, can produce thin-walled geometries with branches and holes, which have previously been difficult to obtain via topology optimization. The resulting thin-walled structures can provide valuable insights for designing thin-walled lightweight structures made of stamping, investment casting and composite manufacturing.
Strongly Linearizable Implementations of Snapshots and Other Types
Venue: arXiv cs.DC 2019
Year: 2019

Linearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it has been shown [1] that replacing atomic objects with linearizable implementations can affect the probability distribution of execution outcomes in randomized algorithms. Thus, linearizable objects are not always suitable replacements for atomic objects. A stricter correctness condition called strong linearizability has been developed and shown to be appropriate for randomized algorithms in a strong adaptive adversary model [1]. We devise several new lock-free strongly linearizable implementations from atomic registers. In particular, we give the first strongly linearizable lock-free snapshot implementation that uses bounded space. This improves on the unbounded space solution of Denysyuk and Woelfel [2]. As a building block, our algorithm uses a lock-free strongly linearizable ABA-detecting register. We obtain this object by modifying the wait-free linearizable ABA-detecting register of Aghazadeh and Woelfel [3], which, as we show, is not strongly linearizable. Aspnes and Herlihy [4] identified a wide class types that have wait-free linearizable implementations from atomic registers. These types require that any pair of operations either commute, or one overwrites the other. Aspnes and Herlihy gave a general wait-free linearizable implementation of such types, employing a wait-free linearizable snapshot object. Replacing that snapshot object with our lock-free strongly linearizable one, we prove that all types in this class have a lock-free strongly linearizable implementation from atomic registers.
Efficient Decoding of Interleaved Low-Rank Parity-Check Codes
Venue: arXiv cs.IT 2019
Year: 2019

An efficient decoding algorithm for horizontally u-interleaved LRPC codes is proposed and analyzed. Upper bounds on the decoding failure rate and the computational complexity of the algorithm are derived. It is shown that interleaving reduces the decoding failure rate exponentially in the interleaving order u whereas the computational complexity grows linearly.
SpatialNLI: A Spatial Domain Natural Language Interface to Databases Using Spatial Comprehension
Venue: arXiv cs.CL 2019
Year: 2019

A natural language interface (NLI) to databases is an interface that translates a natural language question to a structured query that is executable by database management systems (DBMS). However, an NLI that is trained in the general domain is hard to apply in the spatial domain due to the idiosyncrasy and expressiveness of the spatial questions. Inspired by the machine comprehension model, we propose a spatial comprehension model that is able to recognize the meaning of spatial entities based on the semantics of the context. The spatial semantics learned from the spatial comprehension model is then injected to the natural language question to ease the burden of capturing the spatial-specific semantics. With our spatial comprehension model and information injection, our NLI for the spatial domain, named SpatialNLI, is able to capture the semantic structure of the question and translate it to the corresponding syntax of an executable query accurately. We also experimentally ascertain that SpatialNLI outperforms state-of-the-art methods.
Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
Venue: arXiv cs.LG 2019
Year: 2019

Attempts from different disciplines to provide a fundamental understanding of deep learning have advanced rapidly in recent years, yet a unified framework remains relatively limited. In this article, we provide one possible way to align existing branches of deep learning theory through the lens of dynamical system and optimal control. By viewing deep neural networks as discrete-time nonlinear dynamical systems, we can analyze how information propagates through layers using mean field theory. When optimization algorithms are further recast as controllers, the ultimate goal of training processes can be formulated as an optimal control problem. In addition, we can reveal convergence and generalization properties by studying the stochastic dynamics of optimization algorithms. This viewpoint features a wide range of theoretical study from information bottleneck to statistical physics. It also provides a principled way for hyper-parameter tuning when optimal control theory is introduced. Our framework fits nicely with supervised learning and can be extended to other learning problems, such as Bayesian learning, adversarial training, and specific forms of meta learning, without efforts. The review aims to shed lights on the importance of dynamics and optimal control when developing deep learning theory.
The Single-Face Ideal Orientation Problem in Planar Graphs
Venue: arXiv cs.DS 2019
Year: 2019

We consider the ideal orientation problem in planar graphs. In this problem, we are given an undirected graph $G$ with positive edge lengths and $k$ pairs of distinct vertices $(s_1, t_1), \dots, (s_k, t_k)$ called terminals, and we want to assign an orientation to each edge such that for all $i$ the distance from $s_i$ to $t_i$ is preserved or report that no such orientation exists. We show that the problem is NP-hard in planar graphs. On the other hand, we show that the problem is polynomial-time solvable in planar graphs when $k$ is fixed, the vertices $s_1, t_1, \dots, s_k, t_k$ are all on the same face, and no two of terminal pairs cross (a pair $(s_i, t_i)$ crosses $(s_j, t_j)$ if the cyclic order of the vertices is $s_i,s_j,t_i,t_j$). For serial instances, we give a simpler and faster algorithm running in $O(n \log n)$ time, even if $k$ is part of the input. (An instance is serial if the terminals appear in cyclic order $u_1, v_1, \dots, u_k, v_k$, where for each $i$ we have either $(u_i, v_i) = (s_i, t_i)$ or $(u_i, v_i) = (t_i, s_i)$.) Finally, we consider a generalization of the problem in which the sum of the distances from $s_i$ to $t_i$ is to be minimized; in this case we give an algorithm for serial instances running in $O(kn^5)$ time.
An Auto-ML Framework Based on GBDT for Lifelong Learning
Venue: arXiv cs.LG 2019
Year: 2019

Automatic Machine Learning (Auto-ML) has attracted more and more attention in recent years, our work is to solve the problem of data drift, which means that the distribution of data will gradually change with the acquisition process, resulting in a worse performance of the auto-ML model. We construct our model based on GBDT, Incremental learning and full learning are used to handle with drift problem. Experiments show that our method performs well on the five data sets. Which shows that our method can effectively solve the problem of data drift and has robust performance.
PopEval: A Character-Level Approach to End-To-End Evaluation Compatible with Word-Level Benchmark Dataset
Venue: arXiv cs.CV 2019
Year: 2019

The most prevalent scope of interest for OCR applications used to be scanned documents, but it has now shifted towards the natural scene. Despite the change of times, the existing evaluation methods are still based on the old criteria suited better for the past interests. In this paper, we propose PopEval, a novel evaluation approach for the recent OCR interests. The new and past evaluation algorithms were compared through the results on various datasets and OCR models. Compared to the other evaluation methods, the proposed evaluation algorithm was closer to the human's qualitative evaluation than other existing methods. Although the evaluation algorithm was devised as a character-level approach, the comparative experiment revealed that PopEval is also compatible on existing benchmark datasets annotated at word-level. The proposed evaluation algorithm is not only applicable to current end-to-end tasks, but also suggests a new direction to redesign the evaluation concept for further OCR researches.