OpenRaiser/Intern-Atlas huggingface dataset:
BlockDrop: Dynamic Inference Paths in Residual Networks
Venue: arXiv cs.CV 2019
Year: 2019

Very deep convolutional neural networks offer excellent recognition results, yet their computational expense limits their impact for many real-world applications. We introduce BlockDrop, an approach that learns to dynamically choose which layers of a deep network to execute during inference so as to best reduce total computation without degrading prediction accuracy. Exploiting the robustness of Residual Networks (ResNets) to layer dropping, our framework selects on-the-fly which residual blocks to evaluate for a given novel image. In particular, given a pretrained ResNet, we train a policy network in an associative reinforcement learning setting for the dual reward of utilizing a minimal number of blocks while preserving recognition accuracy. We conduct extensive experiments on CIFAR and ImageNet. The results provide strong quantitative and qualitative evidence that these learned policies not only accelerate inference but also encode meaningful visual information. Built upon a ResNet-101 model, our method achieves a speedup of 20\% on average, going as high as 36\% for some images, while maintaining the same 76.4\% top-1 accuracy on ImageNet.
Critical Learning Periods in Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Similar to humans and animals, deep artificial neural networks exhibit critical periods during which a temporary stimulus deficit can impair the development of a skill. The extent of the impairment depends on the onset and length of the deficit window, as in animal models, and on the size of the neural network. Deficits that do not affect low-level statistics, such as vertical flipping of the images, have no lasting effect on performance and can be overcome with further training. To better understand this phenomenon, we use the Fisher Information of the weights to measure the effective connectivity between layers of a network during training. Counterintuitively, information rises rapidly in the early phases of training, and then decreases, preventing redistribution of information resources in a phenomenon we refer to as a loss of "Information Plasticity". Our analysis suggests that the first few epochs are critical for the creation of strong connections that are optimal relative to the input data distribution. Once such strong connections are created, they do not appear to change during additional training. These findings suggest that the initial learning transient, under-scrutinized compared to asymptotic behavior, plays a key role in determining the outcome of the training process. Our findings, combined with recent theoretical results in the literature, also suggest that forgetting (decrease of information in the weights) is critical to achieving invariance and disentanglement in representation learning. Finally, critical periods are not restricted to biological systems, but can emerge naturally in learning systems, whether biological or artificial, due to fundamental constrains arising from learning dynamics and information processing.
Adversarial Transfer Learning for Cross-domain Visual Recognition
Venue: arXiv cs.CV 2019
Year: 2019

In many practical visual recognition scenarios, feature distribution in the source domain is generally different from that of the target domain, which results in the emergence of general cross-domain visual recognition problems. To address the problems of visual domain mismatch, we propose a novel semi-supervised adversarial transfer learning approach, which is called Coupled adversarial transfer Domain Adaptation (CatDA), for distribution alignment between two domains. The proposed CatDA approach is inspired by cycleGAN, but leveraging multiple shallow multilayer perceptrons (MLPs) instead of deep networks. Specifically, our CatDA comprises of two symmetric and slim sub-networks, such that the coupled adversarial learning framework is formulated. With such symmetry of two generators, the input data from source/target domain can be fed into the MLP network for target/source domain generation, supervised by two confrontation oriented coupled discriminators. Notably, in order to avoid the critical flaw of high-capacity of the feature extraction function during domain adversarial training, domain specific loss and domain knowledge fidelity loss are proposed in each generator, such that the effectiveness of the proposed transfer network is guaranteed. Additionally, the essential difference from cycleGAN is that our method aims to generate domain-agnostic and aligned features for domain adaptation and transfer learning rather than synthesize realistic images. We show experimentally on a number of benchmark datasets and the proposed approach achieves competitive performance over state-of-the-art domain adaptation and transfer learning approaches.
Active Regression via Linear-Sample Sparsification
Venue: arXiv cs.LG 2019
Year: 2019

We present an approach that improves the sample complexity for a variety of curve fitting problems, including active learning for linear regression, polynomial regression, and continuous sparse Fourier transforms. In the active linear regression problem, one would like to estimate the least squares solution $β^*$ minimizing $\|Xβ- y\|_2$ given the entire unlabeled dataset $X \in \mathbb{R}^{n \times d}$ but only observing a small number of labels $y_i$. We show that $O(d)$ labels suffice to find a constant factor approximation $\tildeβ$: \[ \mathbb{E}[\|X\tildeβ - y\|_2^2] \leq 2 \mathbb{E}[\|X β^* - y\|_2^2]. \] This improves on the best previous result of $O(d \log d)$ from leverage score sampling. We also present results for the \emph{inductive} setting, showing when $\tildeβ$ will generalize to fresh samples; these apply to continuous settings such as polynomial regression. Finally, we show how the techniques yield improved results for the non-linear sparse Fourier transform setting.
Behavioural equivalences for timed systems
Venue: arXiv cs.LO 2019
Year: 2019

