OpenRaiser/Intern-Atlas huggingface dataset:
Approximating Nash Social Welfare under Binary XOS and Binary Subadditive Valuations
Venue: arXiv cs.GT 2021
Year: 2021

We study the problem of allocating indivisible goods among agents in a fair and economically efficient manner. In this context, the Nash social welfare-defined as the geometric mean of agents' valuations for their assigned bundles-stands as a fundamental measure that quantifies the extent of fairness of an allocation. Focusing on instances in which the agents' valuations have binary marginals, we develop essentially tight results for (approximately) maximizing Nash social welfare under two of the most general classes of complement-free valuations, i.e., under binary XOS and binary subadditive valuations. For binary XOS valuations, we develop a polynomial-time algorithm that finds a constant-factor (specifically $288$) approximation for the optimal Nash social welfare, in the standard value-oracle model. The allocations computed by our algorithm also achieve constant-factor approximation for social welfare and the groupwise maximin share guarantee. These results imply that-in the case of binary XOS valuations-there necessarily exists an allocation that simultaneously satisfies multiple (approximate) fairness and efficiency criteria. We complement the algorithmic result by proving that Nash social welfare maximization is APX-hard under binary XOS valuations. Furthermore, this work establishes an interesting separation between the binary XOS and binary subadditive settings. In particular, we prove that an exponential number of value queries are necessarily required to obtain even a sub-linear approximation for Nash social welfare under binary subadditive valuations.
Towards real time assessment of earthfill dams via Model Order Reduction
Venue: arXiv cs.CE 2021
Year: 2021

The use of Internet of Things (IoT) technologies is becoming a preferred solution for the assessment of tailings dams' safety. Real-time sensor monitoring proves to be a key tool for reducing the risk related to these ever-evolving earth-fill structures, that exhibit a high rate of sudden and hazardous failures. In order to optimally exploit real-time embankment monitoring, one major hindrance has to be overcome: the creation of a supporting numerical model for stability analysis, with rapid-enough response to perform data assimilation in real time. A model should be built, such that its response can be obtained faster than the physical evolution of the analyzed phenomenon. In this work, Reduced Order Modelling (ROM) is used to boost computational efficiency in solving the coupled hydro-mechanical system of equations governing the problem. The Reduced Basis method is applied to the coupled hydro-mechanical equations that govern the groundwater flow, that are made non-linear as a result of considering an unsaturated soil. The resulting model's performance is assessed by solving a 2D and a 3D problem relevant to tailings dams' safety. The ROM technique achieves a speedup of 3 to 15 times with respect to the full-order model (FOM) while maintaining high levels of accuracy.
The R-U-A-Robot Dataset: Helping Avoid Chatbot Deception by Detecting User Questions About Human or Non-Human Identity
Venue: arXiv cs.CL 2021
Year: 2021

Humans are increasingly interacting with machines through language, sometimes in contexts where the user may not know they are talking to a machine (like over the phone or a text chatbot). We aim to understand how system designers and researchers might allow their systems to confirm its non-human identity. We collect over 2,500 phrasings related to the intent of ``Are you a robot?". This is paired with over 2,500 adversarially selected utterances where only confirming the system is non-human would be insufficient or disfluent. We compare classifiers to recognize the intent and discuss the precision/recall and model complexity tradeoffs. Such classifiers could be integrated into dialog systems to avoid undesired deception. We then explore how both a generative research model (Blender) as well as two deployed systems (Amazon Alexa, Google Assistant) handle this intent, finding that systems often fail to confirm their non-human identity. Finally, we try to understand what a good response to the intent would be, and conduct a user study to compare the important aspects when responding to this intent.
On the Design of Strategic Task Recommendations for Sustainable Crowdsourcing-Based Content Moderation
Venue: arXiv cs.GT 2021
Year: 2021

Crowdsourcing-based content moderation is a platform that hosts content moderation tasks for crowd workers to review user submissions (e.g. text, images and videos) and make decisions regarding the admissibility of the posted content, along with a gamut of other tasks such as image labeling and speech-to-text conversion. In an attempt to reduce cognitive overload at the workers and improve system efficiency, these platforms offer personalized task recommendations according to the worker's preferences. However, the current state-of-the-art recommendation systems disregard the effects on worker's mental health, especially when they are repeatedly exposed to content moderation tasks with extreme content (e.g. violent images, hate-speech). In this paper, we propose a novel, strategic recommendation system for the crowdsourcing platform that recommends jobs based on worker's mental status. Specifically, this paper models interaction between the crowdsourcing platform's recommendation system (leader) and the worker (follower) as a Bayesian Stackelberg game where the type of the follower corresponds to the worker's cognitive atrophy rate and task preferences. We discuss how rewards and costs should be designed to steer the game towards desired outcomes in terms of maximizing the platform's productivity, while simultaneously improving the working conditions of crowd workers.
DISCO: accurate Discrete Scale Convolutions
Venue: arXiv cs.CV 2021
Year: 2021

