OpenRaiser/Intern-Atlas huggingface dataset:
No-Rainbow Problem and the Surjective Constraint Satisfaction Problem
Venue: arXiv cs.CC 2021
Year: 2021

The Surjective Constraint Satisfaction Problem (SCSP) is the problem of deciding whether there exists a surjective assignment to a set of variables subject to some specified constraints, where a surjective assignment is an assignment containing all elements of the domain. In this paper we show that the most famous SCSP, called No-Rainbow Problem, is NP-Hard. Additionally, we disprove the conjecture saying that the SCSP over a constraint language $Γ$ and the CSP over the same language with constants have the same computational complexity up to poly-time reductions. Our counter-example also shows that the complexity of the SCSP cannot be described in terms of polymorphisms of the constraint language.
A Topological Characterization of Modulo-$p$ Arguments and Implications for Necklace Splitting
Venue: arXiv cs.CC 2021
Year: 2021

The classes PPA-$p$ have attracted attention lately, because they are the main candidates for capturing the complexity of Necklace Splitting with $p$ thieves, for prime $p$. However, these classes were not known to have complete problems of a topological nature, which impedes any progress towards settling the complexity of the Necklace Splitting problem. On the contrary, topological problems have been pivotal in obtaining completeness results for PPAD and PPA, such as the PPAD-completeness of finding a Nash equilibrium [Daskalakis et al., 2009, Chen et al., 2009b] and the PPA-completeness of Necklace Splitting with 2 thieves [Filos-Ratsikas and Goldberg, 2019]. In this paper, we provide the first topological characterization of the classes PPA-$p$. First, we show that the computational problem associated with a simple generalization of Tucker's Lemma, termed $p$-polygon-Tucker, as well as the associated Borsuk-Ulam-type theorem, $p$-polygon-Borsuk-Ulam, are PPA-$p$-complete. Then, we show that the computational version of the well-known BSS Theorem [Barany et al., 1981], as well as the associated BSS-Tucker problem are PPA-$p$-complete. Finally, using a different generalization of Tucker's Lemma (termed $\mathbb{Z}_p$-star-Tucker), which we prove to be PPA-$p$-complete, we prove that $p$-thief Necklace Splitting is in PPA-$p$. This latter result gives a new combinatorial proof for the Necklace Splitting theorem, the only proof of this nature other than that of Meunier [2014]. All of our containment results are obtained through a new combinatorial proof for $\mathbb{Z}_p$-versions of Tucker's lemma that is a natural generalization of the standard combinatorial proof of Tucker's lemma by Freund and Todd [1981]. We believe that this new proof technique is of independent interest.
On Infinite-Width Hypernetworks
Venue: arXiv cs.LG 2021
Year: 2021

{\em Hypernetworks} are architectures that produce the weights of a task-specific {\em primary network}. A notable application of hypernetworks in the recent literature involves learning to output functional representations. In these scenarios, the hypernetwork learns a representation corresponding to the weights of a shallow MLP, which typically encodes shape or image information. While such representations have seen considerable success in practice, they remain lacking in the theoretical guarantees in the wide regime of the standard architectures. In this work, we study wide over-parameterized hypernetworks. We show that unlike typical architectures, infinitely wide hypernetworks do not guarantee convergence to a global minima under gradient descent. We further show that convexity can be achieved by increasing the dimensionality of the hypernetwork's output, to represent wide MLPs. In the dually infinite-width regime, we identify the functional priors of these architectures by deriving their corresponding GP and NTK kernels, the latter of which we refer to as the {\em hyperkernel}. As part of this study, we make a mathematical contribution by deriving tight bounds on high order Taylor expansion terms of standard fully connected ReLU networks.
Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons
Venue: arXiv cs.CG 2021
Year: 2021

We address the following problem: Given a simple polygon $P$ with $n$ vertices and two points $s$ and $t$ inside it, find a minimum link path between them such that a given target point $q$ is visible from at least one point on the path. The method is based on partitioning a portion of $P$ into a number of faces of equal link distance from a source point. This partitioning is essentially a shortest path map (SPM). In this paper, we present an optimal algorithm with $O(n)$ time bound, which is the same as the time complexity of the standard minimum link paths problem.
Intermittent Inverse-Square Lévy Walks are Optimal for Finding Targets of All Sizes
Venue: arXiv cs.DS 2021
Year: 2021

Lévy walks are random walk processes whose step-lengths follow a long-tailed power-law distribution. Due to their abundance as movement patterns of biological organisms, significant theoretical efforts have been devoted to identifying the foraging circumstances that would make such patterns advantageous. However, despite extensive research, there is currently no mathematical proof indicating that Lévy walks are, in any manner, preferable strategies in higher dimensions than one. Here we prove that in finite two-dimensional terrains, the inverse-square Lévy walk strategy is extremely efficient at finding sparse targets of arbitrary size and shape. Moreover, this holds even under the weak model of intermittent detection. Conversely, any other intermittent Lévy walk fails to efficiently find either large targets or small ones. Our results shed new light on the \emph{Lévy foraging hypothesis}, and are thus expected to impact future experiments on animals performing Lévy walks.
Co-occurrence of deep convolutional features for image search
Venue: arXiv cs.CV 2021
Year: 2021

