OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting epistemic uncertainty of the deep learning models to generate adversarial samples
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural network architectures are considered to be robust to random perturbations. Nevertheless, it was shown that they could be severely vulnerable to slight but carefully crafted perturbations of the input, termed as adversarial samples. In recent years, numerous studies have been conducted in this new area called "Adversarial Machine Learning" to devise new adversarial attacks and to defend against these attacks with more robust DNN architectures. However, almost all the research work so far has been concentrated on utilising model loss function to craft adversarial examples or create robust models. This study explores the usage of quantified epistemic uncertainty obtained from Monte-Carlo Dropout Sampling for adversarial attack purposes by which we perturb the input to the areas where the model has not seen before. We proposed new attack ideas based on the epistemic uncertainty of the model. Our results show that our proposed hybrid attack approach increases the attack success rates from 82.59% to 85.40%, 82.86% to 89.92% and 88.06% to 90.03% on MNIST Digit, MNIST Fashion and CIFAR-10 datasets, respectively.
Fast real and complex root-finding methods for well-conditioned polynomials
Venue: arXiv cs.SC 2021
Year: 2021

Given a polynomial $p$ of degree $d$ and a bound $κ$ on a condition number of $p$, we present the first root-finding algorithms that return all its real and complex roots with a number of bit operations quasi-linear in $d \log^2(κ)$. More precisely, several condition numbers can be defined depending on the norm chosen on the coefficients of the polynomial. Let $p(x) = \sum\_{k=0}^d a\_k x^k = \sum\_{k=0}^d \sqrt{\binom d k} b\_k x^k$. We call the condition number associated with a perturbation of the $a\_k$ the hyperbolic condition number $κ\_h$, and the one associated with a perturbation of the $b\_k$ the elliptic condition number $κ\_e$. For each of these condition numbers, we present algorithms that find the real and the complex roots of $p$ in $O\left(d\log^2(dκ)\ \text{polylog}(\log(dκ))\right)$ bit operations.Our algorithms are well suited for random polynomials since $κ\_h$ (resp. $κ\_e$) is bounded by a polynomial in $d$ with high probability if the $a\_k$ (resp. the $b\_k$) are independent, centered Gaussian variables of variance $1$.
A Dynamic Data Structure for Temporal Reachability with Unsorted Contact Insertions
Venue: arXiv cs.DS 2021
Year: 2021

Temporal graphs represent interactions between entities over the time. These interactions may be direct (a contact between two nodes at some time instant), or indirect, through sequences of contacts called temporal paths (journeys). Deciding whether an entity can reach another through a journey is useful for various applications in communication networks and epidemiology, among other fields. In this paper, we present a data structure which maintains temporal reachability information under the addition of new contacts (i.e., triplets $(u,v,t)$ indicating that node $u$ and node $v$ interacted at time $t$). In contrast to previous works, the contacts can be inserted in arbitrary order -- in particular, non-chronologically -- which corresponds to systems where the information is collected a posteriori (e.g. when trying to reconstruct contamination chains among people). The main component of our data structure is a generalization of transitive closure called timed transitive closure (TTC), which allows us to maintain reachability information relative to all nested time intervals, without storing all these intervals, nor the journeys themselves. TTCs are of independent interest and we study a number of their general properties. Let $n$ be the number of nodes and $τ$ be the number of timestamps in the lifetime of the temporal graph. Our data structure answers reachability queries regarding the existence of a journey from a given node to another within given time interval in time $O(\logτ)$; it has an amortized insertion time of $O(n^2\logτ)$; and it can reconstruct a valid journey that witnesses reachability in time $O(k\logτ)$, where $k<n$ is the maximum number of edges of this journey. Finally, the space complexity of our reachability data structure is $O(n^2τ)$, which remains within the worst-case size of the temporal graph itself.
Contrastive Embeddings for Neural Architectures
Venue: arXiv cs.LG 2021
Year: 2021

The performance of algorithms for neural architecture search strongly depends on the parametrization of the search space. We use contrastive learning to identify networks across different initializations based on their data Jacobians, and automatically produce the first architecture embeddings independent from the parametrization of the search space. Using our contrastive embeddings, we show that traditional black-box optimization algorithms, without modification, can reach state-of-the-art performance in Neural Architecture Search. As our method provides a unified embedding space, we perform for the first time transfer learning between search spaces. Finally, we show the evolution of embeddings during training, motivating future studies into using embeddings at different training stages to gain a deeper understanding of the networks in a search space.
Understanding health and behavioral trends of successful students through machine learning models
Venue: arXiv cs.CY 2021
Year: 2021

