OpenRaiser/Intern-Atlas huggingface dataset:
The Price of Hierarchical Clustering
Venue: arXiv cs.DS 2022
Year: 2022

Hierarchical Clustering is a popular tool for understanding the hereditary properties of a data set. Such a clustering is actually a sequence of clusterings that starts with the trivial clustering in which every data point forms its own cluster and then successively merges two existing clusters until all points are in the same cluster. A hierarchical clustering achieves an approximation factor of $α$ if the costs of each $k$-clustering in the hierarchy are at most $α$ times the costs of an optimal $k$-clustering. We study as cost functions the maximum (discrete) radius of any cluster ($k$-center problem) and the maximum diameter of any cluster ($k$-diameter problem). In general, the optimal clusterings do not form a hierarchy and hence an approximation factor of $1$ cannot be achieved. We call the smallest approximation factor that can be achieved for any instance the price of hierarchy. For the $k$-diameter problem we improve the upper bound on the price of hierarchy to $3+2\sqrt{2}\approx 5.83$. Moreover we significantly improve the lower bounds for $k$-center and $k$-diameter, proving a price of hierarchy of exactly $4$ and $3+2\sqrt{2}$, respectively.
How Are Communication Channels on GitHub Presented to Their Intended Audience? -- A Thematic Analysis
Venue: arXiv cs.SE 2022
Year: 2022

Communication is essential in software development, and even more in distributed settings. Communication activities need to be organized and coordinated to defend against the threat of productivity losses, increases in cognitive load, and stress among team members. With a plethora of communication channels that were identified by previous research in open-source projects, there is a need to explore organizational issues in how these communication channels are introduced, explained, and motivated for use among all project members. In this study, we wanted to understand which communication channels are used in GitHub projects and how they are presented to the GitHub project audience. We employed thematic analysis to analyze 151 artifacts in 90 GitHub projects. Our results revealed 32 unique communications channels that can be divided into nine different types. Projects mostly provide channels of different types, but for some types (e.g., chat) it is common to provide several channels. Maintainers are aware that channels have different properties and help the developers to decide which channel should be used in which case. However, this is not true for all projects, and often we have not found any explicit reasons why maintainers chose to provide one channel over another. Different channels can be used for different purposes and have different affordances, so maintainers have to decide wisely which channels they want to provide and make clear which channel should be used in which case. Otherwise, developers might feel overwhelmed of too many channels and information can get fragmented over multiple channels.
Approximate Selection with Unreliable Comparisons in Optimal Expected Time
Venue: arXiv cs.DS 2022
Year: 2022

Given $n$ elements, an integer $k$ and a parameter $\varepsilon$, we study to select an element with rank in $(k-n\varepsilon,k+n\varepsilon]$ using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant error probability, and multiple comparisons between the same pair of elements are independent. In this fault model, the fundamental problems of finding the minimum, selecting the $k$-th smallest element and sorting have been shown to require $Θ\big(n \log \frac{1}{Q}\big)$, $Θ\big(n\log \frac{\min\{k,n-k\}}{Q}\big)$ and $Θ\big(n\log \frac{n}{Q}\big)$ comparisons, respectively, to achieve success probability $1-Q$. Recently, Leucci and Liu proved that the approximate minimum selection problem ($k=0$) requires expected $Θ(\varepsilon^{-1}\log \frac{1}{Q})$ comparisons. We develop a randomized algorithm that performs expected $O(\frac{k}{n}\varepsilon^{-2} \log \frac{1}{Q})$ comparisons to achieve success probability at least $1-Q$. We also prove that any randomized algorithm with success probability at least $1-Q$ performs expected $Ω(\frac{k}{n}\varepsilon^{-2}\log \frac{1}{Q})$ comparisons. Our results indicate a clear distinction between approximating the minimum and approximating the $k$-th smallest element, which holds even for the high probability guarantee, e.g., if $k=\frac{n}{2}$ and $Q=\frac{1}{n}$, $Θ(\varepsilon^{-1}\log n)$ versus $Θ(\varepsilon^{-2}\log n)$. Moreover, if $\varepsilon=n^{-α}$ for $α\in (0,\frac{1}{2})$, the asymptotic difference is almost quadratic, i.e., $\tildeΘ(n^α)$ versus $\tildeΘ(n^{2α})$.
Real-Time Streaming and Event-driven Control of Scientific Experiments
Venue: arXiv cs.DC 2022
Year: 2022

