OpenRaiser/Intern-Atlas huggingface dataset:
Uncertainty Quantification by Ensemble Learning for Computational Optical Form Measurements
Venue: arXiv cs.LG 2021
Year: 2021

Uncertainty quantification by ensemble learning is explored in terms of an application from computational optical form measurements. The application requires to solve a large-scale, nonlinear inverse problem. Ensemble learning is used to extend a recently developed deep learning approach for this application in order to provide an uncertainty quantification of its predicted solution to the inverse problem. By systematically inserting out-of-distribution errors as well as noisy data the reliability of the developed uncertainty quantification is explored. Results are encouraging and the proposed application exemplifies the ability of ensemble methods to make trustworthy predictions on high dimensional data in a real-world application.
DEUS: A Data-driven Approach to Estimate User Satisfaction in Multi-turn Dialogues
Venue: arXiv cs.CL 2021
Year: 2021

Digital assistants are experiencing rapid growth due to their ability to assist users with day-to-day tasks where most dialogues are happening multi-turn. However, evaluating multi-turn dialogues remains challenging, especially at scale. We suggest a context-sensitive method to estimate the turn-level satisfaction for dialogue considering various types of user preferences. The costs of interactions between users and dialogue systems are formulated using a budget consumption concept. We assume users have an initial interaction budget for a dialogue formed based on the task complexity and that each turn has a cost. When the task is completed, or the budget has been exhausted, users quit the dialogue. We demonstrate our method's effectiveness by extensive experimentation with a simulated dialogue platform and real multi-turn dialogues.
Accelerating Distributed-Memory Autotuning via Statistical Analysis of Execution Paths
Venue: arXiv cs.DC 2021
Year: 2021

The prohibitive expense of automatic performance tuning at scale has largely limited the use of autotuning to libraries for shared-memory and GPU architectures. We introduce a framework for approximate autotuning that achieves a desired confidence in each algorithm configuration's performance by constructing confidence intervals to describe the performance of individual kernels (subroutines of benchmarked programs). Once a kernel's performance is deemed sufficiently predictable for a set of inputs, subsequent invocations are avoided and replaced with a predictive model of the execution time. We then leverage online execution path analysis to coordinate selective kernel execution and propagate each kernel's statistical profile. This strategy is effective in the presence of frequently-recurring computation and communication kernels, which is characteristic to algorithms in numerical linear algebra. We encapsulate this framework as part of a new profiling tool, Critter, that automates kernel execution decisions and propagates statistical profiles along critical paths of execution. We evaluate performance prediction accuracy obtained by our selective execution methods using state-of-the-art distributed-memory implementations of Cholesky and QR factorization on Stampede2, and demonstrate speed-ups of up to 7.1x with 98% prediction accuracy.
SWIS -- Shared Weight bIt Sparsity for Efficient Neural Network Acceleration
Venue: arXiv cs.LG 2021
Year: 2021

Quantization is spearheading the increase in performance and efficiency of neural network computing systems making headway into commodity hardware. We present SWIS - Shared Weight bIt Sparsity, a quantization framework for efficient neural network inference acceleration delivering improved performance and storage compression through an offline weight decomposition and scheduling algorithm. SWIS can achieve up to 54.3% (19.8%) point accuracy improvement compared to weight truncation when quantizing MobileNet-v2 to 4 (2) bits post-training (with retraining) showing the strength of leveraging shared bit-sparsity in weights. SWIS accelerator gives up to 6x speedup and 1.9x energy improvement overstate of the art bit-serial architectures.
Multi-Party Proof Generation in QAP-based zk-SNARKs
Venue: arXiv cs.CR 2021
Year: 2021

Zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) allows a party, known as the prover, to convince another party, known as the verifier, that he knows a private value $v$, without revealing it, such that $F(u,v)=y$ for some function $F$ and public values $u$ and $y$. There are various versions of zk-SNARK, among them, Quadratic Arithmetic Program (QAP)-based zk-SNARK has been widely used in practice, specially in Blockchain technology. This is attributed to two desirable features; its fixed-size proof and the very light computation load of the verifier. However, the computation load of the prover in QAP-based zkSNARKs, is very heavy, even-though it is designed to be very efficient. This load can be beyond the prover's computation power to handle, and has to be offloaded to some external servers. In the existing offloading solutions, either (i) the load of computation, offloaded to each sever, is a fraction of the prover's primary computation (e.g., DZIK), however the servers need to be trusted, (ii) the servers are not required to be trusted, but the computation complexity imposed to each one is the same as the prover's primary computation (e.g., Trinocchio). In this paper, we present a scheme, which has the benefits of both solutions. In particular, we propose a secure multi-party proof generation algorithm where the prover can delegate its task to $N $ servers, where (i) even if a group of $T \in \mathbb{N}$ servers, $T\le N$, collude, they cannot gain any information about the secret value $v$, (ii) the computation complexity of each server is less than $1/(N-T)$ of the prover's primary computation. The design is such that we don't lose the efficiency of the prover's algorithm in the process of delegating the tasks to external servers.
Supporting a Crowd-powered Accessible Online Art Gallery for People with Visual Impairments: A Feasibility Study
Venue: arXiv cs.HC 2021
Year: 2021

