OpenRaiser/Intern-Atlas huggingface dataset:
Firefighter Problem with Minimum Budget: Hardness and Approximation Algorithm for Unit Disk Graphs
Venue: arXiv cs.DS 2022
Year: 2022

Unit disk graphs are the set of graphs which represent the intersection of disk graphs and interval graphs. These graphs are of great importance due to their structural similarity with wireless communication networks. Firefighter problem on unit disk graph is interesting as it models the virus spreading in an wireless network and asks for a solution to stop it. In this paper, we consider the MIN-BUDGET firefighter problem where the goal is to determine the minimum number of firefighters required and the nodes to place them at each time instant to save a given set of vertices of a given graph and a fire breakout node. We show that, the MIN-BUDGET firefighter problem in a unit disk graph is NP-Hard. We also present a constant factor approximation algorithm.
Design and Implementation of Knowledge Base for Runtime Management of Software Defined Hardware
Venue: arXiv cs.SE 2022
Year: 2022

Runtime-reconfigurable software coupled with reconfigurable hardware is highly desirable as a means towards maximizing runtime efficiency without compromising programmability. Compilers for such software systems are extremely difficult to design as they must leverage different types of hardware at runtime. To address the need for static and dynamic compiler optimization of workflows matched to dynamically reconfigurable hardware, we propose a novel design of the central component of a dynamic software compiler for software defined hardware. Our comprehensive design focuses not just on static knowledge but also on semi-supervised extraction of knowledge from program executions and developing their performance models. Specifically, our novel {\it dynamic and extensible knowledge base} 1) continuously gathers knowledge during execution of workflows 2) identifies {\it optimal} implementations of workflows on {\it optimal} (available) hardware configurations. It plays a hub role in storing information from, and providing information to other components of the compiler, as well as the human analyst. Through a rich tripartite graph representation, the knowledge base captures and learns extensive information on decomposition and mapping of code steps to kernels and mapping of kernels to available hardware configurations. The knowledge base is implemented using the C++ Boost Library and is capable of quickly processing offline and online queries and updates. We show that our knowledge base can answer queries in $1ms$ regardless of the number of workflows it stores. To the best of our knowledge, this is the first design of a dynamic and extensible knowledge base to support compilation of high-level languages to leverage arbitrary reconfigurable platforms.
Training Compute-Optimal Large Language Models
Venue: arXiv cs.CL 2022
Year: 2022

We investigate the optimal model size and number of tokens for training a transformer language model under a given compute budget. We find that current large language models are significantly undertrained, a consequence of the recent focus on scaling language models whilst keeping the amount of training data constant. By training over 400 language models ranging from 70 million to over 16 billion parameters on 5 to 500 billion tokens, we find that for compute-optimal training, the model size and the number of training tokens should be scaled equally: for every doubling of model size the number of training tokens should also be doubled. We test this hypothesis by training a predicted compute-optimal model, Chinchilla, that uses the same compute budget as Gopher but with 70B parameters and 4$\times$ more more data. Chinchilla uniformly and significantly outperforms Gopher (280B), GPT-3 (175B), Jurassic-1 (178B), and Megatron-Turing NLG (530B) on a large range of downstream evaluation tasks. This also means that Chinchilla uses substantially less compute for fine-tuning and inference, greatly facilitating downstream usage. As a highlight, Chinchilla reaches a state-of-the-art average accuracy of 67.5% on the MMLU benchmark, greater than a 7% improvement over Gopher.
Wildfire risk forecast: An optimizable fire danger index
Venue: arXiv cs.LG 2022
Year: 2022

Wildfire events have caused severe losses in many places around the world and are expected to increase with climate change. Throughout the years many technologies have been developed to identify fire events early on and to simulate fire behavior once they have started. Another particularly helpful technology is fire risk indices, which use weather forcing to make advanced predictions of the risk of fire. Predictions of fire risk indices can be used, for instance, to allocate resources in places with high risk. These indices have been developed over the years as empirical models with parameters that were estimated in lab experiments and field tests. These parameters, however, may not fit well all places where these models are used. In this paper we propose a novel implementation of one index (NFDRS IC) as a differentiable function in which one can optimize its internal parameters via gradient descent. We leverage existing machine learning frameworks (PyTorch) to construct our model. This approach has two benefits: (1) the NFDRS IC parameters can be improved for each region using actual observed fire events, and (2) the internal variables remain intact for interpretations by specialists instead of meaningless hidden layers as in traditional neural networks. In this paper we evaluate our strategy with actual fire events for locations in the USA and Europe.
Algorithmic Improvement and GPU Acceleration of the GenASM Algorithm
Venue: arXiv cs.AR 2022
Year: 2022

