OpenRaiser/Intern-Atlas huggingface dataset:
Almost Tight Approximation Algorithms for Explainable Clustering
Venue: arXiv cs.LG 2021
Year: 2021

Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal of accuracy and interpretability by humans. In this paper, we study a recent framework of explainable clustering first suggested by Dasgupta et al.~\cite{dasgupta2020explainable}. Specifically, we focus on the $k$-means and $k$-medians problems and provide nearly tight upper and lower bounds. First, we provide an $O(\log k \log \log k)$-approximation algorithm for explainable $k$-medians, improving on the best known algorithm of $O(k)$~\cite{dasgupta2020explainable} and nearly matching the known $Ω(\log k)$ lower bound~\cite{dasgupta2020explainable}. In addition, in low-dimensional spaces $d \ll \log k$, we show that our algorithm also provides an $O(d \log^2 d)$-approximate solution for explainable $k$-medians. This improves over the best known bound of $O(d \log k)$ for low dimensions~\cite{laber2021explainable}, and is a constant for constant dimensional spaces. To complement this, we show a nearly matching $Ω(d)$ lower bound. Next, we study the $k$-means problem in this context and provide an $O(k \log k)$-approximation algorithm for explainable $k$-means, improving over the $O(k^2)$ bound of Dasgupta et al. and the $O(d k \log k)$ bound of \cite{laber2021explainable}. To complement this we provide an almost tight $Ω(k)$ lower bound, improving over the $Ω(\log k)$ lower bound of Dasgupta et al. Given an approximate solution to the classic $k$-means and $k$-medians, our algorithm for $k$-medians runs in time $O(kd \log^2 k )$ and our algorithm for $k$-means runs in time $ O(k^2 d)$.
Target-dependent UNITER: A Transformer-Based Multimodal Language Comprehension Model for Domestic Service Robots
Venue: arXiv cs.RO 2021
Year: 2021

Currently, domestic service robots have an insufficient ability to interact naturally through language. This is because understanding human instructions is complicated by various ambiguities and missing information. In existing methods, the referring expressions that specify the relationships between objects are insufficiently modeled. In this paper, we propose Target-dependent UNITER, which learns the relationship between the target object and other objects directly by focusing on the relevant regions within an image, rather than the whole image. Our method is an extension of the UNITER-based Transformer that can be pretrained on general-purpose datasets. We extend the UNITER approach by introducing a new architecture for handling the target candidates. Our model is validated on two standard datasets, and the results show that Target-dependent UNITER outperforms the baseline method in terms of classification accuracy.
A Business Model for Resource Sharing in Cell-Free UAVs-Assisted Wireless Networks
Venue: arXiv cs.NI 2021
Year: 2021

Unmanned aerial vehicles (UAVs) are widely deployed to enhance the wireless network capacity and to provide communication services to mobile users beyond the infrastructure coverage. Recently, with the help of a promising technology called network virtualization, multiple service providers (SPs) can share the infrastructures and wireless resources owned by the mobile network operators (MNOs). Then, they provide specific services to their mobile users using the resources obtained from MNOs. However, wireless resource sharing among SPs is challenging as each SP wants to maximize their utility/profit selfishly while satisfying the QoS requirement of their mobile users. Therefore, in this paper, we propose joint user association and wireless resource sharing problem in the cell-free UAVs-assisted wireless networks with the objective of maximizing the total network utility of the SPs while ensuring QoS constraints of their mobile users and the resource constraints of the UAVs deployed by MNOs. To solve the proposed mixed-integer non-convex problem, we decompose the proposed problem into two subproblems: users association, and resource sharing problems. Then, a two-sided matching algorithm is deployed in order to solve users association problem. We further deploy the whale optimization and Lagrangian relaxation algorithms to solve the resource sharing problem. Finally, extensive numerical results are provided in order to show the effectiveness of our proposed algorithm.
Exploiting Positional Information for Session-based Recommendation
Venue: arXiv cs.IR 2021
Year: 2021

