OpenRaiser/Intern-Atlas huggingface dataset:
Multilevel constructions: coding, packing and geometric uniformity
Venue: arXiv cs.IT 2019
Year: 2019

Lattice and special nonlattice multilevel constellations constructed from binary codes, such as Constructions A, C, and D, have relevant applications in Mathematics (sphere packing) and in Communication (multi-stage decoding and efficient vector quantization). In this work, we explore some properties of Construction C, in particular its geometric uniformity. We then propose a new multilevel construction, inspired by bit interleaved coded modulation (BICM), that we call Construction C*. We investigate the geometric uniformity, laticeness, and minimum distance properties of Construction C* and discuss its superior packing efficiency when compared to Construction C.
Deep Learning with Convolutional Neural Network for Objective Skill Evaluation in Robot-assisted Surgery
Venue: arXiv cs.CV 2019
Year: 2019

With the advent of robot-assisted surgery, the role of data-driven approaches to integrate statistics and machine learning is growing rapidly with prominent interests in objective surgical skill assessment. However, most existing work requires translating robot motion kinematics into intermediate features or gesture segments that are expensive to extract, lack efficiency, and require significant domain-specific knowledge. We propose an analytical deep learning framework for skill assessment in surgical training. A deep convolutional neural network is implemented to map multivariate time series data of the motion kinematics to individual skill levels. We perform experiments on the public minimally invasive surgical robotic dataset, JHU-ISI Gesture and Skill Assessment Working Set (JIGSAWS). Our proposed learning model achieved a competitive accuracy of 92.5%, 95.4%, and 91.3%, in the standard training tasks: Suturing, Needle-passing, and Knot-tying, respectively. Without the need of engineered features or carefully-tuned gesture segmentation, our model can successfully decode skill information from raw motion profiles via end-to-end learning. Meanwhile, the proposed model is able to reliably interpret skills within 1-3 second window, without needing an observation of entire training trial. This study highlights the potentials of deep architectures for an proficient online skill assessment in modern surgical training.
Binary Classification in Unstructured Space With Hypergraph Case-Based Reasoning
Venue: arXiv cs.LG 2019
Year: 2019

Binary classification is one of the most common problem in machine learning. It consists in predicting whether a given element belongs to a particular class. In this paper, a new algorithm for binary classification is proposed using a hypergraph representation. The method is agnostic to data representation, can work with multiple data sources or in non-metric spaces, and accommodates with missing values. As a result, it drastically reduces the need for data preprocessing or feature engineering. Each element to be classified is partitioned according to its interactions with the training set. For each class, a seminorm over the training set partition is learnt to represent the distribution of evidence supporting this class. Empirical validation demonstrates its high potential on a wide range of well-known datasets and the results are compared to the state-of-the-art. The time complexity is given and empirically validated. Its robustness with regard to hyperparameter sensitivity is studied and compared to standard classification methods. Finally, the limitation of the model space is discussed, and some potential solutions proposed.
Laplacian Smoothing Gradient Descent
Venue: arXiv cs.LG 2019
Year: 2019

We propose a class of very simple modifications of gradient descent and stochastic gradient descent. We show that when applied to a large variety of machine learning problems, ranging from logistic regression to deep neural nets, the proposed surrogates can dramatically reduce the variance, allow to take a larger step size, and improve the generalization accuracy. The methods only involve multiplying the usual (stochastic) gradient by the inverse of a positive definitive matrix (which can be computed efficiently by FFT) with a low condition number coming from a one-dimensional discrete Laplacian or its high order generalizations. It also preserves the mean and increases the smallest component and decreases the largest component. The theory of Hamilton-Jacobi partial differential equations demonstrates that the implicit version of the new algorithm is almost the same as doing gradient descent on a new function which (i) has the same global minima as the original function and (ii) is ``more convex". Moreover, we show that optimization algorithms with these surrogates converge uniformly in the discrete Sobolev $H_σ^p$ sense and reduce the optimality gap for convex optimization problems. The code is available at: \url{https://github.com/BaoWangMath/LaplacianSmoothing-GradientDescent}
Extending Recurrent Neural Aligner for Streaming End-to-End Speech Recognition in Mandarin
Venue: arXiv cs.SD 2019
Year: 2019

End-to-end models have been showing superiority in Automatic Speech Recognition (ASR). At the same time, the capacity of streaming recognition has become a growing requirement for end-to-end models. Following these trends, an encoder-decoder recurrent neural network called Recurrent Neural Aligner (RNA) has been freshly proposed and shown its competitiveness on two English ASR tasks. However, it is not clear if RNA can be further improved and applied to other spoken language. In this work, we explore the applicability of RNA in Mandarin Chinese and present four effective extensions: In the encoder, we redesign the temporal down-sampling and introduce a powerful convolutional structure. In the decoder, we utilize a regularizer to smooth the output distribution and conduct joint training with a language model. On two Mandarin Chinese conversational telephone speech recognition (MTS) datasets, our Extended-RNA obtains promising performance. Particularly, it achieves 27.7% character error rate (CER), which is superior to current state-of-the-art result on the popular HKUST task.
Fast Convex Pruning of Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