This study analyzes patterns of physical, mental, lifestyle, and personality factors in college students in different periods over the course of a semester and models their relationships with students' academic performance. The data analyzed was collected through smartphones and Fitbit. The use of machine learning models derived from the gathered data was employed to observe the extent of students' behavior associated with their GPA, lifestyle, physical health, mental health, and personality attributes. A mutual agreement method was used in which rather than looking at the accuracy of results, the model parameters and weights of features were used to find common behavioral trends. From the results of the model creation, it was determined that the most significant indicator of academic success defined as a higher GPA, was the places a student spent their time. Lifestyle and personality factors were deemed more significant than mental and physical factors. This study will provide insight into the impact of different factors and the timing of those factors on students' academic performance.
Counterfactual Contextual Multi-Armed Bandit: a Real-World Application to Diagnose Apple Diseases
Venue: arXiv cs.LG 2021
Year: 2021

Post-harvest diseases of apple are one of the major issues in the economical sector of apple production, causing severe economical losses to producers. Thus, we developed DSSApple, a picture-based decision support system able to help users in the diagnosis of apple diseases. Specifically, this paper addresses the problem of sequentially optimizing for the best diagnosis, leveraging past interactions with the system and their contextual information (i.e. the evidence provided by the users). The problem of learning an online model while optimizing for its outcome is commonly addressed in the literature through a stochastic active learning paradigm - i.e. Contextual Multi-Armed Bandit (CMAB). This methodology interactively updates the decision model considering the success of each past interaction with respect to the context provided in each round. However, this information is very often partial and inadequate to handle such complex decision making problems. On the other hand, human decisions implicitly include unobserved factors (referred in the literature as unobserved confounders) that significantly contribute to the human's final decision. In this paper, we take advantage of the information embedded in the observed human decisions to marginalize confounding factors and improve the capability of the CMAB model to identify the correct diagnosis. Specifically, we propose a Counterfactual Contextual Multi-Armed Bandit, a model based on the causal concept of counterfactual. The proposed model is validated with offline experiments based on data collected through a large user study on the application. The results prove that our model is able to outperform both traditional CMAB algorithms and observed user decisions, in real-world tasks of predicting the correct apple disease.
Social and behavioral determinants of health in the era of artificial intelligence with electronic health records: A scoping review
Venue: arXiv cs.CY 2021
Year: 2021

Background: There is growing evidence that social and behavioral determinants of health (SBDH) play a substantial effect in a wide range of health outcomes. Electronic health records (EHRs) have been widely employed to conduct observational studies in the age of artificial intelligence (AI). However, there has been little research into how to make the most of SBDH information from EHRs. Methods: A systematic search was conducted in six databases to find relevant peer-reviewed publications that had recently been published. Relevance was determined by screening and evaluating the articles. Based on selected relevant studies, a methodological analysis of AI algorithms leveraging SBDH information in EHR data was provided. Results: Our synthesis was driven by an analysis of SBDH categories, the relationship between SBDH and healthcare-related statuses, and several NLP approaches for extracting SDOH from clinical literature. Discussion: The associations between SBDH and health outcomes are complicated and diverse; several pathways may be involved. Using Natural Language Processing (NLP) technology to support the extraction of SBDH and other clinical ideas simplifies the identification and extraction of essential concepts from clinical data, efficiently unlocks unstructured data, and aids in the resolution of unstructured data-related issues. Conclusion: Despite known associations between SBDH and disease, SBDH factors are rarely investigated as interventions to improve patient outcomes. Gaining knowledge about SBDH and how SBDH data can be collected from EHRs using NLP approaches and predictive models improves the chances of influencing health policy change for patient wellness, and ultimately promoting health and health equity. Keywords: Social and Behavioral Determinants of Health, Artificial Intelligence, Electronic Health Records, Natural Language Processing, Predictive Model
Fuzzy-AHP approach using Normalized Decision Matrix on Tourism Trend Ranking based-on Social Media
Venue: arXiv cs.SI 2021
Year: 2021

This research discusses multi-criteria decision making (MCDM) using Fuzzy-AHP methods of tourism. The fuzzy-AHP process will rank tourism trends based on data from social media. Social media is one of the channels with the largest source of data input in determining tourism development. The development uses social media interactions based on the facilities visited, including reviews, stories, likes, forums, blogs, and feedback. This experiment aims to prioritize facilities that are the trend of tourism. The priority ranking uses weight criteria and the ranking process. The highest rank is in the attractions of the Park/Picnic Area, with the final weight calculation value of 0.6361. Fuzzy-AHP can rank optimally with an MSE value of \approx 0.0002.
Concepts, Properties and an Approach for Compositional Generalization
Venue: arXiv cs.AI 2021
Year: 2021

Compositional generalization is the capacity to recognize and imagine a large amount of novel combinations from known components. It is a key in human intelligence, but current neural networks generally lack such ability. This report connects a series of our work for compositional generalization, and summarizes an approach. The first part contains concepts and properties. The second part looks into a machine learning approach. The approach uses architecture design and regularization to regulate information of representations. This report focuses on basic ideas with intuitive and illustrative explanations. We hope this work would be helpful to clarify fundamentals of compositional generalization and lead to advance artificial intelligence.
The Challenges of Assessing and Evaluating the Students at Distance
Venue: arXiv cs.CY 2021
Year: 2021

