OpenRaiser/Intern-Atlas huggingface dataset:
Why Convolutional Networks Learn Oriented Bandpass Filters: Theory and Empirical Support
Venue: arXiv cs.CV 2020
Year: 2020

It has been repeatedly observed that convolutional architectures when applied to image understanding tasks learn oriented bandpass filters. A standard explanation of this result is that these filters reflect the structure of the images that they have been exposed to during training: Natural images typically are locally composed of oriented contours at various scales and oriented bandpass filters are matched to such structure. We offer an alternative explanation based not on the structure of images, but rather on the structure of convolutional architectures. In particular, complex exponentials are the eigenfunctions of convolution. These eigenfunctions are defined globally; however, convolutional architectures operate locally. To enforce locality, one can apply a windowing function to the eigenfunctions, which leads to oriented bandpass filters as the natural operators to be learned with convolutional architectures. From a representational point of view, these filters allow for a local systematic way to characterize and operate on an image or other signal. We offer empirical support for the hypothesis that convolutional networks learn such filters at all of their convolutional layers. While previous research has shown evidence of filters having oriented bandpass characteristics at early layers, ours appears to be the first study to document the predominance of such filter characteristics at all layers. Previous studies have missed this observation because they have concentrated on the cumulative compositional effects of filtering across layers, while we examine the filter characteristics that are present at each layer.
On the proper orientation number of chordal graphs
Venue: arXiv cs.CC 2020
Year: 2020

An orientation $D$ of a graph $G=(V,E)$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each $v \in V(G)$, the indegree of $v$ in $D$, denoted by $d^-_D(v)$, is the number of arcs with head $v$ in $D$. An orientation $D$ of $G$ is proper if $d^-_D(u)\neq d^-_D(v)$, for all $uv\in E(G)$. An orientation with maximum indegree at most $k$ is called a $k$-orientation. The proper orientation number of $G$, denoted by $\overrightarrowχ(G)$, is the minimum integer $k$ such that $G$ admits a proper $k$-orientation. We prove that determining whether $\overrightarrowχ(G) \leq k$ is NP-complete for chordal graphs of bounded diameter, but can be solved in linear-time in the subclass of quasi-threshold graphs. When parameterizing by $k$, we argue that this problem is FPT for chordal graphs and argue that no polynomial kernel exists, unless $NP\subseteq coNP/\ poly$. We present a better kernel to the subclass of split graphs and a linear kernel to the class of cobipartite graphs. Concerning bounds, we prove tight upper bounds for subclasses of block graphs. We also present new families of trees having proper orientation number at most 2 and at most 3. Actually, we prove a general bound stating that any graph $G$ having no adjacent vertices of degree at least $c+1$ have proper orientation number at most $c$. This implies new classes of (outer)planar graphs with bounded proper orientation number. We also prove that maximal outerplanar graphs $G$ whose weak-dual is a path satisfy $\overrightarrowχ(G)\leq 13$. Finally, we present simple bounds to the classes of chordal claw-free graphs and cographs.
RfD-Net: Point Scene Understanding by Semantic Instance Reconstruction
Venue: arXiv cs.CV 2020
Year: 2020

Semantic scene understanding from point clouds is particularly challenging as the points reflect only a sparse set of the underlying 3D geometry. Previous works often convert point cloud into regular grids (e.g. voxels or bird-eye view images), and resort to grid-based convolutions for scene understanding. In this work, we introduce RfD-Net that jointly detects and reconstructs dense object surfaces directly from raw point clouds. Instead of representing scenes with regular grids, our method leverages the sparsity of point cloud data and focuses on predicting shapes that are recognized with high objectness. With this design, we decouple the instance reconstruction into global object localization and local shape prediction. It not only eases the difficulty of learning 2-D manifold surfaces from sparse 3D space, the point clouds in each object proposal convey shape details that support implicit function learning to reconstruct any high-resolution surfaces. Our experiments indicate that instance detection and reconstruction present complementary effects, where the shape prediction head shows consistent effects on improving object detection with modern 3D proposal network backbones. The qualitative and quantitative evaluations further demonstrate that our approach consistently outperforms the state-of-the-arts and improves over 11 of mesh IoU in object reconstruction.
Twitter Spam Detection: A Systematic Review
Venue: arXiv cs.CR 2020
Year: 2020