Image search can be tackled using deep features from pre-trained Convolutional Neural Networks (CNN). The feature map from the last convolutional layer of a CNN encodes descriptive information from which a discriminative global descriptor can be obtained. We propose a new representation of co-occurrences from deep convolutional features to extract additional relevant information from this last convolutional layer. Combining this co-occurrence map with the feature map, we achieve an improved image representation. We present two different methods to get the co-occurrence representation, the first one based on direct aggregation of activations, and the second one, based on a trainable co-occurrence representation. The image descriptors derived from our methodology improve the performance in very well-known image retrieval datasets as we prove in the experiments.
Differentially Private Naive Bayes Classifier using Smooth Sensitivity
Venue: arXiv cs.CR 2021
Year: 2021

With the increasing collection of users' data, protecting individual privacy has gained more interest. Differential Privacy is a strong concept of protecting individuals. Naive Bayes is one of the popular machine learning algorithm, used as a baseline for many tasks. In this work, we have provided a differentially private Naive Bayes classifier that adds noise proportional to the Smooth Sensitivity of its parameters. We have compared our result to Vaidya, Shafiq, Basu, and Hong in which they have scaled the noise to the global sensitivity of the parameters. Our experiment results on the real-world datasets show that the accuracy of our method has improved significantly while still preserving $\varepsilon$-differential privacy.
Understanding Cross-Lingual Syntactic Transfer in Multilingual Recurrent Neural Networks
Venue: arXiv cs.CL 2021
Year: 2021

It is now established that modern neural language models can be successfully trained on multiple languages simultaneously without changes to the underlying architecture. But what kind of knowledge is really shared among languages within these models? Does multilingual training mostly lead to an alignment of the lexical representation spaces or does it also enable the sharing of purely grammatical knowledge? In this paper we dissect different forms of cross-lingual transfer and look for its most determining factors, using a variety of models and probing tasks. We find that exposing our LMs to a related language does not always increase grammatical knowledge in the target language, and that optimal conditions for lexical-semantic transfer may not be optimal for syntactic transfer.
Unification-based Reconstruction of Multi-hop Explanations for Science Questions
Venue: arXiv cs.AI 2021
Year: 2021

This paper presents a novel framework for reconstructing multi-hop explanations in science Question Answering (QA). While existing approaches for multi-hop reasoning build explanations considering each question in isolation, we propose a method to leverage explanatory patterns emerging in a corpus of scientific explanations. Specifically, the framework ranks a set of atomic facts by integrating lexical relevance with the notion of unification power, estimated analysing explanations for similar questions in the corpus. An extensive evaluation is performed on the Worldtree corpus, integrating k-NN clustering and Information Retrieval (IR) techniques. We present the following conclusions: (1) The proposed method achieves results competitive with Transformers, yet being orders of magnitude faster, a feature that makes it scalable to large explanatory corpora (2) The unification-based mechanism has a key role in reducing semantic drift, contributing to the reconstruction of many hops explanations (6 or more facts) and the ranking of complex inference facts (+12.0 Mean Average Precision) (3) Crucially, the constructed explanations can support downstream QA models, improving the accuracy of BERT by up to 10% overall.
Crowdsourced Labeling for Worker-Task Specialization Model
Venue: arXiv cs.HC 2021
Year: 2021

We consider crowdsourced labeling under a $d$-type worker-task specialization model, where each worker and task is associated with one particular type among a finite set of types and a worker provides a more reliable answer to tasks of the matched type than to tasks of unmatched types. We design an inference algorithm that recovers binary task labels (up to any given recovery accuracy) by using worker clustering, worker skill estimation and weighted majority voting. The designed inference algorithm does not require any information about worker/task types, and achieves any targeted recovery accuracy with the best known performance (minimum number of queries per task).
A polynomial time algorithm to compute the connected tree-width of a series-parallel graph
Venue: arXiv cs.DS 2021
Year: 2021

