OpenRaiser/Intern-Atlas huggingface dataset:
Noisy Concurrent Training for Efficient Learning under Label Noise
Venue: arXiv cs.CV 2020
Year: 2020

Deep neural networks (DNNs) fail to learn effectively under label noise and have been shown to memorize random labels which affect their generalization performance. We consider learning in isolation, using one-hot encoded labels as the sole source of supervision, and a lack of regularization to discourage memorization as the major shortcomings of the standard training procedure. Thus, we propose Noisy Concurrent Training (NCT) which leverages collaborative learning to use the consensus between two models as an additional source of supervision. Furthermore, inspired by trial-to-trial variability in the brain, we propose a counter-intuitive regularization technique, target variability, which entails randomly changing the labels of a percentage of training samples in each batch as a deterrent to memorization and over-generalization in DNNs. Target variability is applied independently to each model to keep them diverged and avoid the confirmation bias. As DNNs tend to prioritize learning simple patterns first before memorizing the noisy labels, we employ a dynamic learning scheme whereby as the training progresses, the two models increasingly rely more on their consensus. NCT also progressively increases the target variability to avoid memorization in later stages. We demonstrate the effectiveness of our approach on both synthetic and real-world noisy benchmark datasets.
Sparsification Lower Bounds for List $H$-Coloring
Venue: arXiv cs.CC 2020
Year: 2020

We investigate the List $H$-Coloring problem, the generalization of graph coloring that asks whether an input graph $G$ admits a homomorphism to the undirected graph $H$ (possibly with loops), such that each vertex $v \in V(G)$ is mapped to a vertex on its list $L(v) \subseteq V(H)$. An important result by Feder, Hell, and Huang [JGT 2003] states that List $H$-Coloring is polynomial-time solvable if $H$ is a so-called bi-arc graph, and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an $n$-vertex instance be efficiently reduced to an equivalent instance of bitsize $O(n^{2-\varepsilon})$ for some $\varepsilon > 0$? We prove that if $H$ is not a bi-arc graph, then List $H$-Coloring does not admit such a sparsification algorithm unless $NP \subseteq coNP/poly$. Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs $H$ which are not bi-arc graphs.
Modeling human visual search: A combined Bayesian searcher and saliency map approach for eye movement guidance in natural scenes
Venue: arXiv cs.AI 2020
Year: 2020

Finding objects is essential for almost any daily-life visual task. Saliency models have been useful to predict fixation locations in natural images, but are static, i.e., they provide no information about the time-sequence of fixations. Nowadays, one of the biggest challenges in the field is to go beyond saliency maps to predict a sequence of fixations related to a visual task, such as searching for a given target. Bayesian observer models have been proposed for this task, as they represent visual search as an active sampling process. Nevertheless, they were mostly evaluated on artificial images, and how they adapt to natural images remains largely unexplored. Here, we propose a unified Bayesian model for visual search guided by saliency maps as prior information. We validated our model with a visual search experiment in natural scenes recording eye movements. We show that, although state-of-the-art saliency models perform well in predicting the first two fixations in a visual search task, their performance degrades to chance afterward. This suggests that saliency maps alone are good to model bottom-up first impressions, but are not enough to explain the scanpaths when top-down task information is critical. Thus, we propose to use them as priors of Bayesian searchers. This approach leads to a behavior very similar to humans for the whole scanpath, both in the percentage of target found as a function of the fixation rank and the scanpath similarity, reproducing the entire sequence of eye movements.
Evaluating Interactive Summarization: an Expansion-Based Framework
Venue: arXiv cs.CL 2020
Year: 2020

Allowing users to interact with multi-document summarizers is a promising direction towards improving and customizing summary results. Different ideas for interactive summarization have been proposed in previous work but these solutions are highly divergent and incomparable. In this paper, we develop an end-to-end evaluation framework for expansion-based interactive summarization, which considers the accumulating information along an interactive session. Our framework includes a procedure of collecting real user sessions and evaluation measures relying on standards, but adapted to reflect interaction. All of our solutions are intended to be released publicly as a benchmark, allowing comparison of future developments in interactive summarization. We demonstrate the use of our framework by evaluating and comparing baseline implementations that we developed for this purpose, which will serve as part of our benchmark. Our extensive experimentation and analysis of these systems motivate our design choices and support the viability of our framework.
Towards Stable Imbalanced Data Classification via Virtual Big Data Projection
Venue: arXiv cs.LG 2020
Year: 2020

