OpenRaiser/Intern-Atlas huggingface dataset:
Degree-restricted strength decompositions and algebraic branching programs
Venue: arXiv cs.CC 2022
Year: 2022

We analyze Kumar's recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that gives better bounds in some cases. The lower bound relies on Noether-Lefschetz type conditions on the hypersurface defined by the homogeneous polynomial. In the explicit example that we provide, the lower bound is proved resorting to classical intersection theory. Furthermore, we use similar methods to improve the known lower bound methods for slice rank of polynomials. We consider a sequence of polynomials that have been studied before by Shioda and show that for these polynomials the improved lower bound matches the known upper bound.
UnrealNAS: Can We Search Neural Architectures with Unreal Data?
Venue: arXiv cs.CV 2022
Year: 2022

Neural architecture search (NAS) has shown great success in the automatic design of deep neural networks (DNNs). However, the best way to use data to search network architectures is still unclear and under exploration. Previous work has analyzed the necessity of having ground-truth labels in NAS and inspired broad interest. In this work, we take a further step to question whether real data is necessary for NAS to be effective. The answer to this question is important for applications with limited amount of accessible data, and can help people improve NAS by leveraging the extra flexibility of data generation. To explore if NAS needs real data, we construct three types of unreal datasets using: 1) randomly labeled real images; 2) generated images and labels; and 3) generated Gaussian noise with random labels. These datasets facilitate to analyze the generalization and expressivity of the searched architectures. We study the performance of architectures searched on these constructed datasets using popular differentiable NAS methods. Extensive experiments on CIFAR, ImageNet and CheXpert show that the searched architectures can achieve promising results compared with those derived from the conventional NAS pipeline with real labeled data, suggesting the feasibility of performing NAS with unreal data.
Tangle 2.0 Leaderless Nakamoto Consensus on the Heaviest DAG
Venue: arXiv cs.DC 2022
Year: 2022

We introduce the theoretical foundations of the Tangle 2.0, a probabilistic leaderless consensus protocol based on a directed acyclic graph (DAG) called the Tangle. The Tangle naturally succeeds the blockchain as its next evolutionary step as it offers features suited to establish more efficient and scalable distributed ledger solutions. Consensus is no longer found in the longest chain but on the heaviest DAG, where PoW is replaced by a stake- or reputation-based weight function. The DAG structure and the underlying Reality-based UTXO Ledger allow parallel validation of transactions without the need for total ordering. Moreover, it enables the removal of the intermediary of miners and validators, allowing a pure two-step process that follows the \emph{propose-vote} paradigm at the node level and not at the validator level. We propose a framework to analyse liveness and safety under different communication and adversary models. This allows providing impossibility results in some edge cases and in the asynchronous communication model. We provide formal proof of the security of the protocol assuming a common random coin.
WeakSATD: Detecting Weak Self-admitted Technical Debt
Venue: arXiv cs.SE 2022
Year: 2022

Speeding up development may produce technical debt, i.e., not-quite-right code for which the effort to make it right increases with time as a sort of interest. Developers may be aware of the debt as they admit it in their code comments. Literature reports that such a self-admitted technical debt survives for a long time in a program, but it is not yet clear its impact on the quality of the code in the long term. We argue that self-admitted technical debt contains a number of different weaknesses that may affect the security of a program. Therefore, the longer a debt is not paid back the higher is the risk that the weaknesses can be exploited. To discuss our claim and rise the developers' awareness of the vulnerability of the self-admitted technical debt that is not paid back, we explore the self-admitted technical debt in the Chromium C-code to detect any known weaknesses. In this preliminary study, we first mine the Common Weakness Enumeration repository to define heuristics for the automatic detection and fix of weak code. Then, we parse the C-code to find self-admitted technical debt and the code block it refers to. Finally, we use the heuristics to find weak code snippets associated to self-admitted technical debt and recommend their potential mitigation to developers. Such knowledge can be used to prioritize self-admitted technical debt for repair. A prototype has been developed and applied to the Chromium code. Initial findings report that 55\% of self-admitted technical debt code contains weak code of 14 different types.
The Extremal GDoF Gain of Optimal versus Binary Power Control in $K$ User Interference Networks Is $Θ(\sqrt{K})$
Venue: arXiv cs.IT 2022
Year: 2022

