OpenRaiser/Intern-Atlas huggingface dataset:
Small-Sample Inferred Adaptive Recoding for Batched Network Coding
Venue: arXiv cs.IT 2021
Year: 2021

Batched network coding is a low-complexity network coding solution to feedbackless multi-hop wireless packet network transmission with packet loss. The data to be transmitted is encoded into batches where each of which consists of a few coded packets. Unlike the traditional forwarding strategy, the intermediate network nodes have to perform recoding, which generates recoded packets by network coding operations restricted within the same batch. Adaptive recoding is a technique to adapt the fluctuation of packet loss by optimizing the number of recoded packets per batch to enhance the throughput. The input rank distribution, which is a piece of information regarding the batches arriving at the node, is required to apply adaptive recoding. However, this distribution is not known in advance in practice as the incoming link's channel condition may change from time to time. On the other hand, to fully utilize the potential of adaptive recoding, we need to have a good estimation of this distribution. In other words, we need to guess this distribution from a few samples so that we can apply adaptive recoding as soon as possible. In this paper, we propose a distributionally robust optimization for adaptive recoding with a small-sample inferred prediction of the input rank distribution. We develop an algorithm to efficiently solve this optimization with the support of theoretical guarantees that our optimization's performance would constitute as a confidence lower bound of the optimal throughput with high probability.
Randomized Multiple Model Multiple Hypothesis Tracking
Venue: arXiv cs.IT 2021
Year: 2021

This paper considers the data association problem for multi-target tracking. Multiple hypothesis tracking is a popular algorithm for solving this problem but it is NP-hard and is is quite complicated for a large number of targets or for tracking maneuvering targets. To improve tracking performance and enhance robustness, we propose a randomized multiple model multiple hypothesis tracking method, which has three distinctive advantages. First, it yields a randomized data association solution which maximizes the expectation of the logarithm of the posterior probability and can be solved efficiently by linear programming. Next, the state estimation performance is improved by the random coefficient matrices Kalman filter, which mitigates the difficulty introduced by randomized data association, i.e., where the coefficient matrices of the dynamic system are random. Third, the probability that the target follows a specific dynamic model is derived by jointly optimizing the multiple possible models and data association hypotheses, and it does not require prior mode transition probabilities. Thus, it is more robust for tracking multiple maneuvering targets. Simulations demonstrate the efficiency and superior results of the proposed algorithm over interacting multiple model multiple hypothesis tracking.
TimeGym: Debugging for Time Series Modeling in Python
Venue: arXiv cs.LG 2021
Year: 2021

We introduce the TimeGym Forecasting Debugging Toolkit, a Python library for testing and debugging time series forecasting pipelines. TimeGym simplifies the testing forecasting pipeline by providing generic tests for forecasting pipelines fresh out of the box. These tests are based on common modeling challenges of time series. Our library enables forecasters to apply a Test-Driven Development approach to forecast modeling, using specified oracles to generate artificial data with noise.
A Review on Oracle Issues in Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning contrasts with traditional software development in that the oracle is the data, and the data is not always a correct representation of the problem that machine learning tries to model. We present a survey of the oracle issues found in machine learning and state-of-the-art solutions for dealing with these issues. These include lines of research for differential testing, metamorphic testing, and test coverage. We also review some recent improvements to robustness during modeling that reduce the impact of oracle issues, as well as tools and frameworks for assisting in testing and discovering issues specific to the dataset.
Finding Collisions in Interactive Protocols -- Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
Venue: arXiv cs.CR 2021
Year: 2021

