OpenRaiser/Intern-Atlas huggingface dataset:
Codes with hierarchical locality from covering maps of curves
Venue: arXiv cs.IT 2019
Year: 2019

Locally recoverable (LRC) codes provide ways of recovering erased coordinates of the codeword without having to access each of the remaining coordinates. A subfamily of LRC codes with hierarchical locality (H-LRC codes) provides added flexibility to the construction by introducing several tiers of recoverability for correcting different numbers of erasures. We present a general construction of codes with 2-level hierarchical locality from maps between algebraic curves and specialize it to several code families obtained from quotients of curves by a subgroup of the automorphism group, including rational, elliptic, Kummer, and Artin-Schreier curves. We further address the question of H-LRC codes with availability, and suggest a general construction of such codes from fiber products of curves. Detailed calculations of parameters for H-LRC codes with availability are performed for Reed-Solomon- and Hermitian-like code families. Finally, we construct asymptotically good families of H-LRC codes from curves related to the Garcia-Stichtenoth tower.
The Mathematics of Changing one's Mind, via Jeffrey's or via Pearl's update rule
Venue: arXiv cs.AI 2019
Year: 2019

Evidence in probabilistic reasoning may be 'hard' or 'soft', that is, it may be of yes/no form, or it may involve a strength of belief, in the unit interval [0, 1]. Reasoning with soft, [0, 1]-valued evidence is important in many situations but may lead to different, confusing interpretations. This paper intends to bring more mathematical and conceptual clarity to the field by shifting the existing focus from specification of soft evidence to accomodation of soft evidence. There are two main approaches, known as Jeffrey's rule and Pearl's method; they give different outcomes on soft evidence. This paper argues that they can be understood as correction and as improvement. It describes these two approaches as different ways of updating with soft evidence, highlighting their differences, similarities and applications. This account is based on a novel channel-based approach to Bayesian probability. Proper understanding of these two update mechanisms is highly relevant for inference, decision tools and probabilistic programming languages.
Faster Algorithms for All-Pairs Bounded Min-Cuts
Venue: arXiv cs.DS 2019
Year: 2019

The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum $s$-$t$ cut (or just its value) for all pairs of vertices $s,t$. We study this problem in directed graphs with unit edge/vertex capacities (corresponding to edge/vertex connectivity). Our focus is on the $k$-bounded case, where the algorithm has to find all pairs with min-cut value less than $k$, and report only those. The most basic case $k=1$ is the Transitive Closure (TC) problem, which can be solved in graphs with $n$ vertices and $m$ edges in time $O(mn)$ combinatorially, and in time $O(n^ω)$ where $ω<2.38$ is the matrix-multiplication exponent. These time bounds are conjectured to be optimal. We present new algorithms and conditional lower bounds that advance the frontier for larger $k$, as follows: (i) A randomized algorithm for vertex capacities that runs in time $O((nk)^ω)$. (ii) Two deterministic algorithms for edge capacities (which is more general) that work in DAGs and further reports a minimum cut for each pair. The first algorithm is combinatorial (does not involve matrix multiplication) and runs in time $O(2^{O(k^2)}\cdot mn)$. The second algorithm can be faster on dense DAGs and runs in time $O((k\log n)^{4^k+o(k)} n^ω)$. (iii) The first super-cubic lower bound of $n^{ω-1-o(1)} k^2$ time under the $4$-Clique conjecture, which holds even in the simplest case of DAGs with unit vertex capacities. It improves on the previous (SETH-based) lower bounds even in the unbounded setting $k=n$. For combinatorial algorithms, our reduction implies an $n^{2-o(1)} k^2$ conditional lower bound. Thus, we identify new settings where the complexity of the problem is (conditionally) higher than that of TC.
oo7: Low-overhead Defense against Spectre Attacks via Program Analysis
Venue: arXiv cs.CR 2019
Year: 2019