While people with visual impairments are interested in artwork as much as their sighted peers, their experience is limited to few selective artworks that are exhibited at certain museums. To enable people with visual impairments to access and appreciate as many artworks as possible at ease, we propose an online art gallery that allows users to explore different parts of a painting displayed on their touchscreen-based devices while listening to corresponding verbal descriptions of the touched part on the screen. To investigate the scalability of our approach, we first explored if anonymous crowd who may not have expertise in art are capable of providing visual descriptions of artwork as a preliminary study. Then we conducted a user study with 9 participants with visual impairments to explore the potential of our system for independent artwork appreciation by assessing if and how well the system supports 4 steps of Feldman Model of Criticism. The findings suggest that visual descriptions of artworks produced by an anonymous crowd are sufficient for people with visual impairments to interpret and appreciate paintings with their own judgments which is different from existing approaches that focused on delivering descriptions and opinions written by art experts. Based on the lessons learned from the study, we plan to collect visual descriptions of a greater number of artwork and distribute our online art gallery publicly to make more paintings accessible for people with visual impairments.
A Kernel Framework to Quantify a Model's Local Predictive Uncertainty under Data Distributional Shifts
Venue: arXiv cs.LG 2021
Year: 2021

Traditional Bayesian approaches for model uncertainty quantification rely on notoriously difficult processes of marginalization over each network parameter to estimate its probability density function (PDF). Our hypothesis is that internal layer outputs of a trained neural network contain all of the information related to both its mapping function (quantified by its weights) as well as the input data distribution. We therefore propose a framework for predictive uncertainty quantification of a trained neural network that explicitly estimates the PDF of its raw prediction space (before activation), p(y'|x,w), which we refer to as the model PDF, in a Gaussian reproducing kernel Hilbert space (RKHS). The Gaussian RKHS provides a localized density estimate of p(y'|x,w), which further enables us to utilize gradient based formulations of quantum physics to decompose the model PDF in terms of multiple local uncertainty moments that provide much greater resolution of the PDF than the central moments characterized by Bayesian methods. This provides the framework with a better ability to detect distributional shifts in test data away from the training data PDF learned by the model. We evaluate the framework against existing uncertainty quantification methods on benchmark datasets that have been corrupted using common perturbation techniques. The kernel framework is observed to provide model uncertainty estimates with much greater precision based on the ability to detect model prediction errors.
Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximation
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we study the dynamics of temporal difference learning with neural network-based value function approximation over a general state space, namely, \emph{Neural TD learning}. We consider two practically used algorithms, projection-free and max-norm regularized Neural TD learning, and establish the first convergence bounds for these algorithms. An interesting observation from our results is that max-norm regularization can dramatically improve the performance of TD learning algorithms, both in terms of sample complexity and overparameterization. In particular, we prove that max-norm regularization improves state-of-the-art sample complexity and overparameterization bounds. The results in this work rely on a novel Lyapunov drift analysis of the network parameters as a stopped and controlled random process.
The Fusemate Logic Programming System (System Description)
Venue: arXiv cs.LO 2021
Year: 2021

Fusemate is a logic programming system that implements the possible model semantics for disjunctive logic programs. Its input language is centered around a weak notion of stratification with comprehension and aggregation operators on top of it. Fusemate is implemented as a shallow embedding in the Scala programming language. This enables using Scala data types natively as terms, a tight interface with external systems, and it makes model computation available as an ordinary container data structure constructor. The paper describes the above features and demonstrates them with a non-trivial use-case, the embedding of the description logic $\cal ALCIF$ into Fusemate's input language This version of the paper corrects an error in the published version, which used an unsuitable version of "blocking" in the $\cal ALCIF$ embedding.
ForceNet: A Graph Neural Network for Large-Scale Quantum Calculations
Venue: arXiv cs.LG 2021
Year: 2021

With massive amounts of atomic simulation data available, there is a huge opportunity to develop fast and accurate machine learning models to approximate expensive physics-based calculations. The key quantity to estimate is atomic forces, where the state-of-the-art Graph Neural Networks (GNNs) explicitly enforce basic physical constraints such as rotation-covariance. However, to strictly satisfy the physical constraints, existing models have to make tradeoffs between computational efficiency and model expressiveness. Here we explore an alternative approach. By not imposing explicit physical constraints, we can flexibly design expressive models while maintaining their computational efficiency. Physical constraints are implicitly imposed by training the models using physics-based data augmentation. To evaluate the approach, we carefully design a scalable and expressive GNN model, ForceNet, and apply it to OC20 (Chanussot et al., 2020), an unprecedentedly-large dataset of quantum physics calculations. Our proposed ForceNet is able to predict atomic forces more accurately than state-of-the-art physics-based GNNs while being faster both in training and inference. Overall, our promising and counter-intuitive results open up an exciting avenue for future research.
ActiveGuard: An Active DNN IP Protection Technique via Adversarial Examples
Venue: arXiv cs.CR 2021
Year: 2021