We study the round and communication complexities of various cryptographic protocols. We give tight lower bounds on the round and communication complexities of any fully black-box reduction of a statistically hiding commitment scheme from one-way permutations, and from trapdoor permutations. As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols and the reconstruction paradigm of Gennaro and Trevisan (FOCS '00).
Automated Driver Testing for Small Footprint Embedded Systems
Venue: arXiv cs.SE 2021
Year: 2021

Embedded systems represent a billionaire market and are present in most of the processors produced in the world.Embedded software interacts with external peripherals such as sensors and actuators through drivers. The strong interaction between drivers and external peripherals often hamper embedded software development, in special the testing task, giving that the physical environment may not be deterministic and difficult to be recreated during the tests, the hardware may not be available or its presence may not be desirable or costly. Aiming at addressing these problems, this paper introduces a solution to test drivers on microcontrollers, based on a method that uses three components: a Device Under Test (DUT), a Double device, and a computer. The computer runs a test orchestration code, while the DUT runs the test target code, and the Double plays the role of the real external peripherals that interact with the DUT. The proposed solution was successfully implemented and validated using different protocols.
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing
Venue: arXiv cs.CR 2021
Year: 2021

This paper uses a variant of the notion of \emph{inaccessible entropy} (Haitner, Reingold, Vadhan and Wee, STOC 2009), to give an alternative construction and proof for the fundamental result, first proved by Rompel (STOC 1990), that \emph{Universal One-Way Hash Functions (UOWHFs)} can be based on any one-way functions. We observe that a small tweak of any one-way function $f$ is already a weak form of a UOWHF: consider the function $F(x,i)$ that returns the $i$-bit-long prefix of $f(x)$. If $F$ were a UOWHF then given a random $x$ and $i$ it would be hard to come up with $x'\neq x$ such that $F(x,i)=F(x',i)$. While this may not be the case, we show (rather easily) that it is hard to sample $x'$ with almost full entropy among all the possible such values of $x'$. The rest of our construction simply amplifies and exploits this basic property.Combined with other recent work, the construction of three fundamental cryptographic primitives (Pseudorandom Generators, Statistically Hiding Commitments and UOWHFs) out of one-way functions is now to a large extent unified. In particular, all three constructions rely on and manipulate computational notions of entropy in similar ways. Pseudorandom Generators rely on the well-established notion of pseudoentropy, whereas Statistically Hiding Commitments and UOWHFs rely on the newer notion of inaccessible entropy.
Sentiment and Emotion Classification of Epidemic Related Bilingual data from Social Media
Venue: arXiv cs.LG 2021
Year: 2021

In recent years, sentiment analysis and emotion classification are two of the most abundantly used techniques in the field of Natural Language Processing (NLP). Although sentiment analysis and emotion classification are used commonly in applications such as analyzing customer reviews, the popularity of candidates contesting in elections, and comments about various sporting events; however, in this study, we have examined their application for epidemic outbreak detection. Early outbreak detection is the key to deal with epidemics effectively, however, the traditional ways of outbreak detection are time-consuming which inhibits prompt response from the respective departments. Social media platforms such as Twitter, Facebook, Instagram, etc. allow the users to express their thoughts related to different aspects of life, and therefore, serve as a substantial source of information in such situations. The proposed study exploits the bilingual (Urdu and English) data from Twitter and NEWS websites related to the dengue epidemic in Pakistan, and sentiment analysis and emotion classification are performed to acquire deep insights from the data set for gaining a fair idea related to an epidemic outbreak. Machine learning and deep learning algorithms have been used to train and implement the models for the execution of both tasks. The comparative performance of each model has been evaluated using accuracy, precision, recall, and f1-measure.
Technical Report for Valence-Arousal Estimation on Affwild2 Dataset
Venue: arXiv cs.CV 2021
Year: 2021

In this work, we describe our method for tackling the valence-arousal estimation challenge from ABAW FG-2020 Competition. The competition organizers provide an in-the-wild Aff-Wild2 dataset for participants to analyze affective behavior in real-life settings. We use MIMAMO Net \cite{deng2020mimamo} model to achieve information about micro-motion and macro-motion for improving video emotion recognition and achieve Concordance Correlation Coefficient (CCC) of 0.415 and 0.511 for valence and arousal on the reselected validation set.
Broadly Applicable Targeted Data Sample Omission Attacks
Venue: arXiv cs.LG 2021
Year: 2021

We introduce a novel clean-label targeted poisoning attack on learning mechanisms. While classical poisoning attacks typically corrupt data via addition, modification and omission, our attack focuses on data omission only. Our attack misclassifies a single, targeted test sample of choice, without manipulating that sample. We demonstrate the effectiveness of omission attacks against a large variety of learners including deep neural networks, SVM and decision trees, using several datasets including MNIST, IMDB and CIFAR. The focus of our attack on data omission only is beneficial as well, as it is simpler to implement and analyze. We show that, with a low attack budget, our attack's success rate is above 80%, and in some cases 100%, for white-box learning. It is systematically above the reference benchmark for black-box learning. For both white-box and black-box cases, changes in model accuracy are negligible, regardless of the specific learner and dataset. We also prove theoretically in a simplified agnostic PAC learning framework that, subject to dataset size and distribution, our omission attack succeeds with high probability against any successful simplified agnostic PAC learner.
Towards Error Measures which Influence a Learners Inductive Bias to the Ground Truth
Venue: arXiv cs.LG 2021
Year: 2021

