OpenRaiser/Intern-Atlas huggingface dataset:
Street Crossing Aid Using Light-weight CNNs for the Visually Impaired
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we address an issue that the visually impaired commonly face while crossing intersections and propose a solution that takes form as a mobile application. The application utilizes a deep learning convolutional neural network model, LytNetV2, to output necessary information that the visually impaired may lack when without human companions or guide-dogs. A prototype of the application runs on iOS devices of versions 11 or above. It is designed for comprehensiveness, concision, accuracy, and computational efficiency through delivering the two most important pieces of information, pedestrian traffic light color and direction, required to cross the road in real-time. Furthermore, it is specifically aimed to support those facing financial burden as the solution takes the form of a free mobile application. Through the modification and utilization of key principles in MobileNetV3 such as depthwise seperable convolutions and squeeze-excite layers, the deep neural network model achieves a classification accuracy of 96% and average angle error of 6.15 degrees, while running at a frame rate of 16.34 frames per second. Additionally, the model is trained as an image classifier, allowing for a faster and more accurate model. The network is able to outperform other methods such as object detection and non-deep learning algorithms in both accuracy and thoroughness. The information is delivered through both auditory signals and vibrations, and it has been tested on seven visually impaired and has received above satisfactory responses.
Deep Learning for Deepfakes Creation and Detection: A Survey
Venue: arXiv cs.CV 2022
Year: 2022

Deep learning has been successfully applied to solve various complex problems ranging from big data analytics to computer vision and human-level control. Deep learning advances however have also been employed to create software that can cause threats to privacy, democracy and national security. One of those deep learning-powered applications recently emerged is deepfake. Deepfake algorithms can create fake images and videos that humans cannot distinguish them from authentic ones. The proposal of technologies that can automatically detect and assess the integrity of digital visual media is therefore indispensable. This paper presents a survey of algorithms used to create deepfakes and, more importantly, methods proposed to detect deepfakes in the literature to date. We present extensive discussions on challenges, research trends and directions related to deepfake technologies. By reviewing the background of deepfakes and state-of-the-art deepfake detection methods, this study provides a comprehensive overview of deepfake techniques and facilitates the development of new and more robust methods to deal with the increasingly challenging deepfakes.
Advice Complexity of Adaptive Priority Algorithms
Venue: arXiv cs.DS 2022
Year: 2022

The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. We also present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.
QuaRL: Quantization for Fast and Environmentally Sustainable Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

