OpenRaiser/Intern-Atlas huggingface dataset:
Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique
Venue: arXiv cs.CC 2022
Year: 2022

We study the complexity of computing (and approximating) VC Dimension and Littlestone's Dimension when we are given the concept class explicitly. We give a simple reduction from Maximum (Unbalanced) Biclique problem to approximating VC Dimension and Littlestone's Dimension. With this connection, we derive a range of hardness of approximation results and running time lower bounds. For example, under the (randomized) Gap-Exponential Time Hypothesis or the Strongish Planted Clique Hypothesis, we show a tight inapproximability result: both dimensions are hard to approximate to within a factor of $o(\log n)$ in polynomial-time. These improve upon constant-factor inapproximability results from [Manurangsi and Rubinstein, COLT 2017].
Privacy-preserving Non-negative Matrix Factorization with Outliers
Venue: arXiv cs.LG 2022
Year: 2022

Non-negative matrix factorization is a popular unsupervised machine learning algorithm for extracting meaningful features from data which are inherently non-negative. However, such data sets may often contain privacy-sensitive user data, and therefore, we may need to take necessary steps to ensure the privacy of the users while analyzing the data. In this work, we focus on developing a Non-negative matrix factorization algorithm in the privacy-preserving framework. More specifically, we propose a novel privacy-preserving algorithm for non-negative matrix factorisation capable of operating on private data, while achieving results comparable to those of the non-private algorithm. We design the framework such that one has the control to select the degree of privacy grantee based on the utility gap. We show our proposed framework's performance in six real data sets. The experimental results show that our proposed method can achieve very close performance with the non-private algorithm under some parameter regime, while ensuring strict privacy.
Max Markov Chain
Venue: arXiv cs.AI 2022
Year: 2022

In this paper, we introduce Max Markov Chain (MMC), a novel representation for a useful subset of High-order Markov Chains (HMCs) with sparse correlations among the states. MMC is parsimony while retaining the expressiveness of HMCs. Even though parameter optimization is generally intractable as with HMC approximate models, it has an analytical solution, better sample efficiency, and the desired spatial and computational advantages over HMCs and approximate HMCs. Simultaneously, efficient approximate solutions exist for this type of chains as we show empirically, which allow MMCs to scale to large domains where HMCs and approximate HMCs would struggle to perform. We compare MMC with HMC, first-order Markov chain, and an approximate HMC model in synthetic domains with various data types to demonstrate that MMC is a valuable alternative for modeling stochastic processes and has many potential applications.
Learning to Grasp the Ungraspable with Emergent Extrinsic Dexterity
Venue: arXiv cs.RO 2022
Year: 2022

A simple gripper can solve more complex manipulation tasks if it can utilize the external environment such as pushing the object against the table or a vertical wall, known as "Extrinsic Dexterity." Previous work in extrinsic dexterity usually has careful assumptions about contacts which impose restrictions on robot design, robot motions, and the variations of the physical parameters. In this work, we develop a system based on reinforcement learning (RL) to address these limitations. We study the task of "Occluded Grasping" which aims to grasp the object in configurations that are initially occluded; the robot needs to move the object into a configuration from which these grasps can be achieved. We present a system with model-free RL that successfully achieves this task using a simple gripper with extrinsic dexterity. The policy learns emergent behaviors of pushing the object against the wall to rotate and then grasp it without additional reward terms on extrinsic dexterity. We discuss important components of the system including the design of the RL problem, multi-grasp training and selection, and policy generalization with automatic curriculum. Most importantly, the policy trained in simulation is zero-shot transferred to a physical robot. It demonstrates dynamic and contact-rich motions with a simple gripper that generalizes across objects with various size, density, surface friction, and shape with a 78% success rate. Videos can be found at https://sites.google.com/view/grasp-ungraspable/.
Reliable Malware Analysis and Detection using Topology Data Analysis
Venue: arXiv cs.CR 2022
Year: 2022