It is well known that the treewidth of a graph $G$ corresponds to the node search number where a team of cops is pursuing a robber that is lazy, visible and has the ability to move at infinite speed via unguarded path. In recent papers, connected node search strategies have been considered. A search stratregy is connected if at each step the set of vertices that is or has been occupied by the team of cops, induced a connected subgraph of $G$. It has been shown that the connected search number of a graph $G$ can be expressed as the connected treewidth, denoted $\mathbf{ctw}(G),$ that is defined as the minimum width of a rooted tree-decomposition $({{\cal X},T,r})$ such that the union of the bags corresponding to the nodes of a path of $T$ containing the root $r$ is connected. Clearly we have that $\mathbf{tw}(G)\leqslant \mathbf{ctw}(G)$. It is paper, we initiate the algorithmic study of connected treewidth. We design a $O(n^2\cdot\log n)$-time dynamic programming algorithm to compute the connected treewidth of a biconnected series-parallel graphs. At the price of an extra $n$ factor in the running time, our algorithm genralizes to graphs of treewidth at most $2$.
Fundamental Limits of Distributed Encoding
Venue: arXiv cs.IT 2021
Year: 2021

In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprising of $K\in\mathbb{N}$ isolated source nodes and $N\in\mathbb{N}$ encoding nodes. Each source node has one symbol from a finite field and sends it to all encoding nodes. Each encoding node stores an encoded symbol, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of adversarial nodes, denoted by $β\in\mathbb{N}$, and the number of symbols that each one generates, denoted by $v\in\mathbb{N}$, the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of $t \in\mathbb{N}$ encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. In this paper, we study $t^*\in\mathbb{N}$, the minimum of $t$, which is a function of $K$, $N$, $β$, and $v$. We show that when the encoding nodes use linear coding, $t^*_{\textrm{linear}}=K+2β(v-1)$, if $N\ge K+2β(v-1)$, and $t^*_{\textrm{linear}}=N$, if $N\le K+2β(v-1)$. In order to achieve $t^*_{\textrm{linear}}$, we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. For the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node.
Occlusion-Aware Depth Estimation with Adaptive Normal Constraints
Venue: arXiv cs.CV 2021
Year: 2021

We present a new learning-based method for multi-frame depth estimation from a color video, which is a fundamental problem in scene understanding, robot navigation or handheld 3D reconstruction. While recent learning-based methods estimate depth at high accuracy, 3D point clouds exported from their depth maps often fail to preserve important geometric feature (e.g., corners, edges, planes) of man-made scenes. Widely-used pixel-wise depth errors do not specifically penalize inconsistency on these features. These inaccuracies are particularly severe when subsequent depth reconstructions are accumulated in an attempt to scan a full environment with man-made objects with this kind of features. Our depth estimation algorithm therefore introduces a Combined Normal Map (CNM) constraint, which is designed to better preserve high-curvature features and global planar regions. In order to further improve the depth estimation accuracy, we introduce a new occlusion-aware strategy that aggregates initial depth predictions from multiple adjacent views into one final depth map and one occlusion probability map for the current reference view. Our method outperforms the state-of-the-art in terms of depth estimation accuracy, and preserves essential geometric features of man-made indoor scenes much better than other algorithms.
Effect of Annotation Errors on Drone Detection with YOLOv3
Venue: arXiv cs.CV 2021
Year: 2021

Following the recent advances in deep networks, object detection and tracking algorithms with deep learning backbones have been improved significantly; however, this rapid development resulted in the necessity of large amounts of annotated labels. Even if the details of such semi-automatic annotation processes for most of these datasets are not known precisely, especially for the video annotations, some automated labeling processes are usually employed. Unfortunately, such approaches might result with erroneous annotations. In this work, different types of annotation errors for object detection problem are simulated and the performance of a popular state-of-the-art object detector, YOLOv3, with erroneous annotations during training and testing stages is examined. Moreover, some inevitable annotation errors in CVPR-2020 Anti-UAV Challenge dataset is also examined in this manner, while proposing a solution to correct such annotation errors of this valuable data set.
Classical and quantum regression analysis for the optoelectronic performance of NTCDA/p-Si UV photodiode
Venue: arXiv cs.LG 2021
Year: 2021

Due to the pivotal role of UV photodiodes in many technological applications in tandem with the high efficiency achieved by machine learning techniques in regression and classification problems, different artificial intelligence techniques are adopted model the performance of organic/inorganic heterojunction UV photodiode. Herein, the performance of a fabricated Au/NTCDA/p-Si/Al photodiode was explained in details and showed an excellent responsivity, and detectivity for UV light of intensities ranges from 20 to 80 ${mW/cm^2}$. The fabricated photodiodes exhibited a linear current-irradiance relationship under illumination up to 65 ${mW/cm^2}$. It also exhibits good response times of ${t_{rise} = 408}$ ms and ${t_{fall} = 490}$ ms. Furthermore, we have not only fitted the characteristic I-V curve but also evaluated three classical algorithms; k-nearest neighbour, artificial neural network, and genetic programming besides using a quantum neural network to predict the behaviour of the fabricated device. The models have achieved outstanding results and managed to capture the trend of the target values. The Quantum Neural Network has been used for the first time to model the photodiode. The models can be used instead of repeating the fabrication process. This means a reduction in cost and manufacturing time.
Effective Fusion of Deep Multitasking Representations for Robust Visual Tracking
Venue: arXiv cs.CV 2021
Year: 2021

