OpenRaiser/Intern-Atlas huggingface dataset:
Transfer Adaptation Learning: A Decade Survey
Venue: arXiv cs.CV 2020
Year: 2020

The world we see is ever-changing and it always changes with people, things, and the environment. Domain is referred to as the state of the world at a certain moment. A research problem is characterized as transfer adaptation learning (TAL) when it needs knowledge correspondence between different moments/domains. Conventional machine learning aims to find a model with the minimum expected risk on test data by minimizing the regularized empirical risk on the training data, which, however, supposes that the training and test data share similar joint probability distribution. TAL aims to build models that can perform tasks of target domain by learning knowledge from a semantic related but distribution different source domain. It is an energetic research filed of increasing influence and importance, which is presenting a blowout publication trend. This paper surveys the advances of TAL methodologies in the past decade, and the technical challenges and essential problems of TAL have been observed and discussed with deep insights and new perspectives. Broader solutions of transfer adaptation learning being created by researchers are identified, i.e., instance re-weighting adaptation, feature adaptation, classifier adaptation, deep network adaptation and adversarial adaptation, which are beyond the early semi-supervised and unsupervised split. The survey helps researchers rapidly but comprehensively understand and identify the research foundation, research status, theoretical limitations, future challenges and under-studied issues (universality, interpretability, and credibility) to be broken in the field toward universal representation and safe applications in open-world scenarios.
Low-rank Tensor Grid for Image Completion
Venue: arXiv cs.LG 2020
Year: 2020

Tensor completion estimates missing components by exploiting the low-rank structure of multi-way data. The recently proposed methods based on tensor train (TT) and tensor ring (TR) show better performance in image recovery than classical ones. Compared with TT and TR, the projected entangled pair state (PEPS), which is also called tensor grid (TG), allows more interactions between different dimensions, and may lead to more compact representation. In this paper, we propose to perform image completion based on low-rank tensor grid. A two-stage density matrix renormalization group algorithm is used for initialization of TG decomposition, which consists of multiple TT decompositions. The latent TG factors can be alternatively obtained by solving alternating least squares problems. To further improve the computational efficiency, a multi-linear matrix factorization for low rank TG completion is developed by using parallel matrix factorization. Experimental results on synthetic data and real-world images show the proposed methods outperform the existing ones in terms of recovery accuracy.
Counting Polygon Triangulations is Hard
Venue: arXiv cs.CG 2020
Year: 2020

We prove that it is $\#\mathsf{P}$-complete to count the triangulations of a (non-simple) polygon.
Smart Home Personal Assistants: A Security and Privacy Review
Venue: arXiv cs.CR 2020
Year: 2020

Smart Home Personal Assistants (SPA) are an emerging innovation that is changing the way in which home users interact with the technology. However, there are a number of elements that expose these systems to various risks: i) the open nature of the voice channel they use, ii) the complexity of their architecture, iii) the AI features they rely on, and iv) their use of a wide-range of underlying technologies. This paper presents an in-depth review of the security and privacy issues in SPA, categorizing the most important attack vectors and their countermeasures. Based on this, we discuss open research challenges that can help steer the community to tackle and address current security and privacy issues in SPA. One of our key findings is that even though the attack surface of SPA is conspicuously broad and there has been a significant amount of recent research efforts in this area, research has so far focused on a small part of the attack surface, particularly on issues related to the interaction between the user and the SPA devices. We also point out that further research is needed to tackle issues related to authorization, speech recognition or profiling, to name a few. To the best of our knowledge, this is the first article to conduct such a comprehensive review and characterization of the security and privacy issues and countermeasures of SPA.
Varying-order NURBS discretization: An accurate and efficient method for isogeometric analysis of large deformation contact problems
Venue: arXiv cs.NA 2020
Year: 2020

In this paper, a novel varying order NURBS discretization method is proposed to enhance the performance of isogeometric analysis within the framework of computational contact mechanics. The method makes use of higher-order NURBS for contact integral evaluations. Lower-orders NURBS capable of modelling complex geometries exactly are utilized for the bulk discretization. This unexplored idea provides the possibility to refine the geometry through controllable order elevation strategy for isogeometric analysis. To achieve this, a higher-order NURBS layer is used as the contact boundary layer of the bodies. The NURBS layer is constructed using the surface refinement strategies such that it is accompanied by a large number of additional degrees of freedom and matches with the bulk parametrization. The validity of the presented isogeometric mortar contact formulation with varying-order NURBS discretization is first examined through the contact patch test. The capabilities and benefits of the proposed methodology are then demonstrated in detail using two-dimensional frictionless and frictional contact problems, considering both small and large deformations. It is shown that using the proposed method, accurate solutions can be achieved even with a coarse mesh. It is also shown that the current method requires a considerably lower computational cost compared to standard NURBS discretization while retaining robustness and stability. The simplicity of the method lends itself to be conveniently embedded in an existing isogeometric contact code after only a few minor modifications.
High-Throughput CNN Inference on Embedded ARM big.LITTLE Multi-Core Processors
Venue: arXiv cs.LG 2020
Year: 2020