Nowadays, with the rise of Internet access and mobile devices around the globe, more people are using social networks for collaboration and receiving real-time information. Twitter, the microblogging that is becoming a critical source of communication and news propagation, has grabbed the attention of spammers to distract users. So far, researchers have introduced various defense techniques to detect spams and combat spammer activities on Twitter. To overcome this problem, in recent years, many novel techniques have been offered by researchers, which have greatly enhanced the spam detection performance. Therefore, it raises a motivation to conduct a systematic review about different approaches of spam detection on Twitter. This review focuses on comparing the existing research techniques on Twitter spam detection systematically. Literature review analysis reveals that most of the existing methods rely on Machine Learning-based algorithms. Among these Machine Learning algorithms, the major differences are related to various feature selection methods. Hence, we propose a taxonomy based on different feature selection methods and analyses, namely content analysis, user analysis, tweet analysis, network analysis, and hybrid analysis. Then, we present numerical analyses and comparative studies on current approaches, coming up with open challenges that help researchers develop solutions in this topic.
Energy Aware Routing with Computational Offloading for Wireless Sensor Networks
Venue: arXiv cs.NI 2020
Year: 2020

Wireless sensor networks (WSN) are characterized by a network of small, battery powered devices, operating remotely with no pre-existing infrastructure. The unique structure of WSN allow for novel approaches to data reduction and energy preservation. This paper presents a modification to the existing Q-routing protocol by providing an alternate action of performing sensor data reduction in place thereby reducing energy consumption, bandwidth usage, and message transmission time. The algorithm is further modified to include an energy factor which increases the cost of forwarding as energy reserves deplete. This encourages the network to conserve energy in favor of network preservation when energy reserves are low. Our experimental results show that this approach can, in periods of high network traffic, simultaneously reduce bandwidth, conserve energy, and maintain low message transition times.
Bringing AI To Edge: From Deep Learning's Perspective
Venue: arXiv cs.LG 2020
Year: 2020

Edge computing and artificial intelligence (AI), especially deep learning for nowadays, are gradually intersecting to build a novel system, called edge intelligence. However, the development of edge intelligence systems encounters some challenges, and one of these challenges is the \textit{computational gap} between computation-intensive deep learning algorithms and less-capable edge systems. Due to the computational gap, many edge intelligence systems cannot meet the expected performance requirements. To bridge the gap, a plethora of deep learning techniques and optimization methods are proposed in the past years: light-weight deep learning models, network compression, and efficient neural architecture search. Although some reviews or surveys have partially covered this large body of literature, we lack a systematic and comprehensive review to discuss all aspects of these deep learning techniques which are critical for edge intelligence implementation. As various and diverse methods which are applicable to edge systems are proposed intensively, a holistic review would enable edge computing engineers and community to know the state-of-the-art deep learning techniques which are instrumental for edge intelligence and to facilitate the development of edge intelligence systems. This paper surveys the representative and latest deep learning techniques that are useful for edge intelligence systems, including hand-crafted models, model compression, hardware-aware neural architecture search and adaptive deep learning models. Finally, based on observations and simple experiments we conducted, we discuss some future directions.
Advancements of federated learning towards privacy preservation: from federated learning to split learning
Venue: arXiv cs.LG 2020
Year: 2020

In the distributed collaborative machine learning (DCML) paradigm, federated learning (FL) recently attracted much attention due to its applications in health, finance, and the latest innovations such as industry 4.0 and smart vehicles. FL provides privacy-by-design. It trains a machine learning model collaboratively over several distributed clients (ranging from two to millions) such as mobile phones, without sharing their raw data with any other participant. In practical scenarios, all clients do not have sufficient computing resources (e.g., Internet of Things), the machine learning model has millions of parameters, and its privacy between the server and the clients while training/testing is a prime concern (e.g., rival parties). In this regard, FL is not sufficient, so split learning (SL) is introduced. SL is reliable in these scenarios as it splits a model into multiple portions, distributes them among clients and server, and trains/tests their respective model portions to accomplish the full model training/testing. In SL, the participants do not share both data and their model portions to any other parties, and usually, a smaller network portion is assigned to the clients where data resides. Recently, a hybrid of FL and SL, called splitfed learning, is introduced to elevate the benefits of both FL (faster training/testing time) and SL (model split and training). Following the developments from FL to SL, and considering the importance of SL, this chapter is designed to provide extensive coverage in SL and its variants. The coverage includes fundamentals, existing findings, integration with privacy measures such as differential privacy, open problems, and code implementation.
A Review of Recent Advances of Binary Neural Networks for Edge Computing
Venue: arXiv cs.LG 2020
Year: 2020

