OpenRaiser/Intern-Atlas huggingface dataset:
High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility
Venue: arXiv cs.IR 2021
Year: 2021

Approximate Nearest Neighbor Search (ANNS) in high dimensional space is essential in database and information retrieval. Recently, there has been a surge of interest in exploring efficient graph-based indices for the ANNS problem. Among them, Navigating Spreading-out Graph (NSG) provides fine theoretical analysis and achieves state-of-the-art performance. However, we find there are several limitations with NSG: 1) NSG has no theoretical guarantee on nearest neighbor search when the query is not indexed in the database; 2) NSG is too sparse which harms the search performance. In addition, NSG suffers from high indexing complexity. To address the above problems, we propose the Satellite System Graphs (SSG) and a practical variant NSSG. Specifically, we propose a novel pruning strategy to produce SSGs from the complete graph. SSGs define a new family of MSNETs in which the out-edges of each node are distributed evenly in all directions. Each node in the graph builds effective connections to its neighborhood omnidirectionally, whereupon we derive SSG's excellent theoretical properties for both indexed and unindexed queries. We can adaptively adjust the sparsity of an SSG with a hyper-parameter to optimize the search performance. Further, NSSG is proposed to reduce the indexing complexity of the SSG for large-scale applications. Both theoretical and extensive experimental analyses are provided to demonstrate the strengths of the proposed approach over the existing representative algorithms. Our code has been released at https://github.com/ZJULearning/SSG.
Selection Heuristics on Semantic Genetic Programming for Classification Problems
Venue: arXiv cs.LG 2021
Year: 2021

Individual's semantics have been used for guiding the learning process of Genetic Programming solving supervised learning problems. The semantics has been used to proposed novel genetic operators as well as different ways of performing parent selection. The latter is the focus of this contribution by proposing three heuristics for parent selection that replace the fitness function on the selection mechanism entirely. These heuristics complement previous work by being inspired in the characteristics of the addition, Naive Bayes, and Nearest Centroid functions and applying them only when the function is used to create an offspring. These heuristics use different similarity measures among the parents to decide which of them is more appropriate given a function. The similarity functions considered are the cosine similarity, Pearson's correlation, and agreement. We analyze these heuristics' performance against random selection, state-of-the-art selection schemes, and 18 classifiers, including auto-machine-learning techniques, on 30 classification problems with a variable number of samples, variables, and classes. The result indicated that the combination of parent selection based on agreement and random selection to replace an individual in the population produces statistically better results than the classical selection and state-of-the-art schemes, and it is competitive with state-of-the-art classifiers. Finally, the code is released as open-source software.
Natural Adversarial Examples
Venue: arXiv cs.LG 2021
Year: 2021

We introduce two challenging datasets that reliably cause machine learning model performance to substantially degrade. The datasets are collected with a simple adversarial filtration technique to create datasets with limited spurious cues. Our datasets' real-world, unmodified examples transfer to various unseen models reliably, demonstrating that computer vision models have shared weaknesses. The first dataset is called ImageNet-A and is like the ImageNet test set, but it is far more challenging for existing models. We also curate an adversarial out-of-distribution detection dataset called ImageNet-O, which is the first out-of-distribution detection dataset created for ImageNet models. On ImageNet-A a DenseNet-121 obtains around 2% accuracy, an accuracy drop of approximately 90%, and its out-of-distribution detection performance on ImageNet-O is near random chance levels. We find that existing data augmentation techniques hardly boost performance, and using other public training datasets provides improvements that are limited. However, we find that improvements to computer vision architectures provide a promising path towards robust models.
Edge computing server placement with capacitated location allocation
Venue: arXiv cs.NI 2021
Year: 2021

The deployment of edge computing infrastructure requires a careful placement of the edge servers, with an aim to improve application latencies and reduce data transfer load in opportunistic Internet of Things systems. In the edge server placement, it is important to consider computing capacity, available deployment budget, and hardware requirements for the edge servers and the underlying backbone network topology. In this paper, we thoroughly survey the existing literature in edge server placement, identify gaps and present an extensive set of parameters to be considered. We then develop a novel algorithm, called PACK, for server placement as a capacitated location-allocation problem. PACK minimizes the distances between servers and their associated access points, while taking into account capacity constraints for load balancing and enabling workload sharing between servers. Moreover, PACK considers practical issues such as prioritized locations and reliability. We evaluate the algorithm in two distinct scenarios: one with high capacity servers for edge computing in general, and one with low capacity servers for Fog computing. Evaluations are performed with a data set collected in a real-world network, consisting of both dense and sparse deployments of access points across a city area. The resulting algorithm and related tools are publicly available as open source software.
A Novel Approach for Robust Multi Human Action Recognition and Summarization based on 3D Convolutional Neural Networks
Venue: arXiv cs.CV 2021
Year: 2021

