OpenRaiser/Intern-Atlas huggingface dataset:
Fast Neighborhood Rendezvous
Venue: arXiv cs.DC 2021
Year: 2021

In the rendezvous problem, two computing entities (called \emph{agents}) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous \emph{neighborhood rendezvous problem}, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in $O(Δ)$ rounds ($Δ$ is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in $o(Δ)$ rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of $O(\sqrt{n})$ rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, accessibility to neighborhood IDs, and randomization. The first algorithm runs within $\tilde{O}(\sqrt{nΔ/δ} + n/δ)$ rounds for graphs of the minimum degree larger than $\sqrt{n}$, where $n$ is the number of vertices in the graph, and $δ$ is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is $O(n)$, and achieves $\tilde{O}\left( \frac{n}{\sqrtδ} \right)$-round time complexity without using whiteboards. These algorithms attain $o(Δ)$-round complexity in the case of $δ= ω(\sqrt{n} \log n)$ and $δ= ω(n^{2/3} \log^{4/3} n)$ respectively.
Long Short-Term Temporal Meta-learning in Online Recommendation
Venue: arXiv cs.IR 2021
Year: 2021

An effective online recommendation system should jointly capture users' long-term and short-term preferences in both users' internal behaviors (from the target recommendation task) and external behaviors (from other tasks). However, it is extremely challenging to conduct fast adaptations to real-time new trends while making full use of all historical behaviors in large-scale systems, due to the real-world limitations in real-time training efficiency and external behavior acquisition. To address these practical challenges, we propose a novel Long Short-Term Temporal Meta-learning framework (LSTTM) for online recommendation. It arranges user multi-source behaviors in a global long-term graph and an internal short-term graph, and conducts different GAT-based aggregators and training strategies to learn user short-term and long-term preferences separately. To timely capture users' real-time interests, we propose a temporal meta-learning method based on MAML under an asynchronous optimization strategy for fast adaptation, which regards recommendations at different time periods as different tasks. In experiments, LSTTM achieves significant improvements on both offline and online evaluations. It has been deployed on a widely-used online recommendation system named WeChat Top Stories, affecting millions of users.
Covariance Matrix Adaptation Evolution Strategy Assisted by Principal Component Analysis
Venue: arXiv cs.NE 2021
Year: 2021

Over the past decades, more and more methods gain a giant development due to the development of technology. Evolutionary Algorithms are widely used as a heuristic method. However, the budget of computation increases exponentially when the dimensions increase. In this paper, we will use the dimensionality reduction method Principal component analysis (PCA) to reduce the dimension during the iteration of Covariance Matrix Adaptation Evolution Strategy (CMA-ES), which is a good Evolutionary Algorithm that is presented as the numeric type and useful for different kinds of problems. We assess the performance of our new methods in terms of convergence rate on multi-modal problems from the Black-Box Optimization Benchmarking (BBOB) problem set and we also use the framework COmparing Continuous Optimizers (COCO) to see how the new method going and compare it to the other algorithms.
PCA Event-Based Optical Flow for Visual Odometry
Venue: arXiv cs.CV 2021
Year: 2021

With the advent of neuromorphic vision sensors such as event-based cameras, a paradigm shift is required for most computer vision algorithms. Among these algorithms, optical flow estimation is a prime candidate for this process considering that it is linked to a neuromorphic vision approach. Usage of optical flow is widespread in robotics applications due to its richness and accuracy. We present a Principal Component Analysis (PCA) approach to the problem of event-based optical flow estimation. In this approach, we examine different regularization methods which efficiently enhance the estimation of the optical flow. We show that the best variant of our proposed method, dedicated to the real-time context of visual odometry, is about two times faster compared to state-of-the-art implementations while significantly improves optical flow accuracy.
NLP-IIS@UT at SemEval-2021 Task 4: Machine Reading Comprehension using the Long Document Transformer
Venue: arXiv cs.CL 2021
Year: 2021

This paper presents a technical report of our submission to the 4th task of SemEval-2021, titled: Reading Comprehension of Abstract Meaning. In this task, we want to predict the correct answer based on a question given a context. Usually, contexts are very lengthy and require a large receptive field from the model. Thus, common contextualized language models like BERT miss fine representation and performance due to the limited capacity of the input tokens. To tackle this problem, we used the Longformer model to better process the sequences. Furthermore, we utilized the method proposed in the Longformer benchmark on Wikihop dataset which improved the accuracy on our task data from 23.01% and 22.95% achieved by the baselines for subtask 1 and 2, respectively, to 70.30% and 64.38%.
Analysis and Mitigations of Reverse Engineering Attacks on Local Feature Descriptors
Venue: arXiv cs.CV 2021
Year: 2021

As autonomous driving and augmented reality evolve, a practical concern is data privacy. In particular, these applications rely on localization based on user images. The widely adopted technology uses local feature descriptors, which are derived from the images and it was long thought that they could not be reverted back. However, recent work has demonstrated that under certain conditions reverse engineering attacks are possible and allow an adversary to reconstruct RGB images. This poses a potential risk to user privacy. We take this a step further and model potential adversaries using a privacy threat model. Subsequently, we show under controlled conditions a reverse engineering attack on sparse feature maps and analyze the vulnerability of popular descriptors including FREAK, SIFT and SOSNet. Finally, we evaluate potential mitigation techniques that select a subset of descriptors to carefully balance privacy reconstruction risk while preserving image matching accuracy; our results show that similar accuracy can be obtained when revealing less information.
Heterogeneous Risk Minimization
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning algorithms with empirical risk minimization usually suffer from poor generalization performance due to the greedy exploitation of correlations among the training data, which are not stable under distributional shifts. Recently, some invariant learning methods for out-of-distribution (OOD) generalization have been proposed by leveraging multiple training environments to find invariant relationships. However, modern datasets are frequently assembled by merging data from multiple sources without explicit source labels. The resultant unobserved heterogeneity renders many invariant learning methods inapplicable. In this paper, we propose Heterogeneous Risk Minimization (HRM) framework to achieve joint learning of latent heterogeneity among the data and invariant relationship, which leads to stable prediction despite distributional shifts. We theoretically characterize the roles of the environment labels in invariant learning and justify our newly proposed HRM framework. Extensive experimental results validate the effectiveness of our HRM framework.
Employing Agent Beliefs during Fault Diagnosis for IEC 61499 Industrial Cyber-Physical Systems
Venue: arXiv cs.SE 2021
Year: 2021

We have come to rely on industrial-scale cyber-physical systems more and more to manage tasks and machinery in safety-critical situations. Efficient, reliable fault identification and management has become a critical factor in the design of these increasingly sophisticated and complex devices. Teams of co-operating software agents are one way to coordinate the flow of diagnostic information gathered during fault-finding. By wielding domain knowledge of the software architecture used to construct the system, agents build and refine their beliefs about the location and root cause of faults. This paper examines how agents constructed within the GORITE Multi-Agent Framework create and refine their beliefs. We demonstrate three different belief structures implemented within our Fault Diagnostic Engine, showing how each supports a distinct aspect of the agent's reasoning. Using domain knowledge of the IEC 61499 Function Block architecture, agents are able to examine and rigorously evaluate both individual components and entire subsystems.
The D-plus Discriminant and Complexity of Root Clustering
Venue: arXiv cs.SC 2021
Year: 2021

Let $p(x)$ be an integer polynomial with $m\ge 2$ distinct roots $ρ_1,\ldots,ρ_m$ whose multiplicities are $\boldsymbolμ=(μ_1,\ldots,μ_m)$. We define the D-plus discriminant of $p(x)$ to be $D^+(p):= \prod_{1\le i<j\le m}(ρ_i-ρ_j)^{μ_i+μ_j}$. We first prove a conjecture that $D^+(p)$ is a $\boldsymbolμ$-symmetric function of its roots $ρ_1,\ldots,ρ_m$. Our main result gives an explicit formula for $D^+(p)$, as a rational function of its coefficients. Our proof is ideal-theoretic, based on re-casting the classic Poisson resultant as the "symbolic Poisson formula". The D-plus discriminant first arose in the complexity analysis of a root clustering algorithm from Becker et al. (ISSAC 2016). The bit-complexity of this algorithm is proportional to a quantity $\log(|D^+(p)|^{-1})$. As an application of our main result, we give an explicit upper bound on this quantity in terms of the degree of $p$ and its leading coefficient.
Attention-Based 3D Seismic Fault Segmentation Training by a Few 2D Slice Labels
Venue: arXiv cs.CV 2021
Year: 2021

Detection faults in seismic data is a crucial step for seismic structural interpretation, reservoir characterization and well placement. Some recent works regard it as an image segmentation task. The task of image segmentation requires huge labels, especially 3D seismic data, which has a complex structure and lots of noise. Therefore, its annotation requires expert experience and a huge workload. In this study, we present lambda-BCE and lambda-smooth L1loss to effectively train 3D-CNN by some slices from 3D seismic data, so that the model can learn the segmentation of 3D seismic data from a few 2D slices. In order to fully extract information from limited data and suppress seismic noise, we propose an attention module that can be used for active supervision training and embedded in the network. The attention heatmap label is generated by the original label, and letting it supervise the attention module using the lambda-smooth L1loss. The experiment demonstrates the effectiveness of our loss function, the method can extract 3D seismic features from a few 2D slice labels. And it also shows the advanced performance of the attention module, which can significantly suppress the noise in the seismic data while increasing the model's sensitivity to the foreground. Finally, on the public test set, we only use the 2D slice labels training that accounts for 3.3% of the 3D volume label, and achieve similar performance to the 3D volume label training.
RRCD: Redirección de Registros Basada en Compresión de Datos para Tolerar FallosPermanentes en una GPU
Venue: arXiv cs.AR 2021
Year: 2021

The ever-increasing parallelism demand of General-Purpose Graphics Processing Unit (GPGPU) applications pushes toward larger and more energy-hungry register files in successive GPU generations. Reducing the supply voltage beyond its safe limit is an effective way to improve the energy efficiency of register files. However, at these operating voltages, the reliability of the circuit is compromised. This work aims to tolerate permanent faults from process variations in large GPU register files operating below the safe supply voltage limit. To do so, this paper proposes a microarchitectural patching technique, DC-Patch, exploiting the inherent data redundancy of applications to compress registers at run-time with neither compiler assistance nor instruction set modifications. Instead of disabling an entire faulty register file entry, DC-Patch leverages the reliable cells within a faulty entry to store compressed register values. Experimental results show that, with more than a third of faulty register entries, DC-Patch ensures a reliable operation of the register file and reduces the energy consumption by 47% with respect to a conventional register file working at nominal supply voltage. The energy savings are 21% compared to a voltage noise smoothing scheme operating at the safe supply voltage limit. These benefits are obtained with less than 2 and 6% impact on the system performance and area, respectively.
Quick NAT: High performance NAT system on commodity platforms
Venue: arXiv cs.NI 2021
Year: 2021

NAT gateway is an important network system in today's IPv4 network when translating a private IPv4 address to a public address. However, traditional NAT system based on Linux Netfilter cannot achieve high network throughput to meet modern requirements such as data centers. To address this challenge, we improve the network performance of NAT system by three ways. First, we leverage DPDK to enable polling and zero-copy delivery, so as to reduce the cost of interrupt and packet copies. Second, we enable multiple CPU cores to process in parallel and use lock-free hash table to minimize the contention between CPU cores. Third, we use hash search instead of sequential search when looking up the NAT rule table. Evaluation shows that our Quick NAT system significantly improves the performance of NAT on commodity platforms.
Dispatcher: A Message-Passing Approach To Language Modelling
Venue: arXiv cs.CL 2021
Year: 2021

This paper proposes a message-passing mechanism to address language modelling. A new layer type is introduced that aims to substitute self-attention for unidirectional sequence generation tasks. The system is shown to be competitive with existing methods: Given N tokens, the computational complexity is O(N logN) and the memory complexity is O(N) under reasonable assumptions. In the end, the Dispatcher layer is seen to achieve comparable perplexity to prior results while being more efficient.
Efficiency-driven Hardware Optimization for Adversarially Robust Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

With a growing need to enable intelligence in embedded devices in the Internet of Things (IoT) era, secure hardware implementation of Deep Neural Networks (DNNs) has become imperative. We will focus on how to address adversarial robustness for DNNs through efficiency-driven hardware optimizations. Since memory (specifically, dot-product operations) is a key energy-spending component for DNNs, hardware approaches in the past have focused on optimizing the memory. One such approach is approximate digital CMOS memories with hybrid 6T-8T SRAM cells that enable supply voltage (Vdd) scaling yielding low-power operation, without significantly affecting the performance due to read/write failures incurred in the 6T cells. In this paper, we show how the bit-errors in the 6T cells of hybrid 6T-8T memories minimize the adversarial perturbations in a DNN. Essentially, we find that for different configurations of 8T-6T ratios and scaledVdd operation, noise incurred in the hybrid memory architectures is bound within specific limits. This hardware noise can potentially interfere in the creation of adversarial attacks in DNNs yielding robustness. Another memory optimization approach involves using analog memristive crossbars that perform Matrix-Vector-Multiplications (MVMs) efficiently with low energy and area requirements. However, crossbars generally suffer from intrinsic non-idealities that cause errors in performing MVMs, leading to degradation in the accuracy of the DNNs. We will show how the intrinsic hardware variations manifested through crossbar non-idealities yield adversarial robustness to the mapped DNNs without any additional optimization.
Designing a Web Application for Simple and Collaborative Video Annotation That Meets Teaching Routines and Educational Requirements
Venue: arXiv cs.HC 2021
Year: 2021

Video annotation and analysis is an important activity for teaching with and about audiovisual media artifacts because it helps students to learn how to identify textual and formal connections in media products. But school teachers lack adequate tools for video annotation and analysis in media education that are easy-to-use, integrate into established teaching organization, and support quick collaborative work. To address these challenges, we followed a design-based research approach and conducted qualitative interviews with teachers to develop TRAVIS GO, a web application for simple and collaborative video annotation. TRAVIS GO allows for quick and easy use within established teaching settings. The web application provides basic analytical features in an adaptable work space. Key didactic features include tagging and commenting on posts, sharing and exporting projects, and working in live collaboration. Teachers can create assignments according to grade level, learning subject, and class size. Our work contributes further insights for the CSCW community about how to implement user demands into developing educational tools.
NMPC trajectory planner for urban autonomous driving
Venue: arXiv cs.RO 2021
Year: 2021

This paper presents a trajectory planner for autonomous driving based on a Nonlinear Model Predictive Control (NMPC) algorithm that accounts for Pacejka's nonlinear lateral tyre dynamics as well as for zero speed conditions through a novel slip angles calculation. In the NMPC framework, road boundaries and obstacles (both static and moving) are taken into account thanks to soft and hard constraints implementation. The numerical solution of the NMPC problem is carried out using ACADO toolkit coupled with the quadratic programming solver qpOASES. The effectiveness of the proposed NMPC trajectory planner has been tested using CarMaker multibody models. Time analysis results provided by the simulations shown, state that the proposed algorithm can be implemented on the real-time control framework of an autonomous vehicle under the assumption of data coming from an upstream estimation block.
Knapsack and Subset Sum with Small Items
Venue: arXiv cs.DS 2021
Year: 2021

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In this paper we focus on the maximum item size $s$ and the maximum item value $v$. We give algorithms that run in time $O(n + s^3)$ and $O(n + v^3)$ for the Knapsack problem, and in time $\tilde{O}(n + s^{5/3})$ for the Subset Sum problem. Our algorithms work for the more general problem variants with multiplicities, where each input item comes with a (binary encoded) multiplicity, which succinctly describes how many times the item appears in the instance. In these variants $n$ denotes the (possibly much smaller) number of distinct items. Our results follow from combining and optimizing several diverse lines of research, notably proximity arguments for integer programming due to Eisenbrand and Weismantel (TALG 2019), fast structured $(\min,+)$-convolution by Kellerer and Pferschy (J. Comb. Optim. 2004), and additive combinatorics methods originating from Galil and Margalit (SICOMP 1991).
Graph Attention Networks with Positional Embeddings
Venue: arXiv cs.LG 2021
Year: 2021

Graph Neural Networks (GNNs) are deep learning methods which provide the current state of the art performance in node classification tasks. GNNs often assume homophily -- neighboring nodes having similar features and labels--, and therefore may not be at their full potential when dealing with non-homophilic graphs. In this work, we focus on addressing this limitation and enable Graph Attention Networks (GAT), a commonly used variant of GNNs, to explore the structural information within each graph locality. Inspired by the positional encoding in the Transformers, we propose a framework, termed Graph Attentional Networks with Positional Embeddings (GAT-POS), to enhance GATs with positional embeddings which capture structural and positional information of the nodes in the graph. In this framework, the positional embeddings are learned by a model predictive of the graph context, plugged into an enhanced GAT architecture, which is able to leverage both the positional and content information of each node. The model is trained jointly to optimize for the task of node classification as well as the task of predicting graph context. Experimental results show that GAT-POS reaches remarkable improvement compared to strong GNN baselines and recent structural embedding enhanced GNNs on non-homophilic graphs.
Swarm Differential Privacy for Purpose Driven Data-Information-Knowledge-Wisdom Architecture
Venue: arXiv cs.AI 2021
Year: 2021

Privacy protection has recently been in the spotlight of attention to both academia and industry. Society protects individual data privacy through complex legal frameworks. The increasing number of applications of data science and artificial intelligence has resulted in a higher demand for the ubiquitous application of the data. The privacy protection of the broad Data-Information-Knowledge-Wisdom (DIKW) landscape, the next generation of information organization, has taken a secondary role. In this paper, we will explore DIKW architecture through the applications of the popular swarm intelligence and differential privacy. As differential privacy proved to be an effective data privacy approach, we will look at it from a DIKW domain perspective. Swarm Intelligence can effectively optimize and reduce the number of items in DIKW used in differential privacy, thus accelerating both the effectiveness and the efficiency of differential privacy for crossing multiple modals of conceptual DIKW. The proposed approach is demonstrated through the application of personalized data that is based on the open-sourse IRIS dataset. This experiment demonstrates the efficiency of Swarm Intelligence in reducing computing complexity.
Analyzing Online Political Advertisements
Venue: arXiv cs.CL 2021
Year: 2021

Online political advertising is a central aspect of modern election campaigning for influencing public opinion. Computational analysis of political ads is of utmost importance in political science to understand the characteristics of digital campaigning. It is also important in computational linguistics to study features of political discourse and communication on a large scale. In this work, we present the first computational study on online political ads with the aim to (1) infer the political ideology of an ad sponsor; and (2) identify whether the sponsor is an official political party or a third-party organization. We develop two new large datasets for the two tasks consisting of ads from the U.S.. Evaluation results show that our approach that combines textual and visual information from pre-trained neural models outperforms a state-of-the-art method for generic commercial ad classification. Finally, we provide an in-depth analysis of the limitations of our best-performing models and linguistic analysis to study the characteristics of political ads discourse.