OpenRaiser/Intern-Atlas huggingface dataset:
The Dispersion of the Gauss-Markov Source
Venue: arXiv cs.IT 2019
Year: 2019

The Gauss-Markov source produces $U_i = aU_{i-1} + Z_i$ for $i\geq 1$, where $U_0 = 0$, $|a|<1$ and $Z_i\sim\mathcal{N}(0, σ^2)$ are i.i.d. Gaussian random variables. We consider lossy compression of a block of $n$ samples of the Gauss-Markov source under squared error distortion. We obtain the Gaussian approximation for the Gauss-Markov source with excess-distortion criterion for any distortion $d>0$, and we show that the dispersion has a reverse waterfilling representation. This is the \emph{first} finite blocklength result for lossy compression of \emph{sources with memory}. We prove that the finite blocklength rate-distortion function $R(n,d,ε)$ approaches the rate-distortion function $\mathbb{R}(d)$ as $R(n,d,ε) = \mathbb{R}(d) + \sqrt{\frac{V(d)}{n}}Q^{-1}(ε) + o\left(\frac{1}{\sqrt{n}}\right)$, where $V(d)$ is the dispersion, $ε\in (0,1)$ is the excess-distortion probability, and $Q^{-1}$ is the inverse of the $Q$-function. We give a reverse waterfilling integral representation for the dispersion $V(d)$, which parallels that of the rate-distortion functions for Gaussian processes. Remarkably, for all $0 < d\leq \frac{σ^2}{(1+|a|)^2}$, $R(n,d,ε)$ of the Gauss-Markov source coincides with that of $Z_k$, the i.i.d. Gaussian noise driving the process, up to the second-order term. Among novel technical tools developed in this paper is a sharp approximation of the eigenvalues of the covariance matrix of $n$ samples of the Gauss-Markov source, and a construction of a typical set using the maximum likelihood estimate of the parameter $a$ based on $n$ observations.
On the satisfiability problem for fragments of the two-variable logic with one transitive relation
Venue: arXiv cs.LO 2019
Year: 2019

We study the satisfiability problem for the two-variable first-order logic over structures with one transitive relation. % We show that the problem is decidable in 2-NExpTime for the fragment consisting of formulas where existential quantifiers are guarded by transitive atoms. As this fragment enjoys neither the finite model nor the tree model property, to show decidability we introduce novel model construction technique based on the infinite Ramsey theorem. We also point out why the technique is not sufficient to obtain decidability for the full two-variable logic with one transitive relation, hence contrary to our previous claim, [FO$^2$ with one transitive relation is decidable, STACS 2013: 317-328], the status of the latter problem remains open.
Emergence of integrated institutions in a large population of self-governing communities
Venue: arXiv cs.SI 2019
Year: 2019

Most aspects of our lives are governed by large, highly developed institutions that integrate several governance tasks under one authority structure. But theorists differ as to the mechanisms that drive the development of such concentrated governance systems from rudimentary beginnings. Is the emergence of integrated governance schemes a symptom of consolidation of authority by small status groups? Or does integration occur because a complex institution has more potential responses to a complex environment? Here we examine the emergence of complex governance regimes in 5,000 sovereign, resource-constrained, self-governing online communities, ranging in scale from one to thousands of users. Each community begins with no community members and no governance infrastructure. As communities grow, they are subject to selection pressures that keep better managed servers better populated. We identify predictors of community success and test the hypothesis that governance complexity can enhance community fitness. We find that what predicts success depends on size: changes in complexity predict increased success with larger population servers. Specifically, governance rules in a large successful community are more numerous and broader in scope. They also tend to rely more on rules that concentrate power in administrators, and on rules that manage bad behavior and limited server resources. Overall, this work is consistent with theories that formal integrated governance systems emerge to organize collective responses to interdependent resource management problems, especially as factors such as population size exacerbate those problems.
Rateless Codes for Near-Perfect Load Balancing in Distributed Matrix-Vector Multiplication
Venue: arXiv cs.DC 2019
Year: 2019