The Spectre vulnerability in modern processors has been widely reported. The key insight in this vulnerability is that speculative execution in processors can be misused to access the secrets. Subsequently, even though the speculatively executed instructions are squashed, the secret may linger in micro-architectural states such as cache, and can potentially be accessed by an attacker via side channels. In this paper, we propose oo7, a static analysis approach that can mitigate Spectre attacks by detecting potentially vulnerable code snippets in program binaries and protecting them against the attack by patching them. Our key contribution is to balance the concerns of effectiveness, analysis time and run-time overheads. We employ control flow extraction, taint analysis, and address analysis to detect tainted conditional branches and speculative memory accesses. oo7 can detect all fifteen purpose-built Spectre-vulnerable code patterns, whereas Microsoft compiler with Spectre mitigation option can only detect two of them. We also report the results of a large-scale study on applying oo7 to over 500 program binaries (average binary size 261 KB) from different real-world projects. We protect programs against Spectre attack by selectively inserting fences only at vulnerable conditional branches to prevent speculative execution. Our approach is experimentally observed to incur around 5.9% performance overheads on SPECint benchmarks.
Learning Convex Partitions and Computing Game-theoretic Equilibria from Best Response Queries
Venue: arXiv cs.GT 2019
Year: 2019

Suppose that an $m$-simplex is partitioned into $n$ convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that occurs within some distance $ε$ from that point. We present two algorithms for this task: Constant-Dimension Generalised Binary Search (CD-GBS), which for constant $m$ uses $poly(n, \log \left( \frac{1}ε \right))$ queries, and Constant-Region Generalised Binary Search (CR-GBS), which uses CD-GBS as a subroutine and for constant $n$ uses $poly(m, \log \left( \frac{1}ε \right))$ queries. We show via Kakutani's fixed-point theorem that these algorithms provide bounds on the best-response query complexity of computing approximate well-supported equilibria of bimatrix games in which one of the players has a constant number of pure strategies. We also partially extend our results to games with multiple players, establishing further query complexity bounds for computing approximate well-supported equilibria in this setting.
Agent-based opinion formation modeling in social network: a perspective of social psychology
Venue: arXiv cs.SI 2019
Year: 2019

Most previous works on opinion modeling lack the simultaneous study of individual mental activity and group behavior. This paper is motivated to propose an agent-based online opinion formation model based on attitude change theory, group behavior theory and evolutionary game theory in the perspective of sociology and psychology. In this model, there are three factors influencing the persuasion process, including credibility of the leaders, characteristic of the recipient, and group environment. The proposed model is applied to Twitter to analyze the influence of topic type, parameter changing, and opinion leaders on opinion formation. Experimental results show that the opinion evolution of controversial topic shows greater uncertainty and sustainability. The ratio of benefit to cost has a significant impact on opinion formation and a moderate ratio will result in the longest relaxation time or most unified global opinions. Furthermore, celebrities with a large number of followers are more capable of influencing public opinion than experts. This paper enriches the researches on opinion formation modeling, and the results provide managerial insights for business on public relations and market prediction.
Context-adaptive neural network based prediction for image compression
Venue: arXiv cs.NE 2019
Year: 2019

This paper describes a set of neural network architectures, called Prediction Neural Networks Set (PNNS), based on both fully-connected and convolutional neural networks, for intra image prediction. The choice of neural network for predicting a given image block depends on the block size, hence does not need to be signalled to the decoder. It is shown that, while fully-connected neural networks give good performance for small block sizes, convolutional neural networks provide better predictions in large blocks with complex textures. Thanks to the use of masks of random sizes during training, the neural networks of PNNS well adapt to the available context that may vary, depending on the position of the image block to be predicted. When integrating PNNS into a H.265 codec, PSNR-rate performance gains going from 1.46% to 5.20% are obtained. These gains are on average 0.99% larger than those of prior neural network based methods. Unlike the H.265 intra prediction modes, which are each specialized in predicting a specific texture, the proposed PNNS can model a large set of complex textures.
Local Meaning Structures: A Mixed-Method Socio-Semantic Network Analysis
Venue: arXiv cs.SI 2019
Year: 2019

