OpenRaiser/Intern-Atlas huggingface dataset:
Cost-Sensitive Deep Learning with Layer-Wise Cost Estimation
Venue: arXiv cs.CV 2020
Year: 2020

While deep neural networks have succeeded in several visual applications, such as object recognition, detection, and localization, by reaching very high classification accuracies, it is important to note that many real-world applications demand varying costs for different types of misclassification errors, thus requiring cost-sensitive classification algorithms. Current models of deep neural networks for cost-sensitive classification are restricted to some specific network structures and limited depth. In this paper, we propose a novel framework that can be applied to deep neural networks with any structure to facilitate their learning of meaningful representations for cost-sensitive classification problems. Furthermore, the framework allows end-to-end training of deeper networks directly. The framework is designed by augmenting auxiliary neurons to the output of each hidden layer for layer-wise cost estimation, and including the total estimation loss within the optimization objective. Experimental results on public benchmark visual data sets with two cost information settings demonstrate that the proposed framework outperforms state-of-the-art cost-sensitive deep learning models.
Fast Fourier Color Constancy
Venue: arXiv cs.CV 2020
Year: 2020

We present Fast Fourier Color Constancy (FFCC), a color constancy algorithm which solves illuminant estimation by reducing it to a spatial localization task on a torus. By operating in the frequency domain, FFCC produces lower error rates than the previous state-of-the-art by 13-20% while being 250-3000 times faster. This unconventional approach introduces challenges regarding aliasing, directional statistics, and preconditioning, which we address. By producing a complete posterior distribution over illuminants instead of a single illuminant estimate, FFCC enables better training techniques, an effective temporal smoothing technique, and richer methods for error analysis. Our implementation of FFCC runs at ~700 frames per second on a mobile device, allowing it to be used as an accurate, real-time, temporally-coherent automatic white balance algorithm.
Repairing Reed-Solomon Codes With Multiple Erasures
Venue: arXiv cs.IT 2020
Year: 2020

Despite their exceptional error-correcting properties, Reed-Solomon codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure repair method for Reed-Solomon codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.
Operationalizing Declarative and Procedural Knowledge: a Benchmark on Logic Programming Petri Nets (LPPNs)
Venue: arXiv cs.AI 2020
Year: 2020

Modelling, specifying and reasoning about complex systems requires to process in an integrated fashion declarative and procedural aspects of the target domain. The paper reports on an experiment conducted with a propositional version of Logic Programming Petri Nets (LPPNs), a notation extending Petri Nets with logic programming constructs. Two semantics are presented: a denotational semantics that fully maps the notation to ASP via Event Calculus; and a hybrid operational semantics that process separately the causal mechanisms via Petri nets, and the constraints associated to objects and to events via Answer Set Programming (ASP). These two alternative specifications enable an empirical evaluation in terms of computational efficiency. Experimental results show that the hybrid semantics is more efficient w.r.t. sequences, whereas the two semantics follows the same behaviour w.r.t. branchings (although the denotational one performs better in absolute terms).
Word equations in linear space
Venue: arXiv cs.FL 2020
Year: 2020

Satisfiability of word equations is an important problem in the intersection of formal languages and algebra: Given two sequences consisting of letters and variables we are to decide whether there is a substitution for the variables that turns this equation into true equality of strings. The exact computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (nondeterministic) O(n log n). In this paper we show that satisfiability of word equations is in nondeterministic linear space, thus the language of satisfiable word equations is context-sensitive, and by the famous Immerman-Szelepcsenyi theorem: the language of unsatisfiable word equations is also context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for nondeterministic choices of the algorithm, which uses several new ideas to limit the space occupied by the letters.
Autocorrelation and Lower Bound on the 2-Adic Complexity of LSB Sequence of $p$-ary $m$-Sequence
Venue: arXiv cs.IT 2020
Year: 2020

LSB (Least Significant Bit) sequences are widely used as the initial inputs in some modern stream ciphers, such as the ZUC algorithm-the core of the 3GPP LTE International Encryption Standard. Therefore, analyzing the statistical properties (for example, autocorrelation, linear complexity and 2-adic complexity) of these sequences becomes an important research topic. In this paper, we first reduce the autocorrelation distribution of the LSB sequence of a $p$-ary $m$-sequence with period $p^n-1$ for any order $n\geq2$ to the autocorrelation distribution of a corresponding Costas sequence with period $p-1$, and from the computing of which by computer, we obtain the explicit autocorrelation distribution of the LSB sequence for each prime $p<100$. In addition, we give a lower bound on the 2-adic complexity of each of these LSB sequences for all primes $p < 20$, which proves to be large enough to resist the analysis of RAA (Rational Approximation Algorithm) for FCSRs (Feedback with Carry Shift Registers). In particular, for a Mersenne prime $p=2^k-1$ (i.e., $k$ is a prime such that $p$ is also a prime), our results hold for all its bit-component sequences since they are shift equivalent to the LSB sequence.
Oblivious resampling oracles and parallel algorithms for the Lopsided Lovasz Local Lemma
Venue: arXiv cs.DS 2020
Year: 2020