Deep reinforcement learning continues to show tremendous potential in achieving task-level autonomy, however, its computational and energy demands remain prohibitively high. In this paper, we tackle this problem by applying quantization to reinforcement learning. To that end, we introduce a novel Reinforcement Learning (RL) training paradigm, \textit{ActorQ}, to speed up actor-learner distributed RL training. \textit{ActorQ} leverages 8-bit quantized actors to speed up data collection without affecting learning convergence. Our quantized distributed RL training system, \textit{ActorQ}, demonstrates end-to-end speedups \blue{between 1.5 $\times$ and 5.41$\times$}, and faster convergence over full precision training on a range of tasks (Deepmind Control Suite) and different RL algorithms (D4PG, DQN). Furthermore, we compare the carbon emissions (Kgs of CO2) of \textit{ActorQ} versus standard reinforcement learning \blue{algorithms} on various tasks. Across various settings, we show that \textit{ActorQ} enables more environmentally friendly reinforcement learning by achieving \blue{carbon emission improvements between 1.9$\times$ and 3.76$\times$} compared to training RL-agents in full-precision. We believe that this is the first of many future works on enabling computationally energy-efficient and sustainable reinforcement learning. The source code is available here for the public to use: \url{https://github.com/harvard-edge/QuaRL}.
A Method of EV Detour-to-Recharge Behavior Modeling and Charging Station Deployment
Venue: arXiv cs.OH 2022
Year: 2022

Electric vehicles (EVs) are increasingly used in transportation. Worldwide use of EVs, for their limited battery capacity, calls for effective planning of EVs charging stations to enhance the efficiency of using EVs. This paper provides a methodology of describing EV detouring behavior for recharging, and based on this, we adopt the extra driving length caused by detouring and the length of uncompleted route as the indicators of evaluating an EV charging station deployment plan. In this way, we can simulate EV behavior based on travel data (demand). Then, a genetic algorithm (GA) based EV charging station sitting optimization method is developed to obtain an effective plan. A detailed case study based on a 100-node 203-branch transportation network within a 30 km * 30 km region is included to test the effectiveness of our method. Insights from our method may be applicable for charging station planning in various transportation networks.
Instagram Fake and Automated Account Detection
Venue: arXiv cs.IR 2022
Year: 2022

Fake engagement is one of the significant problems in Online Social Networks (OSNs) which is used to increase the popularity of an account in an inorganic manner. The detection of fake engagement is crucial because it leads to loss of money for businesses, wrong audience targeting in advertising, wrong product predictions systems, and unhealthy social network environment. This study is related with the detection of fake and automated accounts which leads to fake engagement on Instagram. Prior to this work, there were no publicly available dataset for fake and automated accounts. For this purpose, two datasets have been published for the detection of fake and automated accounts. For the detection of these accounts, machine learning algorithms like Naive Bayes, Logistic Regression, Support Vector Machines and Neural Networks are applied. Additionally, for the detection of automated accounts, cost sensitive genetic algorithm is proposed to handle the unnatural bias in the dataset. To deal with the unevenness problem in the fake dataset, Smote-nc algorithm is implemented. For the automated and fake account detection datasets, 86% and 96% classification accuracies are obtained, respectively.
Repairnator patches programs automatically
Venue: arXiv cs.SE 2022
Year: 2022

Repairnator is a bot. It constantly monitors software bugs discovered during continuous integration of open-source software and tries to fix them automatically. If it succeeds in synthesizing a valid patch, Repairnator proposes the patch to the human developers, disguised under a fake human identity. To date, Repairnator has been able to producepatches that were accepted by the human developers and permanently merged into the code base. This is a milestone for human-competitiveness in software engineering research on automatic program repair.
On the Risk of Cancelable Biometrics
Venue: arXiv cs.CV 2022
Year: 2022

Cancelable biometrics (CB) employs an irreversible transformation to convert the biometric features into transformed templates while preserving the relative distance between two templates for security and privacy protection. However, distance preservation invites unexpected security issues such as pre-image attacks, which are often neglected.This paper presents a generalized pre-image attack method and its extension version that operates on practical CB systems. We theoretically reveal that distance preservation property is a vulnerability source in the CB schemes. We then propose an empirical information leakage estimation algorithm to access the pre-image attack risk of the CB schemes. The experiments conducted with six CB schemes designed for the face, iris and fingerprint, demonstrate that the risks originating from the distance computed from two transformed templates significantly compromise the security of CB schemes. Our work reveals the potential risk of existing CB systems theoretically and experimentally.
Masked Gradient-Based Causal Structure Learning
Venue: arXiv cs.LG 2022
Year: 2022

This paper studies the problem of learning causal structures from observational data. We reformulate the Structural Equation Model (SEM) with additive noises in a form parameterized by binary graph adjacency matrix and show that, if the original SEM is identifiable, then the binary adjacency matrix can be identified up to super-graphs of the true causal graph under mild conditions. We then utilize the reformulated SEM to develop a causal structure learning method that can be efficiently trained using gradient-based optimization, by leveraging a smooth characterization on acyclicity and the Gumbel-Softmax approach to approximate the binary adjacency matrix. It is found that the obtained entries are typically near zero or one and can be easily thresholded to identify the edges. We conduct experiments on synthetic and real datasets to validate the effectiveness of the proposed method, and show that it readily includes different smooth model functions and achieves a much improved performance on most datasets considered.
Tree-based Intelligent Intrusion Detection System in Internet of Vehicles
Venue: arXiv cs.LG 2022
Year: 2022

The use of autonomous vehicles (AVs) is a promising technology in Intelligent Transportation Systems (ITSs) to improve safety and driving efficiency. Vehicle-to-everything (V2X) technology enables communication among vehicles and other infrastructures. However, AVs and Internet of Vehicles (IoV) are vulnerable to different types of cyber-attacks such as denial of service, spoofing, and sniffing attacks. In this paper, an intelligent intrusion detection system (IDS) is proposed based on tree-structure machine learning models. The results from the implementation of the proposed intrusion detection system on standard data sets indicate that the system has the ability to identify various cyber-attacks in the AV networks. Furthermore, the proposed ensemble learning and feature selection approaches enable the proposed system to achieve high detection rate and low computational cost simultaneously.
Review of Recent Heap Specification and Verification Techniques
Venue: arXiv cs.LO 2022
Year: 2022

The article provides an overview of the existing methods of dynamic memory verification; a comparative analysis is carried out; the applicability for solving problems of control, monitoring, and verification of dynamic memory is evaluated. This article is divided into eight sections. The first section introduces formal verification, followed by a section that discusses dynamic memory management problems. The third section discusses Hoare's calculus resumed by heap transformations to the stack. The fifth and sixth sections introduce the concept of dynamic memory shape analysis and the rotation of pointers. The seventh is on separation logic. The last section discusses possible areas of further research, particularly the recognition at recording level of various instances of objects; automation of proofs; "hot" code, that is, software code that updates itself when the program runs; expanding intuitiveness, for instance, on proof explanations.
IoTSign: Protecting Privacy and Authenticity of IoT using Discrete Cosine Based Steganography
Venue: arXiv cs.CR 2022
Year: 2022

Remotely generated data by Intent of Things (IoT) has recently had a lot of attention for their huge benefits such as efficient monitoring and risk reduction. The transmitted streams usually consist of periodical streams (e.g. activities) and highly private information (e.g. IDs). Despite the obvious benefits, the concerns are the secrecy and the originality of the transferred data. Surprisingly, although these concerns have been well studied for static data, they have received only limited attention for streaming data. Therefore, this paper introduces a new steganographic mechanism that provides (1) robust privacy protection of secret information by concealing them arbitrarily in the transported readings employing a random key, and (2) permanent proof of originality for the normal streams. This model surpasses our previous works by employing the Discrete Cosine Transform to expand the hiding capacity and reduce complexity. The resultant distortion has been accurately measured at all stages - the original, the stego, and the recovered forms - using a well-known measurement matrix called Percentage Residual Difference (PRD). After thorough experiments on three types of streams (i.e. chemical, environmental and smart homes), it has been proven that the original streams have not been affected (< 1 %). Also, the mathematical analysis shows that the model has much lighter (i.e. linear) computational complexity O(n) compared to existing work.
Faster Parallel Algorithm for Approximate Shortest Path
Venue: arXiv cs.DS 2022
Year: 2022

We present the first $m\,\text{polylog}(n)$ work, $\text{polylog}(n)$ time algorithm in the PRAM model that computes $(1+ε)$-approximate single-source shortest paths on weighted, undirected graphs. This improves upon the breakthrough result of Cohen~[JACM'00] that achieves $O(m^{1+ε_0})$ work and $\text{polylog}(n)$ time. While most previous approaches, including Cohen's, leveraged the power of hopsets, our algorithm builds upon the recent developments in \emph{continuous optimization}, studying the shortest path problem from the lens of the closely-related \emph{minimum transshipment} problem. To obtain our algorithm, we demonstrate a series of near-linear work, polylogarithmic-time reductions between the problems of approximate shortest path, approximate transshipment, and $\ell_1$-embeddings, and establish a recursive algorithm that cycles through the three problems and reduces the graph size on each cycle. As a consequence, we also obtain faster parallel algorithms for approximate transshipment and $\ell_1$-embeddings with polylogarithmic distortion. The minimum transshipment algorithm in particular improves upon the previous best $m^{1+o(1)}$ work sequential algorithm of Sherman~[SODA'17]. To improve readability, the paper is almost entirely self-contained, save for several staple theorems in algorithms and combinatorics.
Reconfiguring k-path vertex covers
Venue: arXiv cs.DS 2022
Year: 2022

A vertex subset $I$ of a graph $G$ is called a $k$-path vertex cover if every path on $k$ vertices in $G$ contains at least one vertex from $I$. The \textsc{$k$-Path Vertex Cover Reconfiguration ($k$-PVCR)} problem asks if one can transform one $k$-path vertex cover into another via a sequence of $k$-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of \textsc{$k$-PVCR} from the viewpoint of graph classes under the well-known reconfiguration rules: $\mathsf{TS}$, $\mathsf{TJ}$, and $\mathsf{TAR}$. The problem for $k=2$, known as the \textsc{Vertex Cover Reconfiguration (VCR)} problem, has been well-studied in the literature. We show that certain known hardness results for \textsc{VCR} on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for \textsc{$k$-PVCR}. In particular, we prove a complexity dichotomy for \textsc{$k$-PVCR} on general graphs: on those whose maximum degree is $3$ (and even planar), the problem is $\mathtt{PSPACE}$-complete, while on those whose maximum degree is $2$ (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for \textsc{$k$-PVCR} on trees under each of $\mathsf{TJ}$ and $\mathsf{TAR}$. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given $k$-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.
Correcting Sociodemographic Selection Biases for Population Prediction from Social Media
Venue: arXiv cs.SI 2022
Year: 2022

Social media is increasingly used for large-scale population predictions, such as estimating community health statistics. However, social media users are not typically a representative sample of the intended population -- a "selection bias". Within the social sciences, such a bias is typically addressed with restratification techniques, where observations are reweighted according to how under- or over-sampled their socio-demographic groups are. Yet, restratifaction is rarely evaluated for improving prediction. In this two-part study, we first evaluate standard, "out-of-the-box" restratification techniques, finding they provide no improvement and often even degraded prediction accuracies across four tasks of esimating U.S. county population health statistics from Twitter. The core reasons for degraded performance seem to be tied to their reliance on either sparse or shrunken estimates of each population's socio-demographics. In the second part of our study, we develop and evaluate Robust Poststratification, which consists of three methods to address these problems: (1) estimator redistribution to account for shrinking, as well as (2) adaptive binning and (3) informed smoothing to handle sparse socio-demographic estimates. We show that each of these methods leads to significant improvement in prediction accuracies over the standard restratification approaches. Taken together, Robust Poststratification enables state-of-the-art prediction accuracies, yielding a 53.0% increase in variance explained (R^2) in the case of surveyed life satisfaction, and a 17.8% average increase across all tasks.
Privacy-Preserving Gradient Boosting Decision Trees
Venue: arXiv cs.LG 2022
Year: 2022

The Gradient Boosting Decision Tree (GBDT) is a popular machine learning model for various tasks in recent years. In this paper, we study how to improve model accuracy of GBDT while preserving the strong guarantee of differential privacy. Sensitivity and privacy budget are two key design aspects for the effectiveness of differential private models. Existing solutions for GBDT with differential privacy suffer from the significant accuracy loss due to too loose sensitivity bounds and ineffective privacy budget allocations (especially across different trees in the GBDT model). Loose sensitivity bounds lead to more noise to obtain a fixed privacy level. Ineffective privacy budget allocations worsen the accuracy loss especially when the number of trees is large. Therefore, we propose a new GBDT training algorithm that achieves tighter sensitivity bounds and more effective noise allocations. Specifically, by investigating the property of gradient and the contribution of each tree in GBDTs, we propose to adaptively control the gradients of training data for each iteration and leaf node clipping in order to tighten the sensitivity bounds. Furthermore, we design a novel boosting framework to allocate the privacy budget between trees so that the accuracy loss can be further reduced. Our experiments show that our approach can achieve much better model accuracy than other baselines.
On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs
Venue: arXiv cs.AI 2022
Year: 2022

The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. For undirected graphs, solvability can be decided in polynomial time, as has been shown already in the eighties. Further, recently it has been shown that a special case on directed graphs is solvable in polynomial time. In this paper, we show that the problem is NP-hard in the general case. In addition, some upper bounds are proven.
Computing Equilibria in Binary Networked Public Goods Games
Venue: arXiv cs.GT 2022
Year: 2022

Public goods games study the incentives of individuals to contribute to a public good and their behaviors in equilibria. In this paper, we examine a specific type of public goods game where players are networked and each has binary actions, and focus on the algorithmic aspects of such games. First, we show that checking the existence of a pure-strategy Nash equilibrium is NP-complete. We then identify tractable instances based on restrictions of either utility functions or of the underlying graphical structure. In certain cases, we also show that we can efficiently compute a socially optimal Nash equilibrium. Finally, we propose a heuristic approach for computing approximate equilibria in general binary networked public goods games, and experimentally demonstrate its effectiveness.
Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem
Venue: arXiv cs.AI 2022
Year: 2022

In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k-wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k-wise Kemeny aggregation problem, we introduce a k-wise counterpart of the majority graph. This graph reveals useful to divide the aggregation problem into several sub-problems, which enables to speed up the exact computation of a consensus ranking. By introducing a k-wise counterpart of the Spearman distance, we also provide a 2-approximation algorithm for the k-wise Kemeny aggregation problem. We conclude with numerical tests.