This paper proposes a mixed-method socio-semantic network analysis of meaning structures in practice. While social and institutional fields impose meaning structures, to achieve practical goals field participants gather in groups and locally produce idiocultures of their own. Such idiocultures are difficult to capture structurally, hence, the impact of practice on meaning structures is underrated. To account for this impact, we automatically map local meaning structures - ensembles of semantic associations embedded in specific social groups - to identify the focal elements of these meaning structures, and qualitatively examine contextual usage of such elements. Employing a combination of ethnographic and social network data on two St. Petersburg art collectives, we find the seemingly field-imposed meaning structures to be instantiated differently, depending on group practice. Moreover, we find meaning structures to emerge from group practice and even change the field-wide meaning structures.
Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
Venue: arXiv cs.DC 2019
Year: 2019

The success of modern parallel paradigms such as MapReduce, Hadoop, or Spark, has attracted a significant attention to the Massively Parallel Computation (MPC) model over the past few years, especially on graph problems. In this work, we consider symmetry breaking problems of maximal independent set (MIS) and maximal matching (MM), which are among the most intensively studied problems in distributed/parallel computing, in MPC. These problems are known to admit efficient MPC algorithms if the space per machine is near-linear in $n$, the number of vertices in the graph. This space requirement however, as observed in the literature, is often significantly larger than we can afford; especially when the input graph is sparse. In a sharp contrast, in the truly sublinear regime of $n^{1-Ω(1)}$ space per machine, all the known algorithms take $\log^{Ω(1)} n$ rounds which is considered inefficient. Motivated by this shortcoming, we parametrize our algorithms by the arboricity $α$ of the input graph, which is a well-received measure of its sparsity. We show that both MIS and MM admit $O(\sqrt{\log α}\cdot\log\log α+ \log^2\log n)$ round algorithms using $O(n^ε)$ space per machine for any constant $ε\in (0, 1)$ and using $\widetilde{O}(m)$ total space. Therefore, for the wide range of sparse graphs with small arboricity---such as minor-free graphs, bounded-genus graphs or bounded treewidth graphs---we get an $O(\log^2 \log n)$ round algorithm which exponentially improves prior algorithms. By known reductions, our results also imply a $(1+ε)$-approximation of maximum cardinality matching, a $(2+ε)$-approximation of maximum weighted matching, and a 2-approximation of minimum vertex cover with essentially the same round complexity and memory requirements.
RARD II: The 94 Million Related-Article Recommendation Dataset
Venue: arXiv cs.IR 2019
Year: 2019

The main contribution of this paper is to introduce and describe a new recommender-systems dataset (RARD II). It is based on data from Mr. DLib, a recommender-system as-a-service in the digital library and reference-management-software domain. As such, RARD II complements datasets from other domains such as books, movies, and music. The dataset encompasses 94m recommendations, delivered in the two years from September 2016 to September 2018. The dataset covers an item-space of 24m unique items. RARD II provides a range of rich recommendation data, beyond conventional ratings. For example, in addition to the usual (implicit) ratings matrices, RARD II includes the original recommendation logs, which provide a unique insight into many aspects of the algorithms that generated the recommendations. The logs enable researchers to conduct various analyses about a real-world recommender system. This includes the evaluation of meta-learning approaches for predicting algorithm performance. In this paper, we summarise the key features of this dataset release, describe how it was generated and discuss some of its unique features. Compared to its predecessor RARD, RARD II contains 64% more recommendations, 187% more features (algorithms, parameters, and statistics), 50% more clicks, 140% more documents, and one additional service partner (JabRef).
Hierarchical Multi Task Learning With CTC
Venue: arXiv cs.CL 2019
Year: 2019