The Lovász Local Lemma (LLL) is a probabilistic tool which shows that, if a collection of "bad" events $\mathcal B$ in a probability space are not too likely and not too interdependent, then there is a positive probability that no bad-events in $\mathcal B$ occur. Moser & Tardos (2010) gave sequential and parallel algorithms which transformed most applications of the variable-assignment LLL into efficient algorithms. A framework of Harvey & Vondrák (2015) based on "resampling oracles" extended this to general sequential algorithms for other probability spaces satisfying the Lopsided Lovász Local Lemma (LLLL). We describe a new structural property which holds for all known resampling oracles, which we call "obliviousness." Essentially, it means that the interaction between two bad-events $B, B'$ depends only on the randomness used to resample $B$, and not the precise state within $B$ itself. This property has two major consequences. First, combined with a framework of Kolmogorov (2016), it is the key to achieving a unified parallel LLLL algorithm, which is faster than previous, problem-specific algorithms of Harris (2016) for the variable-assignment LLLL algorithm and of Harris \& Srinivasan (2014) for permutations. This gives the first RNC algorithms for rainbow perfect matchings and rainbow hamiltonian cycles of $K_n$. Second, this property allows us to build LLLL probability spaces out of relatively simple "atomic" events. This provides the first sequential resampling oracle for rainbow perfect matchings on the complete $s$-uniform hypergraph $K_n^{(s)}$, and the first commutative resampling oracle for hamiltonian cycles of $K_n$.
Prediction defaults for networked-guarantee loans
Venue: arXiv cs.CE 2020
Year: 2020

Networked-guarantee loans may cause the systemic risk related concern of the government and banks in China. The prediction of default of enterprise loans is a typical extremely imbalanced prediction problem, and the networked-guarantee make this problem more difficult to solve. Since the guaranteed loan is a debt obligation promise, if one enterprise in the guarantee network falls into a financial crisis, the debt risk may spread like a virus across the guarantee network, even lead to a systemic financial crisis. In this paper, we propose an imbalanced network risk diffusion model to forecast the enterprise default risk in a short future. Positive weighted k-nearest neighbors (p-wkNN) algorithm is developed for the stand-alone case -- when there is no default contagious; then a data-driven default diffusion model is integrated to further improve the prediction accuracy. We perform the empirical study on a real-world three-years loan record from a major commercial bank. The results show that our proposed method outperforms conventional credit risk methods in terms of AUC. In summary, our quantitative risk evaluation model shows promising prediction performance on real-world data, which could be useful to both regulators and stakeholders.
McKernel: A Library for Approximate Kernel Expansions in Log-linear Time
Venue: arXiv cs.LG 2020
Year: 2020

McKernel introduces a framework to use kernel approximates in the mini-batch setting with Stochastic Gradient Descent (SGD) as an alternative to Deep Learning. Based on Random Kitchen Sinks [Rahimi and Recht 2007], we provide a C++ library for Large-scale Machine Learning. It contains a CPU optimized implementation of the algorithm in [Le et al. 2013], that allows the computation of approximated kernel expansions in log-linear time. The algorithm requires to compute the product of matrices Walsh Hadamard. A cache friendly Fast Walsh Hadamard that achieves compelling speed and outperforms current state-of-the-art methods has been developed. McKernel establishes the foundation of a new architecture of learning that allows to obtain large-scale non-linear classification combining lightning kernel expansions and a linear classifier. It travails in the mini-batch setting working analogously to Neural Networks. We show the validity of our method through extensive experiments on MNIST and FASHION MNIST [Xiao et al. 2017].
A Calculus for True Concurrency
Venue: arXiv cs.LO 2020
Year: 2020

We design a calculus for true concurrency called CTC, including its syntax and operational semantics. CTC has good properties modulo several kinds of strongly truly concurrent bisimulations and weakly truly concurrent bisimulations, such as monoid laws, static laws, new expansion law for strongly truly concurrent bisimulations, $τ$ laws for weakly truly concurrent bisimulations, and full congruences for strongly and weakly truly concurrent bisimulations, and also unique solution for recursion.
Greed Works -- Online Algorithms For Unrelated Machine Stochastic Scheduling
Venue: arXiv cs.DS 2020
Year: 2020