Human actions in videos are 3D signals. However, there are a few methods available for multiple human action recognition. For long videos, it's difficult to search within a video for a specific action and/or person. For that, this paper proposes a new technic for multiple human action recognition and summarization for surveillance videos. The proposed approach proposes a new representation of the data by extracting the sequence of each person from the scene. This is followed by an analysis of each sequence to detect and recognize the corresponding actions using 3D convolutional neural networks (3DCNNs). Action-based video summarization is performed by saving each person's action at each time of the video. Results of this work revealed that the proposed method provides accurate multi human action recognition that easily used for summarization of any action. Further, for other videos that can be collected from the internet, which are complex and not built for surveillance applications, the proposed model was evaluated on some datasets like UCF101 and YouTube without any preprocessing. For this category of videos, the summarization is performed on the video sequences by summarizing the actions in each subsequence. The results obtained demonstrate its efficiency compared to state-of-the-art methods.
On $d$-distance $m$-tuple ($\ell, r$)-domination in graphs
Venue: arXiv cs.CC 2021
Year: 2021

In this article, we study the $d$-distance $m$-tuple ($\ell, r$)-domination problem. Given a simple undirected graph $G=(V, E)$, and positive integers $d, m, \ell$ and $r$, a subset $V' \subseteq V$ is said to be a $d$-distance $m$-tuple ($\ell, r$)-dominating set if it satisfies the following conditions: (i) each vertex $v \in V$ is $d$-distance dominated by at least $m$ vertices in $V'$, and (ii) each $r$ size subset $U$ of $V$ is $d$-distance dominated by at least $\ell$ vertices in $V'$. Here, a vertex $v$ is $d$-distance dominated by another vertex $u$ means the shortest path distance between $u$ and $v$ is at most $d$ in $G$. A set $U$ is $d$-distance dominated by a set of $\ell$ vertices means size of the union of the $d$-distance neighborhood of all vertices of $U$ in $V'$ is at least $\ell$. The objective of the $d$-distance $m$-tuple ($\ell, r$)-domination problem is to find a minimum size subset $V' \subseteq V$ satisfying the above two conditions. We prove that the problem of deciding whether a graph $G$ has (i) a 1-distance $m$-tuple ($\ell, r$)-dominating set for each fixed value of $m, \ell$, and $r$, and (ii) a $d$-distance $m$-tuple ($\ell, 2$)-dominating set for each fixed value of $d (> 1), m$, and $\ell$ of cardinality at most $k$ (here $k$ is a positive integer) are NP-complete. We also prove that for any $\varepsilon>0$, the 1-distance $m$-tuple $(\ell, r)$-domination problem and the $d$-distance $m$-tuple $(\ell,2)$-domination problem cannot be approximated within a factor of $(\frac{1}{2}- \varepsilon)\ln |V|$ and $(\frac{1}{4}- \varepsilon)\ln |V|$, respectively, unless $P = NP$.
Machine Learning at the Network Edge: A Survey
Venue: arXiv cs.LG 2021
Year: 2021

Resource-constrained IoT devices, such as sensors and actuators, have become ubiquitous in recent years. This has led to the generation of large quantities of data in real-time, which is an appealing target for AI systems. However, deploying machine learning models on such end-devices is nearly impossible. A typical solution involves offloading data to external computing systems (such as cloud servers) for further processing but this worsens latency, leads to increased communication costs, and adds to privacy concerns. To address this issue, efforts have been made to place additional computing devices at the edge of the network, i.e close to the IoT devices where the data is generated. Deploying machine learning systems on such edge computing devices alleviates the above issues by allowing computations to be performed close to the data sources. This survey describes major research efforts where machine learning systems have been deployed at the edge of computer networks, focusing on the operational aspects including compression techniques, tools, frameworks, and hardware used in successful applications of intelligent edge systems.
Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox based Sampling
Venue: arXiv cs.SI 2021
Year: 2021

This paper considers the problem of estimating a power-law degree distribution of an undirected network using sampled data. Although power-law degree distributions are ubiquitous in nature, the widely used parametric methods for estimating them (e.g. linear regression on double-logarithmic axes, maximum likelihood estimation with uniformly sampled nodes) suffer from the large variance introduced by the lack of data-points from the tail portion of the power-law degree distribution. As a solution, we present a novel maximum likelihood estimation approach that exploits the friendship paradox to sample more efficiently from the tail of the degree distribution. We analytically show that the proposed method results in a smaller bias, variance and a Cramer-Rao lower bound compared to the vanilla maximum-likelihood estimate obtained with uniformly sampled nodes (which is the most commonly used method in literature). Detailed numerical and empirical results are presented to illustrate the performance of the proposed method under different conditions and how it compares with alternative methods. We also show that the proposed method and its desirable properties (i.e. smaller bias, variance and Cramer-Rao lower bound compared to vanilla method based on uniform samples) extend to parametric degree distributions other than the power-law such as exponential degree distributions as well. All the numerical and empirical results are reproducible and the code is publicly available on Github.
A Greek language teaching platform for primary school pupils
Venue: arXiv cs.CY 2021
Year: 2021