Large-scale machine learning and data mining applications require computer systems to perform massive matrix-vector and matrix-matrix multiplication operations that need to be parallelized across multiple nodes. The presence of straggling nodes -- computing nodes that unpredictably slowdown or fail -- is a major bottleneck in such distributed computations. Ideal load balancing strategies that dynamically allocate more tasks to faster nodes require knowledge or monitoring of node speeds as well as the ability to quickly move data. Recently proposed fixed-rate erasure coding strategies can handle unpredictable node slowdown, but they ignore partial work done by straggling nodes thus resulting in a lot of redundant computation. We propose a \emph{rateless fountain coding} strategy that achieves the best of both worlds -- we prove that its latency is asymptotically equal to ideal load balancing, and it performs asymptotically zero redundant computations. Our idea is to create linear combinations of the $m$ rows of the matrix and assign these encoded rows to different worker nodes. The original matrix-vector product can be decoded as soon as slightly more than $m$ row-vector products are collectively finished by the nodes. We conduct experiments in three computing environments: local parallel computing, Amazon EC2, and Amazon Lambda, which show that rateless coding gives as much as $3\times$ speed-up over uncoded schemes.
The Category TOF
Venue: arXiv cs.LO 2019
Year: 2019

We provide a complete set of identities for the symmetric monoidal category, TOF, generated by the Toffoli gate and computational ancillary bits. We do so by demonstrating that the functor which evaluates circuits on total points, is an equivalence into the full subcategory of sets and partial isomorphisms with objects finite powers of the two element set. The structure of the proof builds -- and follows the proof of Cockett et al.-- which provided a full set of identities for the cnot gate with computational ancillary bits. Thus, first it is shown that TOF is a discrete inverse category in which all of the identities for the cnot gate hold; and then a normal form for the restriction idempotents is constructed which corresponds precisely to subobjects of the total points of TOF. This is then used to show that TOF is equivalent to FPinj2, the full subcategory of sets and partial isomorphisms in which objects have cardinality a power of 2.
Hidden Vehicle Sensing via Asynchronous V2V Transmission: A Multi-Path-Geometry Approach
Venue: arXiv cs.IT 2019
Year: 2019

Accurate vehicular sensing is a basic and important operation in autonomous driving. Unfortunately, the existing techniques have their own limitations. For instance, the communication-based approach (e.g., transmission of GPS information) has high latency and low reliability while the reflection-based approach (e.g., RADAR) is incapable of detecting hidden vehicles (HVs) without line-of-sight. This is arguably the reason behind some recent fatal accidents involving autonomous vehicles. To address this issue, this paper presents a novel HV-sensing technology that exploits multi-path transmission from a HV to a sensing vehicle (SV). The powerful technology enables the SV to detect multiple HV-state parameters including position, orientation of driving direction, and size. Its implementation does not even require transmitter-receiver synchronization like conventional mobile positioning techniques. Our design approach leverages estimated information on multi-path (AoA/AoD/ToA) and their geometric relations. As a result, a complex system of equations or optimization problems, where the desired HV-state parameters are variables, can be formulated for different channel-noise conditions. The development of intelligent solution methods ranging from least-square estimator to disk/box minimization yields a set of practical HV-sensing techniques. We study their feasibility conditions in terms of the required number of paths. Furthermore, practical solutions, including sequential path combining and random directional beamforming, are proposed to enable HV-sensing given insufficient paths. Last, realistic simulation of driving in both highway and rural scenarios demonstrates the effectiveness of the proposed techniques. In summary, the proposed technique will enhance the capabilities of existing vehicular sensing technologies by enabling HV-sensing.
Dilated Temporal Relational Adversarial Network for Generic Video Summarization
Venue: arXiv cs.CV 2019
Year: 2019