Using ideas from Generalized Degrees of Freedom (GDoF) analyses and extremal network theory, this work studies the extremal gain of optimal power control over binary (on/off) power control, especially in large interference networks, in search of new theoretical insights. Whereas numerical studies have already established that in most practical settings binary power control is close to optimal, the extremal analysis shows not only that there exist settings where the gain from optimal power control can be quite significant, but also bounds the extremal values of such gains from a GDoF perspective. As its main contribution, this work explicitly characterizes the extremal GDoF gain of optimal over binary power control as $Θ\left(\sqrt{K}\right)$ for all $K$. In particular, the extremal gain is bounded between $\lfloor \sqrt{K}\rfloor$ and $2.5\sqrt{K}$ for every $K$. For $K=2,3,4,5,6$ users, the precise extremal gain is found to be $1, 3/2, 2, 9/4$ and $41/16$, respectively. Networks shown to achieve the extremal gain may be interpreted as multi-tier heterogeneous networks. It is worthwhile to note that because of their focus on asymptotic analysis, the sharp characterizations of extremal gains are valuable primarily from a theoretical perspective, and not as contradictions to the conventional wisdom that binary power control is generally close to optimal in practical, non-asymptotic settings.
Density functions of periodic sequences
Venue: arXiv cs.CG 2022
Year: 2022

Periodic point sets model all solid crystalline materials whose structures are determined in a rigid form and should be studied up to rigid motion or isometry preserving inter-point distances. In 2021 H.Edelsbrunner et al. introduced an infinite sequence of density functions that are continuous isometry invariants of periodic point sets. These density functions turned out to be highly non-trivial even in dimension 1 for periodic sequences of points in the line. This paper fully describes the density functions of any periodic sequence and their symmetry properties. The explicit description theoretically confirms coincidences of density functions that were previously computed only through finite samples.
Virtual and Augmented Reality-Based Assistive Interfaces for Upper-limb Prosthesis Control and Rehabilitation
Venue: arXiv cs.HC 2022
Year: 2022

Functional upper-limb prosthetic training can improve users performance in controlling prostheses and has been incorporated into occupational therapy for individuals in need. In recent years, virtual reality (VR) and augmented reality (AR) technologies have been shown to be promising avenues to improve the convenience of rehabilitative prosthesis training systems. However, it is uncertain if the comprehensive efficacy and effectiveness of VR or AR assistive tools are adequate compared to conventional prosthetic tools and if not, whether enhancements can be made through incorporation of other technical paradigms. This work first presents a mixed reality system we developed for prosthesis control and training. Five able-bodied subjects are involved to perform three-dimensional object manipulation tasks in analogous AR and VR environments. Multiple evaluation metrics are applied to assess subjects performances within the two paradigms. Based on the comparative analysis, we find that VR-based environment promotes more efficient motion along with higher task completion rate and path efficiency while AR paradigm allows subjects to perform motor tasks with shorter time consumed. Another study is conducted to evaluate the efficiency and feasibility of AR-facilitated prosthesis control system compared to that in real-world and if any technical additions can be applied to improve the AR-based system. Three able-bodied subjects were engaged in the experiment to perform object manipulation tasks in a) physical environment, b) AR-without-bypass environment, and c) AR-with-bypass environment. Based on the results obtained from the assessment, we conclude that while our AR-based system modestly lags behind the effectiveness of physical systems, the study conducted using a bypass prosthesis suggests that AR system has the potential to improve the efficacy of prosthesis control.
VWA: Hardware Efficient Vectorwise Accelerator for Convolutional Neural Network
Venue: arXiv cs.AR 2022
Year: 2022

Hardware accelerators for convolution neural networks (CNNs) enable real-time applications of artificial intelligence technology. However, most of the existing designs suffer from low hardware utilization or high area cost due to complex dataflow. This paper proposes a hardware efficient vectorwise CNN accelerator that adopts a 3$\times$3 filter optimized systolic array using 1-D broadcast dataflow to generate partial sum. This enables easy reconfiguration for different kinds of kernels with interleaved input or elementwise input dataflow. This simple and regular data flow results in low area cost while attains high hardware utilization. The presented design achieves 99\%, 97\%, 93.7\%, 94\% hardware utilization for VGG-16, ResNet-34, GoogLeNet, and Mobilenet, respectively. Hardware implementation with TSMC 40nm technology takes 266.9K NAND gate count and 191KB SRAM to support 168GOPS throughput and consumes only 154.98mW when running at 500MHz operating frequency, which has superior area and power efficiency than other designs.
Improved error bounds for the distance distribution of Reed-Solomon codes
Venue: arXiv cs.IT 2022
Year: 2022

We use the generating function approach to derive simple expressions for the factorial moments of the distance distribution over Reed-Solomon codes. We obtain better upper bounds for the error term of a counting formula given by Li and Wan, which gives nontrivial estimates on the number of polynomials over finite fields with prescribed leading coefficients and a given number of linear factors. This improvement leads to new results on the classification of deep holes of Reed Solomon codes.
Twist: Sound Reasoning for Purity and Entanglement in Quantum Programs
Venue: arXiv cs.PL 2022
Year: 2022