The training of Deep Neural Networks (DNN) is costly, thus DNN can be considered as the intellectual properties (IP) of model owners. To date, most of the existing protection works focus on verifying the ownership after the DNN model is stolen, which cannot resist piracy in advance. To this end, we propose an active DNN IP protection method based on adversarial examples against DNN piracy, named ActiveGuard. ActiveGuard aims to achieve authorization control and users' fingerprints management through adversarial examples, and can provide ownership verification. Specifically, ActiveGuard exploits the elaborate adversarial examples as users' fingerprints to distinguish authorized users from unauthorized users. Legitimate users can enter fingerprints into DNN for identity authentication and authorized usage, while unauthorized users will obtain poor model performance due to an additional control layer. In addition, ActiveGuard enables the model owner to embed a watermark into the weights of DNN. When the DNN is illegally pirated, the model owner can extract the embedded watermark and perform ownership verification. Experimental results show that, for authorized users, the test accuracy of LeNet-5 and Wide Residual Network (WRN) models are 99.15% and 91.46%, respectively, while for unauthorized users, the test accuracy of the two DNNs are only 8.92% (LeNet-5) and 10% (WRN), respectively. Besides, each authorized user can pass the fingerprint authentication with a high success rate (up to 100%). For ownership verification, the embedded watermark can be successfully extracted, while the normal performance of the DNN model will not be affected. Further, ActiveGuard is demonstrated to be robust against fingerprint forgery attack, model fine-tuning attack and pruning attack.
Signal recovery from a few linear measurements of its high-order spectra
Venue: arXiv cs.IT 2021
Year: 2021

The $q$-th order spectrum is a polynomial of degree $q$ in the entries of a signal $x\in\mathbb{C}^N$, which is invariant under circular shifts of the signal. For $q\geq 3$, this polynomial determines the signal uniquely, up to a circular shift, and is called a high-order spectrum. The high-order spectra, and in particular the bispectrum ($q=3$) and the trispectrum ($q=4$), play a prominent role in various statistical signal processing and imaging applications, such as phase retrieval and single-particle reconstruction. However, the dimension of the $q$-th order spectrum is $N^{q-1}$, far exceeding the dimension of $x$, leading to increased computational load and storage requirements. In this work, we show that it is unnecessary to store and process the full high-order spectra: a signal can be characterized uniquely, up to symmetries, from only $N+1$ linear measurements of its high-order spectra. The proof relies on tools from algebraic geometry and is corroborated by numerical experiments.
Dynamic Verification of C/C++11 Concurrency over Multi Copy Atomics
Venue: arXiv cs.PL 2021
Year: 2021

We investigate the problem of runtime analysis of C11 programs under Multi-Copy-Atomic semantics (MCA). Under MCA, one can analyze program outcomes solely through interleaving and reordering of thread events. As a result, obtaining intuitive explanations of program outcomes becomes straightforward. Newer versions of ARM (ARMv8 and later), Alpha, and Intel's x-86 support MCA. Our tests reveal that state-of-the-art dynamic verification techniques that analyze program executions under the C11 memory model generate safety property violations that can be interpreted as false alarms under MCA semantics. Sorting the true from false violations puts an undesirable burden on the user. In this work, we provide a dynamic verification technique (MoCA) to analyze C11 program executions which are permitted under the MCA model. We design a happens-before relation and introduce coherence rules to capture precisely those C11 program executions which are allowed under the MCA model. MoCA's exploration of the state-space is based on the state-of-the-art dynamic verification algorithm, source-DPOR. Our experiments validate that MoCA captures all coherent C11 program executions, and is precise for the MCA model.
Efficient Encoding Algorithm of Binary and Non-Binary LDPC Codes Using Block Triangulation
Venue: arXiv cs.IT 2021
Year: 2021

We propose an efficient encoding algorithm for the binary and non-binary low-density parity-check codes. This algorithm transforms the parity part of the parity-check matrix into a block triangular matrix with low weight diagonal submatrices by row and column permutations in the preprocessing stage. This algorithm determines the parity part of a codeword by block back-substitution to reduce the encoding complexity in the encoding stage. Numerical experiments show that this algorithm has a lower encoding complexity than existing encoding algorithms. Moreover, we show that this algorithm encodes the non-binary cycle codes in linear time.
Optimal Communication-Computation Trade-Off in Heterogeneous Gradient Coding
Venue: arXiv cs.IT 2021
Year: 2021