For present e-commerce platforms, session-based recommender systems are developed to predict users' preference for next-item recommendation. Although a session can usually reflect a user's current preference, a local shift of the user's intention within the session may still exist. Specifically, the interactions that take place in the early positions within a session generally indicate the user's initial intention, while later interactions are more likely to represent the latest intention. Such positional information has been rarely considered in existing methods, which restricts their ability to capture the significance of interactions at different positions. To thoroughly exploit the positional information within a session, a theoretical framework is developed in this paper to provide an in-depth analysis of the positional information. We formally define the properties of forward-awareness and backward-awareness to evaluate the ability of positional encoding schemes in capturing the initial and the latest intention. According to our analysis, existing positional encoding schemes are generally forward-aware only, which can hardly represent the dynamics of the intention in a session. To enhance the positional encoding scheme for the session-based recommendation, a dual positional encoding (DPE) is proposed to account for both forward-awareness and backward-awareness. Based on DPE, we propose a novel Positional Recommender (PosRec) model with a well-designed Position-aware Gated Graph Neural Network module to fully exploit the positional information for session-based recommendation tasks. Extensive experiments are conducted on two e-commerce benchmark datasets, Yoochoose and Diginetica and the experimental results show the superiority of the PosRec by comparing it with the state-of-the-art session-based recommender models.
Segmented Federated Learning for Adaptive Intrusion Detection System
Venue: arXiv cs.CR 2021
Year: 2021

Cyberattacks are a major issues and it causes organizations great financial, and reputation harm. However, due to various factors, the current network intrusion detection systems (NIDS) seem to be insufficent. Predominant NIDS identifies Cyberattacks through a handcrafted dataset of rules. Although the recent applications of machine learning and deep learning have alleviated the enormous effort in NIDS, the security of network data has always been a prime concern. However, to encounter the security problem and enable sharing among organizations, Federated Learning (FL) scheme is employed. Although the current FL systems have been successful, a network's data distribution does not always fit into a single global model as in FL. Thus, in such cases, having a single global model in FL is no feasible. In this paper, we propose a Segmented-Federated Learning (Segmented-FL) learning scheme for a more efficient NIDS. The Segmented-FL approach employs periodic local model evaluation based on which the segmentation occurs. We aim to bring similar network environments to the same group. Further, the Segmented-FL system is coupled with a weighted aggregation of local model parameters based on the number of data samples a worker possesses to further augment the performance. The improved performance by our system as compared to the FL and centralized systems on standard dataset further validates our system and makes a strong case for extending our technique across various tasks. The solution finds its application in organizations that want to collaboratively learn on diverse network environments and protect the privacy of individual datasets.
Using Machine Learning to Generate Test Oracles: A Systematic Literature Review
Venue: arXiv cs.SE 2021
Year: 2021

Machine learning may enable the automated generation of test oracles. We have characterized emerging research in this area through a systematic literature review examining oracle types, researcher goals, the ML techniques applied, how the generation process was assessed, and the open research challenges in this emerging field. Based on a sample of 22 relevant studies, we observed that ML algorithms generated test verdict, metamorphic relation, and - most commonly - expected output oracles. Almost all studies employ a supervised or semi-supervised approach, trained on labeled system executions or code metadata - including neural networks, support vector machines, adaptive boosting, and decision trees. Oracles are evaluated using the mutation score, correct classifications, accuracy, and ROC. Work-to-date show great promise, but there are significant open challenges regarding the requirements imposed on training data, the complexity of modeled functions, the ML algorithms employed - and how they are applied - the benchmarks used by researchers, and replicability of the studies. We hope that our findings will serve as a roadmap and inspiration for researchers in this field.
Chalcogenide optomemristors for multi-factor neuromorphic computation
Venue: arXiv cs.ET 2021
Year: 2021