Quantum programming languages enable developers to implement algorithms for quantum computers that promise computational breakthroughs in classically intractable tasks. Programming quantum computers requires awareness of entanglement, the phenomenon in which measurement outcomes of qubits are correlated. Entanglement can determine the correctness of algorithms and suitability of programming patterns. In this work, we formalize purity as a central tool for automating reasoning about entanglement in quantum programs. A pure expression is one whose evaluation is unaffected by the measurement outcomes of qubits that it does not own, implying freedom from entanglement with any other expression in the computation. We present Twist, the first language that features a type system for sound reasoning about purity. The type system enables the developer to identify pure expressions using type annotations. Twist also features purity assertion operators that state the absence of entanglement in the output of quantum gates. To soundly check these assertions, Twist uses a combination of static analysis and runtime verification. We evaluate Twist's type system and analyses on a benchmark suite of quantum programs in simulation, demonstrating that Twist can express quantum algorithms, catch programming errors in them, and support programs that several languages disallow, while incurring runtime verification overhead of less than 3.5%.
Zero Day Threat Detection Using Graph and Flow Based Security Telemetry
Venue: arXiv cs.CR 2022
Year: 2022

Zero Day Threats (ZDT) are novel methods used by malicious actors to attack and exploit information technology (IT) networks or infrastructure. In the past few years, the number of these threats has been increasing at an alarming rate and have been costing organizations millions of dollars to remediate. The increasing expansion of network attack surfaces and the exponentially growing number of assets on these networks necessitate the need for a robust AI-based Zero Day Threat detection model that can quickly analyze petabyte-scale data for potentially malicious and novel activity. In this paper, the authors introduce a deep learning based approach to Zero Day Threat detection that can generalize, scale, and effectively identify threats in near real-time. The methodology utilizes network flow telemetry augmented with asset-level graph features, which are passed through a dual-autoencoder structure for anomaly and novelty detection respectively. The models have been trained and tested on four large scale datasets that are representative of real-world organizational networks and they produce strong results with high precision and recall values. The models provide a novel methodology to detect complex threats with low false-positive rates that allow security operators to avoid alert fatigue while drastically reducing their mean time to response with near-real-time detection. Furthermore, the authors also provide a novel, labelled, cyber attack dataset generated from adversarial activity that can be used for validation or training of other models. With this paper, the authors' overarching goal is to provide a novel architecture and training methodology for cyber anomaly detectors that can generalize to multiple IT networks with minimal to no retraining while still maintaining strong performance.
Machine Learning Operations (MLOps): Overview, Definition, and Architecture
Venue: arXiv cs.LG 2022
Year: 2022

The final goal of all industrial machine learning (ML) projects is to develop ML products and rapidly bring them into production. However, it is highly challenging to automate and operationalize ML products and thus many ML endeavors fail to deliver on their expectations. The paradigm of Machine Learning Operations (MLOps) addresses this issue. MLOps includes several aspects, such as best practices, sets of concepts, and development culture. However, MLOps is still a vague term and its consequences for researchers and professionals are ambiguous. To address this gap, we conduct mixed-method research, including a literature review, a tool review, and expert interviews. As a result of these investigations, we provide an aggregated overview of the necessary principles, components, and roles, as well as the associated architecture and workflows. Furthermore, we furnish a definition of MLOps and highlight open challenges in the field. Finally, this work provides guidance for ML researchers and practitioners who want to automate and operate their ML products with a designated set of technologies.
Creating a Forensic Database of Shoeprints from Online Shoe Tread Photos
Venue: arXiv cs.CV 2022
Year: 2022

Shoe tread impressions are one of the most common types of evidence left at crime scenes. However, the utility of such evidence is limited by the lack of databases of footwear prints that cover the large and growing number of distinct shoe models. Moreover, the database is preferred to contain the 3D shape, or depth, of shoe-tread photos so as to allow for extracting shoeprints to match a query (crime-scene) print. We propose to address this gap by leveraging shoe-tread photos collected by online retailers. The core challenge is to predict depth maps for these photos. As they do not have ground-truth 3D shapes allowing for training depth predictors, we exploit synthetic data that does. We develop a method termed ShoeRinsics that learns to predict depth by leveraging a mix of fully supervised synthetic data and unsupervised retail image data. In particular, we find domain adaptation and intrinsic image decomposition techniques effectively mitigate the synthetic-real domain gap and yield significantly better depth prediction. To validate our method, we introduce 2 validation sets consisting of shoe-tread image and print pairs and define a benchmarking protocol to quantify the quality of predicted depth. On this benchmark, ShoeRinsics outperforms existing methods of depth prediction and synthetic-to-real domain adaptation.
A Bayesian Detect to Track System for Robust Visual Object Tracking and Semi-Supervised Model Learning
Venue: arXiv cs.CV 2022
Year: 2022