In Automatic Speech Recognition it is still challenging to learn useful intermediate representations when using high-level (or abstract) target units such as words. For that reason, character or phoneme based systems tend to outperform word-based systems when just few hundreds of hours of training data are being used. In this paper, we first show how hierarchical multi-task training can encourage the formation of useful intermediate representations. We achieve this by performing Connectionist Temporal Classification at different levels of the network with targets of different granularity. Our model thus performs predictions in multiple scales for the same input. On the standard 300h Switchboard training setup, our hierarchical multi-task architecture exhibits improvements over single-task architectures with the same number of parameters. Our model obtains 14.0% Word Error Rate on the Eval2000 Switchboard subset without any decoder or language model, outperforming the current state-of-the-art on acoustic-to-word models.
Operator-in-the-Loop Deep Sequential Multi-camera Feature Fusion for Person Re-identification
Venue: arXiv cs.CV 2019
Year: 2019

Given a target image as query, person re-identification systems retrieve a ranked list of candidate matches on a per-camera basis. In deployed systems, a human operator scans these lists and labels sighted targets by touch or mouse-based selection. However, classical re-id approaches generate per-camera lists independently. Therefore, target identifications by operator in a subset of cameras cannot be utilized to improve ranking of the target in remaining set of network cameras. To address this shortcoming, we propose a novel sequential multi-camera re-id approach. The proposed approach can accommodate human operator inputs and provides early gains via a monotonic improvement in target ranking. At the heart of our approach is a fusion function which operates on deep feature representations of query and candidate matches. We formulate an optimization procedure custom-designed to incrementally improve query representation. Since existing evaluation methods cannot be directly adopted to our setting, we also propose two novel evaluation protocols. The results on two large-scale re-id datasets (Market-1501, DukeMTMC-reID) demonstrate that our multi-camera method significantly outperforms baselines and other popular feature fusion schemes. Additionally, we conduct a comparative subject-based study of human operator performance. The superior operator performance enabled by our approach makes a compelling case for its integration into deployable video-surveillance systems.
Can Artificial Intelligence Reliably Report Chest X-Rays?: Radiologist Validation of an Algorithm trained on 2.3 Million X-Rays
Venue: arXiv cs.CV 2019
Year: 2019

Background: Chest X-rays are the most commonly performed, cost-effective diagnostic imaging tests ordered by physicians. A clinically validated AI system that can reliably separate normals from abnormals can be invaluble particularly in low-resource settings. The aim of this study was to develop and validate a deep learning system to detect various abnormalities seen on a chest X-ray. Methods: A deep learning system was trained on 2.3 million chest X-rays and their corresponding radiology reports to identify various abnormalities seen on a Chest X-ray. The system was tested against - 1. A three-radiologist majority on an independent, retrospectively collected set of 2000 X-rays(CQ2000) 2. Radiologist reports on a separate validation set of 100,000 scans(CQ100k). The primary accuracy measure was area under the ROC curve (AUC), estimated separately for each abnormality and for normal versus abnormal scans. Results: On the CQ2000 dataset, the deep learning system demonstrated an AUC of 0.92(CI 0.91-0.94) for detection of abnormal scans, and AUC(CI) of 0.96(0.94-0.98), 0.96(0.94-0.98), 0.95(0.87-1), 0.95(0.92-0.98), 0.93(0.90-0.96), 0.89(0.83-0.94), 0.91(0.87-0.96), 0.94(0.93-0.96), 0.98(0.97-1) for the detection of blunted costophrenic angle, cardiomegaly, cavity, consolidation, fibrosis, hilar enlargement, nodule, opacity and pleural effusion. The AUCs were similar on the larger CQ100k dataset except for detecting normals where the AUC was 0.86(0.85-0.86). Interpretation: Our study demonstrates that a deep learning algorithm trained on a large, well-labelled dataset can accurately detect multiple abnormalities on chest X-rays. As these systems improve in accuracy, applying deep learning to widen the reach of chest X-ray interpretation and improve reporting efficiency will add tremendous value in radiology workflows and public health screenings globally.
Efficient Facial Representations for Age, Gender and Identity Recognition in Organizing Photo Albums using Multi-output CNN
Venue: arXiv cs.CV 2019
Year: 2019