Visual object tracking remains an active research field in computer vision due to persisting challenges with various problem-specific factors in real-world scenes. Many existing tracking methods based on discriminative correlation filters (DCFs) employ feature extraction networks (FENs) to model the target appearance during the learning process. However, using deep feature maps extracted from FENs based on different residual neural networks (ResNets) has not previously been investigated. This paper aims to evaluate the performance of twelve state-of-the-art ResNet-based FENs in a DCF-based framework to determine the best for visual tracking purposes. First, it ranks their best feature maps and explores the generalized adoption of the best ResNet-based FEN into another DCF-based method. Then, the proposed method extracts deep semantic information from a fully convolutional FEN and fuses it with the best ResNet-based feature maps to strengthen the target representation in the learning process of continuous convolution filters. Finally, it introduces a new and efficient semantic weighting method (using semantic segmentation feature maps on each video frame) to reduce the drift problem. Extensive experimental results on the well-known OTB-2013, OTB-2015, TC-128 and VOT-2018 visual tracking datasets demonstrate that the proposed method effectively outperforms state-of-the-art methods in terms of precision and robustness of visual tracking.
R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space
Venue: arXiv cs.DS 2021
Year: 2021

Enumerating characteristic substrings (e.g., maximal repeats, minimal unique substrings, and minimal absent words) in a given string has been an important research topic because there are a wide variety of applications in various areas such as string processing and computational biology. Although several enumeration algorithms for characteristic substrings have been proposed, they are not space-efficient in that their space-usage is proportional to the length of an input string. Recently, the run-length encoded Burrows-Wheeler transform (RLBWT) has attracted increased attention in string processing, and various algorithms for the RLBWT have been developed. Developing enumeration algorithms for characteristic substrings with the RLBWT, however, remains a challenge. In this paper, we present r-enum (RLBWT-based enumeration), the first enumeration algorithm for characteristic substrings based on RLBWT. R-enum runs in $O(n \log \log (n/r))$ time and with $O(r \log n)$ bits of working space for string length $n$ and number $r$ of runs in RLBWT, where $r$ is expected to be significantly smaller than $n$ for highly repetitive strings (i.e., strings with many repetitions). Experiments using a benchmark dataset of highly repetitive strings show that the results of r-enum are more space-efficient than the previous results. In addition, we demonstrate the applicability of r-enum to a huge string by performing experiments on a 300-gigabyte string of 100 human genomes.
A Simple Model for Subject Behavior in Subjective Experiments
Venue: arXiv cs.MM 2021
Year: 2021

In a subjective experiment to evaluate the perceptual audiovisual quality of multimedia and television services, raw opinion scores collected from test subjects are often noisy and unreliable. To produce the final mean opinion scores (MOS), recommendations such as ITU-R BT.500, ITU-T P.910 and ITU-T P.913 standardize post-test screening procedures to clean up the raw opinion scores, using techniques such as subject outlier rejection and bias removal. In this paper, we analyze the prior standardized techniques to demonstrate their weaknesses. As an alternative, we propose a simple model to account for two of the most dominant behaviors of subject inaccuracy: bias and inconsistency. We further show that this model can also effectively deal with inattentive subjects that give random scores. We propose to use maximum likelihood estimation to jointly solve the model parameters, and present two numeric solvers: the first based on the Newton-Raphson method, and the second based on an alternating projection (AP). We show that the AP solver generalizes the ITU-T P.913 post-test screening procedure by weighing a subject's contribution to the true quality score by her consistency (thus, the quality scores estimated can be interpreted as bias-subtracted consistency-weighted MOS). We compare the proposed methods with the standardized techniques using real datasets and synthetic simulations, and demonstrate that the proposed methods are the most valuable when the test conditions are challenging (for example, crowdsourcing and cross-lab studies), offering advantages such as better model-data fit, tighter confidence intervals, better robustness against subject outliers, the absence of hard coded parameters and thresholds, and auxiliary information on test subjects. The code for this work is open-sourced at https://github.com/Netflix/sureal.
Arabic Offensive Language on Twitter: Analysis and Experiments
Venue: arXiv cs.CL 2021
Year: 2021

Detecting offensive language on Twitter has many applications ranging from detecting/predicting bullying to measuring polarization. In this paper, we focus on building a large Arabic offensive tweet dataset. We introduce a method for building a dataset that is not biased by topic, dialect, or target. We produce the largest Arabic dataset to date with special tags for vulgarity and hate speech. We thoroughly analyze the dataset to determine which topics, dialects, and gender are most associated with offensive tweets and how Arabic speakers use offensive language. Lastly, we conduct many experiments to produce strong results (F1 = 83.2) on the dataset using SOTA techniques.