We improve on GenASM, a recent algorithm for genomic sequence alignment, by significantly reducing its memory footprint and bandwidth requirement. Our algorithmic improvements reduce the memory footprint by 24$\times$ and the number of memory accesses by 12$\times$. We efficiently parallelize the algorithm for GPUs, achieving a 4.1$\times$ speedup over a CPU implementation of the same algorithm, a 62$\times$ speedup over minimap2's CPU-based KSW2 and a 7.2$\times$ speedup over the CPU-based Edlib for long reads.
Core Risk Minimization using Salient ImageNet
Venue: arXiv cs.CV 2022
Year: 2022

Deep neural networks can be unreliable in the real world especially when they heavily use spurious features for their predictions. Recently, Singla & Feizi (2022) introduced the Salient Imagenet dataset by annotating and localizing core and spurious features of ~52k samples from 232 classes of Imagenet. While this dataset is useful for evaluating the reliance of pretrained models on spurious features, its small size limits its usefulness for training models. In this work, we first introduce the Salient Imagenet-1M dataset with more than 1 million soft masks localizing core and spurious features for all 1000 Imagenet classes. Using this dataset, we first evaluate the reliance of several Imagenet pretrained models (42 total) on spurious features and observe that: (i) transformers are more sensitive to spurious features compared to Convnets, (ii) zero-shot CLIP transformers are highly susceptible to spurious features. Next, we introduce a new learning paradigm called Core Risk Minimization (CoRM) whose objective ensures that the model predicts a class using its core features. We evaluate different computational approaches for solving CoRM and achieve significantly higher (+12%) core accuracy (accuracy when non-core regions corrupted using noise) with no drop in clean accuracy compared to models trained via Empirical Risk Minimization.
Subspace-based Representation and Learning for Phonotactic Spoken Language Recognition
Venue: arXiv cs.SD 2022
Year: 2022

Phonotactic constraints can be employed to distinguish languages by representing a speech utterance as a multinomial distribution or phone events. In the present study, we propose a new learning mechanism based on subspace-based representation, which can extract concealed phonotactic structures from utterances, for language verification and dialect/accent identification. The framework mainly involves two successive parts. The first part involves subspace construction. Specifically, it decodes each utterance into a sequence of vectors filled with phone-posteriors and transforms the vector sequence into a linear orthogonal subspace based on low-rank matrix factorization or dynamic linear modeling. The second part involves subspace learning based on kernel machines, such as support vector machines and the newly developed subspace-based neural networks (SNNs). The input layer of SNNs is specifically designed for the sample represented by subspaces. The topology ensures that the same output can be derived from identical subspaces by modifying the conventional feed-forward pass to fit the mathematical definition of subspace similarity. Evaluated on the "General LR" test of NIST LRE 2007, the proposed method achieved up to 52%, 46%, 56%, and 27% relative reductions in equal error rates over the sequence-based PPR-LM, PPR-VSM, and PPR-IVEC methods and the lattice-based PPR-LM method, respectively. Furthermore, on the dialect/accent identification task of NIST LRE 2009, the SNN-based system performed better than the aforementioned four baseline methods.
Heuristic-based Inter-training to Improve Few-shot Multi-perspective Dialog Summarization
Venue: arXiv cs.CL 2022
Year: 2022

Many organizations require their customer-care agents to manually summarize their conversations with customers. These summaries are vital for decision making purposes of the organizations. The perspective of the summary that is required to be created depends on the application of the summaries. With this work, we study the multi-perspective summarization of customer-care conversations between support agents and customers. We observe that there are different heuristics that are associated with summaries of different perspectives, and explore these heuristics to create weak-labeled data for intermediate training of the models before fine-tuning with scarce human annotated summaries. Most importantly, we show that our approach supports models to generate multi-perspective summaries with a very small amount of annotated data. For example, our approach achieves 94\% of the performance (Rouge-2) of a model trained with the original data, by training only with 7\% of the original data.
Typical Error Exponents: A Dual Domain Derivation
Venue: arXiv cs.IT 2022
Year: 2022

This paper shows that the probability that the error exponent of a given code randomly generated from a pairwise independent ensemble being smaller than a lower bound on the typical random-coding exponent tends to zero as the codeword length tends to infinity. This lower bound is known to be tight for i.i.d. ensembles over the binary symmetric channel and for constant-composition codes over memoryless channels. Our results recover both as special cases and remain valid for arbitrary alphabets, arbitrary channels -- for example finite-state channels with memory -- and arbitrary pairwise-independent ensembles. We specialize our results to the i.i.d., constant-composition and cost-constrained ensembles over discrete memoryless channels and to ensembles over finite-state channels.
Lenses for Composable Servers
Venue: arXiv cs.NI 2022
Year: 2022

We implement the semantics of server operations using parameterised lenses. They allow us to define endpoints and extend them using classical lens composition. The parameterised nature of lenses models state updates while the lens laws mimic properties expected from HTTP. This first approach to server development is extended to use dependent parameterised lenses. An upgrade necessary to model not only endpoints, but entire servers, unlocking the ability to compose them together.
NL-FCOS: Improving FCOS through Non-Local Modules for Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

