OpenRaiser/Intern-Atlas huggingface dataset:
Deep Non-Rigid Structure from Motion with Missing Data
Venue: arXiv cs.CV 2019
Year: 2019

Non-Rigid Structure from Motion (NRSfM) refers to the problem of reconstructing cameras and the 3D point cloud of a non-rigid object from an ensemble of images with 2D correspondences. Current NRSfM algorithms are limited from two perspectives: (i) the number of images, and (ii) the type of shape variability they can handle. These difficulties stem from the inherent conflict between the condition of the system and the degrees of freedom needing to be modeled -- which has hampered its practical utility for many applications within vision. In this paper we propose a novel hierarchical sparse coding model for NRSFM which can overcome (i) and (ii) to such an extent, that NRSFM can be applied to problems in vision previously thought too ill posed. Our approach is realized in practice as the training of an unsupervised deep neural network (DNN) auto-encoder with a unique architecture that is able to disentangle pose from 3D structure. Using modern deep learning computational platforms allows us to solve NRSfM problems at an unprecedented scale and shape complexity. Our approach has no 3D supervision, relying solely on 2D point correspondences. Further, our approach is also able to handle missing/occluded 2D points without the need for matrix completion. Extensive experiments demonstrate the impressive performance of our approach where we exhibit superior precision and robustness against all available state-of-the-art works in some instances by an order of magnitude. We further propose a new quality measure (based on the network weights) which circumvents the need for 3D ground-truth to ascertain the confidence we have in the reconstructability. We believe our work to be a significant advance over state-of-the-art in NRSFM.
Decoding a Complex Visualization in a Science Museum -- An Empirical Study
Venue: arXiv cs.HC 2019
Year: 2019

This study describes a detailed analysis of museum visitors' decoding process as they used a visualization designed to support exploration of a large, complex dataset. Quantitative and qualitative analyses revealed that it took, on average, 43 seconds for visitors to decode enough of the visualization to see patterns and relationships in the underlying data represented, and 54 seconds to arrive at their first correct data interpretation. Furthermore, visitors decoded throughout and not only upon initial use of the visualization. The study analyzed think-aloud data to identify issues visitors had mapping the visual representations to their intended referents, examine why they occurred, and consider if and how these decoding issues were resolved. The paper also describes how multiple visual encodings both helped and hindered decoding and concludes with implications on the design and adaptation of visualizations for informal science learning venues.
Deep Learning Training on the Edge with Low-Precision Posits
Venue: arXiv cs.LG 2019
Year: 2019

Recently, the posit numerical format has shown promise for DNN data representation and compute with ultra-low precision ([5..8]-bit). However, majority of studies focus only on DNN inference. In this work, we propose DNN training using posits and compare with the floating point training. We evaluate on both MNIST and Fashion MNIST corpuses, where 16-bit posits outperform 16-bit floating point for end-to-end DNN training.
Transactional Properties of Permissioned Blockchains
Venue: arXiv cs.DC 2019
Year: 2019

Traditional distributed transaction processing (TP) systems, such as replicated databases, faced difficulties in getting wide adoption for scenarios of enterprise integration due to the level of mutual trust required. Ironically, public blockchains, which promised to solve the problem of mutual trust in collaborative processes, suffer from issues like scalability, probabilistic transaction finality, and lack of data confidentiality. To tackle these issues, permissioned blockchains were introduced as an alternative approach combining the positives of the two worlds and avoiding their drawbacks. However, no sufficient analysis has been done to emphasize their actual capabilities regarding TP. In this paper, we identify a suitable collection of TP criteria to analyze permissioned blockchains and apply them to a prominent set of these systems. Finally, we compare the derived properties and provide general conclusions.
Blockguard: Adaptive Blockchain Security
Venue: arXiv cs.DC 2019
Year: 2019

We consider the problem of varying the security of blockchain transactions according to their importance. This adaptive security is achieved by using variable size consensus committees. To improve performance, such committees function concurrently. We present two algorithms that allow adaptive security by forming concurrent variable size consensus committees on demand. One is based on a single joint blockchain, the other is based on separate sharded blockchains. For in-committee consensus, our algorithms may use various available byzantine-robust fault tolerant algorithms (BFT). We implement synchronous BFT, asynchronous BFT and proof-of-work consensus. We thoroughly evaluate the performance of our adaptive security algorithms.
Landmark Detection in Low Resolution Faces with Semi-Supervised Learning
Venue: arXiv cs.CV 2019
Year: 2019