Advancements in scientific instrument sensors and connected devices provide unprecedented insight into ongoing experiments and present new opportunities for control, optimization, and steering. However, the diversity of sensors and heterogeneity of their data result in make it challenging to fully realize these new opportunities. Organizing and synthesizing diverse data streams in near-real-time requires both rich automation and Machine Learning (ML). To efficiently utilize ML during an experiment, the entire ML lifecycle must be addressed, including refining experiment configurations, retraining models, and applying decisions-tasks that require an equally diverse array of computational resources spanning centralized HPC to the accelerators at the edge. Here we present the Manufacturing Data and Machine Learning platform (MDML). The MDML is designed to standardize the research and operational environment for advanced data analytics and ML-enabled automated process optimization by providing the cyberinfrastructure to integrate sensor data streams and AI in cyber-physical systems for in-situ analysis. To achieve this, the MDML provides a fabric to receive and aggregate IoT data and simultaneously orchestrate remote computation across the computing continuum. In this paper we describe the MDML and show how it is used in advanced manufacturing to act on IoT data and orchestrate distributed ML to guide experiments.
A unified view on Self-Organizing Maps (SOMs) and Stochastic Neighbor Embedding (SNE)
Venue: arXiv cs.LG 2022
Year: 2022

We propose a unified view on two widely used data visualization techniques: Self-Organizing Maps (SOMs) and Stochastic Neighbor Embedding (SNE). We show that they can both be derived from a common mathematical framework. Leveraging this formulation, we propose to compare SOM and SNE quantitatively on two datasets, and discuss possible avenues for future work to take advantage of both approaches.
ExSpliNet: An interpretable and expressive spline-based neural network
Venue: arXiv cs.LG 2022
Year: 2022

In this paper we present ExSpliNet, an interpretable and expressive neural network model. The model combines ideas of Kolmogorov neural networks, ensembles of probabilistic trees, and multivariate B-spline representations. We give a probabilistic interpretation of the model and show its universal approximation properties. We also discuss how it can be efficiently encoded by exploiting B-spline properties. Finally, we test the effectiveness of the proposed model on synthetic approximation problems and classical machine learning benchmark datasets.
Using Ontologies for the Formalization and Recognition of Criticality for Automated Driving
Venue: arXiv cs.AI 2022
Year: 2022

Knowledge representation and reasoning has a long history of examining how knowledge can be formalized, interpreted, and semantically analyzed by machines. In the area of automated vehicles, recent advances suggest the ability to formalize and leverage relevant knowledge as a key enabler in handling the inherently open and complex context of the traffic world. This paper demonstrates ontologies to be a powerful tool for a) modeling and formalization of and b) reasoning about factors associated with criticality in the environment of automated vehicles. For this, we leverage the well-known 6-Layer Model to create a formal representation of the environmental context. Within this representation, an ontology models domain knowledge as logical axioms, enabling deduction on the presence of critical factors within traffic scenes and scenarios. For executing automated analyses, a joint description logic and rule reasoner is used in combination with an a-priori predicate augmentation. We elaborate on the modular approach, present a publicly available implementation, and evaluate the method by means of a large-scale drone data set of urban traffic scenarios.
Efficient Fine-Tuning of BERT Models on the Edge
Venue: arXiv cs.LG 2022
Year: 2022