Virtual Big Data (VBD) proved to be effective to alleviate mode collapse and vanishing generator gradient as two major problems of Generative Adversarial Neural Networks (GANs) very recently. In this paper, we investigate the capability of VBD to address two other major challenges in Machine Learning including deep autoencoder training and imbalanced data classification. First, we prove that, VBD can significantly decrease the validation loss of autoencoders via providing them a huge diversified training data which is the key to reach better generalization to minimize the over-fitting problem. Second, we use the VBD to propose the first projection-based method called cross-concatenation to balance the skewed class distributions without over-sampling. We prove that, cross-concatenation can solve uncertainty problem of data driven methods for imbalanced classification.
Detección de comunidades en redes: Algoritmos y aplicaciones
Venue: arXiv cs.SI 2020
Year: 2020

This master's thesis work has the objective of performing an analysis of the methods for detecting communities in networks. As an initial part, I study of the main features of graph theory and communities, as well as common measures in this problem. Subsequently, I was performed a review of the main methods of detecting communities, developing a classification, taking into account its characteristics and computational complexity for the detection of strengths and weaknesses in the methods, as well as later works. Then, study the problem of classification of a clustering method, this in order to evaluate the quality of the communities detected by analyzing different measures. Finally conclusions are elaborated and possible lines of work that can be derived.
Population Mapping in Informal Settlements with High-Resolution Satellite Imagery and Equitable Ground-Truth
Venue: arXiv cs.CY 2020
Year: 2020

We propose a generalizable framework for the population estimation of dense, informal settlements in low-income urban areas--so called 'slums'--using high-resolution satellite imagery. Precise population estimates are a crucial factor for efficient resource allocations by government authorities and NGO's, for instance in medical emergencies. We utilize equitable ground-truth data, which is gathered in collaboration with local communities: Through training and community mapping, the local population contributes their unique domain knowledge, while also maintaining agency over their data. This practice allows us to avoid carrying forward potential biases into the modeling pipeline, which might arise from a less rigorous ground-truthing approach. We contextualize our approach in respect to the ongoing discussion within the machine learning community, aiming to make real-world machine learning applications more inclusive, fair and accountable. Because of the resource intensive ground-truth generation process, our training data is limited. We propose a gridded population estimation model, enabling flexible and customizable spatial resolutions. We test our pipeline on three experimental site in Nigeria, utilizing pre-trained and fine-tune vision networks to overcome data sparsity. Our findings highlight the difficulties of transferring common benchmark models to real-world tasks. We discuss this and propose steps forward.
'Less Than One'-Shot Learning: Learning N Classes From M<N Samples
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks require large training sets but suffer from high computational cost and long training times. Training on much smaller training sets while maintaining nearly the same accuracy would be very beneficial. In the few-shot learning setting, a model must learn a new class given only a small number of samples from that class. One-shot learning is an extreme form of few-shot learning where the model must learn a new class from a single example. We propose the `less than one'-shot learning task where models must learn $N$ new classes given only $M<N$ examples and we show that this is achievable with the help of soft labels. We use a soft-label generalization of the k-Nearest Neighbors classifier to explore the intricate decision landscapes that can be created in the `less than one'-shot learning setting. We analyze these decision landscapes to derive theoretical lower bounds for separating $N$ classes using $M<N$ soft-label samples and investigate the robustness of the resulting systems.
Objective, Probabilistic, and Generalized Noise Level Dependent Classifications of sets of more or less 2D Periodic Images into Plane Symmetry Groups
Venue: arXiv cs.CV 2020
Year: 2020

Crystallographic symmetry classifications from real-world images with periodicities in two dimensions (2D) are of interest to crystallographers and practitioners of computer vision studies alike. Currently, these classifications are typically made by both communities in a subjective manner that relies on arbitrary thresholds for judgments, and are reported under the pretense of being definitive, which is impossible. Moreover, the computer vision community tends to use direct space methods to make such classifications instead of more powerful and computationally efficient Fourier space methods. This is because the proper functioning of those methods requires more periodic repeats of a unit cell motif than are commonly present in images analyzed by the computer vision community. We demonstrate a novel approach to plane symmetry group classifications that is enabled by Kenichi Kanatani's Geometric Akaike Information Criterion and associated Geometric Akaike weights. Our approach leverages the advantages of working in Fourier space, is well suited for handling the hierarchic nature of crystallographic symmetries, and yields probabilistic results that are generalized noise level dependent. The latter feature means crystallographic symmetry classifications can be updated when less noisy image data and more accurate processing algorithms become available. We demonstrate the ability of our approach to objectively estimate the plane symmetry and pseudosymmetries of sets of synthetic 2D-periodic images with varying amounts of red-green-blue and spread noise. Additionally, we suggest a simple solution to the problem of too few periodic repeats in an input image for practical application of Fourier space methods. In doing so, we effectively solve the decades-old and heretofore intractable problem from computer vision of symmetry detection and classification from images in the presence of noise.
Practical Dynamic SC-Flip Polar Decoders: Algorithm and Implementation
Venue: arXiv cs.IT 2020
Year: 2020