IoT Edge intelligence requires Convolutional Neural Network (CNN) inference to take place in the edge devices itself. ARM big.LITTLE architecture is at the heart of prevalent commercial edge devices. It comprises of single-ISA heterogeneous cores grouped into multiple homogeneous clusters that enable power and performance trade-offs. All cores are expected to be simultaneously employed in inference to attain maximal throughput. However, high communication overhead involved in parallelization of computations from convolution kernels across clusters is detrimental to throughput. We present an alternative framework called Pipe-it that employs pipelined design to split convolutional layers across clusters while limiting parallelization of their respective kernels to the assigned cluster. We develop a performance-prediction model that utilizes only the convolutional layer descriptors to predict the execution time of each layer individually on all permitted core configurations (type and count). Pipe-it then exploits the predictions to create a balanced pipeline using an efficient design space exploration algorithm. Pipe-it on average results in a 39% higher throughput than the highest antecedent throughput.
Interacting spreading processes in multilayer networks
Venue: arXiv cs.SI 2020
Year: 2020

The world of network science is fascinating and filled with complex phenomena that we aspire to understand. One of them is the dynamics of spreading processes over complex networked structures. Building the knowledge-base in the field where we can face more than one spreading process propagating over a network that has more than one layer is a challenging task, as the complexity comes both from the environment in which the spread happens and from characteristics and interplay of spreads' propagation. As this cross-disciplinary field bringing together computer science, network science, biology and physics has rapidly grown over the last decade, there is a need to comprehensively review the current state-of-the-art and offer to the research community a roadmap that helps to organise the future research in this area. Thus, this survey is a first attempt to present the current landscape of the multi-processes spread over multilayer networks and to suggest the potential ways forward.
Rectified Decision Trees: Towards Interpretability, Compression and Empirical Soundness
Venue: arXiv cs.LG 2020
Year: 2020

How to obtain a model with good interpretability and performance has always been an important research topic. In this paper, we propose rectified decision trees (ReDT), a knowledge distillation based decision trees rectification with high interpretability, small model size, and empirical soundness. Specifically, we extend the impurity calculation and the pure ending condition of the classical decision tree to propose a decision tree extension that allows the use of soft labels generated by a well-trained teacher model in training and prediction process. It is worth noting that for the acquisition of soft labels, we propose a new multiple cross-validation based method to reduce the effects of randomness and overfitting. These approaches ensure that ReDT retains excellent interpretability and even achieves fewer nodes than the decision tree in the aspect of compression while having relatively good performance. Besides, in contrast to traditional knowledge distillation, back propagation of the student model is not necessarily required in ReDT, which is an attempt of a new knowledge distillation approach. Extensive experiments are conducted, which demonstrates the superiority of ReDT in interpretability, compression, and empirical soundness.
Regularity/Controllability/Observability of an NDS with Descriptor Form Subsystems and Generalized LFTs
Venue: arXiv cs.SY 2020
Year: 2020

This paper investigates regularity, controllability and observability for a networked dynamic system (NDS) with its subsystems being described in a descriptor form and system matrices of each subsystem being represented by a generalized linear fractional transformation (GLFT) of its parameters. Except a well-posedness condition, no any other constraints are put on either parameters or connections of a subsystem. Based on the Kronecker canonical form (KCF) of a matrix pencil, some matrix rank based necessary and sufficient conditions are established respectively for the regularity and complete controllability/observability of the NDS, in which the associated matrix depends affinely on both subsystem parameters and subsystem connections. These conditions keep the property that all the involved numerical computations are performed on each subsystem independently, which is attractive in the analysis and synthesis of a large scale NDS. Moreover, some explicit and easily checkable requirements are derived for subsystem dynamics/parameters with which a completely controllable/observable NDS can be constructed more easily.
Subset Selection for Matrices with Fixed Blocks
Venue: arXiv cs.DS 2020
Year: 2020