Scale is often seen as a given, disturbing factor in many vision tasks. When doing so it is one of the factors why we need more data during learning. In recent work scale equivariance was added to convolutional neural networks. It was shown to be effective for a range of tasks. We aim for accurate scale-equivariant convolutional neural networks (SE-CNNs) applicable for problems where high granularity of scale and small kernel sizes are required. Current SE-CNNs rely on weight sharing and kernel rescaling, the latter of which is accurate for integer scales only. To reach accurate scale equivariance, we derive general constraints under which scale-convolution remains equivariant to discrete rescaling. We find the exact solution for all cases where it exists, and compute the approximation for the rest. The discrete scale-convolution pays off, as demonstrated in a new state-of-the-art classification on MNIST-scale and on STL-10 in the supervised learning setting. With the same SE scheme, we also improve the computational effort of a scale-equivariant Siamese tracker on OTB-13.
Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering
Venue: arXiv cs.SI 2021
Year: 2021

Triangle counting is a fundamental technique in network analysis, that has received much attention in various input models. The vast majority of triangle counting algorithms are targeted to static graphs. Yet, many real-world graphs are directed and temporal, where edges come with timestamps. Temporal triangles yield much more information, since they account for both the graph topology and the timestamps. Temporal triangle counting has seen a few recent results, but there are varying definitions of temporal triangles. In all cases, temporal triangle patterns enforce constraints on the time interval between edges (in the triangle). We define a general notion $(δ_{1,3}, δ_{1,2}, δ_{2,3})$-temporal triangles that allows for separate time constraints for all pairs of edges. Our main result is a new algorithm, DOTTT (Degeneracy Oriented Temporal Triangle Totaler), that exactly counts all directed variants of $(δ_{1,3}, δ_{1,2}, δ_{2,3})$-temporal triangles. Using the classic idea of degeneracy ordering with careful combinatorial arguments, we can prove that DOTTT runs in $O(mκ\log m)$ time, where $m$ is the number of (temporal) edges and $κ$ is the graph degeneracy (max core number). Up to log factors, this matches the running time of the best static triangle counters. Moreover, this running time is better than existing. DOTTT has excellent practical behavior and runs twice as fast as existing state-of-the-art temporal triangle counters (and is also more general). For example, DOTTT computes all types of temporal queries in Bitcoin temporal network with half a billion edges in less than an hour on a commodity machine.
Privacy-Preserving Training of Tree Ensembles over Continuous Data
Venue: arXiv cs.CR 2021
Year: 2021

Most existing Secure Multi-Party Computation (MPC) protocols for privacy-preserving training of decision trees over distributed data assume that the features are categorical. In real-life applications, features are often numerical. The standard ``in the clear'' algorithm to grow decision trees on data with continuous values requires sorting of training examples for each feature in the quest for an optimal cut-point in the range of feature values in each node. Sorting is an expensive operation in MPC, hence finding secure protocols that avoid such an expensive step is a relevant problem in privacy-preserving machine learning. In this paper we propose three more efficient alternatives for secure training of decision tree based models on data with continuous features, namely: (1) secure discretization of the data, followed by secure training of a decision tree over the discretized data; (2) secure discretization of the data, followed by secure training of a random forest over the discretized data; and (3) secure training of extremely randomized trees (``extra-trees'') on the original data. Approaches (2) and (3) both involve randomizing feature choices. In addition, in approach (3) cut-points are chosen randomly as well, thereby alleviating the need to sort or to discretize the data up front. We implemented all proposed solutions in the semi-honest setting with additive secret sharing based MPC. In addition to mathematically proving that all proposed approaches are correct and secure, we experimentally evaluated and compared them in terms of classification accuracy and runtime. We privately train tree ensembles over data sets with 1000s of instances or features in a few minutes, with accuracies that are at par with those obtained in the clear. This makes our solution orders of magnitude more efficient than the existing approaches, which are based on oblivious sorting.
BiToD: A Bilingual Multi-Domain Dataset For Task-Oriented Dialogue Modeling
Venue: arXiv cs.CL 2021
Year: 2021

Task-oriented dialogue (ToD) benchmarks provide an important avenue to measure progress and develop better conversational agents. However, existing datasets for end-to-end ToD modeling are limited to a single language, hindering the development of robust end-to-end ToD systems for multilingual countries and regions. Here we introduce BiToD, the first bilingual multi-domain dataset for end-to-end task-oriented dialogue modeling. BiToD contains over 7k multi-domain dialogues (144k utterances) with a large and realistic bilingual knowledge base. It serves as an effective benchmark for evaluating bilingual ToD systems and cross-lingual transfer learning approaches. We provide state-of-the-art baselines under three evaluation settings (monolingual, bilingual, and cross-lingual). The analysis of our baselines in different settings highlights 1) the effectiveness of training a bilingual ToD system compared to two independent monolingual ToD systems, and 2) the potential of leveraging a bilingual knowledge base and cross-lingual transfer learning to improve the system performance under low resource condition.
Variational Leakage: The Role of Information Complexity in Privacy Leakage
Venue: arXiv cs.LG 2021
Year: 2021

