OpenRaiser/Intern-Atlas huggingface dataset:
Petri Net Modeling for Ising Model Formulation in Quantum Annealing
Venue: arXiv cs.DM 2021
Year: 2021

Quantum annealing is an emerging new platform for combinatorial optimization, requiring an Ising model formulation for optimization problems. The formulation can be an essential obstacle to the permeation of this innovation into broad areas of everyday life. Our research is aimed at the proposal of a Petri net modeling approach for an Ising model formulation. Although the proposed method requires users to model their optimization problems with Petri nets, this process can be carried out in a relatively straightforward manner if we know the target problem and the simple Petri net modeling rules. With our method, the constraints and objective functions in the target optimization problems are represented as fundamental characteristics of Petri net models, extracted systematically from Petri net models, and then converted into binary quadratic nets, equivalent to Ising models. The proposed method can drastically reduce the difficulty of the Ising model formulation.
Darlin: Recursive Proofs using Marlin
Venue: arXiv cs.CR 2021
Year: 2021

This document describes Darlin, a succinct zero-knowledge argument of knowledge based on the Marlin SNARK (Chiesa et al., Eurocrypt 2020) and the `dlog' polynomial commitment scheme from Bootle et al. EUROCRYPT 2016. Darlin addresses recursive proofs by integrating the amortization technique from Halo (IACR eprint 2019/099) for the non-succinct parts of the dlog verifier, and we adapt their strategy for bivariate circuit encoding polynomials to aggregate Marlin's inner sumchecks across the nodes the recursive scheme. We estimate the performance impact of inner sumcheck aggregation by about 30% in a tree-like scheme of in-degree 2, and beyond when applied to linear recursion.
Attend2Pack: Bin Packing through Deep Reinforcement Learning with Attention
Venue: arXiv cs.LG 2021
Year: 2021

This paper seeks to tackle the bin packing problem (BPP) through a learning perspective. Building on self-attention-based encoding and deep reinforcement learning algorithms, we propose a new end-to-end learning model for this task of interest. By decomposing the combinatorial action space, as well as utilizing a new training technique denoted as prioritized oversampling, which is a general scheme to speed up on-policy learning, we achieve state-of-the-art performance in a range of experimental settings. Moreover, although the proposed approach attend2pack targets offline-BPP, we strip our method down to the strict online-BPP setting where it is also able to achieve state-of-the-art performance. With a set of ablation studies as well as comparisons against a range of previous works, we hope to offer as a valid baseline approach to this field of study.
A Robust Deep Ensemble Classifier for Figurative Language Detection
Venue: arXiv cs.CL 2021
Year: 2021

Recognition and classification of Figurative Language (FL) is an open problem of Sentiment Analysis in the broader field of Natural Language Processing (NLP) due to the contradictory meaning contained in phrases with metaphorical content. The problem itself contains three interrelated FL recognition tasks: sarcasm, irony and metaphor which, in the present paper, are dealt with advanced Deep Learning (DL) techniques. First, we introduce a data prepossessing framework towards efficient data representation formats so that to optimize the respective inputs to the DL models. In addition, special features are extracted in order to characterize the syntactic, expressive, emotional and temper content reflected in the respective social media text references. These features aim to capture aspects of the social network user's writing method. Finally, features are fed to a robust, Deep Ensemble Soft Classifier (DESC) which is based on the combination of different DL techniques. Using three different benchmark datasets (one of them containing various FL forms) we conclude that the DESC model achieves a very good performance, worthy of comparison with relevant methodologies and state-of-the-art technologies in the challenging field of FL recognition.
Information cohomology of classical vector-valued observables
Venue: arXiv cs.IT 2021
Year: 2021

We provide here a novel algebraic characterization of two information measures associated with a vector-valued random variable, its differential entropy and the dimension of the underlying space, purely based on their recursive properties (the chain rule and the nullity-rank theorem, respectively). More precisely, we compute the information cohomology of Baudot and Bennequin with coefficients in a module of continuous probabilistic functionals over a category that mixes discrete observables and continuous vector-valued observables, characterizing completely the 1-cocycles; evaluated on continuous laws, these cocycles are linear combinations of the differential entropy and the dimension.
Model compression as constrained optimization, with application to neural nets. Part V: combining compressions
Venue: arXiv cs.LG 2021
Year: 2021

Model compression is generally performed by using quantization, low-rank approximation or pruning, for which various algorithms have been researched in recent years. One fundamental question is: what types of compression work better for a given model? Or even better: can we improve by combining compressions in a suitable way? We formulate this generally as a problem of optimizing the loss but where the weights are constrained to equal an additive combination of separately compressed parts; and we give an algorithm to learn the corresponding parts' parameters. Experimentally with deep neural nets, we observe that 1) we can find significantly better models in the error-compression space, indicating that different compression types have complementary benefits, and 2) the best type of combination depends exquisitely on the type of neural net. For example, we can compress ResNets and AlexNet using only 1 bit per weight without error degradation at the cost of adding a few floating point weights. However, VGG nets can be better compressed by combining low-rank with a few floating point weights.
Aligning an optical interferometer with beam divergence control and continuous action space
Venue: arXiv cs.RO 2021
Year: 2021

Reinforcement learning is finding its way to real-world problem application, transferring from simulated environments to physical setups. In this work, we implement vision-based alignment of an optical Mach-Zehnder interferometer with a confocal telescope in one arm, which controls the diameter and divergence of the corresponding beam. We use a continuous action space; exponential scaling enables us to handle actions within a range of over two orders of magnitude. Our agent trains only in a simulated environment with domain randomizations. In an experimental evaluation, the agent significantly outperforms an existing solution and a human expert.
Redescription Model Mining
Venue: arXiv cs.DB 2021
Year: 2021

This paper introduces Redescription Model Mining, a novel approach to identify interpretable patterns across two datasets that share only a subset of attributes and have no common instances. In particular, Redescription Model Mining aims to find pairs of describable data subsets -- one for each dataset -- that induce similar exceptional models with respect to a prespecified model class. To achieve this, we combine two previously separate research areas: Exceptional Model Mining and Redescription Mining. For this new problem setting, we develop interestingness measures to select promising patterns, propose efficient algorithms, and demonstrate their potential on synthetic and real-world data. Uncovered patterns can hint at common underlying phenomena that manifest themselves across datasets, enabling the discovery of possible associations between (combinations of) attributes that do not appear in the same dataset.
Convergence analysis for gradient flows in the training of artificial neural networks with ReLU activation
Venue: arXiv cs.LG 2021
Year: 2021

Gradient descent (GD) type optimization schemes are the standard methods to train artificial neural networks (ANNs) with rectified linear unit (ReLU) activation. Such schemes can be considered as discretizations of gradient flows (GFs) associated to the training of ANNs with ReLU activation and most of the key difficulties in the mathematical convergence analysis of GD type optimization schemes in the training of ANNs with ReLU activation seem to be already present in the dynamics of the corresponding GF differential equations. It is the key subject of this work to analyze such GF differential equations in the training of ANNs with ReLU activation and three layers (one input layer, one hidden layer, and one output layer). In particular, in this article we prove in the case where the target function is possibly multi-dimensional and continuous and in the case where the probability distribution of the input data is absolutely continuous with respect to the Lebesgue measure that the risk of every bounded GF trajectory converges to the risk of a critical point. In addition, in this article we show in the case of a 1-dimensional affine linear target function and in the case where the probability distribution of the input data coincides with the standard uniform distribution that the risk of every bounded GF trajectory converges to zero if the initial risk is sufficiently small. Finally, in the special situation where there is only one neuron on the hidden layer (1-dimensional hidden layer) we strengthen the above named result for affine linear target functions by proving that that the risk of every (not necessarily bounded) GF trajectory converges to zero if the initial risk is sufficiently small.
A Dual-Connection based Handover Scheme for Ultra-Dense Millimeter-Wave Cellular Networks
Venue: arXiv cs.NI 2021
Year: 2021

Mobile users in an ultra-dense millimeter-wave cellular network experience handover events more frequently than in conventional networks, which results in increased service interruption time and performance degradation due to blockages. Multi-connectivity has been proposed to resolve this, and it also extends the coverage of millimeter-wave communications. In this paper, we propose a dual-connection based handover scheme for mobile UEs in an environment where they are connected simultaneously with two millimeter-wave cells to overcome frequent handover problems. This scheme allows a mobile UE to choose its serving link between the two mmWave connections according to the measured SINRs and then the corresponding base stations may forward duplicate packets to the UE. We compare our dual-connection based scheme with a conventional single-connection based scheme through ns-3 simulation. The simulation results show that the proposed scheme significantly reduces handover rate and delay. Therefore, we argue that the dual-connection based scheme helps mobile users achieve performance goals they require in ultra-dense cellular environments.
White-Box Cartoonization Using An Extended GAN Framework
Venue: arXiv cs.CV 2021
Year: 2021

In the present study, we propose to implement a new framework for estimating generative models via an adversarial process to extend an existing GAN framework and develop a white-box controllable image cartoonization, which can generate high-quality cartooned images/videos from real-world photos and videos. The learning purposes of our system are based on three distinct representations: surface representation, structure representation, and texture representation. The surface representation refers to the smooth surface of the images. The structure representation relates to the sparse colour blocks and compresses generic content. The texture representation shows the texture, curves, and features in cartoon images. Generative Adversarial Network (GAN) framework decomposes the images into different representations and learns from them to generate cartoon images. This decomposition makes the framework more controllable and flexible which allows users to make changes based on the required output. This approach overcomes any previous system in terms of maintaining clarity, colours, textures, shapes of images yet showing the characteristics of cartoon images.
Photonic Extreme Learning Machine based on frequency multiplexing
Venue: arXiv cs.ET 2021
Year: 2021

The optical domain is a promising field for physical implementation of neural networks, due to the speed and parallelism of optics. Extreme Learning Machines (ELMs) are feed-forward neural networks in which only output weights are trained, while internal connections are randomly selected and left untrained. Here we report on a photonic ELM based on a frequency-multiplexed fiber setup. Multiplication by output weights can be performed either offline on a computer, or optically by a programmable spectral filter. We present both numerical simulations and experimental results on classification tasks and a nonlinear channel equalization task.
Cumulative Assessment for Urban 3D Modeling
Venue: arXiv cs.CV 2021
Year: 2021

Urban 3D modeling from satellite images requires accurate semantic segmentation to delineate urban features, multiple view stereo for 3D reconstruction of surface heights, and 3D model fitting to produce compact models with accurate surface slopes. In this work, we present a cumulative assessment metric that succinctly captures error contributions from each of these components. We demonstrate our approach by providing challenging public datasets and extending two open source projects to provide an end-to-end 3D modeling baseline solution to stimulate further research and evaluation with a public leaderboard.
Efficient Real-Time Image Recognition Using Collaborative Swarm of UAVs and Convolutional Networks
Venue: arXiv cs.CV 2021
Year: 2021

Unmanned Aerial Vehicles (UAVs) have recently attracted significant attention due to their outstanding ability to be used in different sectors and serve in difficult and dangerous areas. Moreover, the advancements in computer vision and artificial intelligence have increased the use of UAVs in various applications and solutions, such as forest fires detection and borders monitoring. However, using deep neural networks (DNNs) with UAVs introduces several challenges of processing deeper networks and complex models, which restricts their on-board computation. In this work, we present a strategy aiming at distributing inference requests to a swarm of resource-constrained UAVs that classifies captured images on-board and finds the minimum decision-making latency. We formulate the model as an optimization problem that minimizes the latency between acquiring images and making the final decisions. The formulated optimization solution is an NP-hard problem. Hence it is not adequate for online resource allocation. Therefore, we introduce an online heuristic solution, namely DistInference, to find the layers placement strategy that gives the best latency among the available UAVs. The proposed approach is general enough to be used for different low decision-latency applications as well as for all CNN types organized into the pipeline of layers (e.g., VGG) or based on residual blocks (e.g., ResNet).
Optimal Space and Time for Streaming Pattern Matching
Venue: arXiv cs.DS 2021
Year: 2021

In this work, we study longest common substring, pattern matching, and wildcard pattern matching in the asymmetric streaming model. In this streaming model, we have random access to one string and streaming access to the other one. We present streaming algorithms with provable guarantees for these three fundamental problems. In particular, our algorithms for pattern matching improve the upper bound and beat the unconditional lower bounds on the memory of randomized and deterministic streaming algorithms. In addition to this, we present algorithms for wildcard pattern matching in the asymmetric streaming model that have optimal space and time.
Preserving Diversity when Partitioning: A Geometric Approach
Venue: arXiv cs.DM 2021
Year: 2021

Diversity plays a crucial role in multiple contexts such as team formation, representation of minority groups and generally when allocating resources fairly. Given a community composed by individuals of different types, we study the problem of partitioning this community such that the global diversity is preserved as much as possible in each subgroup. We consider the diversity metric introduced by Simpson in his influential work that, roughly speaking, corresponds to the inverse probability that two individuals are from the same type when taken uniformly at random, with replacement, from the community of interest. We provide a novel perspective by reinterpreting this quantity in geometric terms. We characterize the instances in which the optimal partition exactly preserves the global diversity in each subgroup. When this is not possible, we provide an efficient polynomial-time algorithm that outputs an optimal partition for the problem with two types. Finally, we discuss further challenges and open questions for the problem that considers more than two types.
A Survey on Personal Image Retrieval Systems
Venue: arXiv cs.HC 2021
Year: 2021

The number of photographs taken worldwide is growing rapidly and steadily. While a small subset of these images is annotated and shared by users through social media platforms, due to the sheer number of images in personal photo repositories (shared or not shared), finding specific images remains challenging. This survey explores existing image retrieval techniques as well as photo-organizer applications to highlight their relative strengths in addressing this challenge.
An Initial Investigation of Non-Native Spoken Question-Answering
Venue: arXiv cs.CL 2021
Year: 2021

Text-based machine comprehension (MC) systems have a wide-range of applications, and standard corpora exist for developing and evaluating approaches. There has been far less research on spoken question answering (SQA) systems. The SQA task considered in this paper is to extract the answer from a candidate$\text{'}$s spoken response to a question in a prompt-response style language assessment test. Applying these MC approaches to this SQA task rather than, for example, off-topic response detection provides far more detailed information that can be used for further downstream processing. One significant challenge is the lack of appropriately annotated speech corpora to train systems for this task. Hence, a transfer-learning style approach is adopted where a system trained on text-based MC is evaluated on an SQA task with non-native speakers. Mismatches must be considered between text documents and spoken responses; non-native spoken grammar and written grammar. In practical SQA, ASR systems are used, necessitating an investigation of the impact of ASR errors. We show that a simple text-based ELECTRA MC model trained on SQuAD2.0 transfers well for SQA. It is found that there is an approximately linear relationship between ASR errors and the SQA assessment scores but grammar mismatches have minimal impact.
Approximation algorithms for the directed path partition problems
Venue: arXiv cs.DS 2021
Year: 2021

Given a directed graph $G = (V, E)$, the $k$-path partition problem is to find a minimum collection of vertex-disjoint directed paths each of order at most $k$ to cover all the vertices of $V$. The problem has various applications in facility location, network monitoring, transportation and others. Its special case on undirected graphs has received much attention recently, but the general directed version is seemingly untouched in the literature. We present the first $k/2$-approximation algorithm, for any $k \ge 3$, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When $k \ge 7$, we present an improved $(k+2)/3$-approximation algorithm based on the maximum path-cycle cover followed by a careful $2$-cycle elimination process. When $k = 3$, we define the second novel kind of augmenting paths and propose an improved $13/9$-approximation algorithm.
On the Nature of Code Cloning in Open-Source Java Projects
Venue: arXiv cs.SE 2021
Year: 2021

Code cloning plays a very important role in open-source software engineering. The presence of clones within a project may indicate a need for refactoring, and clones between projects are even more interesting, since code migration takes place and violations are possible. But how is code being copied? How prevalent is the process and on what level does it happen? In this general study, we attempt to shed some light on these questions by searching for clones in a large dataset of over 23 thousand Java projects on the level of both files and methods, and by studying the code fragments themselves and their clone pairs. We study the size and the age of code fragments, the prevalence of their clones, relationships between exact and non-exact clones, as well as between method-level and file-level clones. We also discover and describe various anomalies in the code clones that were detected in the dataset. Our research shows that the copying occurs all through the years of the Java code existence and that method-level copying is much more prevalent than file-level copying, with only 35.4% of methods having no clones at all. Additionally, some of the discovered anomalies can be useful for future large-scale cloning research as they can be used for removing auto-generated code.
Hitting Weighted Even Cycles in Planar Graphs
Venue: arXiv cs.DS 2021
Year: 2021

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph $G$ which intersects all copies of subgraphs~$F$ from a fixed family $\mathcal F$. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs $G$, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (\ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is $Θ(\log n)$, and that adding sparsity inequalities reduces the integrality gap to~10. Our main result is a primal-dual algorithm that yields a $47/7\approx6.71$-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs.