OpenRaiser/Intern-Atlas huggingface dataset:
Information in propositional proofs and algorithmic proof search
Venue: arXiv cs.CC 2021
Year: 2021

We study from the proof complexity perspective the (informal) proof search problem: Is there an optimal way to search for propositional proofs? We note that for any fixed proof system there exists a time-optimal proof search algorithm. Using classical proof complexity results about reflection principles we prove that a time-optimal proof search algorithm exists without restricting proof systems iff a p-optimal proof system exists. To characterize precisely the time proof search algorithms need for individual formulas we introduce a new proof complexity measure based on algorithmic information concepts. In particular, to a proof system $P$ we attach {\bf information-efficiency function} $i_P(τ)$ assigning to a tautology a natural number, and we show that: - $i_P(τ)$ characterizes time any $P$-proof search algorithm has to use on $τ$ and that for a fixed $P$ there is such an information-optimal algorithm, - a proof system is information-efficiency optimal iff it is p-optimal, - for non-automatizable systems $P$ there are formulas $τ$ with short proofs but having large information measure $i_P(τ)$. We isolate and motivate the problem to establish unconditional super-logarithmic lower bounds for $i_P(τ)$ where no super-polynomial size lower bounds are known. We also point out connections of the new measure with some topics in proof complexity other than proof search.
Coastline extraction from ALOS-2 satellite SAR images
Venue: arXiv cs.CV 2021
Year: 2021

The continuous monitoring of a shore plays an essential role in designing strategies for shore protection against erosion. To avoid the effect of clouds and sunlight, satellite-based imagery with synthetic aperture radar is used to provide the required data. We show how such data can be processed using state-of-the-art methods, namely, by a deep-learning-based approach, to detect the coastline location. We split the process into data reading, data preprocessing, model training, inference, ensembling, and postprocessing, and describe the best techniques for each of the parts. Finally, we present our own solution that is able to precisely extract the coastline from an image even if it is not recognizable by a human. Our solution has been validated against the real GPS location of the coastline during Signate's competition, where it was runner-up among 109 teams across the whole world.
MIPT-NSU-UTMN at SemEval-2021 Task 5: Ensembling Learning with Pre-trained Language Models for Toxic Spans Detection
Venue: arXiv cs.CL 2021
Year: 2021

This paper describes our system for SemEval-2021 Task 5 on Toxic Spans Detection. We developed ensemble models using BERT-based neural architectures and post-processing to combine tokens into spans. We evaluated several pre-trained language models using various ensemble techniques for toxic span identification and achieved sizable improvements over our baseline fine-tuned BERT models. Finally, our system obtained a F1-score of 67.55% on test data.
Application specific dataflow machine construction for programming FPGAs via Lucent
Venue: arXiv cs.PL 2021
Year: 2021

Field Programmable Gate Arrays (FPGAs) have the potential to accelerate specific HPC codes. However even with the advent of High Level Synthesis (HLS), which enables FPGA programmers to write code in C or C++, programming such devices still requires considerable expertise. Much of this is due to the fact that these architectures are founded on dataflow rather than the Von Neumann abstraction of CPUs or GPUs. Thus programming FPGAs via imperative languages is not optimal and can result in very significant performance differences between the first and final versions of algorithms on dataflow architectures with the steps in between often not obvious and requiring considerable expertise. In this position paper we argue that languages built upon dataflow principals should be exploited to enable fast by construction codes for FPGAs, and this is akin to the programmer adopting the abstraction of developing a bespoke dataflow machine specialised for their application. It is our belief that much can be learnt from the generation of dataflow languages that gained popularity in the 1970s and 1980s around programming general purpose dataflow machines, and we introduce Lucent which is a modern derivative of Lucid, and used as a vehicle to explore this hypothesis. The idea behind Lucent is to provide high programmer productivity and performance for FPGAs by giving developers the most suitable language level abstractions. The focus of Lucent is very much to support the acceleration of HPC kernels, rather than the embedded electronics and circuit level, and we provide a brief overview of the language driven by examples.
How Should Network Slice Instances be Provided to Multiple Use Cases of a Single Vertical Industry?
Venue: arXiv cs.NI 2021
Year: 2021

There are a large number of vertical industries implementing multiple use cases, each use case characterized by diverging service, network, and connectivity requirements such as automobile, manufacturing, power grid, etc. Such heterogeneity cannot be effectively managed and efficiently mapped onto a single type of network slice instance (NSI). Thus the tailored provisioning of an end-to-end network slicing solution to a vertical industry that consists of multiple use cases is a critical issue, which motivates this article, aimed at exploring this never-addressed and challenging research problem by proposing the Use-case Specific Network Slicing and the SubNetwork Slicing concepts that enable the provisioning of Use-case-specific NSI(US-NSI) and GeNeric NSI(GN-NSI), respectively. Both approaches tackle the same technical issue of provisioning, management, and orchestration of per vertical per use case NSIs in order to improve resource allocation and enhance network performance. The article also presents the architectural frameworks for managing US-NSI and GN-NSI, which extend the service deployment concept and system architecture of network slicing for vertical customers of fifth-generation (5G) mobile networks.
Latent Code-Based Fusion: A Volterra Neural Network Approach
Venue: arXiv cs.CV 2021
Year: 2021

We propose a deep structure encoder using the recently introduced Volterra Neural Networks (VNNs) to seek a latent representation of multi-modal data whose features are jointly captured by a union of subspaces. The so-called self-representation embedding of the latent codes leads to a simplified fusion which is driven by a similarly constructed decoding. The Volterra Filter architecture achieved reduction in parameter complexity is primarily due to controlled non-linearities being introduced by the higher-order convolutions in contrast to generalized activation functions. Experimental results on two different datasets have shown a significant improvement in the clustering performance for VNNs auto-encoder over conventional Convolutional Neural Networks (CNNs) auto-encoder. In addition, we also show that the proposed approach demonstrates a much-improved sample complexity over CNN-based auto-encoder with a superb robust classification performance.
Error Propagation in Satellite Multi-image Geometry
Venue: arXiv cs.CV 2021
Year: 2021

This paper describes an investigation of the source of geospatial error in digital surface models (DSMs) constructed from multiple satellite images. In this study the uncertainty in surface geometry is separated into two spatial components; global error that affects the absolute position of the surface, and local error that varies from surface point to surface point. The global error component is caused by inaccuracy in the satellite imaging process, mainly due to uncertainty in the satellite position and orientation (pose) during image collection. A key result of the investigation is a new algorithm for determining the absolute geoposition of the DSM that takes into account the pose covariance of each satellite during image collection. This covariance information is used to weigh the evidence from each image in the computation of the global position of the DSM. The use of covariance information significantly decreases the overall uncertainty in global position. The paper also describes an approach to the prediction of local error in the DSM surface. The observed variance in surface position within a single stereo surface reconstruction defines the local horizontal error. The variance in the fused set of elevations from multiple stereo pairs at a single DSM location defines the local vertical error. These accuracy predictions are compared to ground truth provided by LiDAR scans of the same geographic region of interest.
Hyperspectral Pigment Analysis of Cultural Heritage Artifacts Using the Opaque Form of Kubelka-Munk Theory
Venue: arXiv cs.CV 2021
Year: 2021

Kubelka-Munk (K-M) theory has been successfully used to estimate pigment concentrations in the pigment mixtures of modern paintings in spectral imagery. In this study the single-constant K-M theory has been utilized for the classification of green pigments in the Selden Map of China, a navigational map of the South China Sea likely created in the early seventeenth century. Hyperspectral data of the map was collected at the Bodleian Library, University of Oxford, and can be used to estimate the pigment diversity, and spatial distribution, within the map. This work seeks to assess the utility of analyzing the data in the K/S space from Kubelka-Munk theory, as opposed to the traditional reflectance domain. We estimate the dimensionality of the data and extract endmembers in the reflectance domain. Then we perform linear unmixing to estimate abundances in the K/S space, and following Bai, et al. (2017), we perform a classification in the abundance space. Finally, due to the lack of ground truth labels, the classification accuracy was estimated by computing the mean spectrum of each class as the representative signature of that class, and calculating the root mean squared error with all the pixels in that class to create a spatial representation of the error. This highlights both the magnitude of, and any spatial pattern in, the errors, indicating if a particular pigment is not well modeled in this approach.
Disentangled Contrastive Learning for Learning Robust Textual Representations
Venue: arXiv cs.CL 2021
Year: 2021

Although the self-supervised pre-training of transformer models has resulted in the revolutionizing of natural language processing (NLP) applications and the achievement of state-of-the-art results with regard to various benchmarks, this process is still vulnerable to small and imperceptible permutations originating from legitimate inputs. Intuitively, the representations should be similar in the feature space with subtle input permutations, while large variations occur with different meanings. This motivates us to investigate the learning of robust textual representation in a contrastive manner. However, it is non-trivial to obtain opposing semantic instances for textual samples. In this study, we propose a disentangled contrastive learning method that separately optimizes the uniformity and alignment of representations without negative sampling. Specifically, we introduce the concept of momentum representation consistency to align features and leverage power normalization while conforming the uniformity. Our experimental results for the NLP benchmarks demonstrate that our approach can obtain better results compared with the baselines, as well as achieve promising improvements with invariance tests and adversarial attacks. The code is available in https://github.com/zxlzr/DCL.
Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
Venue: arXiv cs.DS 2021
Year: 2021

We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a $(1+ε)$-approximation requires either $n^{Ω(1)}$ space or $Ω(1/ε)$ passes, even on highly restricted families of graphs such as bounded-degree planar graphs. For multiple of these problems, this bound matches those of existing algorithms and is thus (asymptotically) optimal. Our results considerably strengthen prior lower bounds even for arbitrary graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there has been a plethora of lower bounds for single-pass algorithms for these problems; however, the only multi-pass lower bounds proven very recently in [Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with exponentially smaller $o(\log{(1/ε)})$ passes for these problems. One key ingredient of our proofs is a simple streaming XOR Lemma, a generic hardness amplification result, that we prove: informally speaking, if a $p$-pass $s$-space streaming algorithm can only solve a decision problem with advantage $δ> 0$ over random guessing, then it cannot solve XOR of $\ell$ independent copies of the problem with advantage much better than $δ^{\ell}$. This result can be of independent interest and useful for other streaming lower bounds as well.
ODT FLOW: A Scalable Platform for Extracting, Analyzing, and Sharing Multi-source Multi-scale Human Mobility
Venue: arXiv cs.DC 2021
Year: 2021

In response to the soaring needs of human mobility data, especially during disaster events such as the COVID-19 pandemic, and the associated big data challenges, we develop a scalable online platform for extracting, analyzing, and sharing multi-source multi-scale human mobility flows. Within the platform, an origin-destination-time (ODT) data model is proposed to work with scalable query engines to handle heterogenous mobility data in large volumes with extensive spatial coverage, which allows for efficient extraction, query, and aggregation of billion-level origin-destination (OD) flows in parallel at the server-side. An interactive spatial web portal, ODT Flow Explorer, is developed to allow users to explore multi-source mobility datasets with user-defined spatiotemporal scales. To promote reproducibility and replicability, we further develop ODT Flow REST APIs that provide researchers with the flexibility to access the data programmatically via workflows, codes, and programs. Demonstrations are provided to illustrate the potential of the APIs integrating with scientific workflows and with the Jupyter Notebook environment. We believe the platform coupled with the derived multi-scale mobility data can assist human mobility monitoring and analysis during disaster events such as the ongoing COVID-19 pandemic and benefit both scientific communities and the general public in understanding human mobility dynamics.
A Non-Negative Matrix Factorization Game
Venue: arXiv cs.GT 2021
Year: 2021

We present a novel game-theoretic formulation of Non-Negative Matrix Factorization (NNMF), a popular data-analysis method with many scientific and engineering applications. The game-theoretic formulation is shown to have favorable scaling and parallelization properties, while retaining reconstruction and convergence performance comparable to the traditional Multiplicative Updates algorithm.
Shuffler: A Large Scale Data Management Tool for ML in Computer Vision
Venue: arXiv cs.CV 2021
Year: 2021

Datasets in the computer vision academic research community are primarily static. Once a dataset is accepted as a benchmark for a computer vision task, researchers working on this task will not alter it in order to make their results reproducible. At the same time, when exploring new tasks and new applications, datasets tend to be an ever changing entity. A practitioner may combine existing public datasets, filter images or objects in them, change annotations or add new ones to fit a task at hand, visualize sample images, or perhaps output statistics in the form of text or plots. In fact, datasets change as practitioners experiment with data as much as with algorithms, trying to make the most out of machine learning models. Given that ML and deep learning call for large volumes of data to produce satisfactory results, it is no surprise that the resulting data and software management associated to dealing with live datasets can be quite complex. As far as we know, there is no flexible, publicly available instrument to facilitate manipulating image data and their annotations throughout a ML pipeline. In this work, we present Shuffler, an open source tool that makes it easy to manage large computer vision datasets. It stores annotations in a relational, human-readable database. Shuffler defines over 40 data handling operations with annotations that are commonly useful in supervised learning applied to computer vision and supports some of the most well-known computer vision datasets. Finally, it is easily extensible, making the addition of new operations and datasets a task that is fast and easy to accomplish.
Cybersecurity in Smart Farming: Canada Market Research
Venue: arXiv cs.CR 2021
Year: 2021

The Cyber Science Lab (CSL) and Smart Cyber-Physical System (SCPS) Lab at the University of Guelph conduct a market study of cybersecurity technology adoption and requirements for smart and precision farming in Canada. We conducted 17 stakeholder/key opinion leader interviews in Canada and the USA, as well as conducting extensive secondary research, to complete this study. Each interview generally required 15-20 minutes to complete. Interviews were conducted using a client-approved interview guide. Secondary and primary research focussed on the following areas of investigation: Market size and segmentation Market forecast and growth rate Competitive landscape Market challenges/barriers to entry Market trends/growth drivers Adoption/commercialization of the technology
Point wise or Feature wise? Benchmark Comparison of Public Available LiDAR Odometry Algorithms in Urban Canyons
Venue: arXiv cs.RO 2021
Year: 2021

Robust and precise localization is essential for the autonomous system with navigation requirements. Light detection and ranging (LiDAR) odometry is extensively studied in the past decades to achieve this goal. Satisfactory accuracy can be achieved in scenarios with abundant environmental features using existing LiDAR odometry (LO) algorithms. Unfortunately, the performance of the LiDAR odometry is significantly degraded in urban canyons with numerous dynamic objects and complex environmental structures. Meanwhile, it is still not clear from the existing literature which LO algorithms perform well in such challenging environments. To fill this gap, this paper evaluates an array of popular and extensively studied LO pipelines using the datasets collected in urban canyons of Hong Kong. We present the results in terms of their positioning accuracy and computational efficiency. Three major factors dominating the performance of LO in urban canyons are concluded, including the ego-vehicle dynamic, moving objects, and degree of urbanization. According to our experiment results, point-wise achieves better accuracy in urban canyons while feature-wise achieves cost-efficiency and satisfactory positioning accuracy.
Virtual Barriers in Augmented Reality for Safe and Effective Human-Robot Cooperation in Manufacturing
Venue: arXiv cs.RO 2021
Year: 2021

Safety is a fundamental requirement in any human-robot collaboration scenario. To ensure the safety of users for such scenarios, we propose a novel Virtual Barrier system facilitated by an augmented reality interface. Our system provides two kinds of Virtual Barriers to ensure safety: 1) a Virtual Person Barrier which encapsulates and follows the user to protect them from colliding with the robot, and 2) Virtual Obstacle Barriers which users can spawn to protect objects or regions that the robot should not enter. To enable effective human-robot collaboration, our system includes an intuitive robot programming interface utilizing speech commands and hand gestures, and features the capability of automatic path re-planning when potential collisions are detected as a result of a barrier intersecting the robot's planned path. We compared our novel system with a standard 2D display interface through a user study, where participants performed a task mimicking an industrial manufacturing procedure. Results show that our system increases the user's sense of safety and task efficiency, and makes the interaction more intuitive.
Contextualized Knowledge-aware Attentive Neural Network: Enhancing Answer Selection with Knowledge
Venue: arXiv cs.CL 2021
Year: 2021

