OpenRaiser/Intern-Atlas huggingface dataset:
On Dominance-Free Samples of a (Colored) Stochastic Dataset
Venue: arXiv cs.CG 2020
Year: 2020

A point $p \in \mathbb{R}^d$ is said to dominate another point $q \in \mathbb{R}^d$ if the coordinate of $p$ is greater than or equal to the coordinate of $q$ in every dimension. A set of points in $\mathbb{R}^d$ is dominance-free if any two points do not dominate each other. We consider the problem of counting the dominance-free subsets of a given dataset in $\mathbb{R}^d$, or more generally, computing the probability that a random sample of a stochastic dataset in $\mathbb{R}^d$ where each point is sampled independently with its existence probability is dominance-free. In fact, we investigate a colored generalization of the problem, in which the points in the given stochastic dataset are colored and we are interested in the random samples that are inter-color dominance-free (i.e., any two points with different colors do not dominate each other). We propose the first algorithm that solves the problem for $d=2$ in near-quadratic time. On the other hand, we show that the problem is #P-hard for any $d \geq 3$, even if the points have a restricted color pattern; this implies the #P-hardness of the uncolored version (i.e., computing the dominance-free probability of a uncolored stochastic dataset) for $d \geq 3$. In addition, we show that even when the existence probabilities of the points are all equal to 0.5, the problem remains #P-hard for any $d \geq 7$; this implies the #P-hardness of counting dominance-free subsets for $d \geq 7$. In order to prove our hardness results, we establish some results about embedding the vertices a graph into low-dimensional Euclidean space such that two vertices are connected by an edge in the graph iff they form a dominance pair in the embedding. These results may be of independent interest and can possibly be applied to other problems.
Aggressive Congestion Control Mechanism for Space Systems
Venue: arXiv cs.NI 2020
Year: 2020

How to implement an impeccable space system-of-systems (SoS) internetworking architecture has been a significant issue in system engineering for years. Reliable data transmission is considered one of the most important technologies of space SoS internetworking systems. Due to the high bit error rate (BER), long time delay and asymmetrical channel in the space communication environment, the congestion control mechanism of classic transport control protocols (TCP) shows unsatisfying performances. With the help of existing TCP modifications, this paper contributes an aggressive congestion control mechanism. The proposed mechanism is characterized with a fast start procedure, as well as the feedback information to analyze network traffic and with a link terminating processing mechanism, which can help to reveal the real reason of packet loss, and maintain the size of congestion window at a high level. Simulation results are shown in the end to verify the proposed scheme.
Access Strategy in Super WiFi Network Powered by Solar Energy Harvesting: A POMDP Method
Venue: arXiv cs.IT 2020
Year: 2020

The recently announced Super Wi-Fi Network proposal in United States is aiming to enable Internet access in a nation-wide area. As traditional cable-connected power supply system becomes impractical or costly for a wide range wireless network, new infrastructure deployment for Super Wi-Fi is required. The fast developing Energy Harvesting (EH) techniques receive global attentions for their potential of solving the above power supply problem. It is a critical issue, from the user's perspective, how to make efficient network selection and access strategies. Unlike traditional wireless networks, the battery charge state and tendency in EH based networks have to be taken into account when making network selection and access, which has not been well investigated. In this paper, we propose a practical and efficient framework for multiple base stations access strategy in an EH powered Super Wi-Fi network. We consider the access strategy from the user's perspective, who exploits downlink transmission opportunities from one base station. To formulate the problem, we used Partially Observable Markov Decision Process (POMDP) to model users' observations on the base stations' battery situation and decisions on the base station selection and access. Simulation results show that our methods are efficacious and significantly outperform the traditional widely used CSMA method.
Domains and Event Structures for Fusions
Venue: arXiv cs.LO 2020
Year: 2020

Stable event structures, and their duality with prime algebraic domains arising as partial orders of configurations, are a landmark of concurrency theory, providing a clear characterisation of causality in computations. They have been used for defining a concurrent semantics of several formalisms, from Petri nets to (linear) graph rewriting systems, which in turn lay at the basis of many visual modelling frameworks. Stability however is restrictive when dealing with formalisms with "fusion", i.e., where a computational step can not only consume and produce but also merge parts of the state. This happens, e.g., for graph rewriting systems with non-linear rules, which are needed to cover some relevant applications (such as the graphical encoding of calculi with name passing). Guided by the need of capturing the semantics of formalisms with fusion we leave aside stability and we characterise, as a natural generalisation of prime algebraic domains, a class of domains, referred to as weak prime domains. We then identify a corresponding class of event structures, that we call connected event structures, via a duality result formalised as an equivalence of categories. We show that connected event structures are exactly the class of event structures that arise as the semantics of non-linear graph rewriting systems. Interestingly, the category of general unstable event structures coreflects into our category of weak prime domains, so that our result provides a characterisation of the partial orders of configurations of such event structures.
Heterogeneous domain adaptation: An unsupervised approach
Venue: arXiv cs.LG 2020
Year: 2020

Domain adaptation leverages the knowledge in one domain - the source domain - to improve learning efficiency in another domain - the target domain. Existing heterogeneous domain adaptation research is relatively well-progressed, but only in situations where the target domain contains at least a few labeled instances. In contrast, heterogeneous domain adaptation with an unlabeled target domain has not been well-studied. To contribute to the research in this emerging field, this paper presents: (1) an unsupervised knowledge transfer theorem that guarantees the correctness of transferring knowledge; and (2) a principal angle-based metric to measure the distance between two pairs of domains: one pair comprises the original source and target domains and the other pair comprises two homogeneous representations of two domains. The theorem and the metric have been implemented in an innovative transfer model, called a Grassmann-Linear monotonic maps-geodesic flow kernel (GLG), that is specifically designed for heterogeneous unsupervised domain adaptation (HeUDA). The linear monotonic maps meet the conditions of the theorem and are used to construct homogeneous representations of the heterogeneous domains. The metric shows the extent to which the homogeneous representations have preserved the information in the original source and target domains. By minimizing the proposed metric, the GLG model learns the homogeneous representations of heterogeneous domains and transfers knowledge through these learned representations via a geodesic flow kernel. To evaluate the model, five public datasets were reorganized into ten HeUDA tasks across three applications: cancer detection, credit assessment, and text classification. The experiments demonstrate that the proposed model delivers superior performance over the existing baselines.
Almost Optimal Phaseless Compressed Sensing with Sublinear Decoding Time
Venue: arXiv cs.IT 2020
Year: 2020

In the problem of compressive phase retrieval, one wants to recover an approximately $k$-sparse signal $x \in \mathbb{C}^n$, given the magnitudes of the entries of $Φx$, where $Φ\in \mathbb{C}^{m \times n}$. This problem has received a fair amount of attention, with sublinear time algorithms appearing in \cite{cai2014super,pedarsani2014phasecode,yin2015fast}. In this paper we further investigate the direction of sublinear decoding for real signals by giving a recovery scheme under the $\ell_2 / \ell_2$ guarantee, with almost optimal, $\Oh(k \log n )$, number of measurements. Our result outperforms all previous sublinear-time algorithms in the case of real signals. Moreover, we give a very simple deterministic scheme that recovers all $k$-sparse vectors in $\Oh(k^3)$ time, using $4k-1$ measurements.
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries
Venue: arXiv cs.DB 2020
Year: 2020