This paper is focused on the automatic extraction of persons and their attributes (gender, year of born) from album of photos and videos. We propose the two-stage approach, in which, firstly, the convolutional neural network simultaneously predicts age/gender from all photos and additionally extracts facial representations suitable for face identification. We modified the MobileNet, which is preliminarily trained to perform face recognition, in order to additionally recognize age and gender. In the second stage of our approach, extracted faces are grouped using hierarchical agglomerative clustering techniques. The born year and gender of a person in each cluster are estimated using aggregation of predictions for individual photos. We experimentally demonstrated that our facial clustering quality is competitive with the state-of-the-art neural networks, though our implementation is much computationally cheaper. Moreover, our approach is characterized by more accurate video-based age/gender recognition when compared to the publicly available models.
Towards a general mathematical theory of experimental science
Venue: arXiv cs.AI 2019
Year: 2019

We lay the groundwork for a formal framework that studies scientific theories and can serve as a unified foundation for the different theories within physics. We define a scientific theory as a set of verifiable statements, assertions that can be shown to be true with an experimental test in finite time. By studying the algebra of such objects, we show that verifiability already provides severe constraints. In particular, it requires that a set of physically distinguishable cases is naturally equipped with the mathematical structures (i.e. second-countable Kolmogorov topologies and $σ$-algebras) that form the foundation of manifold theory, differential geometry, measure theory, probability theory and all the major branches of mathematics currently used in physics. This gives a clear physical meaning to those mathematical structures and provides a strong justification for their use in science. Most importantly it provides a formal framework to incorporate additional assumptions and constrain the search space for new physical theories.
Eyeriss v2: A Flexible Accelerator for Emerging Deep Neural Networks on Mobile Devices
Venue: arXiv cs.DC 2019
Year: 2019

A recent trend in DNN development is to extend the reach of deep learning applications to platforms that are more resource and energy constrained, e.g., mobile devices. These endeavors aim to reduce the DNN model size and improve the hardware processing efficiency, and have resulted in DNNs that are much more compact in their structures and/or have high data sparsity. These compact or sparse models are different from the traditional large ones in that there is much more variation in their layer shapes and sizes, and often require specialized hardware to exploit sparsity for performance improvement. Thus, many DNN accelerators designed for large DNNs do not perform well on these models. In this work, we present Eyeriss v2, a DNN accelerator architecture designed for running compact and sparse DNNs. To deal with the widely varying layer shapes and sizes, it introduces a highly flexible on-chip network, called hierarchical mesh, that can adapt to the different amounts of data reuse and bandwidth requirements of different data types, which improves the utilization of the computation resources. Furthermore, Eyeriss v2 can process sparse data directly in the compressed domain for both weights and activations, and therefore is able to improve both processing speed and energy efficiency with sparse models. Overall, with sparse MobileNet, Eyeriss v2 in a 65nm CMOS process achieves a throughput of 1470.6 inferences/sec and 2560.3 inferences/J at a batch size of 1, which is 12.6x faster and 2.5x more energy efficient than the original Eyeriss running MobileNet. We also present an analysis methodology called Eyexam that provides a systematic way of understanding the performance limits for DNN processors as a function of specific characteristics of the DNN model and accelerator design; it applies these characteristics as sequential steps to increasingly tighten the bound on the performance limits.
Perceptual Video Super Resolution with Enhanced Temporal Consistency
Venue: arXiv cs.CV 2019
Year: 2019

With the advent of perceptual loss functions, new possibilities in super-resolution have emerged, and we currently have models that successfully generate near-photorealistic high-resolution images from their low-resolution observations. Up to now, however, such approaches have been exclusively limited to single image super-resolution. The application of perceptual loss functions on video processing still entails several challenges, mostly related to the lack of temporal consistency of the generated images, i.e., flickering artifacts. In this work, we present a novel adversarial recurrent network for video upscaling that is able to produce realistic textures in a temporally consistent way. The proposed architecture naturally leverages information from previous frames due to its recurrent architecture, i.e. the input to the generator is composed of the low-resolution image and, additionally, the warped output of the network at the previous step. Together with a video discriminator, we also propose additional loss functions to further reinforce temporal consistency in the generated sequences. The experimental validation of our algorithm shows the effectiveness of our approach which obtains images with high perceptual quality and improved temporal consistency.