Edge computing is promising to become one of the next hottest topics in artificial intelligence because it benefits various evolving domains such as real-time unmanned aerial systems, industrial applications, and the demand for privacy protection. This paper reviews recent advances on binary neural network (BNN) and 1-bit CNN technologies that are well suitable for front-end, edge-based computing. We introduce and summarize existing work and classify them based on gradient approximation, quantization, architecture, loss functions, optimization method, and binary neural architecture search. We also introduce applications in the areas of computer vision and speech recognition and discuss future applications for edge computing.
Improving Scalability of Contrast Pattern Mining for Network Traffic Using Closed Patterns
Venue: arXiv cs.NI 2020
Year: 2020

Contrast pattern mining (CPM) aims to discover patterns whose support increases significantly from a background dataset compared to a target dataset. CPM is particularly useful for characterising changes in evolving systems, e.g., in network traffic analysis to detect unusual activity. While most existing techniques focus on extracting either the whole set of contrast patterns (CPs) or minimal sets, the problem of efficiently finding a relevant subset of CPs, especially in high dimensional datasets, is an open challenge. In this paper, we focus on extracting the most specific set of CPs to discover significant changes between two datasets. Our approach to this problem uses closed patterns to substantially reduce redundant patterns. Our experimental results on several real and emulated network traffic datasets demonstrate that our proposed unsupervised algorithm is up to 100 times faster than an existing approach for CPM on network traffic data [2]. In addition, as an application of CPs, we demonstrate that CPM is a highly effective method for detection of meaningful changes in network traffic.
A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources
Venue: arXiv cs.SI 2020
Year: 2020

Heterogeneous graphs (HGs) also known as heterogeneous information networks have become ubiquitous in real-world scenarios; therefore, HG embedding, which aims to learn representations in a lower-dimension space while preserving the heterogeneous structures and semantics for downstream tasks (e.g., node/graph classification, node clustering, link prediction), has drawn considerable attentions in recent years. In this survey, we perform a comprehensive review of the recent development on HG embedding methods and techniques. We first introduce the basic concepts of HG and discuss the unique challenges brought by the heterogeneity for HG embedding in comparison with homogeneous graph representation learning; and then we systemically survey and categorize the state-of-the-art HG embedding methods based on the information they used in the learning process to address the challenges posed by the HG heterogeneity. In particular, for each representative HG embedding method, we provide detailed introduction and further analyze its pros and cons; meanwhile, we also explore the transformativeness and applicability of different types of HG embedding methods in the real-world industrial environments for the first time. In addition, we further present several widely deployed systems that have demonstrated the success of HG embedding techniques in resolving real-world application problems with broader impacts. To facilitate future research and applications in this area, we also summarize the open-source code, existing graph learning platforms and benchmark datasets. Finally, we explore the additional issues and challenges of HG embedding and forecast the future research directions in this field.
Algorithms for Influence Maximization in Socio-Physical Networks
Venue: arXiv cs.SI 2020
Year: 2020

Given a directed graph (representing a social network), the influence maximization problem is to find k nodes which, when influenced (or activated), would maximize the number of remaining nodes that get activated. In this paper, we consider a more general version of the problem that includes an additional set of nodes, termed as physical nodes, such that a node in the social network is covered by one or more physical nodes. A physical node exists in one of two states at any time, opened or closed, and there is a constraint on the maximum number of physical nodes that can be opened. In this setting, an inactive node in the social network becomes active if it has enough active neighbors in the social network and if it is covered by at least one of the opened physical nodes. This problem arises in disaster recovery, where a displaced social group decides to return after a disaster only after enough groups in its social network return and some infrastructure components in its neighborhood are repaired. The general problem is NP-hard to approximate within any constant factor and thus we characterize optimal and approximation algorithms for special instances of the problem.
Person Perception Biases Exposed: Revisiting the First Impressions Dataset
Venue: arXiv cs.CV 2020
Year: 2020

This work revisits the ChaLearn First Impressions database, annotated for personality perception using pairwise comparisons via crowdsourcing. We analyse for the first time the original pairwise annotations, and reveal existing person perception biases associated to perceived attributes like gender, ethnicity, age and face attractiveness. We show how person perception bias can influence data labelling of a subjective task, which has received little attention from the computer vision and machine learning communities by now. We further show that the mechanism used to convert pairwise annotations to continuous values may magnify the biases if no special treatment is considered. The findings of this study are relevant for the computer vision community that is still creating new datasets on subjective tasks, and using them for practical applications, ignoring these perceptual biases.
Windowed Prophet Inequalities
Venue: arXiv cs.DS 2020
Year: 2020