Landmark detection algorithms trained on high resolution images perform poorly on datasets containing low resolution images. This deters the performance of algorithms relying on quality landmarks, for example, face recognition. To the best of our knowledge, there does not exist any dataset consisting of low resolution face images along with their annotated landmarks, making supervised training infeasible. In this paper, we present a semi-supervised approach to predict landmarks on low resolution images by learning them from labeled high resolution images. The objective of this work is to show that predicting landmarks directly on low resolution images is more effective than the current practice of aligning images after rescaling or superresolution. In a two-step process, the proposed approach first learns to generate low resolution images by modeling the distribution of target low resolution images. In the second stage, the roles of generated images and real low resolution images are switched and the model learns to predict landmarks for real low resolution images from generated low resolution images. With extensive experimentation, we study the impact of each of the design choices and also show that prediction of landmarks directly on low resolution images improves the performance of important tasks such as face recognition in low resolution images.
Optimizing Multi-GPU Parallelization Strategies for Deep Learning Training
Venue: arXiv cs.LG 2019
Year: 2019

Deploying deep learning (DL) models across multiple compute devices to train large and complex models continues to grow in importance because of the demand for faster and more frequent training. Data parallelism (DP) is the most widely used parallelization strategy, but as the number of devices in data parallel training grows, so does the communication overhead between devices. Additionally, a larger aggregate batch size per step leads to statistical efficiency loss, i.e., a larger number of epochs are required to converge to a desired accuracy. These factors affect overall training time and beyond a certain number of devices, the speedup from leveraging DP begins to scale poorly. In addition to DP, each training step can be accelerated by exploiting model parallelism (MP). This work explores hybrid parallelization, where each data parallel worker is comprised of more than one device, across which the model dataflow graph (DFG) is split using MP. We show that at scale, hybrid training will be more effective at minimizing end-to-end training time than exploiting DP alone. We project that for Inception-V3, GNMT, and BigLSTM, the hybrid strategy provides an end-to-end training speedup of at least 26.5%, 8%, and 22% respectively compared to what DP alone can achieve at scale.
Towards a General Framework for Static Cost Analysis of Parallel Logic Programs
Venue: arXiv cs.PL 2019
Year: 2019

The estimation and control of resource usage is now an important challenge in an increasing number of computing systems. In particular, requirements on timing and energy arise in a wide variety of applications such as internet of things, cloud computing, health, transportation, and robots. At the same time, parallel computing, with (heterogeneous) multi-core platforms in particular, has become the dominant paradigm in computer architecture. Predicting resource usage on such platforms poses a difficult challenge. Most work on static resource analysis has focused on sequential programs, and relatively little progress has been made on the analysis of parallel programs, or more specifically on parallel logic programs. We propose a novel, general, and flexible framework for setting up cost equations/relations which can be instantiated for performing resource usage analysis of parallel logic programs for a wide range of resources, platforms and execution models. The analysis estimates both lower and upper bounds on the resource usage of a parallel program (without executing it) as functions on input data sizes. In addition, it also infers other meaningful information to better exploit and assess the potential and actual parallelism of a system. We develop a method for solving cost relations involving the max function that arise in the analysis of parallel programs. Finally, we instantiate our general framework for the analysis of logic programs with Independent And-Parallelism, report on an implementation within the CiaoPP system, and provide some experimental results. To our knowledge, this is the first approach to the cost analysis of parallel logic programs.
uBaaS: A Unified Blockchain as a Service Platform
Venue: arXiv cs.SE 2019
Year: 2019

Blockchain is an innovative distributed ledger technology which has attracted a wide range of interests for building the next generation of applications to address lack-of-trust issues in business. Blockchain as a service (BaaS) is a promising solution to improve the productivity of blockchain application development. However, existing BaaS deployment solutions are mostly vendor-locked: they are either bound to a cloud provider or a blockchain platform. In addition to deployment, design and implementation of blockchain-based applications is a hard task requiring deep expertise. Therefore, this paper presents a unified blockchain as a service platform (uBaaS) to support both design and deployment of blockchain-based applications. The services in uBaaS include deployment as a service, design pattern as a service and auxiliary services. In uBaaS, deployment as a service is platform agnostic, which can avoid lock-in to specific cloud platforms, while design pattern as a service applies design patterns for data management and smart contract design to address the scalability and security issues of blockchain. The proposed solutions are evaluated using a real-world quality tracing use case in terms of feasibility and scalability.
Lifelong and Interactive Learning of Factual Knowledge in Dialogues
Venue: arXiv cs.CL 2019
Year: 2019

Dialogue systems are increasingly using knowledge bases (KBs) storing real-world facts to help generate quality responses. However, as the KBs are inherently incomplete and remain fixed during conversation, it limits dialogue systems' ability to answer questions and to handle questions involving entities or relations that are not in the KB. In this paper, we make an attempt to propose an engine for Continuous and Interactive Learning of Knowledge (CILK) for dialogue systems to give them the ability to continuously and interactively learn and infer new knowledge during conversations. With more knowledge accumulated over time, they will be able to learn better and answer more questions. Our empirical evaluation shows that CILK is promising.
Capsule Networks Need an Improved Routing Algorithm
Venue: arXiv cs.CV 2019
Year: 2019