This study aims to develop an online Greek language learning platform via a learning management system based on the WordPress platform for primary school pupils with Russian as a mother tongue. The subject was chosen with a view to aid both the communication needs of Russian native speakers in Greece, as well as their smooth integration into society. For the purpose of the current study, we investigated how Greek language is learnt in Russia, how widespread and popular it is, whether it is supported by the Russian educational system, as well as whether Greek language distance learning could be achieved. Moreover, LMS (Learning management system) environments were investigated as well, aiming at selecting the most student-teacher-friendly one. Taking into account that the platform is addressed to children, a presentable and properly developed material was designed, thus making the learning of each module more interesting and comprehensible throughout its short duration. With GrfKids platform speakers of other languages have the opportunity to learn Greek in an interactive asynchronous teaching environment with an automatic assessment. Moreover,GrfKids can be easily and immediately expanded both to pupils' linguistic, as well as age range. GrfKids provides Greek language courses to children with Russian as a mother tongue with interactive modules in which the learners can adapt the learning time by themselves. It is easy to use, functional and easily adapted to the ages it is addressed to.
The House That Knows You: User Authentication Based on IoT Data
Venue: arXiv cs.CR 2021
Year: 2021

Home-based Internet of Things (IoT) devices have gained in popularity and many households have become 'smart' by using devices such as smart sensors, locks, and voice-based assistants. Traditional authentication methods such as passwords, biometrics or multi-factor (using SMS or email) are either not applicable in the smart home setting, or they are inconvenient as they break the natural flow of interaction with these devices. Voice-based biometrics are limited due to safety and privacy concerns. Given the limitations of existing authentication techniques, we explore new opportunities for user authentication in smart home environments. Specifically, we design a novel authentication method based on behavioral features extracted from user interactions with IoT devices. We perform an IRB-approved user study in the IoT lab at our university over a period of three weeks. We collect network traffic from multiple users interacting with 15 IoT devices in our lab and extract a large number of features to capture user activity. We experiment with multiple classification algorithms and also design an ensemble classifier with two models using disjoint set of features. We demonstrate that our ensemble model can classify five users with 0.97 accuracy. The behavioral authentication modules could help address the new challenges emerging with smart home ecosystems and they open up the possibility of creating flexible policies for authorization and access control.
AutoML: A Survey of the State-of-the-Art
Venue: arXiv cs.LG 2021
Year: 2021

Deep learning (DL) techniques have penetrated all aspects of our lives and brought us great convenience. However, building a high-quality DL system for a specific task highly relies on human expertise, hindering the applications of DL to more areas. Automated machine learning (AutoML) becomes a promising solution to build a DL system without human assistance, and a growing number of researchers focus on AutoML. In this paper, we provide a comprehensive and up-to-date review of the state-of-the-art (SOTA) in AutoML. First, we introduce AutoML methods according to the pipeline, covering data preparation, feature engineering, hyperparameter optimization, and neural architecture search (NAS). We focus more on NAS, as it is currently very hot sub-topic of AutoML. We summarize the performance of the representative NAS algorithms on the CIFAR-10 and ImageNet datasets and further discuss several worthy studying directions of NAS methods: one/two-stage NAS, one-shot NAS, and joint hyperparameter and architecture optimization. Finally, we discuss some open problems of the existing AutoML methods for future research.
Attentive Normalization
Venue: arXiv cs.CV 2021
Year: 2021

In state-of-the-art deep neural networks, both feature normalization and feature attention have become ubiquitous. % with significant performance improvement shown in a vast amount of tasks. They are usually studied as separate modules, however. In this paper, we propose a light-weight integration between the two schema and present Attentive Normalization (AN). Instead of learning a single affine transformation, AN learns a mixture of affine transformations and utilizes their weighted-sum as the final affine transformation applied to re-calibrate features in an instance-specific way. The weights are learned by leveraging channel-wise feature attention. In experiments, we test the proposed AN using four representative neural architectures in the ImageNet-1000 classification benchmark and the MS-COCO 2017 object detection and instance segmentation benchmark. AN obtains consistent performance improvement for different neural architectures in both benchmarks with absolute increase of top-1 accuracy in ImageNet-1000 between 0.5\% and 2.7\%, and absolute increase up to 1.8\% and 2.2\% for bounding box and mask AP in MS-COCO respectively. We observe that the proposed AN provides a strong alternative to the widely used Squeeze-and-Excitation (SE) module. The source codes are publicly available at https://github.com/iVMCL/AOGNet-v2 (the ImageNet Classification Repo) and https://github.com/iVMCL/AttentiveNorm\_Detection (the MS-COCO Detection and Segmentation Repo).
New Design Paradigm of Distortion Cost Function for Efficient JPEG Steganography
Venue: arXiv cs.MM 2021
Year: 2021

