OpenRaiser/Intern-Atlas huggingface dataset:
Obtaining a Canonical Polygonal Schema from a Greedy Homotopy Basis with Minimal Mesh Refinement
Venue: arXiv cs.CG 2020
Year: 2020

Any closed manifold of genus g can be cut open to form a topological disk and then mapped to a regular polygon with 4g sides. This construction is called the canonical polygonal schema of the manifold, and is a key ingredient for many applications in graphics and engineering, where a parameterization between two shapes with same topology is often needed. The sides of the 4g-gon define on the manifold a system of loops, which all intersect at a single point and are disjoint elsewhere. Computing a shortest system of loops of this kind is NP-hard. A computationally tractable alternative consists in computing a set of shortest loops that are not fully disjoint in polynomial time, using the greedy homotopy basis algorithm proposed by Erickson and Whittlesey, and then detach them in post processing via mesh refinement. Despite this operation is conceptually simple, known refinement strategies do not scale well for high genus shapes, triggering a mesh growth that may exceed the amount of memory available in modern computers, leading to failures. In this paper we study various local refinement operators to detach cycles in a system of loops, and show that there are important differences between them, both in terms of mesh complexity and preservation of the original surface. We ultimately propose two novel refinement approaches: the former minimizes the number of new elements in the mesh, possibly at the cost of a deviation from the input geometry. The latter allows to trade mesh complexity for geometric accuracy, bounding deviation from the input surface. Both strategies are trivial to implement, and experiments confirm that they allow to realize canonical polygonal schemas even for extremely high genus shapes where previous methods fail.
Verifiable and Auditable Digital Interchange Framework
Venue: arXiv cs.DC 2020
Year: 2020

We address the problem of fairness and transparency in online marketplaces selling digital content, where all parties are not actively participating in the trade. We present the design, implementation and evaluation of VADER, a highly scalable solution for multi-party fair digital exchange that combines the trusted execution of blockchains with intelligent protocol design and incentivization schemes. We prototype VADER on Hyperledger Fabric and extensively evaluate our system on a realistic testbed spanning five public cloud datacenters, spread across four continents. Our results demonstrate that VADER adds only minimal overhead of 16% in median case compared to a baseline solution, while significantly outperforming a naive blockchain based solution that adds an overhead of 764%.
NOMA Enhanced Terrestrial and Aerial IoT Networks with Partial CSI
Venue: arXiv cs.IT 2020
Year: 2020

This article investigates a non-orthogonal multiple access (NOMA) enhanced Internet of Things (IoT) network. In order to provide connectivity, a novel cluster strategy is proposed, where multiple devices can be served simultaneously. Two potential scenarios are investigated: 1) NOMA enhanced terrestrial IoT networks and 2) NOMA enhanced aerial IoT networks. We utilize stochastic geometry tools to model the spatial randomness of both terrestrial and aerial devices. New channel statistics are derived for both terrestrial and aerial devices. The exact and the asymptotic expressions in terms of coverage probability are derived. In order to obtain further engineering insights, short-packet communication scenarios are investigated. From our analysis, we show that the performance of NOMA enhanced IoT networks is capable of outperforming OMA enhanced IoT networks. Moreover, based on simulation results, there exists an optimal value of the transmit power that maximizes the coverage probability.
Unsupervised Enhancement of Real-World Depth Images Using Tri-Cycle GAN
Venue: arXiv cs.CV 2020
Year: 2020

Low quality depth poses a considerable challenge to computer vision algorithms. In this work we aim to enhance highly degraded, real-world depth images acquired by a low-cost sensor, for which an analytical noise model is unavailable. In the absence of clean ground-truth, we approach the task as an unsupervised domain-translation between the low-quality sensor domain and a high-quality sensor domain, represented using two unpaired training sets. We employ the highly-successful Cycle-GAN to this task, but find it to perform poorly in this case. Identifying the sources of the failure, we introduce several modifications to the framework, including a larger generator architecture, depth-specific losses that take into account missing pixels, and a novel Tri-Cycle loss which promotes information-preservation while addressing the asymmetry between the domains. We show that the resulting framework dramatically improves over the original Cycle-GAN both visually and quantitatively, extending its applicability to more challenging and asymmetric translation tasks.
Revisiting Challenges in Data-to-Text Generation with Fact Grounding
Venue: arXiv cs.CL 2020
Year: 2020