Neural processing on devices and circuits is fast becoming a popular approach to emulate biological neural networks. Elaborate CMOS and memristive technologies have been employed to achieve this, including chalcogenide-based in-memory computing concepts. Here we show that nano-scaled films of chalcogenide semiconductors can serve as building-blocks for novel types of neural computations where their tunable electronic and optical properties are jointly exploited. We demonstrate that ultrathin photoactive cavities of Ge-doped Selenide can emulate the computationally powerful non-linear operations of three-factor neo-Hebbian plasticity and the shunting inhibition. We apply this property to solve a maze game through reinforcement learning, as well as a single-neuron solution to the XOR, which is a linearly inseparable problem with point-neurons. Our results point to a new breed of memristors with broad implications for neuromorphic computing.
Incorporating Monitors in Reactive Synthesis without Paying the Price
Venue: arXiv cs.LO 2021
Year: 2021

Temporal synthesis attempts to construct reactive programs that satisfy a given declarative (LTL) formula. Practitioners have found it challenging to work exclusively with declarative specifications, and have found languages that combine modelling with declarative specifications more useful. Synthesised controllers may also need to work with pre-existing or manually constructed programs. In this paper we explore an approach that combines synthesis of declarative specifications in the presence of an existing behaviour model as a monitor, with the benefit of not having to reason about the state space of the monitor. We suggest a formal language with automata monitors as non-repeating and repeating triggers for LTL formulas. We use symbolic automata with memory as triggers, resulting in a strictly more expressive and succinct language than existing regular expression triggers. We give a compositional synthesis procedure for this language, where reasoning about the monitor state space is minimal. To show the advantages of our approach we apply it to specifications requiring counting and constraints over arbitrarily long sequence of events, where we can also see the power of parametrisation, easily handled in our approach. We provide a tool to construct controllers (in the form of symbolic automata) for our language.
Concept Identification of Directly and Indirectly Related Mentions Referring to Groups of Persons
Venue: arXiv cs.CL 2021
Year: 2021

Unsupervised concept identification through clustering, i.e., identification of semantically related words and phrases, is a common approach to identify contextual primitives employed in various use cases, e.g., text dimension reduction, i.e., replace words with the concepts to reduce the vocabulary size, summarization, and named entity resolution. We demonstrate the first results of an unsupervised approach for the identification of groups of persons as actors extracted from a set of related articles. Specifically, the approach clusters mentions of groups of persons that act as non-named entity actors in the texts, e.g., "migrant families" = "asylum-seekers." Compared to our baseline, the approach keeps the mentions of the geopolitical entities separated, e.g., "Iran leaders" != "European leaders," and clusters (in)directly related mentions with diverse wording, e.g., "American officials" = "Trump Administration."
An Algorithm for Flow Control in Computer Networks Based in Discrete Control Theory
Venue: arXiv cs.NI 2021
Year: 2021

Developing of an effective flow control algorithm to avoid congestion is a hot topic in computer network society. This document gives a mathematical model for general network at the beginning, and then discrete control theory is proposed as a key tool to design a new flow control algorithm to avoid congestion in the high-speed computer network, the proposed algorithm ensures stability of network system. The results of the simulation show that the proposed method can adjust the sending speed and the queue level in the buffer quickly and effectively. In addition, the method is easy to implement and apply to high-speed computer network.
Blockchains for Spectrum Management in Wireless Networks: A Survey
Venue: arXiv cs.NI 2021
Year: 2021