Gradient coding allows a master node to derive the aggregate of the partial gradients, calculated by some worker nodes over the local data sets, with minimum communication cost, and in the presence of stragglers. In this paper, for gradient coding with linear encoding, we characterize the optimum communication cost for heterogeneous distributed systems with \emph{arbitrary} data placement, with $s \in \mathbb{N}$ stragglers and $a \in \mathbb{N}$ adversarial nodes. In particular, we show that the optimum communication cost, normalized by the size of the gradient vectors, is equal to $(r-s-2a)^{-1}$, where $r \in \mathbb{N}$ is the minimum number that a data partition is replicated. In other words, the communication cost is determined by the data partition with the minimum replication, irrespective of the structure of the placement. The proposed achievable scheme also allows us to target the computation of a polynomial function of the aggregated gradient matrix. It also allows us to borrow some ideas from approximation computing and propose an approximate gradient coding scheme for the cases when the repetition in data placement is smaller than what is needed to meet the restriction imposed on communication cost or when the number of stragglers appears to be more than the presumed value in the system design.
An Empirical Study of the Landscape of Open Source Projects in Baidu, Alibaba, and Tencent
Venue: arXiv cs.SE 2021
Year: 2021

Open source software has drawn more and more attention from researchers, developers and companies nowadays. Meanwhile, many Chinese technology companies are embracing open source and choosing to open source their projects. Nevertheless, most previous studies are concentrated on international companies such as Microsoft or Google, while the practical values of open source projects of Chinese technology companies remain unclear. To address this issue, we conduct a mixed-method study to investigate the landscape of projects open sourced by three large Chinese technology companies, namely Baidu, Alibaba, and Tencent (BAT). We study the categories and characteristics of open source projects, the developer's perceptions towards open sourcing effort for these companies, and the internationalization effort of their open source projects. We collected 1,000 open source projects that were open sourced by BAT in GitHub and performed an online survey that received 101 responses from developers of these projects. Some key findings include: 1) BAT prefer to open source frontend development projects, 2) 88\% of the respondents are positive towards open sourcing software projects in their respective companies, 3) 64\% of the respondents reveal that the most common motivations for BAT to open source their projects are the desire to gain fame, expand their influence and gain recruitment advantage, 4) respondents believe that the most common internationalization effort is "providing an English version of readme files", 5) projects with more internationalization effort (i.e., include an English readme file) are more popular. Our findings provide directions for software engineering researchers and provide practical suggestions to software developers and Chinese technology companies.
Simulation-to-Real domain adaptation with teacher-student learning for endoscopic instrument segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Purpose: Segmentation of surgical instruments in endoscopic videos is essential for automated surgical scene understanding and process modeling. However, relying on fully supervised deep learning for this task is challenging because manual annotation occupies valuable time of the clinical experts. Methods: We introduce a teacher-student learning approach that learns jointly from annotated simulation data and unlabeled real data to tackle the erroneous learning problem of the current consistency-based unsupervised domain adaptation framework. Results: Empirical results on three datasets highlight the effectiveness of the proposed framework over current approaches for the endoscopic instrument segmentation task. Additionally, we provide analysis of major factors affecting the performance on all datasets to highlight the strengths and failure modes of our approach. Conclusion: We show that our proposed approach can successfully exploit the unlabeled real endoscopic video frames and improve generalization performance over pure simulation-based training and the previous state-of-the-art. This takes us one step closer to effective segmentation of surgical tools in the annotation scarce setting.
Open Range Pitch Tracking for Carrier Frequency Difference Estimation from HF Transmitted Speech
Venue: arXiv cs.SD 2021
Year: 2021

In this paper we investigate the task of detecting carrier frequency differences from demodulated single sideband signals by examining the pitch contours of the received baseband speech signal in the short-time spectral domain. From the detected pitch frequency trajectory and its harmonics a carrier frequency difference, which is caused by demodulating the radio signal with the wrong carrier frequency, can be deduced. A computationally efficient realization in the power cepstral domain is presented. The core component, i.e., the pitch tracking algorithm, is shown to perform comparably to a state of the art algorithm. The full carrier frequency difference estimation system is tested on recordings of real transmissions over HF links. A comparison with an existing approach shows improved estimation accuracy, both on short and longer speech utterances
An analytic BRDF for materials with spherical Lambertian scatterers
Venue: arXiv cs.GR 2021
Year: 2021

We present a new analytic BRDF for porous materials comprised of spherical Lambertian scatterers. The BRDF has a single parameter: the albedo of the Lambertian particles. The resulting appearance exhibits strong back scattering and saturation effects that height-field-based models such as Oren-Nayar cannot reproduce.