The COVID-19 pandemic has caused a strong effect on higher education institutions with the closure of classroom teaching activities. In this unprecedented crisis, of global proportion, educators and families had to deal with unpredictability and learn new ways of teaching. This short essay aims to explore the challenges posed to Portuguese higher education institutions and to analyze the challenges posed to evaluation models. To this end, the relevance of formative and summative assessment models in distance education is explored and the perception of teachers and students about the practices adopted in remote assessment is discussed. On the teachers' side, there is a high concern about adopting fraud-free models, and an excessive focus on the summative assessment component that in the distance learning model has less preponderance when compared to the gradual monitoring and assessment processes of the students, while on the students' side, problems arise regarding equipment to follow the teaching sessions and concerns about their privacy, particularly when intrusive IT solutions request the access to their cameras, audio, and desktop.
A strongly universal cellular automaton on the heptagrid with seven states
Venue: arXiv cs.DM 2021
Year: 2021

In this paper, we prove that there is a strongly universal cellular automaton on the heptagrid with seven states which is rotation invariant. This improves a previous paper of the author where the automaton required ten states.
The Singleton Fallacy: Why Current Critiques of Language Models Miss the Point
Venue: arXiv cs.CL 2021
Year: 2021

This paper discusses the current critique against neural network-based Natural Language Understanding (NLU) solutions known as language models. We argue that much of the current debate rests on an argumentation error that we will refer to as the singleton fallacy: the assumption that language, meaning, and understanding are single and uniform phenomena that are unobtainable by (current) language models. By contrast, we will argue that there are many different types of language use, meaning and understanding, and that (current) language models are build with the explicit purpose of acquiring and representing one type of structural understanding of language. We will argue that such structural understanding may cover several different modalities, and as such can handle several different types of meaning. Our position is that we currently see no theoretical reason why such structural knowledge would be insufficient to count as "real" understanding.
We might walk together, but I run faster: Network Fairness and Scalability in Blockchains
Venue: arXiv cs.DC 2021
Year: 2021

Blockchain-based Distributed Ledgers (DLs) promise to transform the existing financial system by making it truly democratic. In the past decade, blockchain technology has seen many novel applications ranging from the banking industry to real estate. However, in order to be adopted universally, blockchain systems must be scalable to support a high volume of transactions. As we increase the throughput of the DL system, the underlying peer-to-peer network might face multiple levels of challenges to keep up with the requirements. Due to varying network capacities, the slower nodes would be at a relative disadvantage compared to the faster ones, which could negatively impact their revenue. In order to quantify their relative advantage or disadvantage, we introduce two measures of network fairness, $p_f$, the probability of frontrunning and $α_f$, the publishing fairness. We show that as we scale the blockchain, both these measures deteriorate, implying that the slower nodes face a disadvantage at higher throughputs. It results in the faster nodes getting more than their fair share of the reward while the slower nodes (slow in terms of network quality) get less. Thus, fairness and scalability in blockchain systems do not go hand in hand. In a setting with rational miners, lack of fairness causes miners to deviate from the "longest chain rule" or undercut, which would reduce the blockchain's resilience against byzantine adversaries. Hence, fairness is not only a desirable property for a blockchain system but also essential for the security of the blockchain and any scalable blockchain protocol proposed must ensure fairness.
A full complexity dichotomy for immanant families
Venue: arXiv cs.CC 2021
Year: 2021

Given an integer $n\geq 1$ and an irreducible character $χ_λ$ of $S_{n}$ for some partition $λ$ of $n$, the immanant $\mathrm{imm}_λ:\mathbb{C}^{n\times n}\to\mathbb{C}$ maps matrices $A\in\mathbb{C}^{n\times n}$ to $\mathrm{imm}_λ(A)=\sum_{π\in S_{n}}χ_λ(π)\prod_{i=1}^{n}A_{i,π(i)}$. Important special cases include the determinant and permanent, which are the immanants associated with the sign and trivial character, respectively. It is known that immanants can be evaluated in polynomial time for characters that are close to the sign character: Given a partition $λ$ of $n$ with $s$ parts, let $b(λ):=n-s$ count the boxes to the right of the first column in the Young diagram of $λ$. For a family of partitions $Λ$, let $b(Λ):=\max_{λ\inΛ}b(λ)$ and write Imm$(Λ)$ for the problem of evaluating $\mathrm{imm}_λ(A)$ on input $A$ and $λ\inΛ$. If $b(Λ)<\infty$, then Imm$(Λ)$ is known to be polynomial-time computable. This subsumes the case of the determinant. On the other hand, if $b(Λ)=\infty$, then previously known hardness results suggest that Imm$(Λ)$ cannot be solved in polynomial time. However, these results only address certain restricted classes of families $Λ$. In this paper, we show that the parameterized complexity assumption FPT $\neq$ #W[1] rules out polynomial-time algorithms for Imm$(Λ)$ for any computationally reasonable family of partitions $Λ$ with $b(Λ)=\infty$. We give an analogous result in algebraic complexity under the assumption VFPT $\neq$ VW[1]. Furthermore, if $b(λ)$ even grows polynomially in $Λ$, we show that Imm$(Λ)$ is hard for #P and VNP. This concludes a series of partial results on the complexity of immanants obtained over the last 35 years.
Semi-Streaming Algorithms for Submodular Matroid Intersection
Venue: arXiv cs.DS 2021
Year: 2021