We develop a fast, tractable technique called Net-Trim for simplifying a trained neural network. The method is a convex post-processing module, which prunes (sparsifies) a trained network layer by layer, while preserving the internal responses. We present a comprehensive analysis of Net-Trim from both the algorithmic and sample complexity standpoints, centered on a fast, scalable convex optimization program. Our analysis includes consistency results between the initial and retrained models before and after Net-Trim application and guarantees on the number of training samples needed to discover a network that can be expressed using a certain number of nonzero terms. Specifically, if there is a set of weights that uses at most $s$ terms that can re-create the layer outputs from the layer inputs, we can find these weights from $\mathcal{O}(s\log N/s)$ samples, where $N$ is the input size. These theoretical results are similar to those for sparse regression using the Lasso, and our analysis uses some of the same recently-developed tools (namely recent results on the concentration of measure and convex analysis). Finally, we propose an algorithmic framework based on the alternating direction method of multipliers (ADMM), which allows a fast and simple implementation of Net-Trim for network pruning and compression.
Semantics of Data Mining Services in Cloud Computing
Venue: arXiv cs.DC 2019
Year: 2019

In recent years with the rise of Cloud Computing, many companies providing services in the cloud, are empowering a new series of services to their catalogue, such as data mining and data processing, taking advantage of the vast computing resources available to them. Different service definition proposals have been put forward to address the problem of describing services in Cloud Computing in a comprehensive way. Bearing in mind that each provider has its own definition of the logic of its services, and specifically of data mining services, it should be pointed out that the possibility of describing services in a flexible way between providers is fundamental in order to maintain the usability and portability of this type of Cloud Computing services. The use of semantic technologies based on the proposal offered by Linked Data for the definition of services, allows the design and modelling of data mining services, achieving a high degree of interoperability. In this article a schema for the definition of data mining services on cloud computing is presented considering all key aspects of service, such as prices, interfaces, Software Level Agreement, instances or data mining workflow, among others. The new schema is based on Linked Data, and it reuses other schemata obtaining a better and more complete definition of the services. In order to validate the completeness of the scheme, a series of data mining services have been created where a set of algorithms such as Random Forest or K-Means are modeled as services. In addition, a dataset has been generated including the definition of the services of several actual Cloud Computing data mining providers, confirming the effectiveness of the schema.
FrankenGAN: Guided Detail Synthesis for Building Mass-Models Using Style-Synchonized GANs
Venue: arXiv cs.GR 2019
Year: 2019

Coarse building mass models are now routinely generated at scales ranging from individual buildings through to whole cities. For example, they can be abstracted from raw measurements, generated procedurally, or created manually. However, these models typically lack any meaningful semantic or texture details, making them unsuitable for direct display. We introduce the problem of automatically and realistically decorating such models by adding semantically consistent geometric details and textures. Building on the recent success of generative adversarial networks (GANs), we propose FrankenGAN, a cascade of GANs to create plausible details across multiple scales over large neighborhoods. The various GANs are synchronized to produce consistent style distributions over buildings and neighborhoods. We provide the user with direct control over the variability of the output. We allow her to interactively specify style via images and manipulate style-adapted sliders to control style variability. We demonstrate our system on several large-scale examples. The generated outputs are qualitatively evaluated via a set of user studies and are found to be realistic, semantically-plausible, and style-consistent.
HybridNet: Integrating Model-based and Data-driven Learning to Predict Evolution of Dynamical Systems
Venue: arXiv cs.AI 2019
Year: 2019

The robotic systems continuously interact with complex dynamical systems in the physical world. Reliable predictions of spatiotemporal evolution of these dynamical systems, with limited knowledge of system dynamics, are crucial for autonomous operation. In this paper, we present HybridNet, a framework that integrates data-driven deep learning and model-driven computation to reliably predict spatiotemporal evolution of a dynamical systems even with in-exact knowledge of their parameters. A data-driven deep neural network (DNN) with Convolutional LSTM (ConvLSTM) as the backbone is employed to predict the time-varying evolution of the external forces/perturbations. On the other hand, the model-driven computation is performed using Cellular Neural Network (CeNN), a neuro-inspired algorithm to model dynamical systems defined by coupled partial differential equations (PDEs). CeNN converts the intricate numerical computation into a series of convolution operations, enabling a trainable PDE solver. With a feedback control loop, HybridNet can learn the physical parameters governing the system's dynamics in real-time, and accordingly adapt the computation models to enhance prediction accuracy for time-evolving dynamical systems. The experimental results on two dynamical systems, namely, heat convection-diffusion system, and fluid dynamical system, demonstrate that the HybridNet produces higher accuracy than the state-of-the-art deep learning based approach.
Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
Venue: arXiv cs.CC 2019
Year: 2019