Data-to-text generation models face challenges in ensuring data fidelity by referring to the correct input source. To inspire studies in this area, Wiseman et al. (2017) introduced the RotoWire corpus on generating NBA game summaries from the box- and line-score tables. However, limited attempts have been made in this direction and the challenges remain. We observe a prominent bottleneck in the corpus where only about 60% of the summary contents can be grounded to the boxscore records. Such information deficiency tends to misguide a conditioned language model to produce unconditioned random facts and thus leads to factual hallucinations. In this work, we restore the information balance and revamp this task to focus on fact-grounded data-to-text generation. We introduce a purified and larger-scale dataset, RotoWire-FG (Fact-Grounding), with 50% more data from the year 2017-19 and enriched input tables, hoping to attract more research focuses in this direction. Moreover, we achieve improved data fidelity over the state-of-the-art models by integrating a new form of table reconstruction as an auxiliary task to boost the generation quality.
A Comparative Study for Non-rigid Image Registration and Rigid Image Registration
Venue: arXiv cs.CV 2020
Year: 2020

Image registration algorithms can be generally categorized into two groups: non-rigid and rigid. Recently, many deep learning-based algorithms employ a neural net to characterize non-rigid image registration function. However, do they always perform better? In this study, we compare the state-of-art deep learning-based non-rigid registration approach with rigid registration approach. The data is generated from Kaggle Dog vs Cat Competition \url{https://www.kaggle.com/c/dogs-vs-cats/} and we test the algorithms' performance on rigid transformation including translation, rotation, scaling, shearing and pixelwise non-rigid transformation. The Voxelmorph is trained on rigidset and nonrigidset separately for comparison and we also add a gaussian blur layer to its original architecture to improve registration performance. The best quantitative results in both root-mean-square error (RMSE) and mean absolute error (MAE) metrics for rigid registration are produced by SimpleElastix and non-rigid registration by Voxelmorph. We select representative samples for visual assessment.
Deep Optimized Multiple Description Image Coding via Scalar Quantization Learning
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we introduce a deep multiple description coding (MDC) framework optimized by minimizing multiple description (MD) compressive loss. First, MD multi-scale-dilated encoder network generates multiple description tensors, which are discretized by scalar quantizers, while these quantized tensors are decompressed by MD cascaded-ResBlock decoder networks. To greatly reduce the total amount of artificial neural network parameters, an auto-encoder network composed of these two types of network is designed as a symmetrical parameter sharing structure. Second, this autoencoder network and a pair of scalar quantizers are simultaneously learned in an end-to-end self-supervised way. Third, considering the variation in the image spatial distribution, each scalar quantizer is accompanied by an importance-indicator map to generate MD tensors, rather than using direct quantization. Fourth, we introduce the multiple description structural similarity distance loss, which implicitly regularizes the diversified multiple description generations, to explicitly supervise multiple description diversified decoding in addition to MD reconstruction loss. Finally, we demonstrate that our MDC framework performs better than several state-of-the-art MDC approaches regarding image coding efficiency when tested on several commonly available datasets.
Mobility-assisted Over-the-Air Computation for Backscatter Sensor Networks
Venue: arXiv cs.NI 2020
Year: 2020

Future intelligent systems will consist of a massive number of battery-less sensors, where quick and accurate aggregation of sensor data will be of paramount importance. Over-the-air computation (AirComp) is a promising technology wherein sensors concurrently transmit their measurements over the wireless channel, and a reader receives the noisy version of a function of measurements due to the superposition property. A key challenge in AirComp is the accurate power alignment of individual transmissions, addressed previously by using conventional precoding methods. In this paper, we investigate a UAVenabled backscatter communication framework, wherein UAV acts both as a power emitter and reader. The mobility of the reader is leveraged to replace the complicated precoding at sensors, where UAV first collects sum channel gains in the first flyover, and then, use these to estimate the actual aggregated sensor data in the second flyover. Our results demonstrate improvements of up to 10 dB in MSE compared to that of a benchmark case where UAV is incognizant of sum channel gains.
Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks
Venue: arXiv cs.NI 2020
Year: 2020

User demand for increasing amounts of wireless capacity continues to outpace supply, and so to meet this demand, significant progress has been made in new MIMO wireless physical layer techniques. Higher-performance systems now remain impractical largely only because their algorithms are extremely computationally demanding. For optimal performance, an amount of computation that increases at an exponential rate both with the number of users and with the data rate of each user is often required. The base station's computational capacity is thus becoming one of the key limiting factors on wireless capacity. QuAMax is the first large MIMO centralized radio access network design to address this issue by leveraging quantum annealing on the problem. We have implemented QuAMax on the 2,031 qubit D-Wave 2000Q quantum annealer, the state-of-the-art in the field. Our experimental results evaluate that implementation on real and synthetic MIMO channel traces, showing that 10~$μ$s of compute time on the 2000Q can enable 48 user, 48 AP antenna BPSK communication at 20 dB SNR with a bit error rate of $10^{-6}$ and a 1,500 byte frame error rate of $10^{-4}$.
Tangent-Space Gradient Optimization of Tensor Network for Machine Learning
Venue: arXiv cs.LG 2020
Year: 2020

The gradient-based optimization method for deep machine learning models suffers from gradient vanishing and exploding problems, particularly when the computational graph becomes deep. In this work, we propose the tangent-space gradient optimization (TSGO) for the probabilistic models to keep the gradients from vanishing or exploding. The central idea is to guarantee the orthogonality between the variational parameters and the gradients. The optimization is then implemented by rotating parameter vector towards the direction of gradient. We explain and testify TSGO in tensor network (TN) machine learning, where the TN describes the joint probability distribution as a normalized state $\left| ψ\right\rangle $ in Hilbert space. We show that the gradient can be restricted in the tangent space of $\left\langle ψ\right.\left| ψ\right\rangle = 1$ hyper-sphere. Instead of additional adaptive methods to control the learning rate in deep learning, the learning rate of TSGO is naturally determined by the angle $θ$ as $η= \tan θ$. Our numerical results reveal better convergence of TSGO in comparison to the off-the-shelf Adam.
Residual Attention Net for Superior Cross-Domain Time Sequence Modeling
Venue: arXiv cs.LG 2020
Year: 2020

We present a novel architecture, residual attention net (RAN), which merges a sequence architecture, universal transformer, and a computer vision architecture, residual net, with a high-way architecture for cross-domain sequence modeling. The architecture aims at addressing the long dependency issue often faced by recurrent-neural-net-based structures. This paper serves as a proof-of-concept for a new architecture, with RAN aiming at providing the model a higher level understanding of sequence patterns. To our best knowledge, we are the first to propose such an architecture. Out of the standard 85 UCR data sets, we have achieved 35 state-of-the-art results with 10 results matching current state-of-the-art results without further model fine-tuning. The results indicate that such architecture is promising in complex, long-sequence modeling and may have vast, cross-domain applications.
Age-Oriented Opportunistic Relaying in Cooperative Status Update Systems with Stochastic Arrivals
Venue: arXiv cs.IT 2020
Year: 2020

This paper considers a cooperative status update system with a source aiming to send randomly generated status updates to a designated destination as timely as possible with the help of a relay. We adopt a recently proposed concept, Age of Information (AoI), to characterize the timeliness of the status updates. We propose an age-oriented opportunistic relaying (AoR) protocol to reduce the AoI of the considered system. Specifically, the relay opportunistically replaces the source to retransmit the successfully received status updates that have not been correctly delivered to the destination, but the retransmission of the relay can be preempted by the arrival of a new status update at the source. By carefully analyzing the evolution of AoI, we derive a closed-form expression of the average AoI for the proposed AoR protocol. We further minimize the average AoI by optimizing the generation probability of the status updates at the source. Simulation results validate our theoretical analysis and demonstrate that the average AoI performance of the proposed AoR protocol is superior to that of the non-cooperative system.
Incremental Unsupervised Domain-Adversarial Training of Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

In the context of supervised statistical learning, it is typically assumed that the training set comes from the same distribution that draws the test samples. When this is not the case, the behavior of the learned model is unpredictable and becomes dependent upon the degree of similarity between the distribution of the training set and the distribution of the test set. One of the research topics that investigates this scenario is referred to as domain adaptation. Deep neural networks brought dramatic advances in pattern recognition and that is why there have been many attempts to provide good domain adaptation algorithms for these models. Here we take a different avenue and approach the problem from an incremental point of view, where the model is adapted to the new domain iteratively. We make use of an existing unsupervised domain-adaptation algorithm to identify the target samples on which there is greater confidence about their true label. The output of the model is analyzed in different ways to determine the candidate samples. The selected set is then added to the source training set by considering the labels provided by the network as ground truth, and the process is repeated until all target samples are labelled. Our results report a clear improvement with respect to the non-incremental case in several datasets, also outperforming other state-of-the-art domain adaptation algorithms.
Testing Database Engines via Pivoted Query Synthesis
Venue: arXiv cs.DB 2020
Year: 2020

Relational databases are used ubiquitously. They are managed by database management systems (DBMS), which allow inserting, modifying, and querying data using a domain-specific language called Structured Query Language (SQL). Popular DBMS have been extensively tested by fuzzers, which have been successful in finding crash bugs. However, approaches to finding logic bugs, such as when a DBMS computes an incorrect result set, have remained mostly untackled. Differential testing is an effective technique to test systems that support a common language by comparing the outputs of these systems. However, this technique is ineffective for DBMS, because each DBMS typically supports its own SQL dialect. To this end, we devised a novel and general approach that we have termed Pivoted Query Synthesis. The core idea of this approach is to automatically generate queries for which we ensure that they fetch a specific, randomly selected row, called the pivot row. If the DBMS fails to fetch the pivot row, the likely cause is a bug in the DBMS. We tested our approach on three widely-used and mature DBMS, namely SQLite, MySQL, and PostgreSQL. In total, we reported 123 bugs in these DBMS, 99 of which have been fixed or verified, demonstrating that the approach is highly effective and general. We expect that the wide applicability and simplicity of our approach will enable the improvement of robustness of many DBMS.
Stake Shift in Major Cryptocurrencies: An Empirical Study
Venue: arXiv cs.CR 2020
Year: 2020

In the proof-of-stake (PoS) paradigm for maintaining decentralized, permissionless cryptocurrencies, Sybil attacks are prevented by basing the distribution of roles in the protocol execution on the stake distribution recorded in the ledger itself. However, for various reasons this distribution cannot be completely up-to-date, introducing a gap between the present stake distribution, which determines the parties' current incentives, and the one used by the protocol. In this paper, we investigate this issue, and empirically quantify its effects. We survey existing provably secure PoS proposals to observe that the above time gap between the two stake distributions, which we call stake distribution lag, amounts to several days for each of these protocols. Based on this, we investigate the ledgers of four major cryptocurrencies (Bitcoin, Bitcoin Cash, Litecoin and Zcash) and compute the average stake shift (the statistical distance of the two distributions) for each value of stake distribution lag between 1 and 14 days, as well as related statistics. We also empirically quantify the sublinear growth of stake shift with the length of the considered lag interval. Finally, we turn our attention to unusual stake-shift spikes in these currencies: we observe that hard forks trigger major stake shifts and that single real-world actors, mostly exchanges, account for major stake shifts in established cryptocurrency ecosystems.
Causal discovery of linear non-Gaussian acyclic models in the presence of latent confounders
Venue: arXiv cs.LG 2020
Year: 2020

Causal discovery from data affected by latent confounders is an important and difficult challenge. Causal functional model-based approaches have not been used to present variables whose relationships are affected by latent confounders, while some constraint-based methods can present them. This paper proposes a causal functional model-based method called repetitive causal discovery (RCD) to discover the causal structure of observed variables affected by latent confounders. RCD repeats inferring the causal directions between a small number of observed variables and determines whether the relationships are affected by latent confounders. RCD finally produces a causal graph where a bi-directed arrow indicates the pair of variables that have the same latent confounders, and a directed arrow indicates the causal direction of a pair of variables that are not affected by the same latent confounder. The results of experimental validation using simulated data and real-world data confirmed that RCD is effective in identifying latent confounders and causal directions between observed variables.
Handwritten Character Recognition Using Unique Feature Extraction Technique
Venue: arXiv cs.CV 2020
Year: 2020

One of the most arduous and captivating domains under image processing is handwritten character recognition. In this paper we have proposed a feature extraction technique which is a combination of unique features of geometric, zone-based hybrid, gradient features extraction approaches and three different neural networks namely the Multilayer Perceptron network using Backpropagation algorithm (MLP BP), the Multilayer Perceptron network using Levenberg-Marquardt algorithm (MLP LM) and the Convolutional neural network (CNN) which have been implemented along with the Minimum Distance Classifier (MDC). The procedures lead to the conclusion that the proposed feature extraction algorithm is more accurate than its individual counterparts and also that Convolutional Neural Network is the most efficient neural network of the three in consideration.
Roof Age Determination for the Automated Site-Selection of Rooftop Solar
Venue: arXiv cs.OH 2020
Year: 2020

Rooftop solar is one of the most promising tools for drawing down greenhouse gas (GHG) emissions and is cost-competitive with fossil fuels in many areas of the world today. One of the most important criteria for determining the suitability of a building for rooftop solar is the current age of its roof. The reason for this is simple -- because rooftop solar installations are long-lived, the roof needs to be new enough to last for the lifetime of the solar array or old enough to justify being replaced. In this paper we present a data-driven method for determining the age of a roof from historical satellite imagery, which removes one of the last obstacles to a fully automated pipeline for rooftop solar site selection. We estimate that a full solution to this problem would reduce customer acquisition costs for rooftop solar by $\sim$20\%, leading to an additional $\sim$750 megatons of CO$_2$ displaced between 2020 and 2050.
Secure Distributed Storage: Rate-Privacy Trade-Off and XOR-Based Coding Scheme
Venue: arXiv cs.IT 2020
Year: 2020

We consider the problem of storing data in a distributed manner over $T$ servers. We require the data (i) to be recoverable from the $T$ servers, and (ii) to remain private from any $T-1$ colluding servers, where privacy is quantified in terms of mutual information between the data and all the information available at the $T-1$ colluding servers. For this model, we determine (i) the fundamental trade-off between storage size and the level of desired privacy, (ii) the optimal amount of local randomness necessary at the encoder, and (iii)~an explicit low-complexity coding scheme that solely relies on XOR operations and that asymptotically (with the data size) matches the fundamental limits found.
(Newtonian) Space-Time Algebra
Venue: arXiv cs.LO 2020
Year: 2020

The space-time (s-t) algebra provides a mathematical model for communication and computation using values encoded as events in discretized linear (Newtonian) time. Consequently, the input-output behavior of s-t algebra and implemented functions are consistent with the flow of time. The s-t algebra and functions are formally defined. A network design framework for s-t functions is described, and the design of temporal neural networks, a form of spiking neural networks, is discussed as an extended case study. Finally, the relationship with Allen's interval algebra is briefly discussed.