Our concern is the overhead of answering OWL 2 QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and bounded treewidth conjunctive queries (CQs). We show that OMQs with bounded-depth ontologies have nonrecursive datalog (NDL) rewritings that can be constructed and evaluated in LOGCFL for combined complexity, even in NL if their CQs are tree-shaped with a bounded number of leaves, and so incur no overhead in complexity-theoretic terms. For OMQs with arbitrary ontologies and bounded-leaf CQs, NDL-rewritings are constructed and evaluated in LOGCFL. We show experimentally feasibility and scalability of our rewritings compared to previously proposed NDL-rewritings. On the negative side, we prove that answering OMQs with tree-shaped CQs is not fixed-parameter tractable if the ontology depth or the number of leaves in the CQs is regarded as the parameter, and that answering OMQs with a fixed ontology (of infinite depth) is NP-complete for tree-shaped and LOGCFL for bounded-leaf CQs.
On the Expected Value of the Determinant of Random Sum of Rank-One Matrices
Venue: arXiv cs.DS 2020
Year: 2020

We present a simple, yet useful result about the expected value of the determinant of random sum of rank-one matrices. Computing such expectations in general may involve a sum over exponentially many terms. Nevertheless, we show that an interesting and useful class of such expectations that arise in, e.g., D-optimal estimation and random graphs can be computed efficiently via computing a single determinant.
Zero-Shot Learning -- The Good, the Bad and the Ugly
Venue: arXiv cs.CV 2020
Year: 2020

Due to the importance of zero-shot learning, the number of proposed approaches has increased steadily recently. We argue that it is time to take a step back and to analyze the status quo of the area. The purpose of this paper is three-fold. First, given the fact that there is no agreed upon zero-shot learning benchmark, we first define a new benchmark by unifying both the evaluation protocols and data splits. This is an important contribution as published results are often not comparable and sometimes even flawed due to, e.g. pre-training on zero-shot test classes. Second, we compare and analyze a significant number of the state-of-the-art methods in depth, both in the classic zero-shot setting but also in the more realistic generalized zero-shot setting. Finally, we discuss limitations of the current status of the area which can be taken as a basis for advancing it.
Scalable Content Delivery with Coded Caching in Multi-Antenna Fading Channels
Venue: arXiv cs.IT 2020
Year: 2020

We consider the content delivery problem in a fading multi-input single-output channel with cache-aided users. We are interested in the scalability of the equivalent content delivery rate when the number of users, $K$, is large. Analytical results show that, using coded caching and wireless multicasting, without channel state information at the transmitter (CSIT), linear scaling of the content delivery rate with respect to $K$ can be achieved in some different ways. First, if the multicast transmission spans over $L$ independent sub-channels, e.g., in quasi-static fading if $L = 1$, and in block fading or multi-carrier systems if $L>1$, linear scaling can be obtained when the product of the number of transmit antennas and the number of sub-channels scales logarithmically with $K$. Second, even with a fixed number of antennas, we can achieve the linear scaling with a threshold-based user selection requiring only one-bit feedbacks from the users. When CSIT is available, we propose a mixed strategy that combines spatial multiplexing and multicasting. Numerical results show that, by optimizing the power split between spatial multiplexing and multicasting, we can achieve a significant gain of the content delivery rate with moderate cache size.
Hierarchic Kernel Recursive Least-Squares
Venue: arXiv cs.LG 2020
Year: 2020

We present a new kernel-based algorithm for modeling evenly distributed multidimensional datasets that does not rely on input space sparsification. The presented method reorganizes the typical single-layer kernel-based model into a deep hierarchical structure, such that the weights of a kernel model over each dimension are modeled over its adjacent dimension. We show that modeling weights in the suggested structure leads to significant computational speedup and improved modeling accuracy.
Graph Convolutional Encoders for Syntax-aware Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