We study the role of information complexity in privacy leakage about an attribute of an adversary's interest, which is not known a priori to the system designer. Considering the supervised representation learning setup and using neural networks to parameterize the variational bounds of information quantities, we study the impact of the following factors on the amount of information leakage: information complexity regularizer weight, latent space dimension, the cardinalities of the known utility and unknown sensitive attribute sets, the correlation between utility and sensitive attributes, and a potential bias in a sensitive attribute of adversary's interest. We conduct extensive experiments on Colored-MNIST and CelebA datasets to evaluate the effect of information complexity on the amount of intrinsic leakage.
A novel method for recommendation systems using invasive weed optimization
Venue: arXiv cs.IR 2021
Year: 2021

One of the popular approaches in recommendation systems is Collaborative Filtering (CF). The most significant step in CF is choosing the appropriate set of users. For this purpose, similarity measures are usually used for computing the similarity between a specific user and the other users. This paper proposes a new invasive weed optimization (IWO) based CF approach that uses users' context to identify important and effective users set. By using a newly defined similarity measure based on both rating values and a measure values called confidence, the proposed approach calculates the similarity between users and thus identifies and filters the most similar users to a specific user. It then uses IWO to calculate the importance degree of users and finally, by using the identified important users and their importance degrees it predicts unknown ratings. To evaluate the proposed method, several experiments have been performed on two known real world datasets and the results show that the proposed method improves the state of the art results up to 15% in terms of Root Mean Square Error (RMSE) and Mean Absolute Error (MAE).
An End-to-End Breast Tumour Classification Model Using Context-Based Patch Modelling- A BiLSTM Approach for Image Classification
Venue: arXiv cs.CV 2021
Year: 2021

Researchers working on computational analysis of Whole Slide Images (WSIs) in histopathology have primarily resorted to patch-based modelling due to large resolution of each WSI. The large resolution makes WSIs infeasible to be fed directly into the machine learning models due to computational constraints. However, due to patch-based analysis, most of the current methods fail to exploit the underlying spatial relationship among the patches. In our work, we have tried to integrate this relationship along with feature-based correlation among the extracted patches from the particular tumorous region. For the given task of classification, we have used BiLSTMs to model both forward and backward contextual relationship. RNN based models eliminate the limitation of sequence size by allowing the modelling of variable size images within a deep learning model. We have also incorporated the effect of spatial continuity by exploring different scanning techniques used to sample patches. To establish the efficiency of our approach, we trained and tested our model on two datasets, microscopy images and WSI tumour regions. After comparing with contemporary literature we achieved the better performance with accuracy of 90% for microscopy image dataset. For WSI tumour region dataset, we compared the classification results with deep learning networks such as ResNet, DenseNet, and InceptionV3 using maximum voting technique. We achieved the highest performance accuracy of 84%. We found out that BiLSTMs with CNN features have performed much better in modelling patches into an end-to-end Image classification network. Additionally, the variable dimensions of WSI tumour regions were used for classification without the need for resizing. This suggests that our method is independent of tumour image size and can process large dimensional images without losing the resolution details.
Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization
Venue: arXiv cs.LG 2021
Year: 2021

Many popular learning-rate schedules for deep neural networks combine a decaying trend with local perturbations that attempt to escape saddle points and bad local minima. We derive convergence guarantees for bandwidth-based step-sizes, a general class of learning rates that are allowed to vary in a banded region. This framework includes many popular cyclic and non-monotonic step-sizes for which no theoretical guarantees were previously known. We provide worst-case guarantees for SGD on smooth non-convex problems under several bandwidth-based step sizes, including stagewise $1/\sqrt{t}$ and the popular step-decay (constant and then drop by a constant), which is also shown to be optimal. Moreover, we show that its momentum variant converges as fast as SGD with the bandwidth-based step-decay step-size. Finally, we propose novel step-size schemes in the bandwidth-based family and verify their efficiency on several deep neural network training tasks.
Generalized Linear One-Way Jumping Finite Automata
Venue: arXiv cs.FL 2021
Year: 2021