Subset selection for matrices is the task of extracting a column sub-matrix from a given matrix $B\in\mathbb{R}^{n\times m}$ with $m>n$ such that the pseudoinverse of the sampled matrix has as small Frobenius or spectral norm as possible. In this paper, we consider a more general problem of subset selection for matrices that allows a block to be fixed at the beginning. Under this setting, we provide a deterministic method for selecting a column sub-matrix from $B$. We also present a bound for both the Frobenius and spectral norms of the pseudoinverse of the sampled matrix, showing that the bound is asymptotically optimal. The main technology for proving this result is the interlacing families of polynomials developed by Marcus, Spielman, and Srivastava. This idea also results in a deterministic greedy selection algorithm that produces the sub-matrix promised by our result.
Online Explanation Generation for Human-Robot Teaming
Venue: arXiv cs.AI 2020
Year: 2020

As AI becomes an integral part of our lives, the development of explainable AI, embodied in the decision-making process of an AI or robotic agent, becomes imperative. For a robotic teammate, the ability to generate explanations to justify its behavior is one of the key requirements of explainable agency. Prior work on explanation generation has been focused on supporting the rationale behind the robot's decision or behavior. These approaches, however, fail to consider the mental demand for understanding the received explanation. In other words, the human teammate is expected to understand an explanation no matter how much information is presented. In this work, we argue that explanations, especially those of a complex nature, should be made in an online fashion during the execution, which helps spread out the information to be explained and thus reduce the mental workload of humans in highly cognitive demanding tasks. However, a challenge here is that the different parts of an explanation may be dependent on each other, which must be taken into account when generating online explanations. To this end, a general formulation of online explanation generation is presented with three variations satisfying different "online" properties. The new explanation generation methods are based on a model reconciliation setting introduced in our prior work. We evaluated our methods both with human subjects in a simulated rover domain, using NASA Task Load Index (TLX), and synthetically with ten different problems across two standard IPC domains. Results strongly suggest that our methods generate explanations that are perceived as less cognitively demanding and much preferred over the baselines and are computationally efficient.
Algorithms for Verifying Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks are widely used for nonlinear function approximation with applications ranging from computer vision to control. Although these networks involve the composition of simple arithmetic operations, it can be very challenging to verify whether a particular network satisfies certain input-output properties. This article surveys methods that have emerged recently for soundly verifying such properties. These methods borrow insights from reachability analysis, optimization, and search. We discuss fundamental differences and connections between existing algorithms. In addition, we provide pedagogical implementations of existing methods and compare them on a set of benchmark problems.
Fundamentals of Power Allocation Strategies for Downlink Multi-user NOMA with Target Rates
Venue: arXiv cs.IT 2020
Year: 2020

For downlink multi-user non-orthogonal multiple access (NOMA) systems with successive interference cancellation (SIC) receivers, and a base-station not possessing the instantaneous channel gains, the fundamental relationship between the target rates and power allocation is investigated. It is proven that the total interference from signals not removed by SIC has a fundamental upper-limit which is a function of the target rates, and the outage probability is one when exceeding this limit. The concept of well-behaved power allocation strategies is defined, and its properties are proven to be derived solely based on the target rates. The existence of power allocation strategies that enable NOMA to outperform OMA in per-user outage probability is proven, and are always well-behaved for the case when the outage probability performance of NOMA and OMA are equal for all users. The proposed SIC decoding order is then shown to the most energy efficient. The derivation of well-behaved power allocation strategies that have improved outage probability performance over OMA for each user is outlined. Simulations validate the theoretical results, demonstrating that NOMA systems can always outperform OMA systems in outage probability performance, without relying on the exact channel gains.
Extensions of Abelian Automata Groups
Venue: arXiv cs.FL 2020
Year: 2020

A theorem of Nekrashevych and Sidki shows the Mealy Automata structures one can place on Z^m are parametrized by a family of matrices (called "1/2-integral") and a choice of residuation vector e in Z^m. While the impact of the chosen matrix is well understood, the impact of the residuation vector on the resulting structure is seemingly sporadic. In this paper we characterize the impact of the residuation vector e by recognizing an initial structure when e is the first standard basis vector. All other choices of e extend this initial structure by adding "fractional elements" in a way we make precise.
Integral Input-to-State Stability of Nonlinear Time-Delay Systems with Delay-Dependent Impulse Effects
Venue: arXiv cs.SY 2020
Year: 2020

This paper studies integral input-to-state stability (iISS) of nonlinear impulsive systems with time-delay in both the continuous dynamics and the impulses. Several iISS results are established by using the method of Lyapunov-Krasovskii functionals. For impulsive systems with iISS continuous dynamics and destabilizing impulses, we derive two iISS criteria that guarantee the uniform iISS of the whole system provided that the time period between two successive impulse moments is appropriately bounded from below. Then we provide an iISS result for systems with unstable continuous dynamics and stabilizing impulses. For this scenario, it is shown that the iISS properties are guaranteed if the impulses occur frequently enough. For impulsive systems with stabilizing impulses and stable continuous dynamics for zero input, we obtain an iISS result which shows that the entire system is uniformly iISS over arbitrary impulse time sequences. As applications, iISS properties of a class of bilinear systems are studied in details with simulations to demonstrate the presented results.
STNReID : Deep Convolutional Networks with Pairwise Spatial Transformer Networks for Partial Person Re-identification
Venue: arXiv cs.CV 2020
Year: 2020

