OpenRaiser/Intern-Atlas huggingface dataset:
A model-based framework for learning transparent swarm behaviors
Venue: arXiv cs.RO 2021
Year: 2021

This paper proposes a model-based framework to automatically and efficiently design understandable and verifiable behaviors for swarms of robots. The framework is based on the automatic extraction of two distinct models: 1) a neural network model trained to estimate the relationship between the robots' sensor readings and the global performance of the swarm, and 2) a probabilistic state transition model that explicitly models the local state transitions (i.e., transitions in observations from the perspective of a single robot in the swarm) given a policy. The models can be trained from a data set of simulated runs featuring random policies. The first model is used to automatically extract a set of local states that are expected to maximize the global performance. These local states are referred to as desired local states. The second model is used to optimize a stochastic policy so as to increase the probability that the robots in the swarm observe one of the desired local states. Following these steps, the framework proposed in this paper can efficiently lead to effective controllers. This is tested on four case studies, featuring aggregation and foraging tasks. Importantly, thanks to the models, the framework allows us to understand and inspect a swarm's behavior. To this end, we propose verification checks to identify some potential issues that may prevent the swarm from achieving the desired global objective. In addition, we explore how the framework can be used in combination with a "standard" evolutionary robotics strategy (i.e., where performance is measured via simulation), or with online learning.
MWQ: Multiscale Wavelet Quantized Neural Networks
Venue: arXiv cs.CV 2021
Year: 2021

Model quantization can reduce the model size and computational latency, it has become an essential technique for the deployment of deep neural networks on resourceconstrained hardware (e.g., mobile phones and embedded devices). The existing quantization methods mainly consider the numerical elements of the weights and activation values, ignoring the relationship between elements. The decline of representation ability and information loss usually lead to the performance degradation. Inspired by the characteristics of images in the frequency domain, we propose a novel multiscale wavelet quantization (MWQ) method. This method decomposes original data into multiscale frequency components by wavelet transform, and then quantizes the components of different scales, respectively. It exploits the multiscale frequency and spatial information to alleviate the information loss caused by quantization in the spatial domain. Because of the flexibility of MWQ, we demonstrate three applications (e.g., model compression, quantized network optimization, and information enhancement) on the ImageNet and COCO datasets. Experimental results show that our method has stronger representation ability and can play an effective role in quantized neural networks.
Correlation analysis of node and edge centrality measures in artificial complex networks
Venue: arXiv cs.SI 2021
Year: 2021

The importance of a node in a social network is identified through a set of measures called centrality. Degree centrality, closeness centrality, betweenness centrality and clustering coefficient are the most frequently used metrics to compute node centrality. Their computational complexity in some cases makes unfeasible, when not practically impossible, their computations. For this reason we focused on two alternative measures, WERW-Kpath and Game of Thieves, which are at the same time highly descriptive and computationally affordable. Our experiments show that a strong correlation exists between WERW-Kpath and Game of Thieves and the classical centrality measures. This may suggest the possibility of using them as useful and more economic replacements of the classical centrality measures.
Comparing Approaches to Dravidian Language Identification
Venue: arXiv cs.CL 2021
Year: 2021

This paper describes the submissions by team HWR to the Dravidian Language Identification (DLI) shared task organized at VarDial 2021 workshop. The DLI training set includes 16,674 YouTube comments written in Roman script containing code-mixed text with English and one of the three South Dravidian languages: Kannada, Malayalam, and Tamil. We submitted results generated using two models, a Naive Bayes classifier with adaptive language models, which has shown to obtain competitive performance in many language and dialect identification tasks, and a transformer-based model which is widely regarded as the state-of-the-art in a number of NLP tasks. Our first submission was sent in the closed submission track using only the training set provided by the shared task organisers, whereas the second submission is considered to be open as it used a pretrained model trained with external data. Our team attained shared second position in the shared task with the submission based on Naive Bayes. Our results reinforce the idea that deep learning methods are not as competitive in language identification related tasks as they are in many other text classification tasks.
Graph Metrics for Internet Robustness -- A Survey
Venue: arXiv cs.NI 2021
Year: 2021

Research on the robustness of the Internet has gained critical importance in the last decades because more and more individuals, societies and firms rely on this global network infrastructure for communication, knowledge transfer, business processes and e-commerce. In particular, modeling the structure of Internet has inspired several novel graph metrics for assessing important topological robustness features of large complex networks such as the Internet. This survey provides a comparative overview of these metrics, presents their strengths and limitations for analyzing the robustness of the Internet topology, and outlines a conceptual tool set in order to facilitate future analysis and adoption in research and practice.
Discrete Function Bases and Convolutional Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

