OpenRaiser/Intern-Atlas huggingface dataset:
Dynamics Based 3D Skeletal Hand Tracking
Venue: arXiv cs.CV 2017
Year: 2017

Tracking the full skeletal pose of the hands and fingers is a challenging problem that has a plethora of applications for user interaction. Existing techniques either require wearable hardware, add restrictions to user pose, or require significant computation resources. This research explores a new approach to tracking hands, or any articulated model, by using an augmented rigid body simulation. This allows us to phrase 3D object tracking as a linear complementarity problem with a well-defined solution. Based on a depth sensor's samples, the system generates constraints that limit motion orthogonal to the rigid body model's surface. These constraints, along with prior motion, collision/contact constraints, and joint mechanics, are resolved with a projected Gauss-Seidel solver. Due to camera noise properties and attachment errors, the numerous surface constraints are impulse capped to avoid overpowering mechanical constraints. To improve tracking accuracy, multiple simulations are spawned at each frame and fed a variety of heuristics, constraints and poses. A 3D error metric selects the best-fit simulation, helping the system handle challenging hand motions. Such an approach enables real-time, robust, and accurate 3D skeletal tracking of a user's hand on a variety of depth cameras, while only utilizing a single x86 CPU core for processing.
On the computational complexity of dynamic slicing problems for program schemas
Venue: arXiv cs.PL 2017
Year: 2017

Given a program, a quotient can be obtained from it by deleting zero or more statements. The field of program slicing is concerned with computing a quotient of a program which preserves part of the behaviour of the original program. All program slicing algorithms take account of the structural properties of a program such as control dependence and data dependence rather than the semantics of its functions and predicates, and thus work, in effect, with program schemas. The dynamic slicing criterion of Korel and Laski requires only that program behaviour is preserved in cases where the original program follows a particular path, and that the slice/quotient follows this path. In this paper we formalise Korel and Laski's definition of a dynamic slice as applied to linear schemas, and also formulate a less restrictive definition in which the path through the original program need not be preserved by the slice. The less restrictive definition has the benefit of leading to smaller slices. For both definitions, we compute complexity bounds for the problems of establishing whether a given slice of a linear schema is a dynamic slice and whether a linear schema has a non-trivial dynamic slice and prove that the latter problem is NP-hard in both cases. We also give an example to prove that minimal dynamic slices (whether or not they preserve the original path) need not be unique.
What does it all mean? Capturing Semantics of Surgical Data and Algorithms with Ontologies
Venue: arXiv cs.CY 2017
Year: 2017

Every year approximately 234 million major surgeries are performed, leading to plentiful, highly diverse data. This is accompanied by a matching number of novel algorithms for the surgical domain. To garner all benefits of surgical data science it is necessary to have an unambiguous, shared understanding of algorithms and data. This includes inputs and outputs of algorithms and thus their function, but also the semantic content, i.e. meaning of data such as patient parameters. We therefore propose the establishment of a new ontology for data and algorithms in surgical data science. Such an ontology can be used to provide common data sets for the community, encouraging sharing of knowledge and comparison of algorithms on common data. We hold that this is a necessary foundation towards new methods for applications such as semantic-based content retrieval and similarity measures and that it is overall vital for the future of surgical data science.
Online Factorization and Partition of Complex Networks From Random Walks
Venue: arXiv cs.LG 2017
Year: 2017

Finding the reduced-dimensional structure is critical to understanding complex networks. Existing approaches such as spectral clustering are applicable only when the full network is explicitly observed. In this paper, we focus on the online factorization and partition of implicit large-scale networks based on observations from an associated random walk. We formulate this into a nonconvex stochastic factorization problem and propose an efficient and scalable stochastic generalized Hebbian algorithm. The algorithm is able to process dependent state-transition data dynamically generated by the underlying network and learn a low-dimensional representation for each vertex. By applying a diffusion approximation analysis, we show that the continuous-time limiting process of the stochastic algorithm converges globally to the "principal components" of the Markov chain and achieves a nearly optimal sample complexity. Once given the learned low-dimensional representations, we further apply clustering techniques to recover the network partition. We show that when the associated Markov process is lumpable, one can recover the partition exactly with high probability. We apply the proposed approach to model the traffic flow of Manhattan as city-wide random walks. By using our algorithm to analyze the taxi trip data, we discover a latent partition of the Manhattan city that closely matches the traffic dynamics.
The pulse of the city through Twitter: relationships between land use and spatiotemporal demographics
Venue: arXiv cs.CY 2017
Year: 2017