Resource-constrained devices are increasingly the deployment targets of machine learning applications. Static models, however, do not always suffice for dynamic environments. On-device training of models allows for quick adaptability to new scenarios. With the increasing size of deep neural networks, as noted with the likes of BERT and other natural language processing models, comes increased resource requirements, namely memory, computation, energy, and time. Furthermore, training is far more resource intensive than inference. Resource-constrained on-device learning is thus doubly difficult, especially with large BERT-like models. By reducing the memory usage of fine-tuning, pre-trained BERT models can become efficient enough to fine-tune on resource-constrained devices. We propose Freeze And Reconfigure (FAR), a memory-efficient training regime for BERT-like models that reduces the memory usage of activation maps during fine-tuning by avoiding unnecessary parameter updates. FAR reduces fine-tuning time on the DistilBERT model and CoLA dataset by 30%, and time spent on memory operations by 47%. More broadly, reductions in metric performance on the GLUE and SQuAD datasets are around 1% on average.
Why The Trans Programmer?
Venue: arXiv cs.CY 2022
Year: 2022

Through online anecdotal evidence and online communities, there is an in-group idea of trans people (specifically trans-feminine individuals) disproportionately entering computer science education & fields. Existing data suggests this is a plausible trend, yet no research has been done into exactly why. As computer science education (traditional schooling or self-taught methods) is integral to working in computer science fields, a simple research survey was conducted to gather data on 138 trans people's experiences with computer science & computer science education. This article's purpose is to shed insight on the motivations for trans individuals choosing computer science paths, while acting as a basis and call to action for further research.
PSCNN: A 885.86 TOPS/W Programmable SRAM-based Computing-In-Memory Processor for Keyword Spotting
Venue: arXiv cs.AR 2022
Year: 2022

Computing-in-memory (CIM) has attracted significant attentions in recent years due to its massive parallelism and low power consumption. However, current CIM designs suffer from large area overhead of small CIM macros and bad programmablity for model execution. This paper proposes a programmable CIM processor with a single large sized CIM macro instead of multiple smaller ones for power efficient computation and a flexible instruction set to support various binary 1-D convolution Neural Network (CNN) models in an easy way. Furthermore, the proposed architecture adopts the pooling write-back method to support fused or independent convolution/pooling operations to reduce 35.9\% of latency, and the flexible ping-pong feature SRAM to fit different feature map sizes during layer-by-layer execution.The design fabricated in TSMC 28nm technology achieves 150.8 GOPS throughput and 885.86 TOPS/W power efficiency at 10 MHz when executing our binary keyword spotting model, which has higher power efficiency and flexibility than previous designs.
StreamingHub: Interactive Stream Analysis Workflows
Venue: arXiv cs.DB 2022
Year: 2022

Reusable data/code and reproducible analyses are foundational to quality research. This aspect, however, is often overlooked when designing interactive stream analysis workflows for time-series data (e.g., eye-tracking data). A mechanism to transmit informative metadata alongside data may allow such workflows to intelligently consume data, propagate metadata to downstream tasks, and thereby auto-generate reusable, reproducible analytic outputs with zero supervision. Moreover, a visual programming interface to design, develop, and execute such workflows may allow rapid prototyping for interdisciplinary research. Capitalizing on these ideas, we propose StreamingHub, a framework to build metadata propagating, interactive stream analysis workflows using visual programming. We conduct two case studies to evaluate the generalizability of our framework. Simultaneously, we use two heuristics to evaluate their computational fluidity and data growth. Results show that our framework generalizes to multiple tasks with a minimal performance overhead.
An Explore of Virtual Reality for Awareness of the Climate Change Crisis: A Simulation of Sea Level Rise
Venue: arXiv cs.MM 2022
Year: 2022

Virtual Reality (VR) technology has been shown to achieve remarkable results in multiple fields. Due to the nature of the immersive medium of Virtual Reality it logically follows that it can be used as a high-quality educational tool as it offers potentially a higher bandwidth than other mediums such as text, pictures and videos. This short paper illustrates the development of a climate change educational awareness application for virtual reality to simulate virtual scenes of local scenery and sea level rising until 2100 using prediction data. The paper also reports on the current in progress work of porting the system to Augmented Reality (AR) and future work to evaluate the system.
A Comparison of Approaches for Imbalanced Classification Problems in the Context of Retrieving Relevant Documents for an Analysis
Venue: arXiv cs.IR 2022
Year: 2022