We discuss the notion of "discrete function bases" with a particular focus on the discrete basis derived from the Legendre Delay Network (LDN). We characterize the performance of these bases in a delay computation task, and as fixed temporal convolutions in neural networks. Networks using fixed temporal convolutions are conceptually simple and yield state-of-the-art results in tasks such as psMNIST. Main Results (1) We present a numerically stable algorithm for constructing a matrix of DLOPs L in O(qN) (2) The Legendre Delay Network (LDN) can be used to form a discrete function basis with a basis transformation matrix H in O(qN). (3) If q < 300, convolving with the LDN basis online has a lower run-time complexity than convolving with arbitrary FIR filters. (4) Sliding window transformations exist for some bases (Haar, cosine, Fourier) and require O(q) operations per sample and O(N) memory. (5) LTI systems similar to the LDN can be constructed for many discrete function bases; the LDN system is superior in terms of having a finite impulse response. (6) We compare discrete function bases by linearly decoding delays from signals represented with respect to these bases. Results are depicted in Figure 20. Overall, decoding errors are similar. The LDN basis has the highest and the Fourier and cosine bases have the smallest errors. (7) The Fourier and cosine bases feature a uniform decoding error for all delays. These bases should be used if the signal can be represented well in the Fourier domain. (8) Neural network experiments suggest that fixed temporal convolutions can outperform learned convolutions. The basis choice is not critical; we roughly observe the same performance trends as in the delay task. (9) The LDN is the right choice for small q, if the O(q) Euler update is feasible, and if the low O(q) memory requirement is of importance.
Beyond Nyströmformer -- Approximation of self-attention by Spectral Shifting
Venue: arXiv cs.LG 2021
Year: 2021

Transformer is a powerful tool for many natural language tasks which is based on self-attention, a mechanism that encodes the dependence of other tokens on each specific token, but the computation of self-attention is a bottleneck due to its quadratic time complexity. There are various approaches to reduce the time complexity and approximation of matrix is one such. In Nyströmformer, the authors used Nyström based method for approximation of softmax. The Nyström method generates a fast approximation to any large-scale symmetric positive semidefinite (SPSD) matrix using only a few columns of the SPSD matrix. However, since the Nyström approximation is low-rank when the spectrum of the SPSD matrix decays slowly, the Nyström approximation is of low accuracy. Here an alternative method is proposed for approximation which has a much stronger error bound than the Nyström method. The time complexity of this same as Nyströmformer which is $O\left({n}\right)$.
Combining Context-Free and Contextualized Representations for Arabic Sarcasm Detection and Sentiment Identification
Venue: arXiv cs.CL 2021
Year: 2021

Since their inception, transformer-based language models have led to impressive performance gains across multiple natural language processing tasks. For Arabic, the current state-of-the-art results on most datasets are achieved by the AraBERT language model. Notwithstanding these recent advancements, sarcasm and sentiment detection persist to be challenging tasks in Arabic, given the language's rich morphology, linguistic disparity and dialectal variations. This paper proffers team SPPU-AASM's submission for the WANLP ArSarcasm shared-task 2021, which centers around the sarcasm and sentiment polarity detection of Arabic tweets. The study proposes a hybrid model, combining sentence representations from AraBERT with static word vectors trained on Arabic social media corpora. The proposed system achieves a F1-sarcastic score of 0.62 and a F-PN score of 0.715 for the sarcasm and sentiment detection tasks, respectively. Simulation results show that the proposed system outperforms multiple existing approaches for both the tasks, suggesting that the amalgamation of context-free and context-dependent text representations can help capture complementary facets of word meaning in Arabic. The system ranked second and tenth in the respective sub-tasks of sarcasm detection and sentiment identification.
Endurance-Aware Mapping of Spiking Neural Networks to Neuromorphic Hardware
Venue: arXiv cs.NE 2021
Year: 2021

Neuromorphic computing systems are embracing memristors to implement high density and low power synaptic storage as crossbar arrays in hardware. These systems are energy efficient in executing Spiking Neural Networks (SNNs). We observe that long bitlines and wordlines in a memristive crossbar are a major source of parasitic voltage drops, which create current asymmetry. Through circuit simulations, we show the significant endurance variation that results from this asymmetry. Therefore, if the critical memristors (ones with lower endurance) are overutilized, they may lead to a reduction of the crossbar's lifetime. We propose eSpine, a novel technique to improve lifetime by incorporating the endurance variation within each crossbar in mapping machine learning workloads, ensuring that synapses with higher activation are always implemented on memristors with higher endurance, and vice versa. eSpine works in two steps. First, it uses the Kernighan-Lin Graph Partitioning algorithm to partition a workload into clusters of neurons and synapses, where each cluster can fit in a crossbar. Second, it uses an instance of Particle Swarm Optimization (PSO) to map clusters to tiles, where the placement of synapses of a cluster to memristors of a crossbar is performed by analyzing their activation within the workload. We evaluate eSpine for a state-of-the-art neuromorphic hardware model with phase-change memory (PCM)-based memristors. Using 10 SNN workloads, we demonstrate a significant improvement in the effective lifetime.
Fine with "1234"? An Analysis of SMS One-Time Password Randomness in Android Apps
Venue: arXiv cs.CR 2021
Year: 2021