While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of $2$ for the \emph{unweighted} matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is based on the versatile local ratio technique and also applies to generalizations such as weighted hypergraph matchings. However, the framework for the analysis fails for the related problem of weighted matroid intersection and as a result the approximation guarantee for weighted instances did not match the factor $2$ achieved by the greedy algorithm for unweighted instances. Our main result closes this gap by developing a semi-streaming algorithm with an approximation guarantee of $2+ε$ for \emph{weighted} matroid intersection, improving upon the previous best guarantee of $4+ε$. Our techniques also allow us to generalize recent results by Levin and Wajc on submodular maximization subject to matching constraints to that of matroid-intersection constraints. While our algorithm is an adaptation of the local ratio technique used in previous works, the analysis deviates significantly and relies on structural properties of matroid intersection, called kernels. Finally, we also conjecture that our algorithm gives a $(k+ε)$ approximation for the intersection of $k$ matroids but prove that new tools are needed in the analysis as the used structural properties fail for $k\geq 3$.
Distributed Spectrum and Power Allocation for D2D-U Networks: A Scheme based on NN and Federated Learning
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, a Device-to-Device communication on unlicensed bands (D2D-U) enabled network is studied. To improve the spectrum efficiency (SE) on the unlicensed bands and fit its distributed structure while ensuring the fairness among D2D-U links and the harmonious coexistence with WiFi networks, a distributed joint power and spectrum scheme is proposed. In particular, a parameter, named as price, is defined, which is updated at each D2D-U pair by a online trained Neural network (NN) according to the channel state and traffic load. In addition, the parameters used in the NN are updated by two ways, unsupervised self-iteration and federated learning, to guarantee the fairness and harmonious coexistence. Then, a non-convex optimization problem with respect to the spectrum and power is formulated and solved on each D2D-U link to maximize its own data rate. Numerical simulation results are demonstrated to verify the effectiveness of the proposed scheme.
Mutual Information of Neural Network Initialisations: Mean Field Approximations
Venue: arXiv cs.IT 2021
Year: 2021

The ability to train randomly initialised deep neural networks is known to depend strongly on the variance of the weight matrices and biases as well as the choice of nonlinear activation. Here we complement the existing geometric analysis of this phenomenon with an information theoretic alternative. Lower bounds are derived for the mutual information between an input and hidden layer outputs. Using a mean field analysis we are able to provide analytic lower bounds as functions of network weight and bias variances as well as the choice of nonlinear activation. These results show that initialisations known to be optimal from a training point of view are also superior from a mutual information perspective.
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
Venue: arXiv cs.LG 2021
Year: 2021

We study the problem of agnostic learning under the Gaussian distribution. We develop a method for finding hard families of examples for a wide class of problems by using LP duality. For Boolean-valued concept classes, we show that the $L^1$-regression algorithm is essentially best possible, and therefore that the computational difficulty of agnostically learning a concept class is closely related to the polynomial degree required to approximate any function from the class in $L^1$-norm. Using this characterization along with additional analytic tools, we obtain optimal SQ lower bounds for agnostically learning linear threshold functions and the first non-trivial SQ lower bounds for polynomial threshold functions and intersections of halfspaces. We also develop an analogous theory for agnostically learning real-valued functions, and as an application prove near-optimal SQ lower bounds for agnostically learning ReLUs and sigmoids.
Community Detection: Exact Recovery in Weighted Graphs
Venue: arXiv cs.SI 2021
Year: 2021

In community detection, the exact recovery of communities (clusters) has been mainly investigated under the general stochastic block model with edges drawn from Bernoulli distributions. This paper considers the exact recovery of communities in a complete graph in which the graph edges are drawn from either a set of Gaussian distributions with community-dependent means and variances, or a set of exponential distributions with community-dependent means. For each case, we introduce a new semi-metric that describes sufficient and necessary conditions of exact recovery. The necessary and sufficient conditions are asymptotically tight. The analysis is also extended to incomplete, fully connected weighted graphs.