This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of magnitude as those of earlier work, and depend linearly on an upper bound on the squared coefficient of variation of the jobs' processing times. Specifically for deterministic processing times, without and with release times, the competitive ratios are 4 and 7.216, respectively. As to the technical contribution, the paper shows how dual fitting techniques can be used for stochastic and nonpreemptive scheduling problems.
Quantitative Reductions and Vertex-Ranked Infinite Games (Full Version)
Venue: arXiv cs.GT 2020
Year: 2020

We introduce quantitative reductions, a novel technique for structuring the space of quantitative games and solving them that does not rely on a reduction to qualitative games. We show that such reductions exhibit the same desirable properties as their qualitative counterparts and that they additionally retain the optimality of solutions. Moreover, we introduce vertex-ranked games as a general-purpose target for quantitative reductions and show how to solve them. In such games, the value of a play is determined only by a qualitative winning condition and a ranking of the vertices. We provide quantitative reductions of quantitative request-response games and of quantitative Muller games to vertex-ranked games, thus showing EXPTIME-completeness of solving the former two kinds of games. In addition, we exhibit the usefulness and flexibility of vertex-ranked games by showing how to use such games to compute fault-resilient strategies for safety specifications. This work lays the foundation for a general study of fault-resilient strategies for more complex winning conditions.
Finding the Size and the Diameter of a Radio Network Using Short Labels
Venue: arXiv cs.DC 2020
Year: 2020

The number of nodes of a network, called its size, and the largest distance between nodes of a network, called its diameter, are among the most important network parameters. Knowing the size and/or diameter is a prerequisite of many distributed network algorithms. A radio network is a collection of nodes, with wireless transmission and receiving capabilities. It is modeled as a simple undirected graph whose nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node $v$ hears a message from a neighbor $w$ in a round $i$, if $v$ listens in round $i$, and if $w$ is its only neighbor that transmits in round $i$. If $v$ listens in a round, and multiple neighbors of $v$ transmit in this round, a collision occurs at $v$. If $v$ transmits in a round, it does not hear anything. If listening nodes can distinguish collision from silence, we say that the network has collision detection capability, otherwise there is no collision detection. We consider the tasks of size discovery and diameter discovery: finding the size (resp. the diameter) of an unknown radio network with collision detection. All nodes have to output the size (resp. the diameter) of the network, using a deterministic algorithm. Nodes have labels which are binary strings. The length of a labeling scheme is the largest length of a label. We concentrate on the following problems: 1. What is the shortest labeling scheme that permits size discovery in all radio networks of maximum degree $Δ$? 2. What is the shortest labeling scheme that permits diameter discovery in all radio networks? We show that the minimum length of a labeling scheme that permits size discovery is $Θ(\log\log Δ)$. By contrast, we show that diameter discovery can be done using a labeling scheme of constant length.
Am I Done? Predicting Action Progress in Videos
Venue: arXiv cs.CV 2020
Year: 2020

In this paper we deal with the problem of predicting action progress in videos. We argue that this is an extremely important task since it can be valuable for a wide range of interaction applications. To this end we introduce a novel approach, named ProgressNet, capable of predicting when an action takes place in a video, where it is located within the frames, and how far it has progressed during its execution. To provide a general definition of action progress, we ground our work in the linguistics literature, borrowing terms and concepts to understand which actions can be the subject of progress estimation. As a result, we define a categorization of actions and their phases. Motivated by the recent success obtained from the interaction of Convolutional and Recurrent Neural Networks, our model is based on a combination of the Faster R-CNN framework, to make frame-wise predictions, and LSTM networks, to estimate action progress through time. After introducing two evaluation protocols for the task at hand, we demonstrate the capability of our model to effectively predict action progress on the UCF-101 and J-HMDB datasets.
Visual analytics for networked-guarantee loans risk management
Venue: arXiv cs.SI 2020
Year: 2020