One of the first steps in many text-based social science studies is to retrieve documents that are relevant for the analysis from large corpora of otherwise irrelevant documents. The conventional approach in social science to address this retrieval task is to apply a set of keywords and to consider those documents to be relevant that contain at least one of the keywords. But the application of incomplete keyword lists risks drawing biased inferences. More complex and costly methods such as query expansion techniques, topic model-based classification rules, and active as well as passive supervised learning could have the potential to more accurately separate relevant from irrelevant documents and thereby reduce the potential size of bias. Yet, whether applying these more expensive approaches increases retrieval performance compared to keyword lists at all, and if so, by how much, is unclear as a comparison of these approaches is lacking. This study closes this gap by comparing these methods across three retrieval tasks associated with a data set of German tweets (Linder, 2017), the Social Bias Inference Corpus (SBIC) (Sap et al., 2020), and the Reuters-21578 corpus (Lewis, 1997). Results show that query expansion techniques and topic model-based classification rules in most studied settings tend to decrease rather than increase retrieval performance. Active supervised learning, however, if applied on a not too small set of labeled training instances (e.g. 1,000 documents), reaches a substantially higher retrieval performance than keyword lists.
Toward Modeling Creative Processes for Algorithmic Painting
Venue: arXiv cs.AI 2022
Year: 2022

This paper proposes a framework for computational modeling of artistic painting algorithms, inspired by human creative practices. Based on examples from expert artists and from the author's own experience, the paper argues that creative processes often involve two important components: vague, high-level goals (e.g., "make a good painting"), and exploratory processes for discovering new ideas. This paper then sketches out possible computational mechanisms for imitating those elements of the painting process, including underspecified loss functions and iterative painting procedures with explicit task decompositions.
Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction
Venue: arXiv cs.LG 2022
Year: 2022

Bilevel Optimization has witnessed notable progress recently with new emerging efficient algorithms and has been applied to many machine learning tasks such as data cleaning, few-shot learning, and neural architecture search. However, little attention has been paid to solve the bilevel problems under distributed setting. Federated learning (FL) is an emerging paradigm which solves machine learning tasks over distributed-located data. FL problems are challenging to solve due to the heterogeneity and communication bottleneck. However, it is unclear how these challenges will affect the convergence of Bilevel Optimization algorithms. In this paper, we study Federated Bilevel Optimization problems. Specifically, we first propose the FedBiO, a deterministic gradient-based algorithm and we show it requires $O(ε^{-2})$ number of iterations to reach an $ε$-stationary point. Then we propose FedBiOAcc to accelerate FedBiO with the momentum-based variance-reduction technique under the stochastic scenario. We show FedBiOAcc has complexity of $O(ε^{-1.5})$. Finally, we validate our proposed algorithms via the important Fair Federated Learning task. More specifically, we define a bilevel-based group fair FL objective. Our algorithms show superior performances compared to other baselines in numerical experiments.
Improved Weakly Private Information Retrieval Codes
Venue: arXiv cs.IT 2022
Year: 2022

We study the problem of weakly private information retrieval (W-PIR), where a user wishes to retrieve a desired message from $N$ non-colluding servers in a way that the privacy leakage regarding the desired message's identity is less than or equal to a threshold. We propose a new code construction which significantly improves upon the best known result in the literature, based on the following critical observation. In previous constructions, for the extreme case of minimum download, the retrieval pattern is to download the message directly from $N-1$ servers; however this causes leakage to all these $N-1$ servers, and a better retrieval pattern for this extreme case is to download the message directly from a single server. The proposed code construction allows a natural transition to such a pattern, and for both the maximal leakage metric and the mutual information leakage metric, significant improvements can be obtained. We provide explicit solutions, in contrast to a previous work by Lin et al., where only numerical solutions were obtained.
A general approach to deriving diagnosability results of interconnection networks
Venue: arXiv cs.NI 2022
Year: 2022