The large amount of videos popping up every day, make it more and more critical that key information within videos can be extracted and understood in a very short time. Video summarization, the task of finding the smallest subset of frames, which still conveys the whole story of a given video, is thus of great significance to improve efficiency of video understanding. We propose a novel Dilated Temporal Relational Generative Adversarial Network (DTR-GAN) to achieve frame-level video summarization. Given a video, it selects the set of key frames, which contain the most meaningful and compact information. Specifically, DTR-GAN learns a dilated temporal relational generator and a discriminator with three-player loss in an adversarial manner. A new dilated temporal relation (DTR) unit is introduced to enhance temporal representation capturing. The generator uses this unit to effectively exploit global multi-scale temporal context to select key frames and to complement the commonly used Bi-LSTM. To ensure that summaries capture enough key video representation from a global perspective rather than a trivial randomly shorten sequence, we present a discriminator that learns to enforce both the information completeness and compactness of summaries via a three-player loss. The loss includes the generated summary loss, the random summary loss, and the real summary (ground-truth) loss, which play important roles for better regularizing the learned model to obtain useful summaries. Comprehensive experiments on three public datasets show the effectiveness of the proposed approach.
Simple Distances for Trajectories via Landmarks
Venue: arXiv cs.CG 2019
Year: 2019

We develop a new class of distances for objects including lines, hyperplanes, and trajectories, based on the distance to a set of landmarks. These distances easily and interpretably map objects to a Euclidean space, are simple to compute, and perform well in data analysis tasks. For trajectories, they match and in some cases significantly out-perform all state-of-the-art other metrics, can effortlessly be used in k-means clustering, and directly plugged into approximate nearest neighbor approaches which immediately out-perform the best recent advances in trajectory similarity search by several orders of magnitude. These distances do not require a geometry distorting dual (common in the line or halfspace case) or complicated alignment (common in trajectory case). We show reasonable and often simple conditions under which these distances are metrics.
Checking is Believing: Event-Aware Program Anomaly Detection in Cyber-Physical Systems
Venue: arXiv cs.CR 2019
Year: 2019

Securing cyber-physical systems (CPS) against malicious attacks is of paramount importance because these attacks may cause irreparable damages to physical systems. Recent studies have revealed that control programs running on CPS devices suffer from both control-oriented attacks (e.g., code-injection or code-reuse attacks) and data-oriented attacks (e.g., non-control data attacks). Unfortunately, existing detection mechanisms are insufficient to detect runtime data-oriented exploits, due to the lack of runtime execution semantics checking. In this work, we propose Orpheus, a new security methodology for defending against data-oriented attacks by enforcing cyber-physical execution semantics. We first present a general method for reasoning cyber-physical execution semantics of a control program (i.e., causal dependencies between the physical context and program control flows), including the event identification and dependence analysis. As an instantiation of Orpheus, we then present a new program behavior model, i.e., the event-aware finite-state automaton (eFSA). eFSA takes advantage of the event-driven nature of CPS control programs and incorporates event checking in anomaly detection. It detects data-oriented exploits if a specific physical event is missing along with the corresponding event dependent state transition. We evaluate our prototype's performance by conducting case studies under data-oriented attacks. Results show that eFSA can successfully detect different runtime attacks. Our prototype on Raspberry Pi incurs a low overhead, taking 0.0001s for each state transition integrity checking, and 0.063s~0.211s for the cyber-physical contextual consistency checking.
Dynamic Sentence Sampling for Efficient Training of Neural Machine Translation
Venue: arXiv cs.CL 2019
Year: 2019