Artificial intelligence is applied in a range of sectors, and is relied upon for decisions requiring a high level of trust. For regression methods, trust is increased if they approximate the true input-output relationships and perform accurately outside the bounds of the training data. But often performance off-test-set is poor, especially when data is sparse. This is because the conditional average, which in many scenarios is a good approximation of the `ground truth', is only modelled with conventional Minkowski-r error measures when the data set adheres to restrictive assumptions, with many real data sets violating these. To combat this there are several methods that use prior knowledge to approximate the `ground truth'. However, prior knowledge is not always available, and this paper investigates how error measures affect the ability for a regression method to model the `ground truth' in these scenarios. Current error measures are shown to create an unhelpful bias and a new error measure is derived which does not exhibit this behaviour. This is tested on 36 representative data sets with different characteristics, showing that it is more consistent in determining the `ground truth' and in giving improved predictions in regions beyond the range of the training data.
Federated Multi-View Learning for Private Medical Data Integration and Analysis
Venue: arXiv cs.AI 2021
Year: 2021

Along with the rapid expansion of information technology and digitalization of health data, there is an increasing concern on maintaining data privacy while garnering the benefits in medical field. Two critical challenges are identified: Firstly, medical data is naturally distributed across multiple local sites, making it difficult to collectively train machine learning models without data leakage. Secondly, in medical applications, data are often collected from different sources and views, resulting in heterogeneity and complexity that requires reconciliation. This paper aims to provide a generic Federated Multi-View Learning (FedMV) framework for multi-view data leakage prevention, which is based on different types of local data availability and enables to accommodate two types of problems: Vertical Federated Multi-View Learning (V-FedMV) and Horizontal Federated Multi-View Learning (H-FedMV). We experimented with real-world keyboard data collected from BiAffect study. The results demonstrated that the proposed FedMV approach can make full use of multi-view data in a privacy-preserving way, and both V-FedMV and H-FedMV methods perform better than their single-view and pairwise counterparts. Besides, the proposed model can be easily adapted to deal with multi-view sequential data in a federated environment, which has been modeled and experimentally studied. To the best of our knowledge, this framework is the first to consider both vertical and horizontal diversification in the multi-view setting, as well as their sequential federated learning.
Deterministic Rounding of Dynamic Fractional Matchings
Venue: arXiv cs.DS 2021
Year: 2021

We present a framework for deterministically rounding a dynamic fractional matching. Applying our framework in a black-box manner on top of existing fractional matching algorithms, we derive the following new results: (1) The first deterministic algorithm for maintaining a $(2-δ)$-approximate maximum matching in a fully dynamic bipartite graph, in arbitrarily small polynomial update time. (2) The first deterministic algorithm for maintaining a $(1+δ)$-approximate maximum matching in a decremental bipartite graph, in polylogarithmic update time. (3) The first deterministic algorithm for maintaining a $(2+δ)$-approximate maximum matching in a fully dynamic general graph, in small polylogarithmic (specifically, $O(\log^4 n)$) update time. These results are respectively obtained by applying our framework on top of the fractional matching algorithms of Bhattacharya et al. [STOC'16], Bernstein et al. [FOCS'20], and Bhattacharya and Kulkarni [SODA'19]. Prior to our work, there were two known general-purpose rounding schemes for dynamic fractional matchings. Both these schemes, by Arar et al. [ICALP'18] and Wajc [STOC'20], were randomized. Our rounding scheme works by maintaining a good {\em matching-sparsifier} with bounded arboricity, and then applying the algorithm of Peleg and Solomon [SODA'16] to maintain a near-optimal matching in this low arboricity graph. To the best of our knowledge, this is the first dynamic matching algorithm that works on general graphs by using an algorithm for low-arboricity graphs as a black-box subroutine. This feature of our rounding scheme might be of independent interest.
Height Estimation of Children under Five Years using Depth Images
Venue: arXiv cs.CV 2021
Year: 2021

Malnutrition is a global health crisis and is the leading cause of death among children under five. Detecting malnutrition requires anthropometric measurements of weight, height, and middle-upper arm circumference. However, measuring them accurately is a challenge, especially in the global south, due to limited resources. In this work, we propose a CNN-based approach to estimate the height of standing children under five years from depth images collected using a smart-phone. According to the SMART Methodology Manual [5], the acceptable accuracy for height is less than 1.4 cm. On training our deep learning model on 87131 depth images, our model achieved an average mean absolute error of 1.64% on 57064 test images. For 70.3% test images, we estimated height accurately within the acceptable 1.4 cm range. Thus, our proposed solution can accurately detect stunting (low height-for-age) in standing children below five years of age.
Determining 4-edge-connected components in linear time
Venue: arXiv cs.DS 2021
Year: 2021

In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-edge-cuts in a given 3-edge-connected graph, and then we use the output of this algorithm in order to determine the 4-edge-connected components of the graph.
GANs for Urban Design
Venue: arXiv cs.CV 2021
Year: 2021

Development and diffusion of machine learning and big data tools provide a new tool for architects and urban planners that could be used as analytical or design instruments. The topic investigated in this paper is the application of Generative Adversarial Networks to the design of an urban block. The research presents a flexible model able to adapt to the morphological characteristics of a city. This method does not define explicitly any of the parameters of an urban block typical for a city, the algorithm learns them from the existing urban context. This approach has been applied to the cities with different morphology: Milan, Amsterdam, Tallinn, Turin, and Bengaluru in order to see the performance of the model and the possibility of style translation between different cities. The data are gathered from Openstreetmap and Open Data portals of the cities. This research presents the results of the experiments and their quantitative and qualitative evaluation.
Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits
Venue: arXiv cs.CC 2021
Year: 2021

We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over the reals and the complex numbers for the following classes: (1) Set-multilinear depth-$3$ circuits of constant top fan-in $ΣΠΣ\{\sqcup_j X_j\}(k)$ circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for $d$ dimensional tensors for any $d$, but is interesting even for $d=3$. (2) Sums of powers of constantly many linear forms ($Σ\wedgeΣ$ circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. (3) Multilinear depth-3 circuits of constant top fan-in (multilinear $ΣΠΣ(k)$ circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09'). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of $ΣΠΣ(k)$ circuits that also work over large/infinite fields were for the setting when the top fan-in $k$ is at most $2$ (see Sinha 16' and Sinha 20').
Verifiable Computing Using Computation Fingerprints Within FHE
Venue: arXiv cs.CR 2021
Year: 2021

We suggest using Fully Homomorphic Encryption (FHE) to be used, not only to keep the privacy of information but also, to verify computations with no additional significant overhead, using only part of the variables length for verification. This method supports the addition of encrypted values as well as multiplication of encrypted values by the addition of their logarithmic representations and is based on a separation between hardware functionalities. The computer/server performs blackbox additions and is based on the separation of server/device/hardware, such as the enclave, that may deal with additions of logarithmic values and exponentiation. The main idea is to restrict the computer operations and to use part of the variable for computation verification (computation fingerprints) and the other for the actual calculation. The verification part holds the FHE value, of which the calculated result is known (either due to computing locally once or from previous verified computations) and will be checked against the returned FHE value. We prove that a server with bit computation granularity can return consistent encrypted wrong results even when the public key is not provided. For the case of computer word granularity the verification and the actual calculation parts are separated, the verification part (the consecutive bits from the LSB to the MSB of the variables) is fixed across all input vectors. We also consider the case of Single Instruction Multiple Data (SIMD) where the computation fingerprints index in the input vectors is fixed across all vectors.
PathBench: A Benchmarking Platform for Classical and Learned Path Planning Algorithms
Venue: arXiv cs.RO 2021
Year: 2021

Path planning is a key component in mobile robotics. A wide range of path planning algorithms exist, but few attempts have been made to benchmark the algorithms holistically or unify their interface. Moreover, with the recent advances in deep neural networks, there is an urgent need to facilitate the development and benchmarking of such learning-based planning algorithms. This paper presents PathBench, a platform for developing, visualizing, training, testing, and benchmarking of existing and future, classical and learned 2D and 3D path planning algorithms, while offering support for Robot Oper-ating System (ROS). Many existing path planning algorithms are supported; e.g. A*, wavefront, rapidly-exploring random tree, value iteration networks, gated path planning networks; and integrating new algorithms is easy and clearly specified. We demonstrate the benchmarking capability of PathBench by comparing implemented classical and learned algorithms for metrics, such as path length, success rate, computational time and path deviation. These evaluations are done on built-in PathBench maps and external path planning environments from video games and real world databases. PathBench is open source.