Regulatory radio spectrum management is evolving from traditional static frequency allocation and assignment schemes towards dynamic spectrum management and access schemes. This evolution is necessitated by a number of factors including underutilization of licensed spectrum bands, changing market and technological developments and increased demand for spectrum for emerging applications in multimedia communications, internet-of-things and fifth generation (5G) wireless networks. In simple terms dynamic spectrum management involves allowing unlicensed users known as secondary users (SUs) to access the licensed spectrum of a licensed user also known as primary user (PU). This is primarily achieved using spectrum sharing schemes that leverage spectrum database and cognitive radio techniques. However, the use of spectrum database and cognitive radio techniques faces reliability, security and privacy concerns for spectrum sharing. There is also a need to support other requirements of dynamic spectrum management such as secondary spectrum trading market and dynamic spectrum access coordination. In this work, we review the use of blockchains for enabling spectrum sharing and other aspects of dynamic spectrum management. The review covers the use of blockchain to record spectrum management information such as spectrum sensing results and spectrum auction transactions in a secure manner. The article also covers the use of smart contracts to support complex service-levelagreements (SLAs) between network operators which is key to supporting a self-organized secondary spectrum sharing market and enforcement of regulatory policies. A taxonomy of the intersection between blockchain and various concepts of dynamic spectrum management is also provided
Toward 6G: From New Hardware Design to Wireless Semantic and Goal-Oriented Communication Paradigms
Venue: arXiv cs.NI 2021
Year: 2021

Several speculative visions are conjecturing on what 6G services will be able to offer at the horizon of 2030. Nevertheless, the 6G design process is at its preliminary stages. The reality today is that hardware, technologies and new materials required to effectively meet the unprecedented performance targets required for future 6G services and network operation, have not been designed, tested or even do not exist yet. Today, a solid vision on the cost-benefit trade-offs of machine learning and artificial intelligence support for 6G network and services operation optimization is missing. This includes the possible support from hardware efficiency, operation effectiveness and, the immeasurable cost due to data acquisition-transfer-processing. The contribution of this paper is three-fold. This is the first paper deriving crucial 6G key performance indicators on hardware and technology design. Second, we present a new hardware technologies design methodology conceived to enable the effective software-hardware components integration required to meet the challenging performance envisioned for future 6G networks. Third, we suggest a paradigm shift towards goal-oriented and semantic communications, in which a totally new opportunity of joint design of hardware, artificial intelligence and effective communication is offered. The proposed vision is consolidated by our recent results on hardware, technology and machine learning performance.
An Improved Fixed-Parameter Algorithm for 2-Club Cluster Edge Deletion
Venue: arXiv cs.DS 2021
Year: 2021

A 2-club is a graph of diameter at most two. In the decision version of the parametrized {\sc 2-Club Cluster Edge Deletion} problem, an undirected graph $G$ is given along with an integer $k\geq 0$ as parameter, and the question is whether $G$ can be transformed into a disjoint union of 2-clubs by deleting at most $k$ edges. A simple fixed-parameter algorithm solves the problem in $\mathcal{O}^*(3^k)$, and a decade-old algorithm was claimed to have an improved running time of $\mathcal{O}^*(2.74^k)$ via a sophisticated case analysis. Unfortunately, this latter algorithm suffers from a flawed branching scenario. In this paper, an improved fixed-parameter algorithm is presented with a running time in $\mathcal{O}^*(2.695^k)$.
PIR codes from combinatorial structures
Venue: arXiv cs.IT 2021
Year: 2021

A $k$-server Private Information Retrieval (PIR) code is a binary linear $[m,s]$-code admitting a generator matrix such that for every integer $i$ with $1\le i\le s$ there exist $k$ disjoint subsets of columns (called recovery sets) that add up to the vector of weight one, with the single $1$ in position $i$. As shown in \cite{Fazeli1}, a $k$-server PIR code is useful to reduce the storage overhead of a traditional $k$-server PIR protocol. Finding $k$-server PIR codes with a small blocklength for a given dimension has recently become an important research challenge. In this work, we propose new constructions of PIR codes from combinatorial structures, introducing the notion of $k$-partial packing. Several bounds over the existing literature are improved.
Computing Fuzzy Rough Set based Similarities with Fuzzy Inference and Its Application to Sentence Similarity Computations
Venue: arXiv cs.AI 2021
Year: 2021