In capsule networks, the routing algorithm connects capsules in consecutive layers, enabling the upper-level capsules to learn higher-level concepts by combining the concepts of the lower-level capsules. Capsule networks are known to have a few advantages over conventional neural networks, including robustness to 3D viewpoint changes and generalization capability. However, some studies have reported negative experimental results. Nevertheless, the reason for this phenomenon has not been analyzed yet. We empirically analyzed the effect of five different routing algorithms. The experimental results show that the routing algorithms do not behave as expected and often produce results that are worse than simple baseline algorithms that assign the connection strengths uniformly or randomly. We also show that, in most cases, the routing algorithms do not change the classification result but polarize the link strengths, and the polarization can be extreme when they continue to repeat without stopping. In order to realize the true potential of the capsule network, it is essential to develop an improved routing algorithm.
A Process Algebra for Link Layer Protocols
Venue: arXiv cs.NI 2019
Year: 2019

We propose a process algebra for link layer protocols, featuring a unique mechanism for modelling frame collisions. We also formalise suitable liveness properties for link layer protocols specified in this framework. To show applicability we model and analyse two versions of the Carrier-Sense Multiple Access with Collision Avoidance (CSMA/CA) protocol. Our analysis confirms the hidden station problem for the version without virtual carrier sensing. However, we show that the version with virtual carrier sensing not only overcomes this problem, but also the exposed station problem with probability 1. Yet the protocol cannot guarantee packet delivery, not even with probability 1.
Reward Testing Equivalences for Processes
Venue: arXiv cs.LO 2019
Year: 2019

May and must testing were introduced by De Nicola and Hennessy to define semantic equivalences on processes. May-testing equivalence exactly captures safety properties, and must-testing equivalence liveness properties. This paper proposes reward testing and shows that the resulting semantic equivalence also captures conditional liveness properties. It is strictly finer than both the may- and must-testing equivalence.
On the difficulty of learning and predicting the long-term dynamics of bouncing objects
Venue: arXiv cs.CV 2019
Year: 2019

The ability to accurately predict the surrounding environment is a foundational principle of intelligence in biological and artificial agents. In recent years, a variety of approaches have been proposed for learning to predict the physical dynamics of objects interacting in a visual scene. Here we conduct a systematic empirical evaluation of several state-of-the-art unsupervised deep learning models that are considered capable of learning the spatio-temporal structure of a popular dataset composed by synthetic videos of bouncing objects. We show that most of the models indeed obtain high accuracy on the standard benchmark of predicting the next frame of a sequence, and one of them even achieves state-of-the-art performance. However, all models fall short when probed with the more challenging task of generating multiple successive frames. Our results show that the ability to perform short-term predictions does not imply that the model has captured the underlying structure and dynamics of the visual environment, thereby calling for a careful rethinking of the metrics commonly adopted for evaluating temporal models. We also investigate whether the learning outcome could be affected by the use of curriculum-based teaching.
A novel framework of the fuzzy c-means distances problem based weighted distance
Venue: arXiv cs.LG 2019
Year: 2019

Clustering is one of the major roles in data mining that is widely application in pattern recognition and image segmentation. Fuzzy C-means (FCM) is the most used clustering algorithm that proven efficient, fast and easy to implement, however, FCM uses the Euclidean distance that often leads to clustering errors, especially when handling multidimensional and noisy data. In the last few years, many distances metric have been proposed by researchers to improve the performance of the FCM algorithms, and the majority of researchers propose weighted distance. In this paper, we proposed Canberra Weighted Distance to improved performance of the FCM algorithm. The experimental result using the UCI data set show the proposed method is superior to the original method and other clustering methods.
Optimal Attacks on Reinforcement Learning Policies
Venue: arXiv cs.LG 2019
Year: 2019

Control policies, trained using the Deep Reinforcement Learning, have been recently shown to be vulnerable to adversarial attacks introducing even very small perturbations to the policy input. The attacks proposed so far have been designed using heuristics, and build on existing adversarial example crafting techniques used to dupe classifiers in supervised learning. In contrast, this paper investigates the problem of devising optimal attacks, depending on a well-defined attacker's objective, e.g., to minimize the main agent average reward. When the policy and the system dynamics, as well as rewards, are known to the attacker, a scenario referred to as a white-box attack, designing optimal attacks amounts to solving a Markov Decision Process. For what we call black-box attacks, where neither the policy nor the system is known, optimal attacks can be trained using Reinforcement Learning techniques. Through numerical experiments, we demonstrate the efficiency of our attacks compared to existing attacks (usually based on Gradient methods). We further quantify the potential impact of attacks and establish its connection to the smoothness of the policy under attack. Smooth policies are naturally less prone to attacks (this explains why Lipschitz policies, with respect to the state, are more resilient). Finally, we show that from the main agent perspective, the system uncertainties and the attacker can be modeled as a Partially Observable Markov Decision Process. We actually demonstrate that using Reinforcement Learning techniques tailored to POMDP (e.g. using Recurrent Neural Networks) leads to more resilient policies.
Improved Pose Graph Optimization for Planar Motions Using Riemannian Geometry on the Manifold of Dual Quaternions
Venue: arXiv cs.RO 2019
Year: 2019