Increasingly, malwares are becoming complex and they are spreading on networks targeting different infrastructures and personal-end devices to collect, modify, and destroy victim information. Malware behaviors are polymorphic, metamorphic, persistent, able to hide to bypass detectors and adapt to new environments, and even leverage machine learning techniques to better damage targets. Thus, it makes them difficult to analyze and detect with traditional endpoint detection and response, intrusion detection and prevention systems. To defend against malwares, recent work has proposed different techniques based on signatures and machine learning. In this paper, we propose to use an algebraic topological approach called topological-based data analysis (TDA) to efficiently analyze and detect complex malware patterns. Next, we compare the different TDA techniques (i.e., persistence homology, tomato, TDA Mapper) and existing techniques (i.e., PCA, UMAP, t-SNE) using different classifiers including random forest, decision tree, xgboost, and lightgbm. We also propose some recommendations to deploy the best-identified models for malware detection at scale. Results show that TDA Mapper (combined with PCA) is better for clustering and for identifying hidden relationships between malware clusters compared to PCA. Persistent diagrams are better to identify overlapping malware clusters with low execution time compared to UMAP and t-SNE. For malware detection, malware analysts can use Random Forest and Decision Tree with t-SNE and Persistent Diagram to achieve better performance and robustness on noised data.
INGREX: An Interactive Explanation Framework for Graph Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Graph Neural Networks (GNNs) are widely used in many modern applications, necessitating explanations for their decisions. However, the complexity of GNNs makes it difficult to explain predictions. Even though several methods have been proposed lately, they can only provide simple and static explanations, which are difficult for users to understand in many scenarios. Therefore, we introduce INGREX, an interactive explanation framework for GNNs designed to aid users in comprehending model predictions. Our framework is implemented based on multiple explanation algorithms and advanced libraries. We demonstrate our framework in three scenarios covering common demands for GNN explanations to present its effectiveness and helpfulness.
Resource Allocation in MIMO setup
Venue: arXiv cs.IT 2022
Year: 2022

In a multi-input multi-output (MIMO) setup, where one side of the link comprises a linear antenna array, data can be transmitted over the direction of incident rays. Channel capacity for this setup is studied in this paper. We define two different setups; one when the energy is constant and equal over all rays, and one when available energy is evenly distributed over rays. For the latter, we show that there is an upper bound for channel capacity, regardless of the number of rays and antennas. Also, we have compared this setup with the legacy single-input single-output (SISO) AWGN channel.
A Convergence Theory for Federated Average: Beyond Smoothness
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning enables a large amount of edge computing devices to learn a model without data sharing jointly. As a leading algorithm in this setting, Federated Average FedAvg, which runs Stochastic Gradient Descent (SGD) in parallel on local devices and averages the sequences only once in a while, have been widely used due to their simplicity and low communication cost. However, despite recent research efforts, it lacks theoretical analysis under assumptions beyond smoothness. In this paper, we analyze the convergence of FedAvg. Different from the existing work, we relax the assumption of strong smoothness. More specifically, we assume the semi-smoothness and semi-Lipschitz properties for the loss function, which have an additional first-order term in assumption definitions. In addition, we also assume bound on the gradient, which is weaker than the commonly used bounded gradient assumption in the convergence analysis scheme. As a solution, this paper provides a theoretical convergence study on Federated Learning.
Secret Sharing for Generic Theoretic Cryptography
Venue: arXiv cs.CR 2022
Year: 2022