A fundamental premise of SMS One-Time Password (OTP) is that the used pseudo-random numbers (PRNs) are uniquely unpredictable for each login session. Hence, the process of generating PRNs is the most critical step in the OTP authentication. An improper implementation of the pseudo-random number generator (PRNG) will result in predictable or even static OTP values, making them vulnerable to potential attacks. In this paper, we present a vulnerability study against PRNGs implemented for Android apps. A key challenge is that PRNGs are typically implemented on the server-side, and thus the source code is not accessible. To resolve this issue, we build an analysis tool, \sysname, to assess implementations of the PRNGs in an automated manner without the source code requirement. Through reverse engineering, \sysname identifies the apps using SMS OTP and triggers each app's login functionality to retrieve OTP values. It further assesses the randomness of the OTP values to identify vulnerable PRNGs. By analyzing 6,431 commercially used Android apps downloaded from \tool{Google Play} and \tool{Tencent Myapp}, \sysname identified 399 vulnerable apps that generate predictable OTP values. Even worse, 194 vulnerable apps use the OTP authentication alone without any additional security mechanisms, leading to insecure authentication against guessing attacks and replay attacks.
Cluster Analysis of Malware Family Relationships
Venue: arXiv cs.CR 2021
Year: 2021

In this paper, we use $K$-means clustering to analyze various relationships between malware samples. We consider a dataset comprising~20 malware families with~1000 samples per family. These families can be categorized into seven different types of malware. We perform clustering based on pairs of families and use the results to determine relationships between families. We perform a similar cluster analysis based on malware type. Our results indicate that $K$-means clustering can be a powerful tool for data exploration of malware family relationships.
A Comparison of Word2Vec, HMM2Vec, and PCA2Vec for Malware Classification
Venue: arXiv cs.CR 2021
Year: 2021

Word embeddings are often used in natural language processing as a means to quantify relationships between words. More generally, these same word embedding techniques can be used to quantify relationships between features. In this paper, we first consider multiple different word embedding techniques within the context of malware classification. We use hidden Markov models to obtain embedding vectors in an approach that we refer to as HMM2Vec, and we generate vector embeddings based on principal component analysis. We also consider the popular neural network based word embedding technique known as Word2Vec. In each case, we derive feature embeddings based on opcode sequences for malware samples from a variety of different families. We show that we can obtain better classification accuracy based on these feature embeddings, as compared to HMM experiments that directly use the opcode sequences, and serve to establish a baseline. These results show that word embeddings can be a useful feature engineering step in the field of malware analysis.
ZYELL-NCTU NetTraffic-1.0: A Large-Scale Dataset for Real-World Network Anomaly Detection
Venue: arXiv cs.CR 2021
Year: 2021

Network security has been an active research topic for long. One critical issue is improving the anomaly detection capability of intrusion detection systems (IDSs), such as firewalls. However, existing network anomaly datasets are out of date (i.e., being collected many years ago) or IP-anonymized, making the data characteristics differ from today's network. Therefore, this work introduces a new, large-scale, and real-world dataset, ZYELL-NCTU NetTraffic-1.0, which is collected from the raw output of firewalls in a real network, with the objective to advance the development of network security researches.
Robust Collision-free Lightweight Aerial Autonomy for Unknown Area Exploration
Venue: arXiv cs.RO 2021
Year: 2021

Collision-free path planning is an essential requirement for autonomous exploration in unknown environments, especially when operating in confined spaces or near obstacles. This study presents an autonomous exploration technique using a small drone. A local end-point selection method is designed using LiDAR range measurement and then generates the path from the current position to the selected end-point. The generated path shows the consistent collision-free path in real-time by adopting the Euclidean signed distance field-based grid-search method. The simulation results consistently showed the safety, and reliability of the proposed path-planning method. Real-world experiments are conducted in three different mines, demonstrating successful autonomous exploration flight in environments with various structural conditions. The results showed the high capability of the proposed flight autonomy framework for lightweight aerial-robot systems. Besides, our drone performs an autonomous mission during our entry at the Tunnel Circuit competition (Phase 1) of the DARPA Subterranean Challenge.
Multicalibrated Partitions for Importance Weights
Venue: arXiv cs.LG 2021
Year: 2021