During the last years, we have seen significant advances in the object detection task, mainly due to the outperforming results of convolutional neural networks. In this vein, anchor-based models have achieved the best results. However, these models require prior information about the aspect and scales of target objects, needing more hyperparameters to fit. In addition, using anchors to fit bounding boxes seems far from how our visual system does the same visual task. Instead, our visual system uses the interactions of different scene parts to semantically identify objects, called perceptual grouping. An object detection methodology closer to the natural model is anchor-free detection, where models like FCOS or Centernet have shown competitive results, but these have not yet exploited the concept of perceptual grouping. Therefore, to increase the effectiveness of anchor-free models keeping the inference time low, we propose to add non-local attention (NL modules) modules to boost the feature map of the underlying backbone. NL modules implement the perceptual grouping mechanism, allowing receptive fields to cooperate in visual representation learning. We show that non-local modules combined with an FCOS head (NL-FCOS) are practical and efficient. Thus, we establish state-of-the-art performance in clothing detection and handwritten amount recognition problems.
Forecasting with Economic News
Venue: arXiv cs.CE 2022
Year: 2022

The goal of this paper is to evaluate the informational content of sentiment extracted from news articles about the state of the economy. We propose a fine-grained aspect-based sentiment analysis that has two main characteristics: 1) we consider only the text in the article that is semantically dependent on a term of interest (aspect-based) and, 2) assign a sentiment score to each word based on a dictionary that we develop for applications in economics and finance (fine-grained). Our data set includes six large US newspapers, for a total of over 6.6 million articles and 4.2 billion words. Our findings suggest that several measures of economic sentiment track closely business cycle fluctuations and that they are relevant predictors for four major macroeconomic variables. We find that there are significant improvements in forecasting when sentiment is considered along with macroeconomic factors. In addition, we also find that sentiment matters to explains the tails of the probability distribution across several macroeconomic variables.
Texture based Prototypical Network for Few-Shot Semantic Segmentation of Forest Cover: Generalizing for Different Geographical Regions
Venue: arXiv cs.CV 2022
Year: 2022

Forest plays a vital role in reducing greenhouse gas emissions and mitigating climate change besides maintaining the world's biodiversity. The existing satellite-based forest monitoring system utilizes supervised learning approaches that are limited to a particular region and depend on manually annotated data to identify forest. This work envisages forest identification as a few-shot semantic segmentation task to achieve generalization across different geographical regions. The proposed few-shot segmentation approach incorporates a texture attention module in the prototypical network to highlight the texture features of the forest. Indeed, the forest exhibits a characteristic texture different from other classes, such as road, water, etc. In this work, the proposed approach is trained for identifying tropical forests of South Asia and adapted to determine the temperate forest of Central Europe with the help of a few (one image for 1-shot) manually annotated support images of the temperate forest. An IoU of 0.62 for forest class (1-way 1-shot) was obtained using the proposed method, which is significantly higher (0.46 for PANet) than the existing few-shot semantic segmentation approach. This result demonstrates that the proposed approach can generalize across geographical regions for forest identification, creating an opportunity to develop a global forest cover identification tool.
IoT Forensic Frameworks (DFIF, IoTDOTS,FSAIoT): A Comprehensive Study
Venue: arXiv cs.CR 2022
Year: 2022

In the Internet of Things, millions of electronic items, including automobiles, smoke alarms, watches, eyeglasses, webcams, and other devices, are now connected to the Internet (IoT). Aside from the luxury and comfort that the individual obtains in the field of IoT, as well as its ability to communicate and obtain information easily and quickly, the other concerning aspect is the achievement of privacy and security in this connection, especially given the rapid increase in the number of existing and new IoT devices. Concerns, threats, and assaults related to IoT security have been regarded as a potential and problematic area of research. This necessitates the quick development or creation of suitable technologies with the nature of crimes in the IoT environment. On the other hand, criminal investigation specialists encounter difficulties and hurdles due to various locations, data types, instruments used, and device recognition. This paper provides an in-depth explanation of the criminal content of the Internet of Things. It compares its stages to the detailed stages of traditional digital forensics in terms of similarities and differences, the frameworks used in dealing with electronic crimes, and the techniques used in both types. This paper presents previous discussions of researchers in the field of digital forensics. For the IoT, which brings us to the most important parts of this paper, which is a comprehensive study of the IoT criminal frameworks that are used to protect communication in the field of IoT, such as Digital Forensic Investigation Framework (DFIF), Digital Forensic Framework for Smart Environments (IoTDOTS), Forensic State Acquisition from the Internet of Things (FSAIoT), and discusses the challenges in their general frameworks and provides solutions and strategies.
Scheduling UET-UCT DAGs of Depth Two on Two Processors
Venue: arXiv cs.DS 2022
Year: 2022