A new discontinuous model of computation called one-way jumping finite automata was defined by H. Chigahara et. al. This model was a restricted version of the model jumping finite automata. These automata read an input symbol-by-symbol and jump only in one direction. A generalized linear one-way jumping finite automaton makes jumps after deleting a substring of an input string and then changes its state. These automata can make sequence of jumps in only one direction on an input string either from left to right or from right to left. We show that newly defined model is powerful than its original counterpart. We define and compare the variants, generalized right linear one-way jumping finite automata and generalized left linear one-way jumping finite automata. We also compare the newly defined models with Chomsky hierarchy. Finally, we explore closure properties of the model.
KupenStack: Kubernetes based Cloud Native OpenStack
Venue: arXiv cs.DC 2021
Year: 2021

OpenStack is an open-source private cloud used to run VMs and its related cloud services. OpenStack deployment, management, and upgradation require lots of efforts and manual troubleshooting. Also, workloads and services offered by OpenStack cannot self-heal itself on failures. We present KupenStack, a Cloud-Native OpenStack as Code model built on top of Kubernetes stack as Custom Resources. KupenStack is a controller that interacts between Kubernetes and OpenStack and automates complex operations like scaling, LCM, zero-downtime, self-healing, version upgrades, configuration management, and offers OpenStack as a service through code. KupenStack builds cloud-native values like immutable infrastructure, declarative APIs for OpenStack without changing any OpenStack code. If a VM workload goes down for some reason, then KupenStack handles it and automatically spins up a new instance. KupenStack uses OpenStack on Kubernetes deployment for lifecycle management of OpenStack.
Extracting Weighted Automata for Approximate Minimization in Language Modelling
Venue: arXiv cs.LG 2021
Year: 2021

In this paper we study the approximate minimization problem for language modelling. We assume we are given some language model as a black box. The objective is to obtain a weighted finite automaton (WFA) that fits within a given size constraint and which mimics the behaviour of the original model while minimizing some notion of distance between the black box and the extracted WFA. We provide an algorithm for the approximate minimization of black boxes trained for language modelling of sequential data over a one-letter alphabet. By reformulating the problem in terms of Hankel matrices, we leverage classical results on the approximation of Hankel operators, namely the celebrated Adamyan-Arov-Krein (AAK) theory. This allows us to use the spectral norm to measure the distance between the black box and the WFA. We provide theoretical guarantees to study the potentially infinite-rank Hankel matrix of the black box, without accessing the training data, and we prove that our method returns an asymptotically-optimal approximation.
Fortifying Vehicular Security Through Low Overhead Physically Unclonable Functions
Venue: arXiv cs.CR 2021
Year: 2021

Within vehicles, the Controller Area Network (CAN) allows efficient communication between the electronic control units (ECUs) responsible for controlling the various subsystems. The CAN protocol was not designed to include much support for secure communication. The fact that so many critical systems can be accessed through an insecure communication network presents a major security concern. Adding security features to CAN is difficult due to the limited resources available to the individual ECUs and the costs that would be associated with adding the necessary hardware to support any additional security operations without overly degrading the performance of standard communication. Replacing the protocol is another option, but it is subject to many of the same problems. The lack of security becomes even more concerning as vehicles continue to adopt smart features. Smart vehicles have a multitude of communication interfaces would an attacker could exploit to gain access to the networks. In this work we propose a security framework that is based on physically unclonable functions (PUFs) and lightweight cryptography (LWC). The framework does not require any modification to the standard CAN protocol while also minimizing the amount of additional message overhead required for its operation. The improvements in our proposed framework results in major reduction in the number of CAN frames that must be sent during operation. For a system with 20 ECUs for example, our proposed framework only requires 6.5% of the number of CAN frames that is required by the existing approach to successfully authenticate every ECU.
Sensor Fusion-based GNSS Spoofing Attack Detection Framework for Autonomous Vehicles
Venue: arXiv cs.CR 2021
Year: 2021

In this study, a sensor fusion based GNSS spoofing attack detection framework is presented that consists of three concurrent strategies for an autonomous vehicle (AV): (i) prediction of location shift, (ii) detection of turns (left or right), and (iii) recognition of motion state (including standstill state). Data from multiple low-cost in-vehicle sensors (i.e., accelerometer, steering angle sensor, speed sensor, and GNSS) are fused and fed into a recurrent neural network model, which is a long short-term memory (LSTM) network for predicting the location shift, i.e., the distance that an AV travels between two consecutive timestamps. We have then combined k-Nearest Neighbors (k-NN) and Dynamic Time Warping (DTW) algorithms to detect turns using data from the steering angle sensor. In addition, data from an AV's speed sensor is used to recognize the AV's motion state including the standstill state. To prove the efficacy of the sensor fusion-based attack detection framework, attack datasets are created for three unique and sophisticated spoofing attacks turn by turn, overshoot, and stop using the publicly available real-world Honda Research Institute Driving Dataset (HDD). Our analysis reveals that the sensor fusion-based detection framework successfully detects all three types of spoofing attacks within the required computational latency threshold.