The ratio between the probability that two distributions $R$ and $P$ give to points $x$ are known as importance weights or propensity scores and play a fundamental role in many different fields, most notably, statistics and machine learning. Among its applications, importance weights are central to domain adaptation, anomaly detection, and estimations of various divergences such as the KL divergence. We consider the common setting where $R$ and $P$ are only given through samples from each distribution. The vast literature on estimating importance weights is either heuristic, or makes strong assumptions about $R$ and $P$ or on the importance weights themselves. In this paper, we explore a computational perspective to the estimation of importance weights, which factors in the limitations and possibilities obtainable with bounded computational resources. We significantly strengthen previous work that use the MaxEntropy approach, that define the importance weights based on a distribution $Q$ closest to $P$, that looks the same as $R$ on every set $C \in \mathcal{C}$, where $\mathcal{C}$ may be a huge collection of sets. We show that the MaxEntropy approach may fail to assign high average scores to sets $C \in \mathcal{C}$, even when the average of ground truth weights for the set is evidently large. We similarly show that it may overestimate the average scores to sets $C \in \mathcal{C}$. We therefore formulate Sandwiching bounds as a notion of set-wise accuracy for importance weights. We study these bounds to show that they capture natural completeness and soundness requirements from the weights. We present an efficient algorithm that under standard learnability assumptions computes weights which satisfy these bounds. Our techniques rely on a new notion of multicalibrated partitions of the domain of the distributions, which appear to be useful objects in their own right.
MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS in $L_1$ Distance
Venue: arXiv cs.DB 2021
Year: 2021

Approximate Nearest Neighbor Search (ANNS) is a fundamental algorithmic problem, with numerous applications in many areas of computer science. Locality-sensitive hashing (LSH) is one of the most popular solution approaches for ANNS. A common shortcoming of many LSH schemes is that since they probe only a single bucket in a hash table, they need to use a large number of hash tables to achieve a high query accuracy. For ANNS-$L_2$, a multi-probe scheme was proposed to overcome this drawback by strategically probing multiple buckets in a hash table. In this work, we propose MP-RW-LSH, the first and so far only multi-probe LSH solution to ANNS in $L_1$ distance. Another contribution of this work is to explain why a state-of-the-art ANNS-$L_1$ solution called Cauchy projection LSH (CP-LSH) is fundamentally not suitable for multi-probe extension. We show that MP-RW-LSH uses 15 to 53 times fewer hash tables than CP-LSH for achieving similar query accuracies.
DIMY: Enabling Privacy-preserving Contact Tracing
Venue: arXiv cs.CR 2021
Year: 2021

The infection rate of COVID-19 and lack of an approved vaccine has forced governments and health authorities to adopt lockdowns, increased testing, and contact tracing to reduce the spread of the virus. Digital contact tracing has become a supplement to the traditional manual contact tracing process. However, although there have been a number of digital contact tracing apps proposed and deployed, these have not been widely adopted owing to apprehensions surrounding privacy and security. In this paper, we propose a blockchain-based privacy-preserving contact tracing protocol, "Did I Meet You" (DIMY), that provides full-lifecycle data privacy protection on the devices themselves as well as on the back-end servers, to address most of the privacy concerns associated with existing protocols. We have employed Bloom filters to provide efficient privacy-preserving storage, and have used the Diffie-Hellman key exchange for secret sharing among the participants. We show that DIMY provides resilience against many well known attacks while introducing negligible overheads. DIMY's footprint on the storage space of clients' devices and back-end servers is also significantly lower than other similar state of the art apps.
Tuna Nutriment Tracking using Trajectory Mapping in Application to Aquaculture Fish Tank
Venue: arXiv cs.CV 2021
Year: 2021

The cost of fish feeding is usually around 40 percent of total production cost. Estimating a state of fishes in a tank and adjusting an amount of nutriments play an important role to manage cost of fish feeding system. Our approach is based on tracking nutriments on videos collected from an active aquaculture fish farm. Tracking approach is applied to acknowledge movement of nutriment to understand more about the fish behavior. Recently, there has been increasing number of researchers focused on developing tracking algorithms to generate more accurate and faster determination of object. Unfortunately, recent studies have shown that efficient and robust tracking of multiple objects with complex relations remain unsolved. Hence, focusing to develop tracking algorithm in aquaculture is more challenging because tracked object has a lot of aquatic variant creatures. By following aforementioned problem, we develop tuna nutriment tracking based on the classical minimum cost problem which consistently performs well in real environment datasets. In evaluation, the proposed method achieved 21.32 pixels and 3.08 pixels for average error distance and standard deviation, respectively. Quantitative evaluation based on the data generated by human annotators shows that the proposed method is valuable for aquaculture fish farm and can be widely applied to real environment datasets.