We generalize an approach to deriving diagnosability results of various interconnection networks in terms of the popular $g$-good-neighbor and $g$-extra fault-tolerant models, as well as mainstream diagnostic models such as the PMC and the MM* models. As demonstrative examples, we show how to follow this constructive, and effective, process to derive the $g$-extra diagnosabilities of the hypercube, the $(n, k)$-star, and the arrangement graph. These results agree with those achieved individually, without duplicating structure independent technical details. Some of them come with a larger applicable range than those already known, and the result for the arrangement graph in terms of the MM* model is new.
Multi-view Geometry: Correspondences Refinement Based on Algebraic Properties
Venue: arXiv cs.CG 2022
Year: 2022

Correspondences estimation or feature matching is a key step in the image-based 3D reconstruction problem. In this paper, we propose two algebraic properties for correspondences. The first is a rank deficient matrix construct from the correspondences of at least nine key-points on two images (two-view correspondences) and the second is also another rank deficient matrix built from the other correspondences of six key-points on at least five images (multi-view correspondences). To our knowledge, there are no theoretical results for multi-view correspondences prior to this paper. To obtain accurate correspondences, multi-view correspondences seem to be more useful than two-view correspondences. From these two algebraic properties, we propose an refinement algorithm for correspondences. This algorithm is a combination of correspondences refinement, outliers recognition and missing key-points recovery. Real experiments from the project of reconstructing Buddha statue show that the proposed refinement algorithm can reduce the average error from 77 pixels to 55 pixels on the correspondences estimation. This drop is substantial and it validates our results.
MemSE: Fast MSE Prediction for Noisy Memristor-Based DNN Accelerators
Venue: arXiv cs.LG 2022
Year: 2022

Memristors enable the computation of matrix-vector multiplications (MVM) in memory and, therefore, show great potential in highly increasing the energy efficiency of deep neural network (DNN) inference accelerators. However, computations in memristors suffer from hardware non-idealities and are subject to different sources of noise that may negatively impact system performance. In this work, we theoretically analyze the mean squared error of DNNs that use memristor crossbars to compute MVM. We take into account both the quantization noise, due to the necessity of reducing the DNN model size, and the programming noise, stemming from the variability during the programming of the memristance value. Simulations on pre-trained DNN models showcase the accuracy of the analytical prediction. Furthermore the proposed method is almost two order of magnitude faster than Monte-Carlo simulation, thus making it possible to optimize the implementation parameters to achieve minimal error for a given power constraint.
License Plate Privacy in Collaborative Visual Analysis of Traffic Scenes
Venue: arXiv cs.CV 2022
Year: 2022

Traffic scene analysis is important for emerging technologies such as smart traffic management and autonomous vehicles. However, such analysis also poses potential privacy threats. For example, a system that can recognize license plates may construct patterns of behavior of the corresponding vehicles' owners and use that for various illegal purposes. In this paper we present a system that enables traffic scene analysis while at the same time preserving license plate privacy. The system is based on a multi-task model whose latent space is selectively compressed depending on the amount of information the specific features carry about analysis tasks and private information. Effectiveness of the proposed method is illustrated by experiments on the Cityscapes dataset, for which we also provide license plate annotations.
How to choose features to improve prediction performance in lane-changing intention: A meta-analysis
Venue: arXiv cs.RO 2022
Year: 2022

Lane-change is a fundamental driving behavior and highly associated with various types of collisions, such as rear-end collisions, sideswipe collisions, and angle collisions and the increased risk of a traffic crash. This study investigates effectiveness of different features categories combination in lane-changing intention prediction. Studies related to lane-changing intention prediction have been selected followed by strict standards. Then the meta-analysis was employed to not only evaluate the effectiveness of different features categories combination in lane-changing intention but also capture heterogeneity, effect size combination, and publication bias. According to the meta-analysis and reviewed research papers, results indicate that using input features from different types can lead to different performances. And vehicle input type has a better performance in lane-changing intention, prediction, compared with environment or even driver combination input type. Finally, some potential future research directions are proposed based on the findings of the paper.