SC-Flip (SCF) is a low-complexity polar code decoding algorithm with improved performance, and is an alternative to high-complexity (CRC)-aided SC-List (CA-SCL) decoding. However, the performance improvement of SCF is limited since it can correct up to only one channel error ($ω=1$). Dynamic SCF (DSCF) algorithm tackles this problem by tackling multiple errors ($ω\geq 1$), but it requires logarithmic and exponential computations, which make it infeasible for practical applications. In this work, we propose simplifications and approximations to make DSCF practically feasible. First, we reduce the transcendental computations of DSCF decoding to a constant approximation. Then, we show how to incorporate special node decoding techniques into DSCF algorithm, creating the Fast-DSCF decoding. Next, we reduce the search span within the special nodes to further reduce the computational complexity. Following, we describe a hardware architecture for the Fast-DSCF decoder, in which we introduce additional simplifications such as metric normalization and sorter length reduction. All the simplifications and approximations are shown to have minimal impact on the error-correction performance, and the reported Fast-DSCF decoder is the only SCF-based architecture that can correct multiple errors. The Fast-DSCF decoders synthesized using TSMC $65$nm CMOS technology can achieve a $1.25$, $1.06$ and $0.93$ Gbps throughput for $ω\in \{1,2,3\}$, respectively. Compared to the state-of-the-art fast CA-SCL decoders with equivalent FER performance, the proposed decoders are up to $5.8\times$ more area-efficient. Finally, observations at energy dissipation indicate that the Fast-DSCF is more energy-efficient than its CA-SCL-based counterparts.
On Primes, Log-Loss Scores and (No) Privacy
Venue: arXiv cs.LG 2020
Year: 2020

Membership Inference Attacks exploit the vulnerabilities of exposing models trained on customer data to queries by an adversary. In a recently proposed implementation of an auditing tool for measuring privacy leakage from sensitive datasets, more refined aggregates like the Log-Loss scores are exposed for simulating inference attacks as well as to assess the total privacy leakage based on the adversary's predictions. In this paper, we prove that this additional information enables the adversary to infer the membership of any number of datapoints with full accuracy in a single query, causing complete membership privacy breach. Our approach obviates any attack model training or access to side knowledge with the adversary. Moreover, our algorithms are agnostic to the model under attack and hence, enable perfect membership inference even for models that do not memorize or overfit. In particular, our observations provide insight into the extent of information leakage from statistical aggregates and how they can be exploited.
Unsupervised Parallel Corpus Mining on Web Data
Venue: arXiv cs.CL 2020
Year: 2020

With a large amount of parallel data, neural machine translation systems are able to deliver human-level performance for sentence-level translation. However, it is costly to label a large amount of parallel data by humans. In contrast, there is a large-scale of parallel corpus created by humans on the Internet. The major difficulty to utilize them is how to filter them out from the noise website environments. Current parallel data mining methods all require labeled parallel data as the training source. In this paper, we present a pipeline to mine the parallel corpus from the Internet in an unsupervised manner. On the widely used WMT'14 English-French and WMT'16 English-German benchmarks, the machine translator trained with the data extracted by our pipeline achieves very close performance to the supervised results. On the WMT'16 English-Romanian and Romanian-English benchmarks, our system produces new state-of-the-art results, 39.81 and 38.95 BLEU scores, even compared with supervised approaches.
On the Boomerang Uniformity of Permutations of Low Carlitz Rank
Venue: arXiv cs.IT 2020
Year: 2020

Finding permutation polynomials with low differential and boomerang uniformityis an important topic in S-box designs of many block ciphers. For example, AES chooses the inverse function as its S-box, which is differentially 4-uniform and boomerang 6-uniform. Also there has been considerable research on many non-quadratic permutations which are obtained by modifying certain set of points from the inverse function. In this paper, we give a novel approach that shows that plenty of existing modifications of the inverse function are in fact affine equivalent to permutations of low Carlitz rank and those modifications cannot be APN (almost perfect nonlinear) unless the Carlitz rank is very large. Using nice properties of the permutations of Carlitz form, we present the complete list of permutations of Carlitz rank 3 having the boomerang uniformity six, and also give the complete classification of the differential uniformity of permutations of Carlitz rank 3. We also provide, up to affine equivalence, all the involutory permutations of Carlitz rank 3 having the boomerang uniformity six.
The Stability of Low-Density Parity-Check Codes and Some of Its Consequences
Venue: arXiv cs.IT 2020
Year: 2020