Groups of enterprises guarantee each other and form complex guarantee networks when they try to obtain loans from banks. Such secured loan can enhance the solvency and promote the rapid growth in the economic upturn period. However, potential systemic risk may happen within the risk binding community. Especially, during the economic down period, the crisis may spread in the guarantee network like a domino. Monitoring the financial status, preventing or reducing systematic risk when crisis happens is highly concerned by the regulatory commission and banks. We propose visual analytics approach for loan guarantee network risk management, and consolidate the five analysis tasks with financial experts: i) visual analytics for enterprises default risk, whereby a hybrid representation is devised to predict the default risk and developed an interface to visualize key indicators; ii) visual analytics for high default groups, whereby a community detection based interactive approach is presented; iii) visual analytics for high defaults pattern, whereby a motif detection based interactive approach is described, and we adopt a Shneiderman Mantra strategy to reduce the computation complexity. iv) visual analytics for evolving guarantee network, whereby animation is used to help understanding the guarantee dynamic; v) visual analytics approach and interface for default diffusion path. The temporal diffusion path analysis can be useful for the government and bank to monitor the default spread status. It also provides insight for taking precautionary measures to prevent and dissolve systemic financial risk. We implement the system with case studies on a real-world guarantee network. Two financial experts are consulted with endorsement on the developed tool. To the best of our knowledge, this is the first visual analytics tool to explore the guarantee network risks in a systematic manner.
Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients
Venue: arXiv cs.LG 2020
Year: 2020

The ADAM optimizer is exceedingly popular in the deep learning community. Often it works very well, sometimes it doesn't. Why? We interpret ADAM as a combination of two aspects: for each weight, the update direction is determined by the sign of stochastic gradients, whereas the update magnitude is determined by an estimate of their relative variance. We disentangle these two aspects and analyze them in isolation, gaining insight into the mechanisms underlying ADAM. This analysis also extends recent results on adverse effects of ADAM on generalization, isolating the sign aspect as the problematic one. Transferring the variance adaptation to SGD gives rise to a novel method, completing the practitioner's toolbox for problems where ADAM fails.
A Survey on QoE-oriented Wireless Resources Scheduling
Venue: arXiv cs.NI 2020
Year: 2020

Future wireless systems are expected to provide a wide range of services to more and more users. Advanced scheduling strategies thus arise not only to perform efficient radio resource management, but also to provide fairness among the users. On the other hand, the users' perceived quality, i.e., Quality of Experience (QoE), is becoming one of the main drivers within the schedulers design. In this context, this paper starts by providing a comprehension of what is QoE and an overview of the evolution of wireless scheduling techniques. Afterwards, a survey on the most recent QoE-based scheduling strategies for wireless systems is presented, highlighting the application/service of the different approaches reported in the literature, as well as the parameters that were taken into account for QoE optimization. Therefore, this paper aims at helping readers interested in learning the basic concepts of QoE-oriented wireless resources scheduling, as well as getting in touch with its current research frontier.
RSI-CB: A Large Scale Remote Sensing Image Classification Benchmark via Crowdsource Data
Venue: arXiv cs.CV 2020
Year: 2020

In recent years, deep convolutional neural network (DCNN) has seen a breakthrough progress in natural image recognition because of three points: universal approximation ability via DCNN, large-scale database (such as ImageNet), and supercomputing ability powered by GPU. The remote sensing field is still lacking a large-scale benchmark compared to ImageNet and Place2. In this paper, we propose a remote sensing image classification benchmark (RSI-CB) based on massive, scalable, and diverse crowdsource data. Using crowdsource data, such as Open Street Map (OSM) data, ground objects in remote sensing images can be annotated effectively by points of interest, vector data from OSM, or other crowdsource data. The annotated images can be used in remote sensing image classification tasks. Based on this method, we construct a worldwide large-scale benchmark for remote sensing image classification. This benchmark has two sub-datasets with 256 by 256 and 128 by 128 sizes because different DCNNs require different image sizes. The former contains 6 categories with 35 subclasses of more than 24,000 images. The latter contains 6 categories with 45 subclasses of more than 36,000 images. This classification system of ground objects is defined according to the national standard of land-use classification in China and is inspired by the hierarchy mechanism of ImageNet. Finally, we conduct many experiments to compare RSI-CB with the SAT-4, SAT-6, and UC-Merced datasets on handcrafted features, such as scale-invariant feature transform, color histogram, local binary patterns, and GIST, and classical DCNN models, such as AlexNet, VGGNet, GoogLeNet, and ResNet.
Integer Echo State Networks: Efficient Reservoir Computing for Digital Hardware
Venue: arXiv cs.NE 2020
Year: 2020

We propose an approximation of Echo State Networks (ESN) that can be efficiently implemented on digital hardware based on the mathematics of hyperdimensional computing. The reservoir of the proposed integer Echo State Network (intESN) is a vector containing only n-bits integers (where n<8 is normally sufficient for a satisfactory performance). The recurrent matrix multiplication is replaced with an efficient cyclic shift operation. The proposed intESN approach is verified with typical tasks in reservoir computing: memorizing of a sequence of inputs; classifying time-series; learning dynamic processes. Such architecture results in dramatic improvements in memory footprint and computational efficiency, with minimal performance loss. The experiments on a field-programmable gate array confirm that the proposed intESN approach is much more energy efficient than the conventional ESN.