Object tracking is one of the fundamental problems in visual recognition tasks and has achieved significant improvements in recent years. The achievements often come with the price of enormous hardware consumption and expensive labor effort for consecutive labeling. A missing ingredient for robust tracking is achieving performance with minimal modification on network structure and semi-supervised learning intermittent labeled frames. In this paper, we ad-dress these problems in a Bayesian tracking and detection framework parameterized by neural network outputs. In our framework, the tracking and detection process is formulated in a probabilistic way as multi-objects dynamics and network detection uncertainties. With our formulation, we propose a particle filter-based approximate sampling algorithm for tracking object state estimation. Based on our particle filter inference algorithm, a semi-supervised learn-ing algorithm is utilized for learning tracking network on intermittent labeled frames by variational inference. In our experiments, we provide both mAP and probability-based detection measurements for comparison between our algorithm with non-Bayesian solutions. We also train a semi-supervised tracking network on M2Cai16-Tool-Locations Dataset and compare our results with supervised learning on fully labeled frames.
Image Features Influence Reaction Time: A Learned Probabilistic Perceptual Model for Saccade Latency
Venue: arXiv cs.HC 2022
Year: 2022

We aim to ask and answer an essential question "how quickly do we react after observing a displayed visual target?" To this end, we present psychophysical studies that characterize the remarkable disconnect between human saccadic behaviors and spatial visual acuity. Building on the results of our studies, we develop a perceptual model to predict temporal gaze behavior, particularly saccadic latency, as a function of the statistics of a displayed image. Specifically, we implement a neurologically-inspired probabilistic model that mimics the accumulation of confidence that leads to a perceptual decision. We validate our model with a series of objective measurements and user studies using an eye-tracked VR display. The results demonstrate that our model prediction is in statistical alignment with real-world human behavior. Further, we establish that many sub-threshold image modifications commonly introduced in graphics pipelines may significantly alter human reaction timing, even if the differences are visually undetectable. Finally, we show that our model can serve as a metric to predict and alter reaction latency of users in interactive computer graphics applications, thus may improve gaze-contingent rendering, design of virtual experiences, and player performance in e-sports. We illustrate this with two examples: estimating competition fairness in a video game with two different team colors, and tuning display viewing distance to minimize player reaction time.
A Deep Learning Approach to Dst Index Prediction
Venue: arXiv cs.LG 2022
Year: 2022

The disturbance storm time (Dst) index is an important and useful measurement in space weather research. It has been used to characterize the size and intensity of a geomagnetic storm. A negative Dst value means that the Earth's magnetic field is weakened, which happens during storms. In this paper, we present a novel deep learning method, called the Dst Transformer, to perform short-term, 1-6 hour ahead, forecasting of the Dst index based on the solar wind parameters provided by the NASA Space Science Data Coordinated Archive. The Dst Transformer combines a multi-head attention layer with Bayesian inference, which is capable of quantifying both aleatoric uncertainty and epistemic uncertainty when making Dst predictions. Experimental results show that the proposed Dst Transformer outperforms related machine learning methods in terms of the root mean square error and R-squared. Furthermore, the Dst Transformer can produce both data and model uncertainty quantification results, which can not be done by the existing methods. To our knowledge, this is the first time that Bayesian deep learning has been used for Dst index forecasting.
A Simple Contrastive Learning Objective for Alleviating Neural Text Degeneration
Venue: arXiv cs.CL 2022
Year: 2022

The cross-entropy objective has proved to be an all-purpose training objective for autoregressive language models (LMs). However, without considering the penalization of problematic tokens, LMs trained using cross-entropy exhibit text degeneration. To address this, unlikelihood training has been proposed to reduce the probability of unlikely tokens predicted by LMs. But unlikelihood does not consider the relationship between the label tokens and unlikely token candidates, thus showing marginal improvements in degeneration. We propose a new contrastive token learning objective that inherits the advantages of cross-entropy and unlikelihood training and avoids their limitations. The key idea is to teach a LM to generate high probabilities for label tokens and low probabilities of negative candidates. Comprehensive experiments on language modeling and open-domain dialogue generation tasks show that the proposed contrastive token objective yields much less repetitive texts, with a higher generation quality than baseline approaches, achieving the new state-of-the-art performance on text degeneration.