Answer selection, which is involved in many natural language processing applications such as dialog systems and question answering (QA), is an important yet challenging task in practice, since conventional methods typically suffer from the issues of ignoring diverse real-world background knowledge. In this paper, we extensively investigate approaches to enhancing the answer selection model with external knowledge from knowledge graph (KG). First, we present a context-knowledge interaction learning framework, Knowledge-aware Neural Network (KNN), which learns the QA sentence representations by considering a tight interaction with the external knowledge from KG and the textual information. Then, we develop two kinds of knowledge-aware attention mechanism to summarize both the context-based and knowledge-based interactions between questions and answers. To handle the diversity and complexity of KG information, we further propose a Contextualized Knowledge-aware Attentive Neural Network (CKANN), which improves the knowledge representation learning with structure information via a customized Graph Convolutional Network (GCN) and comprehensively learns context-based and knowledge-based sentence representation via the multi-view knowledge-aware attention mechanism. We evaluate our method on four widely-used benchmark QA datasets, including WikiQA, TREC QA, InsuranceQA and Yahoo QA. Results verify the benefits of incorporating external knowledge from KG, and show the robust superiority and extensive applicability of our method.
Deep Attributed Network Representation Learning via Attribute Enhanced Neighborhood
Venue: arXiv cs.AI 2021
Year: 2021

Attributed network representation learning aims at learning node embeddings by integrating network structure and attribute information. It is a challenge to fully capture the microscopic structure and the attribute semantics simultaneously, where the microscopic structure includes the one-step, two-step and multi-step relations, indicating the first-order, second-order and high-order proximity of nodes, respectively. In this paper, we propose a deep attributed network representation learning via attribute enhanced neighborhood (DANRL-ANE) model to improve the robustness and effectiveness of node representations. The DANRL-ANE model adopts the idea of the autoencoder, and expands the decoder component to three branches to capture different order proximity. We linearly combine the adjacency matrix with the attribute similarity matrix as the input of our model, where the attribute similarity matrix is calculated by the cosine similarity between the attributes based on the social homophily. In this way, we preserve the second-order proximity to enhance the robustness of DANRL-ANE model on sparse networks, and deal with the topological and attribute information simultaneously. Moreover, the sigmoid cross-entropy loss function is extended to capture the neighborhood character, so that the first-order proximity is better preserved. We compare our model with the state-of-the-art models on five real-world datasets and two network analysis tasks, i.e., link prediction and node classification. The DANRL-ANE model performs well on various networks, even on sparse networks or networks with isolated nodes given the attribute information is sufficient.