Timed transition systems are behavioural models that include an explicit treatment of time flow and are used to formalise the semantics of several foundational process calculi and automata. Despite their relevance, a general mathematical characterisation of timed transition systems and their behavioural theory is still missing. We introduce the first uniform framework for timed behavioural models that encompasses known behavioural equivalences such as timed bisimulations, timed language equivalences as well as their weak and time-abstract counterparts. All these notions of equivalences are naturally organised by their discriminating power in a spectrum. We prove that this result does not depend on the type of the systems under scrutiny: it holds for any generalisation of timed transition system. We instantiate our framework to timed transition systems and their quantitative extensions such as timed probabilistic systems.
Strategic Topology Switching for Security-Part II: Detection & Switching Topologies
Venue: arXiv cs.MA 2019
Year: 2019

This two-part paper considers strategic topology switching for security in the second-order multi-agent system. In Part II, we propose a strategy on switching topologies to detect zero-dynamics attack (ZDA), whose attack-starting time is allowed to be not the initial time. We first characterize the sufficient and necessary condition for detectability of ZDA, in terms of the network topologies to be switched to and the set of agents to be monitored. We then propose an attack detection algorithm based on the Luenberger observer, using the characterized detectability condition. Employing the strategy on switching times proposed in Part I and the strategy on switching topologies proposed here, a strategic topology-switching algorithm is derived. Its primary advantages are threefold: (i) in achieving consensus in the absence of attacks, the control protocol does not need velocity measurements and the algorithm has no constraint on the magnitudes of coupling weights; (ii) in tracking system in the absence of attacks, the Luenberger observer has no constraint on the magnitudes of observer gains and the number of monitored agents, i.e., only one monitored agent's output is sufficient; (iii) in detecting ZDA, the algorithm allows the defender to have no knowledge of the attack-starting time and the number of misbehaving agents (i.e., agents under attack). Simulations are provided to verify the effectiveness of the strategic topology-switching algorithm.
On density of subgraphs of Cartesian products
Venue: arXiv cs.DM 2019
Year: 2019

In this paper, we extend two classical results about the density of subgraphs of hypercubes to subgraphs $G$ of Cartesian products $G_1\times\cdots\times G_m$ of arbitrary connected graphs. Namely, we show that $\frac{|E(G)|}{|V(G)|}\le \lceil 2\max\{ \text{dens}(G_1),\ldots,\text{dens}(G_m)\} \rceil\log|V(G)|$, where $\text{dens}(H)$ is the maximum ratio $\frac{|E(H')|}{|V(H')|}$ over all subgraphs $H'$ of $H$. We introduce the notions of VC-dimension $\text{VC-dim}(G)$ and VC-density $\text{VC-dens}(G)$ of a subgraph $G$ of a Cartesian product $G_1\times\cdots\times G_m$, generalizing the classical Vapnik-Chervonenkis dimension of set-families (viewed as subgraphs of hypercubes). We prove that if $G_1,\ldots,G_m$ belong to the class ${\mathcal G}(H)$ of all finite connected graphs not containing a given graph $H$ as a minor, then for any subgraph $G$ of $G_1\times\cdots\times G_m$ a sharper inequality $\frac{|E(G)|}{|V(G)|}\le \text{VC-dim}(G)α(H)$ holds, where $α(H)$ is the density of the graphs from ${\mathcal G}(H)$. We refine and sharpen those two results to several specific graph classes. We also derive upper bounds (some of them polylogarithmic) for the size of adjacency labeling schemes of subgraphs of Cartesian products.
Effective Footstep Planning Using Homotopy-Class Guidance
Venue: arXiv cs.RO 2019
Year: 2019

Planning the motion for humanoid robots is a computationally-complex task due to the high dimensionality of the system. Thus, a common approach is to first plan in the low-dimensional space induced by the robot's feet---a task referred to as footstep planning. This low-dimensional plan is then used to guide the full motion of the robot. One approach that has proven successful in footstep planning is using search-based planners such as A* and its many variants. To do so, these search-based planners have to be endowed with effective heuristics to efficiently guide them through the search space. However, designing effective heuristics is a time-consuming task that requires the user to have good domain knowledge. Thus, our goal is to be able to effectively plan the footstep motions taken by a humanoid robot while obviating the burden on the user to carefully design local-minima free heuristics. To this end, we propose to use user-defined homotopy classes in the workspace that are intuitive to define. These homotopy classes are used to automatically generate heuristic functions that efficiently guide the footstep planner. Additionally, we present an extension to homotopy classes such that they are applicable to complex multi-level environments. We compare our approach for footstep planning with a standard approach that uses a heuristic common to footstep planning. In simple scenarios, the performance of both algorithms is comparable. However, in more complex scenarios our approach allows for a speedup in planning of several orders of magnitude when compared to the standard approach.
The Complexity of Satisfiability in Non-Iterated and Iterated Probabilistic Logics
Venue: arXiv cs.LO 2019
Year: 2019