Traditional Neural machine translation (NMT) involves a fixed training procedure where each sentence is sampled once during each epoch. In reality, some sentences are well-learned during the initial few epochs; however, using this approach, the well-learned sentences would continue to be trained along with those sentences that were not well learned for 10-30 epochs, which results in a wastage of time. Here, we propose an efficient method to dynamically sample the sentences in order to accelerate the NMT training. In this approach, a weight is assigned to each sentence based on the measured difference between the training costs of two iterations. Further, in each epoch, a certain percentage of sentences are dynamically sampled according to their weights. Empirical results based on the NIST Chinese-to-English and the WMT English-to-German tasks depict that the proposed method can significantly accelerate the NMT training and improve the NMT performance.
Localization: A Missing Link in the Pipeline of Object Matching and Registration
Venue: arXiv cs.CV 2019
Year: 2019

Image registration is a process of aligning two or more images of same objects using geometric transformation. Most of the existing approaches work on the assumption of location invariance. These approaches require object-centric images to perform matching. Further, in absence of intensity level symmetry between the corresponding points in two images, the learning based registration approaches rely on synthetic deformations, which often fail in real scenarios. To address these issues, a combination of convolutional neural networks (CNNs) to perform the desired registration is developed in this work. The complete objective is divided into three sub-objectives: object localization, segmentation and matching transformation. Object localization step establishes an initial correspondence between the images. A modified version of single shot multi-box detector is used for this purpose. The detected region is cropped to make the images object-centric. Subsequently, the objects are segmented and matched using a spatial transformer network employing thin plate spline deformation. Initial experiments on MNIST and Caltech-101 datasets show that the proposed model is able to produce accurate matching. Quantitative evaluation performed using dice coefficient (DC) and mean intersection over union (mIoU) show that proposed method results in the values of 79% and 66%, respectively for MNIST dataset and the values of 94% and 90%, respectively for Caltech-101 dataset. The proposed framework is extended to the registration of CT and US images, which is free from any data specific assumptions and has better generalization capability as compared to the existing rule-based/classical approaches.
Hyperparameter Optimization for Effort Estimation
Venue: arXiv cs.SE 2019
Year: 2019

Software analytics has been widely used in software engineering for many tasks such as generating effort estimates for software projects. One of the "black arts" of software analytics is tuning the parameters controlling a data mining algorithm. Such hyperparameter optimization has been widely studied in other software analytics domains (e.g. defect prediction and text mining) but, so far, has not been extensively explored for effort estimation. Accordingly, this paper seeks simple, automatic, effective and fast methods for finding good tunings for automatic software effort estimation. We introduce a hyperparameter optimization architecture called OIL (Optimized Inductive Learning). We test OIL on a wide range of hyperparameter optimizers using data from 945 software projects. After tuning, large improvements in effort estimation accuracy were observed (measured in terms of standardized accuracy). From those results, we recommend using regression trees (CART) tuned by different evolution combine with default analogy-based estimator. This particular combination of learner and optimizers often achieves in a few hours what other optimizers need days to weeks of CPU time to accomplish. An important part of this analysis is its reproducibility and refutability. All our scripts and data are on-line. It is hoped that this paper will prompt and enable much more research on better methods to tune software effort estimators.
A Hidden Resource in Wireless Channel Capacity: Dependence Control in Action
Venue: arXiv cs.IT 2019
Year: 2019

This paper aims to initiate the research on dependence control, which transforms the dependence structure of a stochastic process in the system through dependence manipulation, to improve the system performance. Specifically, we develop a dependence control theory for wireless channels, focusing on three principles in dependence control: (i) the asymptotic decay rates of delay and backlog in the system are the measures for dependence comparison and ordering, (ii) the dependence in the arrival process and the service process have a dual potency to influence the system performance, and (iii) the manipulation of the dependence in the free dimensions of the arrival or service process transforms the dependence structure of the arrival or service process. In addition, we apply the theory to the Markov additive process, which is a general model for a class of arrival processes and a versatile model for wireless channel capacity, and derive a set of results for various performance measures, including delay, backlog, and delay-constrained capacity. To demonstrate the use of the theory, we focus on dependence manipulation in wireless channel capacity, where we use copula to represent the dependence structure of the underlying Markov process of wireless channel capacity. We show that, based on a priori information of the temporal dependence of the uncontrollable parameters and the spatial dependence between the uncontrollable and controllable parameters, we can construct a sequence of temporal copulas of the Markov process and obtain a sequence of transition matrices of the controllable parameters to achieve the demanded dependence properties of the wireless channel capacity. This dependence manipulation technique is validated by simulation.
EML-NET:An Expandable Multi-Layer NETwork for Saliency Prediction
Venue: arXiv cs.CV 2019
Year: 2019