We present a novel Riemannian approach for planar pose graph optimization problems. By formulating the cost function based on the Riemannian metric on the manifold of dual quaternions representing planar motions, the nonlinear structure of the SE(2) group is inherently considered. To solve the on-manifold least squares problem, a Riemannian Gauss-Newton method using the exponential retraction is applied. The proposed Riemannian pose graph optimizer (RPG-Opt) is further evaluated based on public planar pose graph data sets. Compared with state-of-the-art frameworks, the proposed method gives equivalent accuracy and better convergence robustness under large uncertainties of odometry measurements.
Critical Reflections on Visualization Authoring Systems
Venue: arXiv cs.HC 2019
Year: 2019

An emerging generation of visualization authoring systems support expressive information visualization without textual programming. As they vary in their visualization models, system architectures, and user interfaces, it is challenging to directly compare these systems using traditional evaluative methods. Recognizing the value of contextualizing our decisions in the broader design space, we present critical reflections on three systems we developed -- Lyra, Data Illustrator, and Charticulator. This paper surfaces knowledge that would have been daunting within the constituent papers of these three systems. We compare and contrast their (previously unmentioned) limitations and trade-offs between expressivity and learnability. We also reflect on common assumptions that we made during the development of our systems, thereby informing future research directions in visualization authoring systems.
Regular languages, derivatives and finite automata
Venue: arXiv cs.FL 2019
Year: 2019

This report is mostly written for educational purposes. It is meant as a self contained introduction to regular languages, regular expressions, and regular expression matching by using Brzozowski derivatives. As such it is mostly based on the work by Brzozowski[4] and Owens et al.[12] The language basics material have been inspired by books[2] and web material[16]. Chapter 1 introduces the fundamental concepts of formal languages, as well as the idea of string derivatives. In chapter 2 we define the class of regular languages, and further develops the theory of derivatives for that class. We use derivatives to prove the Myhill-Nerod theorem, the Pumping lemma, and the closure of regular languages under all Boolean connectives. In chapter 3 we introduce regular expressions and regular expression matching. Chapter 4 connects the theory of regular languages and derivatives with that of finite automata. Chapter 5 looks at the concept of anchors, and how this can be incorporated into a matcher based on derivatives. Chapter 6 discusses submatching using derivatives with an approach inspired by Laurikari and his work on tagged transitions[11]. This is the part we consider as our main contribution to the field. In the last chapter, chapter 7, we summarize by giving a regular expression matching algorithm using the previously discussed techniques. We also discuss related work by others.
Binary component decomposition Part II: The asymmetric case
Venue: arXiv cs.DS 2019
Year: 2019

This paper studies the problem of decomposing a low-rank matrix into a factor with binary entries, either from $\{\pm 1\}$ or from $\{0,1\}$, and an unconstrained factor. The research answers fundamental questions about the existence and uniqueness of these decompositions. It also leads to tractable factorization algorithms that succeed under a mild deterministic condition. This work builds on a companion paper that addresses the related problem of decomposing a low-rank positive-semidefinite matrix into symmetric binary factors.
Learning Effective Embeddings From Crowdsourced Labels: An Educational Case Study
Venue: arXiv cs.HC 2019
Year: 2019

Learning representation has been proven to be helpful in numerous machine learning tasks. The success of the majority of existing representation learning approaches often requires a large amount of consistent and noise-free labels. However, labels are not accessible in many real-world scenarios and they are usually annotated by the crowds. In practice, the crowdsourced labels are usually inconsistent among crowd workers given their diverse expertise and the number of crowdsourced labels is very limited. Thus, directly adopting crowdsourced labels for existing representation learning algorithms is inappropriate and suboptimal. In this paper, we investigate the above problem and propose a novel framework of \textbf{R}epresentation \textbf{L}earning with crowdsourced \textbf{L}abels, i.e., "RLL", which learns representation of data with crowdsourced labels by jointly and coherently solving the challenges introduced by limited and inconsistent labels. The proposed representation learning framework is evaluated in two real-world education applications. The experimental results demonstrate the benefits of our approach on learning representation from limited labeled data from the crowds, and show RLL is able to outperform state-of-the-art baselines. Moreover, detailed experiments are conducted on RLL to fully understand its key components and the corresponding performance.