We study the stability of low-density parity-check (LDPC) codes under blockwise or bitwise maximum $\textit{a posteriori}$ (MAP) decoding, where transmission takes place over a binary-input memoryless output-symmetric channel. Our study stems from the consideration of constructing universal capacity-achieving codes under low-complexity decoding algorithms, where universality refers to the fact that we are considering a family of channels with equal capacity. Consider, e.g., the right-regular sequence by Shokrollahi and the heavy-tail Poisson sequence by Luby $\textit{et al}$. Both sequences are provably capacity-achieving under belief propagation (BP) decoding when transmission takes place over the binary erasure channel (BEC). In this paper we show that many existing capacity-achieving sequences of LDPC codes are not universal under BP decoding. We reveal that the key to showing this non-universality result is determined by the stability of the underlying codes. More concretely, for an ordered and complete channel family and a sequence of LDPC code ensembles, we determine a stability threshold associated with them, which further gives rise to a sufficient condition such that the sequence is not universal under BP decoding. Furthermore, we show that the same stability threshold applies to blockwise or bitwise MAP decoding as well. We present how stability can determine an upper bound on the corresponding blockwise or bitwise MAP threshold, revealing the operational significance of the stability threshold.
Low Density Parity Check Code (LDPC Codes) Overview
Venue: arXiv cs.IT 2020
Year: 2020

This paper basically expresses the core fundamentals and brief overview of the research of R. G. GALLAGER [1] on Low-Density Parity-Check (LDPC) codes and various parameters related to LDPC codes like, encoding and decoding of LDPC codes, code rate, parity check matrix, tanner graph. We also discuss advantages and applications as well as the usage of LDPC codes in 5G technology. We have simulated encoding and decoding of LDPC codes and have acquired results in terms of BER vs SNR graph in MATLAB software. This report was submitted as an assignment in Nirma University
EM-RBR: a reinforced framework for knowledge graph completion from reasoning perspective
Venue: arXiv cs.AI 2020
Year: 2020

Knowledge graph completion aims to predict the new links in given entities among the knowledge graph (KG). Most mainstream embedding methods focus on fact triplets contained in the given KG, however, ignoring the rich background information provided by logic rules driven from knowledge base implicitly. To solve this problem, in this paper, we propose a general framework, named EM-RBR(embedding and rule-based reasoning), capable of combining the advantages of reasoning based on rules and the state-of-the-art models of embedding. EM-RBR aims to utilize relational background knowledge contained in rules to conduct multi-relation reasoning link prediction rather than superficial vector triangle linkage in embedding models. By this way, we can explore relation between two entities in deeper context to achieve higher accuracy. In experiments, we demonstrate that EM-RBR achieves better performance compared with previous models on FB15k, WN18 and our new dataset FB15k-R, especially the new dataset where our model perform futher better than those state-of-the-arts. We make the implementation of EM-RBR available at https://github.com/1173710224/link-prediction-with-rule-based-reasoning.
DeepRemaster: Temporal Source-Reference Attention Networks for Comprehensive Video Enhancement
Venue: arXiv cs.CV 2020
Year: 2020

The remastering of vintage film comprises of a diversity of sub-tasks including super-resolution, noise removal, and contrast enhancement which aim to restore the deteriorated film medium to its original state. Additionally, due to the technical limitations of the time, most vintage film is either recorded in black and white, or has low quality colors, for which colorization becomes necessary. In this work, we propose a single framework to tackle the entire remastering task semi-interactively. Our work is based on temporal convolutional neural networks with attention mechanisms trained on videos with data-driven deterioration simulation. Our proposed source-reference attention allows the model to handle an arbitrary number of reference color images to colorize long videos without the need for segmentation while maintaining temporal consistency. Quantitative analysis shows that our framework outperforms existing approaches, and that, in contrast to existing approaches, the performance of our framework increases with longer videos and more reference color images.
Contextual Semantic Interpretability
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional neural networks (CNN) are known to learn an image representation that captures concepts relevant to the task, but do so in an implicit way that hampers model interpretability. However, one could argue that such a representation is hidden in the neurons and can be made explicit by teaching the model to recognize semantically interpretable attributes that are present in the scene. We call such an intermediate layer a \emph{semantic bottleneck}. Once the attributes are learned, they can be re-combined to reach the final decision and provide both an accurate prediction and an explicit reasoning behind the CNN decision. In this paper, we look into semantic bottlenecks that capture context: we want attributes to be in groups of a few meaningful elements and participate jointly to the final decision. We use a two-layer semantic bottleneck that gathers attributes into interpretable, sparse groups, allowing them contribute differently to the final output depending on the context. We test our contextual semantic interpretable bottleneck (CSIB) on the task of landscape scenicness estimation and train the semantic interpretable bottleneck using an auxiliary database (SUN Attributes). Our model yields in predictions as accurate as a non-interpretable baseline when applied to a real-world test set of Flickr images, all while providing clear and interpretable explanations for each prediction.