The prototypical high-dimensional statistics problem entails finding a structured signal in noise. Many of these problems exhibit an intriguing phenomenon: the amount of data needed by all known computationally efficient algorithms far exceeds what is needed for inefficient algorithms that search over all possible structures. A line of work initiated by Berthet and Rigollet in 2013 has aimed to explain these statistical-computational gaps by reducing from conjecturally hard average-case problems in computer science. However, the delicate nature of average-case reductions has limited the applicability of this approach. In this work we introduce several new techniques to give a web of average-case reductions showing strong computational lower bounds based on the planted clique conjecture using natural problems as intermediates. These include tight lower bounds for Planted Independent Set, Planted Dense Subgraph, Sparse Spiked Wigner, Sparse PCA, a subgraph variant of the Stochastic Block Model and a biased variant of Sparse PCA. We also give algorithms matching our lower bounds and identify the information-theoretic limits of the models we consider.
The Rise of Guardians: Fact-checking URL Recommendation to Combat Fake News
Venue: arXiv cs.IR 2019
Year: 2019

A large body of research work and efforts have been focused on detecting fake news and building online fact-check systems in order to debunk fake news as soon as possible. Despite the existence of these systems, fake news is still wildly shared by online users. It indicates that these systems may not be fully utilized. After detecting fake news, what is the next step to stop people from sharing it? How can we improve the utilization of these fact-check systems? To fill this gap, in this paper, we (i) collect and analyze online users called guardians, who correct misinformation and fake news in online discussions by referring fact-checking URLs; and (ii) propose a novel fact-checking URL recommendation model to encourage the guardians to engage more in fact-checking activities. We found that the guardians usually took less than one day to reply to claims in online conversations and took another day to spread verified information to hundreds of millions of followers. Our proposed recommendation model outperformed four state-of-the-art models by 11%~33%. Our source code and dataset are available at https://github.com/nguyenvo09/CombatingFakeNews.
Toxic Code Snippets on Stack Overflow
Venue: arXiv cs.SE 2019
Year: 2019

Online code clones are code fragments that are copied from software projects or online sources to Stack Overflow as examples. Due to an absence of a checking mechanism after the code has been copied to Stack Overflow, they can become toxic code snippets, e.g., they suffer from being outdated or violating the original software license. We present a study of online code clones on Stack Overflow and their toxicity by incorporating two developer surveys and a large-scale code clone detection. A survey of 201 high-reputation Stack Overflow answerers (33% response rate) showed that 131 participants (65%) have ever been notified of outdated code and 26 of them (20%) rarely or never fix the code. 138 answerers (69%) never check for licensing conflicts between their copied code snippets and Stack Overflow's CC BY-SA 3.0. A survey of 87 Stack Overflow visitors shows that they experienced several issues from Stack Overflow answers: mismatched solutions, outdated solutions, incorrect solutions, and buggy code. 85% of them are not aware of CC BY-SA 3.0 license enforced by Stack Overflow, and 66% never check for license conflicts when reusing code snippets. Our clone detection found online clone pairs between 72,365 Java code snippets on Stack Overflow and 111 open source projects in the curated Qualitas corpus. We analysed 2,289 non-trivial online clone candidates. Our investigation revealed strong evidence that 153 clones have been copied from a Qualitas project to Stack Overflow. We found 100 of them (66%) to be outdated, of which 10 were buggy and harmful for reuse. Furthermore, we found 214 code snippets that could potentially violate the license of their original software and appear 7,112 times in 2,427 GitHub projects.
Development of Robust Fractional-Order Reset Control
Venue: arXiv cs.SY 2019
Year: 2019

In this paper, a framework for the combination of robust fractional order CRONE control with non-linear reset is given for both first and second generation CRONE control. General design rules are derived and presented for these CRONE reset controllers. Within this framework, fractional order control allows for better tuning of the open-loop responses on the one hand. On the other, reset control enables a reduction in phase lag and a corresponding increase in phase margin compared to linear control for similar open loop gain profile. Hence, the combination of the two control methods can provide well-tuned open-loop responses that can overcome the fundamental linear control limitation of Bode's gain-phase relationship. Moreover, as established loop-shaping concepts are used in the controller design, CRONE reset can be highly compatible with the industry. The designed CRONE reset controllers are validated on a one degree-of-freedom Lorentz-actuated precision positioning stage. On this setup, CRONE reset control is shown to provide better tracking performance compared to linear CRONE control, which is in agreement with the predicted performance improvement.
Multivariable Iterative Learning Control Design Procedures: from Decentralized to Centralized, Illustrated on an Industrial Printer
Venue: arXiv cs.SY 2019
Year: 2019