Sharing a secret efficiently amongst a group of participants is not easy since there is always an adversary / eavesdropper trying to retrieve the secret. In secret sharing schemes, every participant is given a unique share. When the desired group of participants come together and provide their shares, the secret is obtained. For other combinations of shares, a garbage value is returned. A threshold secret sharing scheme was proposed by Shamir and Blakley independently. In this (n,t) threshold secret sharing scheme, the secret can be obtained when at least t out of n participants contribute their shares. This paper proposes a novel algorithm to reveal the secret only to the subsets of participants belonging to the access structure. This scheme implements totally generalized ideal secret sharing. Unlike threshold secret sharing schemes, this scheme reveals the secret only to the authorized sets of participants, not any arbitrary set of users with cardinality more than or equal to t. Since any access structure can be realized with this scheme, this scheme can be exploited to implement various access priorities and access control mechanisms. A major advantage of this scheme over the existing ones is that the shares being distributed to the participants is totally independent of the secret being shared. Hence, no restrictions are imposed on the scheme and it finds a wider use in real world applications.
An Open Platform for Simulating the Physical Layer of 6G Communication Systems with Multiple Intelligent Surfaces
Venue: arXiv cs.ET 2022
Year: 2022

Reconfigurable Intelligent Surfaces (RIS) constitute a promising technology that could fulfill the extreme performance and capacity needs of the upcoming 6G wireless networks, by offering software-defined control over wireless propagation phenomena. Despite the existence of many theoretical models describing various aspects of RIS from the signal processing perspective (e.g., channel fading models), there is no open platform to simulate and study their actual physical-layer behavior, especially in the multi-RIS case. In this paper, we develop an open simulation platform, aimed at modeling the physical-layer electromagnetic coupling and propagation between RIS pairs. We present the platform by initially designing a basic unit cell, and then proceeding to progressively model and simulate multiple and larger RISs. The platform can be used for producing verifiable stochastic models for wireless communication in multi-RIS deployments, such as vehicle-to-everything (V2X) communications in autonomous vehicles and cybersecurity schemes, while its code is freely available to the public.
A speech corpus for chronic kidney disease
Venue: arXiv cs.CL 2022
Year: 2022

In this study, we present a speech corpus of patients with chronic kidney disease (CKD) that will be used for research on pathological voice analysis, automatic illness identification, and severity prediction. This paper introduces the steps involved in creating this corpus, including the choice of speech-related parameters and speech lists as well as the recording technique. The speakers in this corpus, 289 CKD patients with varying degrees of severity who were categorized based on estimated glomerular filtration rate (eGFR), delivered sustained vowels, sentence, and paragraph stimuli. This study compared and analyzed the voice characteristics of CKD patients with those of the control group; the results revealed differences in voice quality, phoneme-level pronunciation, prosody, glottal source, and aerodynamic parameters.
iGniter: Interference-Aware GPU Resource Provisioning for Predictable DNN Inference in the Cloud
Venue: arXiv cs.DC 2022
Year: 2022

GPUs are essential to accelerating the latency-sensitive deep neural network (DNN) inference workloads in cloud datacenters. To fully utilize GPU resources, spatial sharing of GPUs among co-located DNN inference workloads becomes increasingly compelling. However, GPU sharing inevitably brings severe performance interference among co-located inference workloads, as motivated by an empirical measurement study of DNN inference on EC2 GPU instances. While existing works on guaranteeing inference performance service level objectives (SLOs) focus on either temporal sharing of GPUs or reactive GPU resource scaling and inference migration techniques, how to proactively mitigate such severe performance interference has received comparatively little attention. In this paper, we propose iGniter, an interference-aware GPU resource provisioning framework for cost-efficiently achieving predictable DNN inference in the cloud. iGniter is comprised of two key components: (1) a lightweight DNN inference performance model, which leverages the system and workload metrics that are practically accessible to capture the performance interference; (2) A cost-efficient GPU resource provisioning strategy that jointly optimizes the GPU resource allocation and adaptive batching based on our inference performance model, with the aim of achieving predictable performance of DNN inference workloads. We implement a prototype of iGniter based on the NVIDIA Triton inference server hosted on EC2 GPU instances. Extensive prototype experiments on four representative DNN models and datasets demonstrate that iGniter can guarantee the performance SLOs of DNN inference workloads with practically acceptable runtime overhead, while saving the monetary cost by up to 25% in comparison to the state-of-the-art GPU resource provisioning strategies.
Transformers on Multilingual Clause-Level Morphology
Venue: arXiv cs.CL 2022
Year: 2022