Recently, with the introduction of JPEG phase-aware steganalysis features, e.g., GFR, the design of JPEG steganographic distortion cost function turns to maintain not only the statistical undetectability in DCT domain but also in spatial domain. To tackle this issue, this paper presents a novel paradigm for the design of JPEG steganographic distortion cost function, which calculates the distortion cost via a generalized Distortion Cost Domain Transformation (DCDT) function. The proposed function comprises the decompressed pixel block embedding changes and their corresponding embedding distortion costs for unit change, where the pixel embedding distortion costs are represented in a more general exponential model, aiming to flexibly allocate the embedding data. In this way, the JPEG steganography could be formulated as the optimization problem of minimizing the overall distortion cost in its decompressed spatial domain, which is equivalent to maximizing its statistical undetectability against JPEG phase-aware steganalysis features. Experimental results show that the proposed DCDT equipped with HiLL (a spatial steganographic distortion cost function) is superior to other state-of-the-art JPEG steganographic schemes, e.g., UERD, J-UNIWARD, and GUED in resisting the detection of JPEG phase-aware feature-based steganalyzers GFR and SCA-GFR, and rivals BET-HiLL with one order of magnitude lower computational complexity, along with the possibility of being further improved by considering the mutually dependent embedding interactions. In addition, the proposed DCDT is also verified to be effective for different image databases and quality factors.
Threshold Changeable Secret Sharing Scheme and Its Application to Group Authentication
Venue: arXiv cs.CR 2021
Year: 2021

Group oriented applications are getting more and more popular in mobile Internet and call for secure and efficient secret sharing (SS) scheme to meet their requirements. A $(t,n)$ threshold SS scheme divides a secret into $n$ shares such that any $t$ or more than $t$ shares can recover the secret while less than $t$ shares cannot. However, an adversary, even without a valid share, may obtain the secret by impersonating a shareholder to recover the secret with $t$ or more legal shareholders. Therefore, this paper uses linear code to propose a threshold changeable secret sharing (TCSS) scheme, in which threshold should increase from $t$ to the exact number of all participants during secret reconstruction. The scheme does not depend on any computational assumption and realizes asymptotically perfect security. Furthermore, based on the proposed TCSS scheme, a group authentication scheme is constructed, which allows a group user to authenticate whether all users are legal group members at once and thus provides efficient and flexible m-to-m authentication for group oriented applications.
SaSTL: Spatial Aggregation Signal Temporal Logic for Runtime Monitoring in Smart Cities
Venue: arXiv cs.CY 2021
Year: 2021

We present SaSTL -- a novel Spatial Aggregation Signal Temporal Logic -- for the efficient runtime monitoring of safety and performance requirements in smart cities. We first describe a study of over 1,000 smart city requirements, some of which can not be specified using existing logic such as Signal Temporal Logic (STL) and its variants. To tackle this limitation, we develop two new logical operators in SaSTL to augment STL for expressing spatial aggregation and spatial counting characteristics that are commonly found in real city requirements. We also develop efficient monitoring algorithms that can check a SaSTL requirement in parallel over multiple data streams (e.g., generated by multiple sensors distributed spatially in a city). We evaluate our SaSTL monitor by applying to two case studies with large-scale real city sensing data (e.g., up to 10,000 sensors in one requirement). The results show that SaSTL has a much higher coverage expressiveness than other spatial-temporal logics, and with a significant reduction of computation time for monitoring requirements. We also demonstrate that the SaSTL monitor can help improve the safety and performance of smart cities via simulated experiments.
Gradient Boosting Survival Tree with Applications in Credit Scoring
Venue: arXiv cs.LG 2021
Year: 2021

Credit scoring plays a vital role in the field of consumer finance. Survival analysis provides an advanced solution to the credit-scoring problem by quantifying the probability of survival time. In order to deal with highly heterogeneous industrial data collected in Chinese market of consumer finance, we propose a nonparametric ensemble tree model called gradient boosting survival tree (GBST) that extends the survival tree models with a gradient boosting algorithm. The survival tree ensemble is learned by minimizing the negative log-likelihood in an additive manner. The proposed model optimizes the survival probability simultaneously for each time period, which can reduce the overall error significantly. Finally, as a test of the applicability, we apply the GBST model to quantify the credit risk with large-scale real market datasets. The results show that the GBST model outperforms the existing survival models measured by the concordance index (C-index), Kolmogorov-Smirnov (KS) index, as well as by the area under the receiver operating characteristic curve (AUC) of each time period.