Iterative Learning Control (ILC) enables high control performance through learning from measured data, using only limited model knowledge in the form of a nominal parametric model. Robust stability requires robustness to modeling errors, often due to deliberate undermodeling. The aim of this paper is to develop a range of approaches for multivariable ILC, where specific attention is given to addressing interaction. The proposed methods either address the interaction in the nominal model, or as uncertainty, i.e., through robust stability. The result is a range of techniques, including the use of the structured singular value (SSV) and Gershgorin bounds, that provide a different trade-off between modeling requirements, i.e., modeling effort and cost, and achievable performance. This allows control engineers to select the approach that fits the modeling budget and control requirements. This trade-off is demonstrated in a case study on an industrial flatbed printer.
Election Score Can Be Harder Than Winner
Venue: arXiv cs.GT 2019
Year: 2019

Election systems based on scores generally determine the winner by computing the score of each candidate and the winner is the candidate with the best score. It would be natural to expect that computing the winner of an election is at least as hard as computing the score of a candidate. We show that this is not always the case. In particular, we show that for Young elections for dichotomous preferences the winner problem is easy, while determining the score of a candidate is hard. This complexity behavior has not been seen before and is unusual. The easiness of the winner problem for dichotomous Young crucially uses the fact that dichotomous preferences guarantee the transitivity of the majority relation. In addition to dichotomous preferences we also look at single-peaked preferences, the most well-studied domain restriction that guarantees the transitivity of the majority relation. We show that for the three major hard election systems and their natural variants, dichotomous Young is the only case where winner is easy and score is hard. This also solves an open question from Lackner and Peters (AAAI 2017), by providing a polynomial-time algorithm for Dodgson score for single-peaked electorates.
On the Design of Multi-Dimensional Compactly Supported Parseval Framelets with Directional Characteristics
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we propose a new method for the construction of multi-dimensional, wavelet-like families of affine frames, commonly referred to as framelets, with specific directional characteristics, small and compact support in space, directional vanishing moments (DVM), and axial symmetries or anti-symmetries. The framelets we construct arise from readily available refinable functions. The filters defining these framelets have few non-zero coefficients, custom-selected orientations and can act as finite-difference operators.
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli
Venue: arXiv cs.CC 2019
Year: 2019

Resolution over linear equations is a natural extension of the popular resolution refutation system, augmented with the ability to carry out basic counting. Denoted Res(lin_R), this refutation system operates with disjunctions of linear equations with boolean variables over a ring R, to refute unsatisfiable sets of such disjunctions. Beginning in the work of [RT08], through the work of [IS14] which focused on tree-like lower bounds, this refutation system was shown to be fairly strong. Subsequent work (cf.[Kra17, IS14, KO18, GK18]) made it evident that establishing lower bounds against general Res(lin_R) refutations is a challenging and interesting task since the system captures a 'minimal' extension of resolution with counting gates for which no super-polynomial lower bounds are known to date. We provide the first super-polynomial size lower bounds on general (dag-like) resolution over linear equations refutations in the large characteristic regime. In particular we prove that the subset-sum principle 1+x1+...+2^n xn=0 requires refutations of exponential size over Q. Our proof technique is nontrivial and novel: roughly speaking, we show that under certain conditions every refutation of a subset-sum instance f=0 must pass through a fat clause containing an equation f=alpha for each alpha in the image of f under boolean assignments. We develop a somewhat different approach to prove exponential lower bounds against tree-like refutations of any subset-sum instance that depends on n variables, hence also separating tree-like from dag-like refutations over the rationals. (Abstract continued in the full paper.)
Parameterized algorithms and data reduction for the short secluded $s$-$t$-path problem
Venue: arXiv cs.DS 2019
Year: 2019

Given a graph $G=(V,E)$, two vertices $s,t\in V$, and two integers $k,\ell$, the Short Secluded Path problem is to find a simple $s$-$t$-path with at most $k$ vertices and $\ell$ neighbors. We study the parameterized complexity of the problem with respect to four structural graph parameters: the vertex cover number, treewidth, feedback vertex number, and feedback edge number. In particular, we completely settle the question of the existence of problem kernels with size polynomial in these parameters and their combinations with $k$ and $\ell$. We also obtain a $2^{O(w)}\cdot \ell^2\cdot n$-time algorithm for graphs of treewidth $w$, which yields subexponential-time algorithms in several graph classes.