This paper describes our winning systems in MRL: The 1st Shared Task on Multilingual Clause-level Morphology (EMNLP 2022 Workshop) designed by KUIS AI NLP team. We present our work for all three parts of the shared task: inflection, reinflection, and analysis. We mainly explore transformers with two approaches: (i) training models from scratch in combination with data augmentation, and (ii) transfer learning with prefix-tuning at multilingual morphological tasks. Data augmentation significantly improves performance for most languages in the inflection and reinflection tasks. On the other hand, Prefix-tuning on a pre-trained mGPT model helps us to adapt analysis tasks in low-data and multilingual settings. While transformer architectures with data augmentation achieved the most promising results for inflection and reinflection tasks, prefix-tuning on mGPT received the highest results for the analysis task. Our systems received 1st place in all three tasks in MRL 2022.
Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits
Venue: arXiv cs.LG 2022
Year: 2022

In the infinite-armed bandit problem, each arm's average reward is sampled from an unknown distribution, and each arm can be sampled further to obtain noisy estimates of the average reward of that arm. Prior work focuses on identifying the best arm, i.e., estimating the maximum of the average reward distribution. We consider a general class of distribution functionals beyond the maximum, and propose unified meta algorithms for both the offline and online settings, achieving optimal sample complexities. We show that online estimation, where the learner can sequentially choose whether to sample a new or existing arm, offers no advantage over the offline setting for estimating the mean functional, but significantly reduces the sample complexity for other functionals such as the median, maximum, and trimmed mean. The matching lower bounds utilize several different Wasserstein distances. For the special case of median estimation, we identify a curious thresholding phenomenon on the indistinguishability between Gaussian convolutions with respect to the noise level, which may be of independent interest.
Task Tree Retrieval for Robotic Cooking
Venue: arXiv cs.RO 2022
Year: 2022

Robotics is used to foster creativity. Humans can perform jobs in their unique manner, depending on the circumstances. This situation applies to food cooking. Robotic technology in the kitchen can speed up the process and reduce its workload. However, the potential of robotics in the kitchen is still unrealized. In this essay, the idea of FOON, a structural knowledge representation built on insights from human manipulations, is introduced. To reduce the failure rate and ensure that the task is effectively completed, three different algorithms have been implemented where weighted values have been assigned to the manipulations depending on the success rates of motion. This knowledge representation was created using videos of open-sourced recipes
A Comparative Study of Smartphone and Smart TV Apps
Venue: arXiv cs.SE 2022
Year: 2022

Context: Smart TVs have become one of the most popular television types. Many app developers and service providers have designed TV versions for their smartphone applications. Despite the extensive studies on mobile app analysis, its TV equivalents receive far too little attention. The relationship between phone and TV has not been the subject of research works. Objective: In this paper, we aim to characterize the relationship between smartphone and smart TV apps. To fill this gap, we conduct a comparative study on smartphone and smart TV apps in this work, which is the starting and fundamental step to uncover the domain-specific challenges. Method: We gather a large-scale phone/TV app pairs from Google Play Store. We then analyzed the app pairs quantitatively and qualitatively from a variety of perspectives, including non-code (e.g., metadata, resources, permissions, etc.), code (e.g., components, methods, user interactions, etc.), security and privacy (e.g., reports of AndroBugs and FlowDroid). Results: Our experimental results indicate that (1) the code of the smartphone and TV apps can be released in the same app package or in separate app packages with the same package name; (2) 43% of resource files and 50% of code methods are reused between phone/TV app pairs; (3) TV and phone versions of the same app often encounter different kinds of security vulnerabilities; and (4) TV apps encounter fewer user interactions than their phone versions, but the type of user interaction events, surprisingly, are similar between phone/TV apps. Conclution: Our findings are valuable for developers and academics in comprehending the TV app ecosystem by providing additional insight into the migration of phone apps to TVs and the design mechanism of analysis tools for TV apps.
Implementation of the Digital QS-SVM-based Beamformer on an FPGA Platform
Venue: arXiv cs.NI 2022
Year: 2022

