OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Delay-Outage Analysis for Noise-Limited Wireless Networks with Caching, Computing, and Communications -- Derivations and Proofs
Venue: arXiv cs.IT 2022
Year: 2022

Performance assessment and optimization for networks jointly performing caching, computing, and communication (3C) has recently drawn significant attention because many emerging applications require 3C functionality. However, studies in the literature mostly focus on the particular algorithms and setups of such networks, while their theoretical understanding and characterization has been less explored. To fill this gap, this paper conducts the asymptotic (scaling-law) analysis for the delay-outage tradeoff of noise-limited wireless edge networks with joint 3C. In particular, assuming the user requests for different tasks following a Zipf distribution, we derive the analytical expression for the optimal caching policy. Based on this, we next derive the closed-form expression for the optimum outage probability as a function of delay and other network parameters for the case that the Zipf parameter is smaller than 1. Then, for the case that the Zipf parameter is larger than 1, we derive the closed-form expressions for upper and lower bounds of the optimum outage probability. We provide insights and interpretations based on the derived expressions. Computer simulations validate our analytical results and insights.
Deep Attention-guided Graph Clustering with Dual Self-supervision
Venue: arXiv cs.CV 2022
Year: 2022

Existing deep embedding clustering works only consider the deepest layer to learn a feature embedding and thus fail to well utilize the available discriminative information from cluster assignments, resulting performance limitation. To this end, we propose a novel method, namely deep attention-guided graph clustering with dual self-supervision (DAGC). Specifically, DAGC first utilizes a heterogeneity-wise fusion module to adaptively integrate the features of an auto-encoder and a graph convolutional network in each layer and then uses a scale-wise fusion module to dynamically concatenate the multi-scale features in different layers. Such modules are capable of learning a discriminative feature embedding via an attention-based mechanism. In addition, we design a distribution-wise fusion module that leverages cluster assignments to acquire clustering results directly. To better explore the discriminative information from the cluster assignments, we develop a dual self-supervision solution consisting of a soft self-supervision strategy with a triplet Kullback-Leibler divergence loss and a hard self-supervision strategy with a pseudo supervision loss. Extensive experiments validate that our method consistently outperforms state-of-the-art methods on six benchmark datasets. Especially, our method improves the ARI by more than 18.14% over the best baseline.
Conversational Recommendation: Theoretical Model and Complexity Analysis
Venue: arXiv cs.AI 2022
Year: 2022

Recommender systems are software applications that help users find items of interest in situations of information overload in a personalized way, using knowledge about the needs and preferences of individual users. In conversational recommendation approaches, these needs and preferences are acquired by the system in an interactive, multi-turn dialog. A common approach in the literature to drive such dialogs is to incrementally ask users about their preferences regarding desired and undesired item features or regarding individual items. A central research goal in this context is efficiency, evaluated with respect to the number of required interactions until a satisfying item is found. This is usually accomplished by making inferences about the best next question to ask to the user. Today, research on dialog efficiency is almost entirely empirical, aiming to demonstrate, for example, that one strategy for selecting questions is better than another one in a given application. With this work, we complement empirical research with a theoretical, domain-independent model of conversational recommendation. This model, which is designed to cover a range of application scenarios, allows us to investigate the efficiency of conversational approaches in a formal way, in particular with respect to the computational complexity of devising optimal interaction strategies. Through such a theoretical analysis we show that finding an efficient conversational strategy is NP-hard, and in PSPACE in general, but for particular kinds of catalogs the upper bound lowers to POLYLOGSPACE. From a practical point of view, this result implies that catalog characteristics can strongly influence the efficiency of individual conversational strategies and should therefore be considered when designing new strategies. A preliminary empirical analysis on datasets derived from a real-world one aligns with our findings.
CLIP2TV: Align, Match and Distill for Video-Text Retrieval
Venue: arXiv cs.CV 2022
Year: 2022

Modern video-text retrieval frameworks basically consist of three parts: video encoder, text encoder and the similarity head. With the success on both visual and textual representation learning, transformer based encoders and fusion methods have also been adopted in the field of video-text retrieval. In this report, we present CLIP2TV, aiming at exploring where the critical elements lie in transformer based methods. To achieve this, We first revisit some recent works on multi-modal learning, then introduce some techniques into video-text retrieval, finally evaluate them through extensive experiments in different configurations. Notably, CLIP2TV achieves 52.9@R1 on MSR-VTT dataset, outperforming the previous SOTA result by 4.1%.
Distribution-Invariant Differential Privacy
Venue: arXiv cs.CR 2022
Year: 2022