We present a simple and effective approach to incorporating syntactic structure into neural attention-based encoder-decoder models for machine translation. We rely on graph-convolutional networks (GCNs), a recent class of neural networks developed for modeling graph-structured data. Our GCNs use predicted syntactic dependency trees of source sentences to produce representations of words (i.e. hidden states of the encoder) that are sensitive to their syntactic neighborhoods. GCNs take word representations as input and produce word representations as output, so they can easily be incorporated as layers into standard encoders (e.g., on top of bidirectional RNNs or convolutional neural networks). We evaluate their effectiveness with English-German and English-Czech translation experiments for different types of encoders and observe substantial improvements over their syntax-agnostic versions in all the considered setups.
Softmax GAN
Venue: arXiv cs.LG 2020
Year: 2020

Softmax GAN is a novel variant of Generative Adversarial Network (GAN). The key idea of Softmax GAN is to replace the classification loss in the original GAN with a softmax cross-entropy loss in the sample space of one single batch. In the adversarial learning of $N$ real training samples and $M$ generated samples, the target of discriminator training is to distribute all the probability mass to the real samples, each with probability $\frac{1}{M}$, and distribute zero probability to generated data. In the generator training phase, the target is to assign equal probability to all data points in the batch, each with probability $\frac{1}{M+N}$. While the original GAN is closely related to Noise Contrastive Estimation (NCE), we show that Softmax GAN is the Importance Sampling version of GAN. We futher demonstrate with experiments that this simple change stabilizes GAN training.
An Integrated Decision and Control Theoretic Solution to Multi-Agent Co-Operative Search Problems
Venue: arXiv cs.RO 2020
Year: 2020

This paper considers the problem of autonomous multi-agent cooperative target search in an unknown environment using a decentralized framework under a no-communication scenario. The targets are considered as static targets and the agents are considered to be homogeneous. The no-communication scenario translates as the agents do not exchange either the information about the environment or their actions among themselves. We propose an integrated decision and control theoretic solution for a search problem which generates feasible agent trajectories. In particular, a perception based algorithm is proposed which allows an agent to estimate the probable strategies of other agents' and to choose a decision based on such estimation. The algorithm shows robustness with respect to the estimation accuracy to a certain degree. The performance of the algorithm is compared with random strategies and numerical simulation shows considerable advantages.
Dynamic algorithms for visibility polygons in simple polygons
Venue: arXiv cs.CG 2020
Year: 2020

We devise the following dynamic algorithms for both maintaining as well as querying for the visibility and weak visibility polygons amid vertex insertions and/or deletions to the simple polygon. * A fully-dynamic algorithm for maintaining the visibility polygon of a fixed point located interior to the simple polygon amid vertex insertions and deletions to the simple polygon. The time complexity to update the visibility polygon of a point $q$ due to the insertion (resp. deletion) of vertex $v$ to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of $q$ due to the insertion (resp. deletion) of $v$. * An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point $p$ in $\mathbb{R}^2$ amid vertex insertions and deletions to the simple polygon. If $p$ is not exterior to the current simple polygon, then the visibility polygon of $p$ is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of $p$. * An incremental algorithm to maintain the weak visibility polygon of a fixed-line segment located interior to the simple polygon amid vertex insertions to the simple polygon. The time complexity to update the weak visibility polygon of a line segment $pq$ due to the insertion of vertex $v$ to the current simple polygon is expressed in terms of the sum of the number of combinatorial updates needed to the geodesic shortest path trees rooted at $p$ and $q$ due to the insertion of $v$. * An output-sensitive algorithm to compute the weak visibility polygon corresponding to any query line segment located interior to the simple polygon amid both the vertex insertions and deletions to the simple polygon. Each of these algorithms requires preprocessing the initial simple polygon.
On Bayesian Fisher Information Maximization for Distributed Vector Estimation
Venue: arXiv cs.IT 2020
Year: 2020