Let L be some extension of classical propositional logic. The non-iterated probabilistic logic over L, is the logic PL that is defined by adding non-nested probabilistic operators in the language of L. For example in PL we can express a statement like "the probability of truthfulness of A is at 0.3" where A is a formula of L. The iterated probabilistic logic over L is the logic PPL, where the probabilistic operators may be iterated (nested). For example, in PPL we can express a statement like "this coin is counterfeit with probability 0.6". In this paper we investigate the influence of probabilistic operators in the complexity of satisfiability in PL and PPL. We obtain complexity bounds, for the aforementioned satisfiability problem, which are parameterized in the complexity of satisfiability of conjunctions of positive and negative formulas that have neither a probabilistic nor a classical operator as a top-connective. As an application of our results we obtain tight complexity bounds for the satisfiability problem in PL and PPL when L is classical propositional logic or justification logic.
Deep Learning Diffuse Optical Tomography
Venue: arXiv cs.CV 2019
Year: 2019

Diffuse optical tomography (DOT) has been investigated as an alternative imaging modality for breast cancer detection thanks to its excellent contrast to hemoglobin oxidization level. However, due to the complicated non-linear photon scattering physics and ill-posedness, the conventional reconstruction algorithms are sensitive to imaging parameters such as boundary conditions. To address this, here we propose a novel deep learning approach that learns non-linear photon scattering physics and obtains an accurate three dimensional (3D) distribution of optical anomalies. In contrast to the traditional black-box deep learning approaches, our deep network is designed to invert the Lippman-Schwinger integral equation using the recent mathematical theory of deep convolutional framelets. As an example of clinical relevance, we applied the method to our prototype DOT system. We show that our deep neural network, trained with only simulation data, can accurately recover the location of anomalies within biomimetic phantoms and live animals without the use of an exogenous contrast agent.
Successive Embedding and Classification Loss for Aerial Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

Deep neural networks can be effective means to automatically classify aerial images but is easy to overfit to the training data. It is critical for trained neural networks to be robust to variations that exist between training and test environments. To address the overfitting problem in aerial image classification, we consider the neural network as successive transformations of an input image into embedded feature representations and ultimately into a semantic class label, and train neural networks to optimize image representations in the embedded space in addition to optimizing the final classification score. We demonstrate that networks trained with this dual embedding and classification loss outperform networks with classification loss only. %We also study placing the embedding loss on different network layers. We also find that moving the embedding loss from commonly-used feature space to the classifier space, which is the space just before softmax nonlinearization, leads to the best classification performance for aerial images. Visualizations of the network's embedded representations reveal that the embedding loss encourages greater separation between target class clusters for both training and testing partitions of two aerial image classification benchmark datasets, MSTAR and AID. Our code is publicly available on GitHub.
Phylogenetics of Indo-European Language families via an Algebro-Geometric Analysis of their Syntactic Structures
Venue: arXiv cs.CL 2019
Year: 2019

Using Phylogenetic Algebraic Geometry, we analyze computationally the phylogenetic tree of subfamilies of the Indo-European language family, using data of syntactic structures. The two main sources of syntactic data are the SSWL database and Longobardi's recent data of syntactic parameters. We compute phylogenetic invariants and likelihood functions for two sets of Germanic languages, a set of Romance languages, a set of Slavic languages and a set of early Indo-European languages, and we compare the results with what is known through historical linguistics.
Enabling Early Audio Event Detection with Neural Networks
Venue: arXiv cs.SD 2019
Year: 2019

This paper presents a methodology for early detection of audio events from audio streams. Early detection is the ability to infer an ongoing event during its initial stage. The proposed system consists of a novel inference step coupled with dual parallel tailored-loss deep neural networks (DNNs). The DNNs share a similar architecture except for their loss functions, i.e. weighted loss and multitask loss, which are designed to efficiently cope with issues common to audio event detection. The inference step is newly introduced to make use of the network outputs for recognizing ongoing events. The monotonicity of the detection function is required for reliable early detection, and will also be proved. Experiments on the ITC-Irst database show that the proposed system achieves state-of-the-art detection performance. Furthermore, even partial events are sufficient to achieve good performance similar to that obtained when an entire event is observed, enabling early event detection.
Incremental Learning in Deep Convolutional Neural Networks Using Partial Network Sharing
Venue: arXiv cs.CV 2019
Year: 2019