Social network data offer interesting opportunities in urban studies. In this study, we used Twitter data to analyse city dynamics over the course of the day. Users of this social network were grouped according to city zone and time slot in order to analyse the daily dynamics of the city and the relationship between this and land use. First, daytime activity in each zone was compared with activity at night in order to determine which zones showed increased activity in each of the time slots. Then, typical Twitter activity profiles were obtained based on the predominant land use in each zone, indicating how land uses linked to activities were activated during the day, but at different rates depending on the type of land use. Lastly, a multiple regression analysis was performed to determine the influence of the different land uses on each of the major time slots (morning, afternoon, evening and night) through their changing coefficients. Activity tended to decrease throughout the day for most land uses (e.g. offices, education, health and transport), but remained constant in parks and increased in retail and residential zones. Our results show that social network data can be used to improve our understanding of the link between land use and urban dynamics.
GP-Unet: Lesion Detection from Weak Labels with a 3D Regression Network
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel convolutional neural network for lesion detection from weak labels. Only a single, global label per image - the lesion count - is needed for training. We train a regression network with a fully convolutional architecture combined with a global pooling layer to aggregate the 3D output into a scalar indicating the lesion count. When testing on unseen images, we first run the network to estimate the number of lesions. Then we remove the global pooling layer to compute localization maps of the size of the input image. We evaluate the proposed network on the detection of enlarged perivascular spaces in the basal ganglia in MRI. Our method achieves a sensitivity of 62% with on average 1.5 false positives per image. Compared with four other approaches based on intensity thresholding, saliency and class maps, our method has a 20% higher sensitivity.
Sensing discomfort of standing passengers in public rail transportation systems using a smart phone
Venue: arXiv cs.HC 2017
Year: 2017

This paper aims to investigate the effect of acceleration on the discomfort of standing passengers. The acceleration levels from different public rail transport lines such as the mass rapid transits (MRTs) and light rail transits (LRTs) of Singapore, as well as the associated qualitative data indicating the discomfort of standing passengers were collected and analyzed. Based on a logistic regression model to analyze the data, a discomfort index was introduced, which can be used to compare various rail lines based on ride comfort. A method for predicting the discomfort of passengers based on the acceleration values was proposed for any given train line.
Parallel Stochastic Gradient Descent with Sound Combiners
Venue: arXiv cs.LG 2017
Year: 2017

Stochastic gradient descent (SGD) is a well known method for regression and classification tasks. However, it is an inherently sequential algorithm at each step, the processing of the current example depends on the parameters learned from the previous examples. Prior approaches to parallelizing linear learners using SGD, such as HOGWILD! and ALLREDUCE, do not honor these dependencies across threads and thus can potentially suffer poor convergence rates and/or poor scalability. This paper proposes SYMSGD, a parallel SGD algorithm that, to a first-order approximation, retains the sequential semantics of SGD. Each thread learns a local model in addition to a model combiner, which allows local models to be combined to produce the same result as what a sequential SGD would have produced. This paper evaluates SYMSGD's accuracy and performance on 6 datasets on a shared-memory machine shows upto 11x speedup over our heavily optimized sequential baseline on 16 cores and 2.2x, on average, faster than HOGWILD!.
Isomorphism between Differential and Moment Invariants under Affine Transform
Venue: arXiv cs.CV 2017
Year: 2017

The invariant is one of central topics in science, technology and engineering. The differential invariant is essential in understanding or describing some important phenomena or procedures in mathematics, physics, chemistry, biology or computer science etc. The derivation of differential invariants is usually difficult or complicated. This paper reports a discovery that under the affine transform, differential invariants have similar structures with moment invariants up to a scalar function of transform parameters. If moment invariants are known, relative differential invariants can be obtained by the substitution of moments by derivatives with the same order. Whereas moment invariants can be calculated by multiple integrals, this method provides a simple way to derive differential invariants without the need to resolve any equation system. Since the definition of moments on different manifolds or in different dimension of spaces is well established, differential invariants on or in them will also be well defined. Considering that moments have a strong background in mathematics and physics, this technique offers a new view angle to the inner structure of invariants. Projective differential invariants can also be found in this way with a screening process.
Countermeasure against Side-Channel Attack in Shared Memory of TrustZone
Venue: arXiv cs.CR 2017
Year: 2017

In this paper we introduced countermeasures against side-channel attacks in the shared memory of TrustZone. We proposed zero-contention cache memory or policy between REE and TEE to prevent from TruSpy attacks in TrustZone. And we suggested that delay time of data path of REE is equal or similar to that of data path of TEE to prevent timing side-channel attacks. Also, we proposed security information flow control based on the Clark-Wilson model, and built the information flow control mechanism using Authentication Tokenization Program (ATP). Accordingly we can expect the improved integrity of the information content between REE and TEE on mobile devices.
Learning Efficient Tensor Representations with Ring Structure Networks
Venue: arXiv cs.NA 2017
Year: 2017