To address practical challenges in establishing and maintaining robust wireless connectivity such as multi-path effects, low latency, size reduction, and high data rate, the digital beamformer is performed by the hybrid antenna array at the frequency of operation of 10 GHz. The proposed digital beamformer, as a spatial filter, is capable of performing Direction of Arrival (DOA) estimation and beamforming. The most well-established machine learning technique of support vector machine (SVM) for the DoA estimation is limited to problems with linearly-separable datasets. To overcome the aforementioned constraint, in the proposed beamformer, the QS-SVM classifier with a small regularizer has been used for the DoA estimation in addition to the two beamforming techniques of LCMV and MVDR. The QS-SVM-based beamformer has been deployed in an FPGA board, as demonstrated in detail in this work. The implementation results have verified the strong performance of the QS-SVM-based beamformer in suppressing undesired signals, deep nulls with powers less than -10 dB in undesired signals, and transferring desired signals. Furthermore, we have demonstrated that the performance of the QS-SVM-based beamformer consists of other advantages of average latency time in the order of milliseconds, performance efficiency of more than 90\%, and throughput of about 100\%.
Exploring Explainability Methods for Graph Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

With the growing use of deep learning methods, particularly graph neural networks, which encode intricate interconnectedness information, for a variety of real tasks, there is a necessity for explainability in such settings. In this paper, we demonstrate the applicability of popular explainability approaches on Graph Attention Networks (GAT) for a graph-based super-pixel image classification task. We assess the qualitative and quantitative performance of these techniques on three different datasets and describe our findings. The results shed a fresh light on the notion of explainability in GNNs, particularly GATs.
Complexity of Simon's problem in classical sense
Venue: arXiv cs.CC 2022
Year: 2022

Simon's problem is a standard example of a problem that is exponential in classical sense, while it admits a polynomial solution in quantum computing. It is about a function $f$ for which it is given that a unique non-zero vector $s$ exists for which $f(x) = f(x \oplus s)$ for all $x$, where $\oplus$ is the exclusive or operator. The goal is to find $s$. The exponential lower bound for the classical sense assumes that $f$ only admits black box access. In this paper we investigate classical complexity when $f$ is given by a standard representation like a circuit. We focus on finding the vector space of all vectors $s$ for which $f(x) = f(x \oplus s)$ for all $x$, for any given $f$. Two main results are: (1) if $f$ is given by any circuit, then checking whether this vector space contains a non-zero element is NP-hard, and (2) if $f$ is given by any ordered BDD, then a basis of this vector space can be computed in polynomial time.
Beyond Instance Discrimination: Relation-aware Contrastive Self-supervised Learning
Venue: arXiv cs.CV 2022
Year: 2022

Contrastive self-supervised learning (CSL) based on instance discrimination typically attracts positive samples while repelling negatives to learn representations with pre-defined binary self-supervision. However, vanilla CSL is inadequate in modeling sophisticated instance relations, limiting the learned model to retain fine semantic structure. On the one hand, samples with the same semantic category are inevitably pushed away as negatives. On the other hand, differences among samples cannot be captured. In this paper, we present relation-aware contrastive self-supervised learning (ReCo) to integrate instance relations, i.e., global distribution relation and local interpolation relation, into the CSL framework in a plug-and-play fashion. Specifically, we align similarity distributions calculated between the positive anchor views and the negatives at the global level to exploit diverse similarity relations among instances. Local-level interpolation consistency between the pixel space and the feature space is applied to quantitatively model the feature differences of samples with distinct apparent similarities. Through explicitly instance relation modeling, our ReCo avoids irrationally pushing away semantically identical samples and carves a well-structured feature space. Extensive experiments conducted on commonly used benchmarks justify that our ReCo consistently gains remarkable performance improvements.