Deep convolutional neural network (DCNN) based supervised learning is a widely practiced approach for large-scale image classification. However, retraining these large networks to accommodate new, previously unseen data demands high computational time and energy requirements. Also, previously seen training samples may not be available at the time of retraining. We propose an efficient training methodology and incrementally growing DCNN to learn new tasks while sharing part of the base network. Our proposed methodology is inspired by transfer learning techniques, although it does not forget previously learned tasks. An updated network for learning new set of classes is formed using previously learned convolutional layers (shared from initial part of base network) with addition of few newly added convolutional kernels included in the later layers of the network. We employed a `clone-and-branch' technique which allows the network to learn new tasks one after another without any performance loss in old tasks. We evaluated the proposed scheme on several recognition applications. The classification accuracy achieved by our approach is comparable to the regular incremental learning approach (where networks are updated with new training samples only, without any network sharing), while achieving energy efficiency, reduction in storage requirements, memory access and training time.
Sketched Clustering via Hybrid Approximate Message Passing
Venue: arXiv cs.IT 2019
Year: 2019

In sketched clustering, a dataset of $T$ samples is first sketched down to a vector of modest size, from which the centroids are subsequently extracted. Advantages include i) reduced storage complexity and ii) centroid extraction complexity independent of $T$. For the sketching methodology recently proposed by Keriven, et al., which can be interpreted as a random sampling of the empirical characteristic function, we propose a sketched clustering algorithm based on approximate message passing. Numerical experiments suggest that our approach is more efficient than the state-of-the-art sketched clustering algorithm "CL-OMPR" (in both computational and sample complexity) and more efficient than k-means++ when $T$ is large.
Efficient Implementation of the Room Simulator for Training Deep Neural Network Acoustic Models
Venue: arXiv cs.SD 2019
Year: 2019

In this paper, we describe how to efficiently implement an acoustic room simulator to generate large-scale simulated data for training deep neural networks. Even though Google Room Simulator in [1] was shown to be quite effective in reducing the Word Error Rates (WERs) for far-field applications by generating simulated far-field training sets, it requires a very large number of Fast Fourier Transforms (FFTs) of large size. Room Simulator in [1] used approximately 80 percent of Central Processing Unit (CPU) usage in our CPU + Graphics Processing Unit (GPU) training architecture [2]. In this work, we implement an efficient OverLap Addition (OLA) based filtering using the open-source FFTW3 library. Further, we investigate the effects of the Room Impulse Response (RIR) lengths. Experimentally, we conclude that we can cut the tail portions of RIRs whose power is less than 20 dB below the maximum power without sacrificing the speech recognition accuracy. However, we observe that cutting RIR tail more than this threshold harms the speech recognition accuracy for rerecorded test sets. Using these approaches, we were able to reduce CPU usage for the room simulator portion down to 9.69 percent in CPU/GPU training architecture. Profiling result shows that we obtain 22.4 times speed-up on a single machine and 37.3 times speed up on Google's distributed training infrastructure.
An Architecture Combining Convolutional Neural Network (CNN) and Support Vector Machine (SVM) for Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

Convolutional neural networks (CNNs) are similar to "ordinary" neural networks in the sense that they are made up of hidden layers consisting of neurons with "learnable" parameters. These neurons receive inputs, performs a dot product, and then follows it with a non-linearity. The whole network expresses the mapping between raw image pixels and their class scores. Conventionally, the Softmax function is the classifier used at the last layer of this network. However, there have been studies (Alalshekmubarak and Smith, 2013; Agarap, 2017; Tang, 2013) conducted to challenge this norm. The cited studies introduce the usage of linear support vector machine (SVM) in an artificial neural network architecture. This project is yet another take on the subject, and is inspired by (Tang, 2013). Empirical data has shown that the CNN-SVM model was able to achieve a test accuracy of ~99.04% using the MNIST dataset (LeCun, Cortes, and Burges, 2010). On the other hand, the CNN-Softmax was able to achieve a test accuracy of ~99.23% using the same dataset. Both models were also tested on the recently-published Fashion-MNIST dataset (Xiao, Rasul, and Vollgraf, 2017), which is suppose to be a more difficult image classification dataset than MNIST (Zalandoresearch, 2017). This proved to be the case as CNN-SVM reached a test accuracy of ~90.72%, while the CNN-Softmax reached a test accuracy of ~91.86%. The said results may be improved if data preprocessing techniques were employed on the datasets, and if the base CNN model was a relatively more sophisticated than the one used in this study.
Potential-Function Proofs for First-Order Methods
Venue: arXiv cs.LG 2019
Year: 2019

This note discusses proofs for convergence of first-order methods based on simple potential-function arguments. We cover methods like gradient descent (for both smooth and non-smooth settings), mirror descent, and some accelerated variants.