Given unit execution time (UET) tasks whose precedence constraints form a directed acyclic graph (DAG), the arcs are associated with unit communication time (UCT) delays. The problem is to schedule the tasks on two processors in order to minimize the makespan. Several polynomial algorithms in the literature are proposed for special classes of digraphs, but the complexity of solving this problem in general case stills a challenging open question. We propose in this paper a linear time algorithm to compute an optimal schedule for the class of DAGs of depth two.
Efficiently Evolving Swarm Behaviors Using Grammatical Evolution With PPA-style Behavior Trees
Venue: arXiv cs.NE 2022
Year: 2022

Evolving swarm behaviors with artificial agents is computationally expensive and challenging. Because reward structures are often sparse in swarm problems, only a few simulations among hundreds evolve successful swarm behaviors. Additionally, swarm evolutionary algorithms typically rely on ad hoc fitness structures, and novel fitness functions need to be designed for each swarm task. This paper evolves swarm behaviors by systematically combining Postcondition-Precondition-Action (PPA) canonical Behavior Trees (BT) with a Grammatical Evolution. The PPA structure replaces ad hoc reward structures with systematic postcondition checks, which allows a common grammar to learn solutions to different tasks using only environmental cues and BT feedback. The static performance of learned behaviors is poor because no agent learns all necessary subtasks, but performance while evolving is excellent because agents can quickly change behaviors in new contexts. The evolving algorithm succeeded in 75\% of learning trials for both foraging and nest maintenance tasks, an eight-fold improvement over prior work.
Electric-field-coupled oscillators for collective electrochemical perception in underwater robotics
Venue: arXiv cs.RO 2022
Year: 2022

This work explores the application of nonlinear oscillators coupled by electric field in water for collective tasks in underwater robotics. Such coupled oscillators operate in clear and colloidal (mud, bottom silt) water and represent a collective electrochemical sensor that is sensitive to global environmental parameters, geometry of common electric field and spatial dynamics of autonomous underwater vehicles (AUVs). Implemented in hardware and software, this approach can be used to create global awareness in the group of robots, which possess limited sensing and communication capabilities. Using oscillators from different AUVs enables extending the range limitations related to electric dipole of a single AUV. Applications of this technique are demonstrated for detecting the number of AUVs, distances between them, perception of dielectric objects, synchronization of behavior and discrimination between 'collective self' and 'collective non-self' through an 'electrical mirror'. These approaches have been implemented in several research projects with AUVs in fresh and salt water.
Improving The Diagnosis of Thyroid Cancer by Machine Learning and Clinical Data
Venue: arXiv cs.LG 2022
Year: 2022

Thyroid cancer is a common endocrine carcinoma that occurs in the thyroid gland. Much effort has been invested in improving its diagnosis, and thyroidectomy remains the primary treatment method. A successful operation without unnecessary side injuries relies on an accurate preoperative diagnosis. Current human assessment of thyroid nodule malignancy is prone to errors and may not guarantee an accurate preoperative diagnosis. This study proposed a machine framework to predict thyroid nodule malignancy based on a novel clinical dataset we collected. The 10-fold cross-validation, bootstrap analysis, and permutation predictor importance were applied to estimate and interpret the model performance under uncertainty. The comparison between model prediction and expert assessment shows the advantage of our framework over human judgment in predicting thyroid nodule malignancy. Our method is accurate, interpretable, and thus useable as additional evidence in the preoperative diagnosis for thyroid cancer.
Bayesian Photonic Accelerators for Energy Efficient and Noise Robust Neural Processing
Venue: arXiv cs.ET 2022
Year: 2022

Artificial neural networks are efficient computing platforms inspired by the brain. Such platforms can tackle a vast area of real-life tasks ranging from image processing to language translation. Silicon photonic integrated chips (PICs), by employing coherent interactions in Mach-Zehnder interferometers, are promising accelerators offering record low power consumption and ultra-fast matrix multiplication. Such photonic accelerators, however, suffer from phase uncertainty due to fabrication errors and crosstalk effects that inhibit the development of high-density implementations. In this work, we present a Bayesian learning framework for such photonic accelerators. In addition to the conventional log-likelihood optimization path, two novel training schemes are derived, namely a regularized version and a fully Bayesian learning scheme. They are applied on a photonic neural network with 512 phase shifters targeting the MNIST dataset. The new schemes, when combined with a pre-characterization stage that provides the passive offsets, are able to dramatically decrease the operational power of the PIC beyond 70%, with just a slight loss in classification accuracy. The full Bayesian scheme, apart from this energy reduction, returns information with respect to the sensitivity of the phase shifters. This information is used to de-activate 31% of the phase actuators and, thus, significantly simplify the driving system.