Several research initiatives have been proposed for computing similarity between two Fuzzy Sets in analysis through Fuzzy Rough Sets. These techniques yield two measures viz. lower similarity and upper similarity. While in most applications only one entity is useful to further analysis and for drawing conclusions. The aim of this paper is to propose novel technique to combine Fuzzy Rough Set based lower similarity and upper similarity using Fuzzy Inference Engine. Further, the proposed approach is applied to the problem computing sentence similarity and have been evaluated on SICK2014 dataset.
Empirically Measuring Transfer Distance for System Design and Operation
Venue: arXiv cs.LG 2021
Year: 2021

Classical machine learning approaches are sensitive to non-stationarity. Transfer learning can address non-stationarity by sharing knowledge from one system to another, however, in areas like machine prognostics and defense, data is fundamentally limited. Therefore, transfer learning algorithms have little, if any, examples from which to learn. Herein, we suggest that these constraints on algorithmic learning can be addressed by systems engineering. We formally define transfer distance in general terms and demonstrate its use in empirically quantifying the transferability of models. We consider the use of transfer distance in the design of machine rebuild procedures to allow for transferable prognostic models. We also consider the use of transfer distance in predicting operational performance in computer vision. Practitioners can use the presented methodology to design and operate systems with consideration for the learning theoretic challenges faced by component learning systems.
Inter-intra Variant Dual Representations forSelf-supervised Video Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Contrastive learning applied to self-supervised representation learning has seen a resurgence in deep models. In this paper, we find that existing contrastive learning based solutions for self-supervised video recognition focus on inter-variance encoding but ignore the intra-variance existing in clips within the same video. We thus propose to learn dual representations for each clip which (\romannumeral 1) encode intra-variance through a shuffle-rank pretext task; (\romannumeral 2) encode inter-variance through a temporal coherent contrastive loss. Experiment results show that our method plays an essential role in balancing inter and intra variances and brings consistent performance gains on multiple backbones and contrastive learning frameworks. Integrated with SimCLR and pretrained on Kinetics-400, our method achieves $\textbf{82.0\%}$ and $\textbf{51.2\%}$ downstream classification accuracy on UCF101 and HMDB51 test sets respectively and $\textbf{46.1\%}$ video retrieval accuracy on UCF101, outperforming both pretext-task based and contrastive learning based counterparts. Our code is available at \href{https://github.com/lzhangbj/DualVar}{https://github.com/lzhangbj/DualVar}.
Road Roughness Estimation Using Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

Road roughness is a very important road condition for the infrastructure, as the roughness affects both the safety and ride comfort of passengers. The roads deteriorate over time which means the road roughness must be continuously monitored in order to have an accurate understand of the condition of the road infrastructure. In this paper, we propose a machine learning pipeline for road roughness prediction using the vertical acceleration of the car and the car speed. We compared well-known supervised machine learning models such as linear regression, naive Bayes, k-nearest neighbor, random forest, support vector machine, and the multi-layer perceptron neural network. The models are trained on an optimally selected set of features computed in the temporal and statistical domain. The results demonstrate that machine learning methods can accurately predict road roughness, using the recordings of the cost approachable in-vehicle sensors installed in conventional passenger cars. Our findings demonstrate that the technology is well suited to meet future pavement condition monitoring, by enabling continuous monitoring of a wide road network.
Linear Discrepancy is $Π_2$-Hard to Approximate
Venue: arXiv cs.CC 2021
Year: 2021

In this note, we prove that the problem of computing the linear discrepancy of a given matrix is $Π_2$-hard, even to approximate within $9/8 - ε$ factor for any $ε> 0$. This strengthens the NP-hardness result of Li and Nikolov [ESA 2020] for the exact version of the problem, and answers a question posed by them. Furthermore, since Li and Nikolov showed that the problem is contained in $Π_2$, our result makes linear discrepancy another natural problem that is $Π_2$-complete (to approximate).