Saliency prediction can benefit from training that involves scene understanding that may be tangential to the central task; this may include understanding places, spatial layout, objects or involve different datasets and their bias. One can combine models, but to do this in a sophisticated manner can be complex, and also result in unwieldy networks or produce competing objectives that are hard to balance. In this paper, we propose a scalable system to leverage multiple powerful deep CNN models to better extract visual features for saliency prediction. Our design differs from previous studies in that the whole system is trained in an almost end-to-end piece-wise fashion. The encoder and decoder components are separately trained to deal with complexity tied to the computational paradigm and required space. Furthermore, the encoder can contain more than one CNN model to extract features, and models can have different architectures or be pre-trained on different datasets. This parallel design yields a better computational paradigm overcoming limits to the variety of information or inference that can be combined at the encoder stage towards deeper networks and a more powerful encoding. Our network can be easily expanded almost without any additional cost, and other pre-trained CNN models can be incorporated availing a wider range of visual knowledge. We denote our expandable multi-layer network as EML-NET and our method achieves the state-of-the-art results on the public saliency benchmarks, SALICON, MIT300 and CAT2000.
Open Loop Execution of Tree-Search Algorithms, extended version
Venue: arXiv cs.LG 2019
Year: 2019

In the context of tree-search stochastic planning algorithms where a generative model is available, we consider on-line planning algorithms building trees in order to recommend an action. We investigate the question of avoiding re-planning in subsequent decision steps by directly using sub-trees as action recommender. Firstly, we propose a method for open loop control via a new algorithm taking the decision of re-planning or not at each time step based on an analysis of the statistics of the sub-tree. Secondly, we show that the probability of selecting a suboptimal action at any depth of the tree can be upper bounded and converges towards zero. Moreover, this upper bound decays in a logarithmic way between subsequent depths. This leads to a distinction between node-wise optimality and state-wise optimality. Finally, we empirically demonstrate that our method achieves a compromise between loss of performance and computational gain.
MTFH: A Matrix Tri-Factorization Hashing Framework for Efficient Cross-Modal Retrieval
Venue: arXiv cs.CV 2019
Year: 2019

Hashing has recently sparked a great revolution in cross-modal retrieval because of its low storage cost and high query speed. Recent cross-modal hashing methods often learn unified or equal-length hash codes to represent the multi-modal data and make them intuitively comparable. However, such unified or equal-length hash representations could inherently sacrifice their representation scalability because the data from different modalities may not have one-to-one correspondence and could be encoded more efficiently by different hash codes of unequal lengths. To mitigate these problems, this paper exploits a related and relatively unexplored problem: encode the heterogeneous data with varying hash lengths and generalize the cross-modal retrieval in various challenging scenarios. To this end, a generalized and flexible cross-modal hashing framework, termed Matrix Tri-Factorization Hashing (MTFH), is proposed to work seamlessly in various settings including paired or unpaired multi-modal data, and equal or varying hash length encoding scenarios. More specifically, MTFH exploits an efficient objective function to flexibly learn the modality-specific hash codes with different length settings, while synchronously learning two semantic correlation matrices to semantically correlate the different hash representations for heterogeneous data comparable. As a result, the derived hash codes are more semantically meaningful for various challenging cross-modal retrieval tasks. Extensive experiments evaluated on public benchmark datasets highlight the superiority of MTFH under various retrieval scenarios and show its competitive performance with the state-of-the-arts.