Tensor train (TT) decomposition is a powerful representation for high-order tensors, which has been successfully applied to various machine learning tasks in recent years. However, since the tensor product is not commutative, permutation of data dimensions makes solutions and TT-ranks of TT decomposition inconsistent. To alleviate this problem, we propose a permutation symmetric network structure by employing circular multilinear products over a sequence of low-order core tensors. This network structure can be graphically interpreted as a cyclic interconnection of tensors, and thus we call it tensor ring (TR) representation. We develop several efficient algorithms to learn TR representation with adaptive TR-ranks by employing low-rank approximations. Furthermore, mathematical properties are investigated, which enables us to perform basic operations in a computationally efficiently way by using TR representations. Experimental results on synthetic signals and real-world datasets demonstrate that the proposed TR network is more expressive and consistently informative than existing TT networks.
Behavior of digital sequences through exotic numeration systems
Venue: arXiv cs.DM 2017
Year: 2017

Many digital functions studied in the literature, e.g., the summatory function of the base-$k$ sum-of-digits function, have a behavior showing some periodic fluctuation. Such functions are usually studied using techniques from analytic number theory or linear algebra. In this paper we develop a method based on exotic numeration systems and we apply it on two examples motivated by the study of generalized Pascal triangles and binomial coefficients of words.
Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers
Venue: arXiv cs.DC 2017
Year: 2017

We analyze the caching overhead incurred by a class of multithreaded algorithms when scheduled by an arbitrary scheduler. We obtain bounds that match or improve upon the well-known $O(Q+S \cdot (M/B))$ caching cost for the randomized work stealing (RWS) scheduler, where $S$ is the number of steals, $Q$ is the sequential caching cost, and $M$ and $B$ are the cache size and block (or cache line) size respectively.
Continual Learning in Generative Adversarial Nets
Venue: arXiv cs.LG 2017
Year: 2017

Developments in deep generative models have allowed for tractable learning of high-dimensional data distributions. While the employed learning procedures typically assume that training data is drawn i.i.d. from the distribution of interest, it may be desirable to model distinct distributions which are observed sequentially, such as when different classes are encountered over time. Although conditional variations of deep generative models permit multiple distributions to be modeled by a single network in a disentangled fashion, they are susceptible to catastrophic forgetting when the distributions are encountered sequentially. In this paper, we adapt recent work in reducing catastrophic forgetting to the task of training generative adversarial networks on a sequence of distinct distributions, enabling continual generative modeling.
On The Multiparty Communication Complexity of Testing Triangle-Freeness
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs. We consider the $\textit{coordinator}$ model, where we have $k$ players receiving private inputs, and a coordinator who receives no input; the coordinator can communicate with all the players, but the players cannot communicate with each other. In this model, we ask: if an input graph is divided between the players, with each player receiving some of the edges, how many bits do the players and the coordinator need to exchange to determine if the graph is triangle-free, or $\textit{far}$ from triangle-free? For general communication protocols, we show that $\tilde{O}(k(nd)^{1/4}+k^2)$ bits are sufficient to test triangle-freeness in graphs of size $n$ with average degree $d$ (the degree need not be known in advance). For $\textit{simultaneous}$ protocols, where there is only one communication round, we give a protocol that uses $\tilde{O}(k \sqrt{n})$ bits when $d = O(\sqrt{n})$ and $\tilde{O}(k (nd)^{1/3})$ when $d = Ω(\sqrt{n})$; here, again, the average degree $d$ does not need to be known in advance. We show that for average degree $d = O(1)$, our simultaneous protocol is asymptotically optimal up to logarithmic factors. For higher degrees, we are not able to give lower bounds on testing triangle-freeness, but we give evidence that the problem is hard by showing that finding an edge that participates in a triangle is hard, even when promised that at least a constant fraction of the edges must be removed in order to make the graph triangle-free.
The Benefit of Being Flexible in Distributed Computation
Venue: arXiv cs.IT 2017
Year: 2017

In wireless distributed computing, networked nodes perform intermediate computations over data placed in their memory and exchange these intermediate values to calculate function values. In this paper we consider an asymmetric setting where each node has access to a random subset of the data, i.e., we cannot control the data placement. The paper makes a simple point: we can realize significant benefits if we are allowed to be "flexible", and decide which node computes which function, in our system. We make this argument in the case where each function depends on only two of the data messages, as is the case in similarity searches. We establish a percolation in the behavior of the system, where, depending on the amount of observed data, by being flexible, we may need no communication at all.
New methods to generate massive synthetic networks
Venue: arXiv cs.SI 2017
Year: 2017