The prophet inequalities problem has received significant study over the past decades and has several applications such as to online auctions. In this paper, we study two variants of the i.i.d. prophet inequalities problem, namely the windowed prophet inequalities problem and the batched prophet inequalities problem. For the windowed prophet inequalities problem, we show that for window size $o(n)$, the optimal competitive ratio is $α\approx 0.745$, the same as in the non-windowed case. In the case where the window size is $n/k$ for some constant $k$, we show that $α_k < WIN_{n/k} \le α_k + o_k(1)$ where $WIN_{n/k}$ is the optimal competitive ratio for the window size $n/k$ prophet inequalities problem and $α_k$ is the optimal competitive ratio for the $k$ sample i.i.d. prophet inequalities problem. Finally, we prove an equivalence between the batched prophet inequalities problem and the i.i.d. prophet inequalities problem.
A biologically plausible neural network for local supervision in cortical microcircuits
Venue: arXiv cs.NE 2020
Year: 2020

The backpropagation algorithm is an invaluable tool for training artificial neural networks; however, because of a weight sharing requirement, it does not provide a plausible model of brain function. Here, in the context of a two-layer network, we derive an algorithm for training a neural network which avoids this problem by not requiring explicit error computation and backpropagation. Furthermore, our algorithm maps onto a neural network that bears a remarkable resemblance to the connectivity structure and learning rules of the cortex. We find that our algorithm empirically performs comparably to backprop on a number of datasets.
From the DESK (Dexterous Surgical Skill) to the Battlefield -- A Robotics Exploratory Study
Venue: arXiv cs.RO 2020
Year: 2020

Short response time is critical for future military medical operations in austere settings or remote areas. Such effective patient care at the point of injury can greatly benefit from the integration of semi-autonomous robotic systems. To achieve autonomy, robots would require massive libraries of maneuvers. While this is possible in controlled settings, obtaining surgical data in austere settings can be difficult. Hence, in this paper, we present the Dexterous Surgical Skill (DESK) database for knowledge transfer between robots. The peg transfer task was selected as it is one of 6 main tasks of laparoscopic training. Also, we provide a ML framework to evaluate novel transfer learning methodologies on this database. The collected DESK dataset comprises a set of surgical robotic skills using the four robotic platforms: Taurus II, simulated Taurus II, YuMi, and the da Vinci Research Kit. Then, we explored two different learning scenarios: no-transfer and domain-transfer. In the no-transfer scenario, the training and testing data were obtained from the same domain; whereas in the domain-transfer scenario, the training data is a blend of simulated and real robot data that is tested on a real robot. Using simulation data enhances the performance of the real robot where limited or no real data is available. The transfer model showed an accuracy of 81% for the YuMi robot when the ratio of real-to-simulated data was 22%-78%. For Taurus II and da Vinci robots, the model showed an accuracy of 97.5% and 93% respectively, training only with simulation data. Results indicate that simulation can be used to augment training data to enhance the performance of models in real scenarios. This shows the potential for future use of surgical data from the operating room in deployable surgical robots in remote areas.
Integral Equations & Model Reduction For Fast Computation of Nonlinear Periodic Response
Venue: arXiv cs.CE 2020
Year: 2020

We propose a reformulation for the integral equations approach of Jain, Breunung \& Haller [Nonlinear Dyn. 97, 313--341 (2019)] to steady-state response computation for periodically forced nonlinear mechanical systems. This reformulation results in additional speed-up and better convergence. We show that the solutions of the reformulated equations are in one-to-one correspondence with those of the original integral equations and derive conditions under which a collocation type approximation converges to the exact solution in the reformulated setting. Furthermore, we observe that model reduction using a selected set of vibration modes of the linearized system substantially enhances the computational performance. Finally, we discuss an open-source implementation of this approach and demonstrate the gains in computational performance using three examples that also include nonlinear finite-element models.
Integer Programming and Incidence Treedepth
Venue: arXiv cs.CC 2020
Year: 2020

Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Koutecký, Levin, and Onn [ICALP 2018] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)? We answer this question in negative. In particular, we prove that deciding the feasibility of a system in the standard form, ${A\mathbf{x} = \mathbf{b}}, {\mathbf{l} \le \mathbf{x} \le \mathbf{u}}$, is $\mathsf{NP}$-hard even when the absolute value of any coefficient in $A$ is 1 and the incidence treedepth of $A$ is 5. Consequently, it is not possible to decide feasibility in polynomial time even if both the assumed parameters are constant, unless $\mathsf{P}=\mathsf{NP}$. Moreover, we complement this intractability result by showing tractability for natural and only slightly more restrictive settings, namely: (1) treedepth with an additional bound on either the maximum arity of constraints or the maximum number of occurrences of variables and (2) the vertex cover number.