We consider the problem of distributed estimation of a Gaussian vector with linear observation model. Each sensor makes a scalar noisy observation of the unknown vector, quantizes its observation, maps it to a digitally modulated symbol, and transmits the symbol over orthogonal power-constrained fading channels to a fusion center (FC). The FC is tasked with fusing the received signals from sensors and estimating the unknown vector. We derive the Bayesian Fisher Information Matrix (FIM) for three types of receivers: (i) coherent receiver (ii) noncoherent receiver with known channel envelopes (iii) noncoherent receiver with known channel statistics only. We also derive the Weiss-Weinstein bound (WWB). We formulate two constrained optimization problems, namely maximizing trace and log-determinant of Bayesian FIM under network transmit power constraint, with sensors transmit powers being the optimization variables. We show that for coherent receiver, these problems are concave. However, for noncoherent receivers, they are not necessarily concave. The solution to the trace of Bayesian FIM maximization problem can be implemented in a distributed fashion. We numerically investigate how the FIM-max power allocation across sensors depends on the sensors observation qualities and physical layer parameters as well as the network transmit power constraint. Moreover, we evaluate the system performance in terms of MSE using the solutions of FIM-max schemes, and compare it with the solution obtained from minimizing the MSE of the LMMSE estimator (MSE-min scheme), and that of uniform power allocation. These comparisons illustrate that, although the WWB is tighter than the inverse of Bayesian FIM, it is still suitable to use FIM-max schemes, since the performance loss in terms of the MSE of the LMMSE estimator is not significant.
On linear weak predictability with single point spectrum degeneracy
Venue: arXiv cs.IT 2020
Year: 2020

The paper studies properties of continuous time processes with spectrum degeneracy at a single point where their Fourier transforms vanish with a certain rate. It appears that these processes are linearly predictable in some weak sense, meaning that convolution integrals over future times can be approximated by causal convolutions over past times. The corresponding predicting kernels are time invariant, and they are presented explicitly in the frequency domain via their transfer functions. These predictors are "universal" meaning that they do not require to know details of the spectrum of the underlying processes; the same predictor can be used for the entire class of processes with a single point spectrum degeneracy. The predictors feature some robustness with respect to noise contamination.
Weighted Regular Tree Grammars with Storage
Venue: arXiv cs.FL 2020
Year: 2020

We introduce weighted regular tree grammars with storage as combination of (a) regular tree grammars with storage and (b) weighted tree automata over multioperator monoids. Each weighted regular tree grammar with storage generates a weighted tree language, which is a mapping from the set of trees to the multioperator monoid. We prove that, for multioperator monoids canonically associated to particular strong bi-monoids, the support of the generated weighted tree languages can be generated by (unweighted) regular tree grammars with storage. We characterize the class of all generated weighted tree languages by the composition of three basic concepts. Moreover, we prove results on the elimination of chain rules and of finite storage types, and we characterize weighted regular tree grammars with storage by a new weighted MSO-logic.
Taming Near Repeat Calculation for Crime Analysis via Cohesive Subgraph Computing
Venue: arXiv cs.DS 2020
Year: 2020

Near repeat (NR) is a well known phenomenon in crime analysis assuming that crime events exhibit correlations within a given time and space frame. Traditional NR calculation generates 2 event pairs if 2 events happened within a given space and time limit. When the number of events is large, however, NR calculation is time consuming and how these pairs are organized are not yet explored. In this paper, we designed a new approach to calculate clusters of NR events efficiently. To begin with, R-tree is utilized to index crime events, a single event is represented by a vertex whereas edges are constructed by range querying the vertex in R-tree, and a graph is formed. Cohesive subgraph approaches are applied to identify the event chains. k-clique, k-truss, k-core plus DBSCAN algorithms are implemented in sequence with respect to their varied range of ability to find cohesive subgraphs. Real world crime data in Chicago, New York and Washington DC are utilized to conduct experiments. The experiment confirmed that near repeat is a solid effect in real big crime data by conducting Mapreduce empowered knox tests. The performance of 4 different algorithms are validated, while the quality of the algorithms are gauged by the distribution of number of cohesive subgraphs and their clustering coefficients. The proposed framework is the first to process the real crime data of million record scale, and is the first to detect NR events with size of more than 2.