One of the biggest needs in network science research is access to large realistic datasets. As data analytics methods permeate a range of diverse disciplines---e.g., computational epidemiology, sustainability, social media analytics, biology, and transportation--- network datasets that can exhibit characteristics encountered in each of these disciplines becomes paramount. The key technical issue is to be able to generate synthetic topologies with pre-specified, arbitrary, degree distributions. Existing methods are limited in their ability to faithfully reproduce macro-level characteristics of networks while at the same time respecting particular degree distributions. We present a suite of three algorithms that exploit the principle of residual degree attenuation to generate synthetic topologies that adhere to macro-level real-world characteristics. By evaluating these algorithms w.r.t. several real-world datasets we demonstrate their ability to faithfully reproduce network characteristics such as node degree, clustering coefficient, hop length, and k-core structure distributions.
Uplift Modeling with Multiple Treatments and General Response Types
Venue: arXiv cs.AI 2017
Year: 2017

Randomized experiments have been used to assist decision-making in many areas. They help people select the optimal treatment for the test population with certain statistical guarantee. However, subjects can show significant heterogeneity in response to treatments. The problem of customizing treatment assignment based on subject characteristics is known as uplift modeling, differential response analysis, or personalized treatment learning in literature. A key feature for uplift modeling is that the data is unlabeled. It is impossible to know whether the chosen treatment is optimal for an individual subject because response under alternative treatments is unobserved. This presents a challenge to both the training and the evaluation of uplift models. In this paper we describe how to obtain an unbiased estimate of the key performance metric of an uplift model, the expected response. We present a new uplift algorithm which creates a forest of randomized trees. The trees are built with a splitting criterion designed to directly optimize their uplift performance based on the proposed evaluation method. Both the evaluation method and the algorithm apply to arbitrary number of treatments and general response types. Experimental results on synthetic data and industry-provided data show that our algorithm leads to significant performance improvement over other applicable methods.
A study on exponential-size neighborhoods for the bin packing problem with conflicts
Venue: arXiv cs.DS 2017
Year: 2017

We propose an iterated local search based on several classes of local and large neighborhoods for the bin packing problem with conflicts. This problem, which combines the characteristics of both bin packing and vertex coloring, arises in various application contexts such as logistics and transportation, timetabling, and resource allocation for cloud computing. We introduce $O(1)$ evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighborhoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. The overall method produces solutions of good quality on the classical benchmark instances and scales very well with an increase of problem size. Extensive computational experiments are conducted to measure the respective contribution of each proposed neighborhood. In particular, the 0-cost moves and the large neighborhood based on set covering contribute very significantly to the search. Several research perspectives are open in relation to possible hybridizations with other state-of-the-art mathematical programming heuristics for this problem.
Clinical Intervention Prediction and Understanding using Deep Networks
Venue: arXiv cs.LG 2017
Year: 2017

Real-time prediction of clinical interventions remains a challenge within intensive care units (ICUs). This task is complicated by data sources that are noisy, sparse, heterogeneous and outcomes that are imbalanced. In this paper, we integrate data from all available ICU sources (vitals, labs, notes, demographics) and focus on learning rich representations of this data to predict onset and weaning of multiple invasive interventions. In particular, we compare both long short-term memory networks (LSTM) and convolutional neural networks (CNN) for prediction of five intervention tasks: invasive ventilation, non-invasive ventilation, vasopressors, colloid boluses, and crystalloid boluses. Our predictions are done in a forward-facing manner to enable "real-time" performance, and predictions are made with a six hour gap time to support clinically actionable planning. We achieve state-of-the-art results on our predictive tasks using deep architectures. We explore the use of feature occlusion to interpret LSTM models, and compare this to the interpretability gained from examining inputs that maximally activate CNN outputs. We show that our models are able to significantly outperform baselines in intervention prediction, and provide insight into model learning, which is crucial for the adoption of such models in practice.
Characteristics of On-time and Late Reward Delivery Projects
Venue: arXiv cs.CY 2017
Year: 2017

The crowdfunding market size has increased exponentially, reaching tens of billions of dollars and showing the popularity of crowdfunding. However, according to Kickstarter, 35% backers did not receive rewards on time. To maintain the trust between creators and backers, and sustain the crowdfunding business growth, it is crucial to understand how on-time and late reward delivery projects are different. In this paper, we analyze characteristics of on-time and late reward delivery projects, especially, focusing on project descriptions, creator profiles, and activeness and linguistic patterns of creators and backers. Our analysis reveals that the less complicated a project is and more actively a creator responds to backers, the higher an on-time reward delivery probability is. It shows there are significant differences between on-time and late reward delivery projects.