Differential privacy is becoming one gold standard for protecting the privacy of publicly shared data. It has been widely used in social science, data science, public health, information technology, and the U.S. decennial census. Nevertheless, to guarantee differential privacy, existing methods may unavoidably alter the conclusion of the original data analysis, as privatization often changes the sample distribution. This phenomenon is known as the trade-off between privacy protection and statistical accuracy. In this work, we mitigate this trade-off by developing a distribution-invariant privatization (DIP) method to reconcile both high statistical accuracy and strict differential privacy. As a result, any downstream statistical or machine learning task yields essentially the same conclusion as if one used the original data. Numerically, under the same strictness of privacy protection, DIP achieves superior statistical accuracy in a wide range of simulation studies and real-world benchmarks.
On the efficiency of a general attack against the MOBS cryptosystem
Venue: arXiv cs.CR 2022
Year: 2022

All instances of the semidirect key exchange protocol, a generalisation of the famous Diffie-Hellman key exchange protocol, satisfy the so-called "telescoping equality"; in some cases, this equality has been used to construct an attack. In this report we present computational evidence suggesting that an instance of the scheme called `MOBS' is an example of a scheme where the telescoping equality has too many solutions to be a practically viable means to conduct an attack.
Theoretical Exploration of Flexible Transmitter Model
Venue: arXiv cs.LG 2022
Year: 2022

Neural network models generally involve two important components, i.e., network architecture and neuron model. Although there are abundant studies about network architectures, only a few neuron models have been developed, such as the MP neuron model developed in 1943 and the spiking neuron model developed in the 1950s. Recently, a new bio-plausible neuron model, Flexible Transmitter (FT) model, has been proposed. It exhibits promising behaviors, particularly on temporal-spatial signals, even when simply embedded into the common feedforward network architecture. This paper attempts to understand the properties of the FT network (FTNet) theoretically. Under mild assumptions, we show that: i) FTNet is a universal approximator; ii) the approximation complexity of FTNet can be exponentially smaller than those of commonly-used real-valued neural networks with feedforward/recurrent architectures and is of the same order in the worst case; iii) any local minimum of FTNet is the global minimum, implying that it is possible to identify global minima by local search algorithms.
Uncertainty quantification of a three-dimensional in-stent restenosis model with surrogate modelling
Venue: arXiv cs.CE 2022
Year: 2022

In-Stent Restenosis is a recurrence of coronary artery narrowing due to vascular injury caused by balloon dilation and stent placement. It may lead to the relapse of angina symptoms or to an acute coronary syndrome. An uncertainty quantification of a model for In-Stent Restenosis with four uncertain parameters (endothelium regeneration time, the threshold strain for smooth muscle cells bond breaking, blood flow velocity and the percentage of fenestration in the internal elastic lamina) is presented. Two quantities of interest were studied, namely the average cross-sectional area and the maximum relative area loss in a vessel. Due to the computational intensity of the model and the number of evaluations required in the uncertainty quantification, a surrogate model, based on Gaussian process regression with proper orthogonal decomposition, was developed which subsequently replaced the original In-Stent Restenosis model in the uncertainty quantification. A detailed analysis of the uncertainty propagation and sensitivity analysis is presented. Around 11% and 16% of uncertainty are observed on the average cross-sectional area and maximum relative area loss respectively, and the uncertainty estimates show that a higher fenestration mainly determines uncertainty in the neointimal growth at the initial stage of the process. On the other hand, the uncertainty in blood flow velocity and endothelium regeneration time mainly determine the uncertainty in the quantities of interest at the later, clinically relevant stages of the restenosis process. The uncertainty in the threshold strain is relatively small compared to the other uncertain parameters.
Assigning and Scheduling Generalized Malleable Jobs under Subadditive or Submodular Processing Speeds
Venue: arXiv cs.DM 2022
Year: 2022

Malleable scheduling is a model that captures the possibility of parallelization to expedite the completion of time-critical tasks. A malleable job can be allocated and processed simultaneously on multiple machines, occupying the same time interval on all these machines. We study a general version of this setting, in which the functions determining the joint processing speed of machines for a given job follow different discrete concavity assumptions (subadditivity, fractional subadditivity, submodularity, and matroid ranks). We show that under these assumptions the problem of scheduling malleable jobs at minimum makespan can be approximated by a considerably simpler assignment problem. Moreover, we provide efficient approximation algorithms for both the scheduling and the assignment problem, with increasingly stronger guarantees for increasingly stronger concavity assumptions, including a logarithmic approximation factor for the case of submodular processing speeds and a constant approximation factor when processing speeds are determined by matroid rank functions. Computational experiments indicate that our algorithms outperform the theoretical worst-case guarantees.
Character-level HyperNetworks for Hate Speech Detection
Venue: arXiv cs.CL 2022
Year: 2022

The massive spread of hate speech, hateful content targeted at specific subpopulations, is a problem of critical social importance. Automated methods of hate speech detection typically employ state-of-the-art deep learning (DL)-based text classifiers-large pretrained neural language models of over 100 million parameters, adapting these models to the task of hate speech detection using relevant labeled datasets. Unfortunately, there are only a few public labeled datasets of limited size that are available for this purpose. We make several contributions with high potential for advancing this state of affairs. We present HyperNetworks for hate speech detection, a special class of DL networks whose weights are regulated by a small-scale auxiliary network. These architectures operate at character-level, as opposed to word or subword-level, and are several orders of magnitude smaller compared to the popular DL classifiers. We further show that training hate detection classifiers using additional large amounts of automatically generated examples is beneficial in general, yet this practice especially boosts the performance of the proposed HyperNetworks. We report the results of extensive experiments, assessing the performance of multiple neural architectures on hate detection using five public datasets. The assessed methods include the pretrained language models of BERT, RoBERTa, ALBERT, MobileBERT and CharBERT, a variant of BERT that incorporates character alongside subword embeddings. In addition to the traditional setup of within-dataset evaluation, we perform cross-dataset evaluation experiments, testing the generalization of the various models in conditions of data shift. Our results show that the proposed HyperNetworks achieve performance that is competitive, and better in some cases, than these pretrained language models, while being smaller by orders of magnitude.
Automated question generation and question answering from Turkish texts
Venue: arXiv cs.LG 2022
Year: 2022

While exam-style questions are a fundamental educational tool serving a variety of purposes, manual construction of questions is a complex process that requires training, experience and resources. Automatic question generation (QG) techniques can be utilized to satisfy the need for a continuous supply of new questions by streamlining their generation. However, compared to automatic question answering (QA), QG is a more challenging task. In this work, we fine-tune a multilingual T5 (mT5) transformer in a multi-task setting for QA, QG and answer extraction tasks using Turkish QA datasets. To the best of our knowledge, this is the first academic work that performs automated text-to-text question generation from Turkish texts. Experimental evaluations show that the proposed multi-task setting achieves state-of-the-art Turkish question answering and question generation performance on TQuADv1, TQuADv2 datasets and XQuAD Turkish split. The source code and the pre-trained models are available at https://github.com/obss/turkish-question-generation.
Review of Pedestrian Trajectory Prediction Methods: Comparing Deep Learning and Knowledge-based Approaches
Venue: arXiv cs.LG 2022
Year: 2022

In crowd scenarios, predicting trajectories of pedestrians is a complex and challenging task depending on many external factors. The topology of the scene and the interactions between the pedestrians are just some of them. Due to advancements in data-science and data collection technologies deep learning methods have recently become a research hotspot in numerous domains. Therefore, it is not surprising that more and more researchers apply these methods to predict trajectories of pedestrians. This paper compares these relatively new deep learning algorithms with classical knowledge-based models that are widely used to simulate pedestrian dynamics. It provides a comprehensive literature review of both approaches, explores technical and application oriented differences, and addresses open questions as well as future development directions. Our investigations point out that the pertinence of knowledge-based models to predict local trajectories is nowadays questionable because of the high accuracy of the deep learning algorithms. Nevertheless, the ability of deep-learning algorithms for large-scale simulation and the description of collective dynamics remains to be demonstrated. Furthermore, the comparison shows that the combination of both approaches (the hybrid approach) seems to be promising to overcome disadvantages like the missing explainability of the deep learning approach.
Performance Analysis over Correlated/Independent Fisher-Snedecor F Fading Multi-User Channels
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, we investigate the impact of correlated fading on the performance of wireless multiple access channels (MAC) in the presence and absence of side information (SI) at transmitters, where the fading coefficients are modeled according to the Fisher-Snedecor F distribution. Specifically, we represent two scenarios: (i) clean MAC (i.e, without SI at transmitters), (ii) doubly dirty MAC (i.e., with the non-causally known SI at transmitters). For both system models, we derive the closedform expressions of the outage probability (OP) as well as the average capacity (AC) under independent fading conditions. Besides, exploiting copula theory, we obtain the exact analytical expressions for the OP and the AC under positive dependence fading conditions in both considered models. Finally, the validity of the analytical results is illustrated numerically.
On the complexity of SAT
Venue: arXiv cs.CC 2022
Year: 2022

In this paper, we prove that no deterministic algorithm can solve SAT in polynomial time in the number of boolean variables.
Scalable Diverse Model Selection for Accessible Transfer Learning
Venue: arXiv cs.LG 2022
Year: 2022

With the preponderance of pretrained deep learning models available off-the-shelf from model banks today, finding the best weights to fine-tune to your use-case can be a daunting task. Several methods have recently been proposed to find good models for transfer learning, but they either don't scale well to large model banks or don't perform well on the diversity of off-the-shelf models. Ideally the question we want to answer is, "given some data and a source model, can you quickly predict the model's accuracy after fine-tuning?" In this paper, we formalize this setting as "Scalable Diverse Model Selection" and propose several benchmarks for evaluating on this task. We find that existing model selection and transferability estimation methods perform poorly here and analyze why this is the case. We then introduce simple techniques to improve the performance and speed of these algorithms. Finally, we iterate on existing methods to create PARC, which outperforms all other methods on diverse model selection. We have released the benchmarks and method code in hope to inspire future work in model selection for accessible transfer learning.
Novel Weight Update Scheme for Hardware Neural Network based on Synaptic Devices Having Abrupt LTP or LTD Characteristics
Venue: arXiv cs.ET 2022
Year: 2022

Mitigating nonlinear weight update characteristics is one of the main challenges in designing neural networks based on synaptic devices. This paper presents a novel weight update method named conditional reverse update scheme (CRUS) for hardware neural network (HNN) consisting of synaptic devices with highly nonlinear or abrupt conductance update characteristics. We formulate a linear optimization method of conductance in synaptic devices to reduce the average deviation of weight changes from those calculated by the Stochastic Gradient Rule (SGD) algorithm. We introduce a metric called update noise (UN) to analyze the training dynamics during training. We then design a weight update rule that reduces the UN averaged over the training process. The optimized network achieves >90% accuracy on the MNIST dataset under highly nonlinear long-term potentiation (LTP) and long-term depression (LTD) conditions while using inaccurate and infrequent conductance sensing. Furthermore, the proposed method shows better accuracy than previously reported nonlinear weight update mitigation techniques under the same hardware specifications and device conditions. It also exhibits robustness to temporal variations in conductance updates. We expect our scheme to relieve design requirements in device and circuit engineering and serve as a practical technique that can be applied to future HNNs.
Eluding Secure Aggregation in Federated Learning via Model Inconsistency
Venue: arXiv cs.LG 2022
Year: 2022

Secure aggregation is a cryptographic protocol that securely computes the aggregation of its inputs. It is pivotal in keeping model updates private in federated learning. Indeed, the use of secure aggregation prevents the server from learning the value and the source of the individual model updates provided by the users, hampering inference and data attribution attacks. In this work, we show that a malicious server can easily elude secure aggregation as if the latter were not in place. We devise two different attacks capable of inferring information on individual private training datasets, independently of the number of users participating in the secure aggregation. This makes them concrete threats in large-scale, real-world federated learning applications. The attacks are generic and equally effective regardless of the secure aggregation protocol used. They exploit a vulnerability of the federated learning protocol caused by incorrect usage of secure aggregation and lack of parameter validation. Our work demonstrates that current implementations of federated learning with secure aggregation offer only a "false sense of security".
Improved Decoding of Expander Codes
Venue: arXiv cs.IT 2022
Year: 2022

We study the classical expander codes, introduced by Sipser and Spielman \cite{SS96}. Given any constants $0< α, \varepsilon < 1/2$, and an arbitrary bipartite graph with $N$ vertices on the left, $M < N$ vertices on the right, and left degree $D$ such that any left subset $S$ of size at most $αN$ has at least $(1-\varepsilon)|S|D$ neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly $\frac{αN}{2 \varepsilon }$. This is strictly better than the best known previous result of $2(1-\varepsilon ) αN$ \cite{Sudan2000note, Viderman13b} whenever $\varepsilon < 1/2$, and improves the previous result significantly when $\varepsilon $ is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever $\varepsilon < \frac{1}{4}$. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.