Partial person re-identification (ReID) is a challenging task because only partial information of person images is available for matching target persons. Few studies, especially on deep learning, have focused on matching partial person images with holistic person images. This study presents a novel deep partial ReID framework based on pairwise spatial transformer networks (STNReID), which can be trained on existing holistic person datasets. STNReID includes a spatial transformer network (STN) module and a ReID module. The STN module samples an affined image (a semantically corresponding patch) from the holistic image to match the partial image. The ReID module extracts the features of the holistic, partial, and affined images. Competition (or confrontation) is observed between the STN module and the ReID module, and two-stage training is applied to acquire a strong STNReID for partial ReID. Experimental results show that our STNReID obtains 66.7% and 54.6% rank-1 accuracies on partial ReID and partial iLIDS datasets, respectively. These values are at par with those obtained with state-of-the-art methods.
One-Way Topological Automata and the Tantalizing Effects of Their Topological Features
Venue: arXiv cs.FL 2020
Year: 2020

We cast new light on the existing models of one-way deterministic topological automata by introducing a fresh but general, convenient model, in which, as each input symbol is read, an interior system of an automaton, known as a configuration, continues to evolve in a topological space by applying continuous transition operators one by one. The acceptance and rejection of a given input are determined by observing the interior system after the input is completely processed. Such automata naturally generalize one-way finite automata of various types, including deterministic, probabilistic, quantum, and pushdown automata. We examine the strengths and weaknesses of the power of this new automata model when recognizing formal languages. We investigate tantalizing effects of various topological features of our topological automata by analyzing their behaviors when different kinds of topological spaces and continuous maps, which are used respectively as configuration spaces and transition operators, are provided to the automata. Finally, we present goals and directions of future studies on the topological features of topological automata.
Two models of double descent for weak features
Venue: arXiv cs.LG 2020
Year: 2020

The "double descent" risk curve was proposed to qualitatively describe the out-of-sample prediction accuracy of variably-parameterized machine learning models. This article provides a precise mathematical analysis for the shape of this curve in two simple data models with the least squares/least norm predictor. Specifically, it is shown that the risk peaks when the number of features $p$ is close to the sample size $n$, but also that the risk decreases towards its minimum as $p$ increases beyond $n$. This behavior is contrasted with that of "prescient" models that select features in an a priori optimal order.
A RAD approach to deep mixture models
Venue: arXiv cs.LG 2020
Year: 2020

Flow based models such as Real NVP are an extremely powerful approach to density estimation. However, existing flow based models are restricted to transforming continuous densities over a continuous input space into similarly continuous distributions over continuous latent variables. This makes them poorly suited for modeling and representing discrete structures in data distributions, for example class membership or discrete symmetries. To address this difficulty, we present a normalizing flow architecture which relies on domain partitioning using locally invertible functions, and possesses both real and discrete valued latent variables. This Real and Discrete (RAD) approach retains the desirable normalizing flow properties of exact sampling, exact inference, and analytically computable probabilities, while at the same time allowing simultaneous modeling of both continuous and discrete structure in a data distribution.
Predicting Citywide Crowd Flows in Irregular Regions Using Multi-View Graph Convolutional Networks
Venue: arXiv cs.CV 2020
Year: 2020

Being able to predict the crowd flows in each and every part of a city, especially in irregular regions, is strategically important for traffic control, risk assessment, and public safety. However, it is very challenging because of interactions and spatial correlations between different regions. In addition, it is affected by many factors: i) multiple temporal correlations among different time intervals: closeness, period, trend; ii) complex external influential factors: weather, events; iii) meta features: time of the day, day of the week, and so on. In this paper, we formulate crowd flow forecasting in irregular regions as a spatio-temporal graph (STG) prediction problem in which each node represents a region with time-varying flows. By extending graph convolution to handle the spatial information, we propose using spatial graph convolution to build a multi-view graph convolutional network (MVGCN) for the crowd flow forecasting problem, where different views can capture different factors as mentioned above. We evaluate MVGCN using four real-world datasets (taxicabs and bikes) and extensive experimental results show that our approach outperforms the adaptations of state-of-the-art methods. And we have developed a crowd flow forecasting system for irregular regions that can now be used internally.