OpenRaiser/Intern-Atlas huggingface dataset:
Continuous Relaxations for the Traveling Salesman Problem
Venue: arXiv cs.DM 2019
Year: 2019

In this work, we aim to explore connections between dynamical systems techniques and combinatorial optimization problems. In particular, we construct heuristic approaches for the traveling salesman problem (TSP) based on embedding the relaxed discrete optimization problem into appropriate manifolds. We explore multiple embedding techniques -- namely, the construction of new dynamical systems on the manifold of orthogonal matrices and associated Procrustes approximations of the TSP cost function. Using these dynamical systems, we analyze the local neighborhood around the optimal TSP solutions (which are equilibria) using computations to approximate the associated \emph{stable manifolds}. We find that these flows frequently converge to undesirable equilibria. However, the solutions of the dynamical systems and the associated Procrustes approximation provide an interesting biasing approach for the popular Lin--Kernighan heuristic which yields fast convergence. The Lin--Kernighan heuristic is typically based on the computation of edges that have a `high probability' of being in the shortest tour, thereby effectively pruning the search space. Our new approach, instead, relies on a natural relaxation of the combinatorial optimization problem to the manifold of orthogonal matrices and the subsequent use of this solution to bias the Lin--Kernighan heuristic. Although the initial cost of computing these edges using the Procrustes solution is higher than existing methods, we find that the Procrustes solution, when coupled with a homotopy computation, contains valuable information regarding the optimal edges. We explore the Procrustes based approach on several TSP instances and find that our approach often requires fewer $k$-opt moves than existing approaches. Broadly, we hope that this work initiates more work in the intersection of dynamical systems theory and combinatorial optimization.
A general framework for path convexities
Venue: arXiv cs.DM 2019
Year: 2019

In this work we deal with the so-called path convexities, defined over special collections of paths. For example, the collection of the shortest paths in a graph is associated with the well-known geodesic convexity, while the collection of the induced paths is associated with the monophonic convexity; and there are many other examples. Besides reviewing the path convexities in the literature, we propose a general path convexity framework, of which most existing path convexities can be viewed as particular cases. Some benefits of the proposed framework are the systematization of the algorithmic study of related problems and the possibility of defining new convexities not yet investigated.
A Rollback in the History of Communication-Induced Checkpointing
Venue: arXiv cs.DC 2019
Year: 2019

The literature on communication-induced checkpointing presents a family of protocols that use logical clocks to control whether forced checkpoints must be taken. Efficiency of these protocols is measured by how many forced checkpoints are needed to ensure no checkpoint will be useless to the application; the fewer forced checkpoints the better. For many years, HMNR, also called Fully Informed (FI), was the most complex and efficient protocol of this family. The Lazy-FI protocol applies a lazy strategy that defers the increase of logical clocks, resulting in a protocol with better efficiency for distributed systems where processes can take basic checkpoints at different rates. Recently, the Fully Informed aNd Efficient (FINE) protocol was proposed using the same control structures as FI, but with a stronger and, presumably better, checkpoint-inducing condition. FINE and its lazy version, called Lazy-FINE, would now be the most efficient checkpointing protocols based on logical clocks. This paper reviews this family of protocols, proves a theorem on a condition that must be enforced by all stronger versions of FI, and proves that both FINE and Lazy-FINE do not guarantee the absence of useless checkpoints. As a consequence, FI and Lazy-FI can be rolled back to the position of most efficient protocols of this family of index-based checkpointing protocols.
Soft Label Memorization-Generalization for Natural Language Inference
Venue: arXiv cs.CL 2019
Year: 2019

Often when multiple labels are obtained for a training example it is assumed that there is an element of noise that must be accounted for. It has been shown that this disagreement can be considered signal instead of noise. In this work we investigate using soft labels for training data to improve generalization in machine learning models. However, using soft labels for training Deep Neural Networks (DNNs) is not practical due to the costs involved in obtaining multiple labels for large data sets. We propose soft label memorization-generalization (SLMG), a fine-tuning approach to using soft labels for training DNNs. We assume that differences in labels provided by human annotators represent ambiguity about the true label instead of noise. Experiments with SLMG demonstrate improved generalization performance on the Natural Language Inference (NLI) task. Our experiments show that by injecting a small percentage of soft label training data (0.03% of training set size) we can improve generalization performance over several baselines.
Robust Communication-Optimal Distributed Clustering Algorithms
Venue: arXiv cs.DS 2019
Year: 2019

In this work, we study the $k$-median and $k$-means clustering problems when the data is distributed across many servers and can contain outliers. While there has been a lot of work on these problems for worst-case instances, we focus on gaining a finer understanding through the lens of beyond worst-case analysis. Our main motivation is the following: for many applications such as clustering proteins by function or clustering communities in a social network, there is some unknown target clustering, and the hope is that running a $k$-median or $k$-means algorithm will produce clusterings which are close to matching the target clustering. Worst-case results can guarantee constant factor approximations to the optimal $k$-median or $k$-means objective value, but not closeness to the target clustering. Our first result is a distributed algorithm which returns a near-optimal clustering assuming a natural notion of stability, namely, approximation stability [Balcan et. al 2013], even when a constant fraction of the data are outliers. The communication complexity is $\tilde O(sk+z)$ where $s$ is the number of machines, $k$ is the number of clusters, and $z$ is the number of outliers. Next, we show this amount of communication cannot be improved even in the setting when the input satisfies various non-worst-case assumptions. We give a matching $Ω(sk+z)$ lower bound on the communication required both for approximating the optimal $k$-means or $k$-median cost up to any constant, and for returning a clustering that is close to the target clustering in Hamming distance. These lower bounds hold even when the data satisfies approximation stability or other common notions of stability, and the cluster sizes are balanced. Therefore, $Ω(sk+z)$ is a communication bottleneck, even for real-world instances.
Optimal Routing for Delay-Sensitive Traffic in Overlay Networks
Venue: arXiv cs.NI 2019
Year: 2019

We design dynamic routing policies for an overlay network which meet delay requirements of real-time traffic being served on top of an underlying legacy network, where the overlay nodes do not know the underlay characteristics. We pose the problem as a constrained MDP, and show that when the underlay implements static policies such as FIFO with randomized routing, then a decentralized policy, that can be computed efficiently in a distributed fashion, is optimal. Our algorithm utilizes multi-timescale stochastic approximation techniques, and its convergence relies on the fact that the recursions asymptotically track a nonlinear differential equation, namely the replicator equation. Extensive simulations show that the proposed policy indeed outperforms the existing policies.
Game-Theoretic Vaccination Against Networked SIS Epidemics and Impacts of Human Decision-Making
Venue: arXiv cs.GT 2019
Year: 2019

We study decentralized protection strategies against Susceptible-Infected-Susceptible (SIS) epidemics on networks. We consider a population game framework where nodes choose whether or not to vaccinate themselves, and the epidemic risk is defined as the infection probability at the endemic state of the epidemic under a degree-based mean-field approximation. Motivated by studies in behavioral economics showing that humans perceive probabilities and risks in a nonlinear fashion, we specifically examine the impacts of such misperceptions on the Nash equilibrium protection strategies. We first establish the existence and uniqueness of a threshold equilibrium where nodes with degrees larger than a certain threshold vaccinate. When the vaccination cost is sufficiently high, we show that behavioral biases cause fewer players to vaccinate, and vice versa. We quantify this effect for a class of networks with power-law degree distributions by proving tight bounds on the ratio of equilibrium thresholds under behavioral and true perceptions of probabilities. We further characterize the socially optimal vaccination policy and investigate the inefficiency of Nash equilibrium.
Exploiting Color Name Space for Salient Object Detection
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we will investigate the contribution of color names for the task of salient object detection. An input image is first converted to color name space, which is consisted of 11 probabilistic channels. By exploiting a surroundedness cue, we obtain a saliency map through a linear combination of a set of sequential attention maps. To overcome the limitation of only using the surroundedness cue, two global cues with respect to color names are invoked to guide the computation of a weighted saliency map. Finally, we integrate the above two saliency maps into a unified framework to generate the final result. In addition, an improved post-processing procedure is introduced to effectively suppress image backgrounds while uniformly highlight salient objects. Experimental results show that the proposed model produces more accurate saliency maps and performs well against twenty-one saliency models in terms of three evaluation metrics on three public data sets.
On noncommutative extensions of linear logic
Venue: arXiv cs.LO 2019
Year: 2019

Pomset logic introduced by Retoré is an extension of linear logic with a self-dual noncommutative connective. The logic is defined by means of proof-nets, rather than a sequent calculus. Later a deep inference system BV was developed with an eye to capturing Pomset logic, but equivalence of system has not been proven up to now. As for a sequent calculus formulation, it has not been known for either of these logics, and there are convincing arguments that such a sequent calculus in the usual sense simply does not exist for them. In an on-going work on semantics we discovered a system similar to Pomset logic, where a noncommutative connective is no longer self-dual. Pomset logic appears as a degeneration, when the class of models is restricted. Motivated by these semantic considerations, we define in the current work a semicommutative multiplicative linear logic}, which is multiplicative linear logic extended with two nonisomorphic noncommutative connectives (not to be confused with very different Abrusci-Ruet noncommutative logic). We develop a syntax of proof-nets and show how this logic degenerates to Pomset logic. However, a more interesting problem than just finding yet another noncommutative logic is to find a sequent calculus for this logic. We introduce decorated sequents, which are sequents equipped with an extra structure of a binary relation of reachability on formulas. We define a decorated sequent calculus for semicommutative logic and prove that it is cut-free, sound and complete. This is adapted to "degenerate" variations, including Pomset logic. Thus, in particular, we give a variant of sequent calculus formulation for Pomset logic, which is one of the key results of the paper.
Local Flow Partitioning for Faster Edge Connectivity
Venue: arXiv cs.DS 2019
Year: 2019

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic $O(m \log^2 n \log\log^2 n)$ time algorithm. This improves both on the best previously known deterministic running time of $O(m \log^{12} n)$ (Kawarabayashi and Thorup, STOC 2015) and the best previously known randomized running time of $O(m \log^{3} n)$ (Karger, J.ACM 2000) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low-conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow and diffusion based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that is both local and produces low conductance cuts. Thus, it may be of independent interest.
Weakly-Supervised Spatial Context Networks
Venue: arXiv cs.CV 2019
Year: 2019

We explore the power of spatial context as a self-supervisory signal for learning visual representations. In particular, we propose spatial context networks that learn to predict a representation of one image patch from another image patch, within the same image, conditioned on their real-valued relative spatial offset. Unlike auto-encoders, that aim to encode and reconstruct original image patches, our network aims to encode and reconstruct intermediate representations of the spatially offset patches. As such, the network learns a spatially conditioned contextual representation. By testing performance with various patch selection mechanisms we show that focusing on object-centric patches is important, and that using object proposal as a patch selection mechanism leads to the highest improvement in performance. Further, unlike auto-encoders, context encoders [21], or other forms of unsupervised feature learning, we illustrate that contextual supervision (with pre-trained model initialization) can improve on existing pre-trained model performance. We build our spatial context networks on top of standard VGG_19 and CNN_M architectures and, among other things, show that we can achieve improvements (with no additional explicit supervision) over the original ImageNet pre-trained VGG_19 and CNN_M models in object categorization and detection on VOC2007.
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
Venue: arXiv cs.DS 2019
Year: 2019

We show how to compute a relative-error low-rank approximation to any positive semidefinite (PSD) matrix in sublinear time, i.e., for any $n \times n$ PSD matrix $A$, in $\tilde O(n \cdot poly(k/ε))$ time we output a rank-$k$ matrix $B$, in factored form, for which $\|A-B\|_F^2 \leq (1+ε)\|A-A_k\|_F^2$, where $A_k$ is the best rank-$k$ approximation to $A$. When $k$ and $1/ε$ are not too large compared to the sparsity of $A$, our algorithm does not need to read all entries of the matrix. Hence, we significantly improve upon previous $nnz(A)$ time algorithms based on oblivious subspace embeddings, and bypass an $nnz(A)$ time lower bound for general matrices (where $nnz(A)$ denotes the number of non-zero entries in the matrix). We prove time lower bounds for low-rank approximation of PSD matrices, showing that our algorithm is close to optimal. Finally, we extend our techniques to give sublinear time algorithms for low-rank approximation of $A$ in the (often stronger) spectral norm metric $\|A-B\|_2^2$ and for ridge regression on PSD matrices.
Faster Algorithms for Growing Prioritized Disks and Rectangles
Venue: arXiv cs.CG 2019
Year: 2019

Motivated by map labeling, Funke, Krumpe, and Storandt [IWOCA 2016] introduced the following problem: we are given a sequence of $n$ disks in the plane. Initially, all disks have radius $0$, and they grow at constant, but possibly different, speeds. Whenever two disks touch, the one with the higher index disappears. The goal is to determine the elimination order, i.e., the order in which the disks disappear. We provide the first general subquadratic algorithm for this problem. Our solution extends to other shapes (e.g., rectangles), and it works in any fixed dimension. We also describe an alternative algorithm that is based on quadtrees. Its running time is $O\big(n \big(\log n + \min \{ \log Δ, \log Φ\}\big)\big)$, where $Δ$ is the ratio of the fastest and the slowest growth rate and $Φ$ is the ratio of the largest and the smallest distance between two disk centers. This improves the running times of previous algorithms by Funke, Krumpe, and Storandt [IWOCA 2016], Bahrdt et al. [ALENEX 2017], and Funke and Storandt [EuroCG 2017]. Finally, we give an $Ω(n\log n)$ lower bound, showing that our quadtree algorithms are almost tight.
Over-Approximation of Fluid Models
Venue: arXiv cs.SY 2019
Year: 2019

Fluid models are a popular formalism in the quantitative modeling of biochemical systems and analytical performance models. The main idea is to approximate a large-scale Markov chain by a compact set of ordinary differential equations (ODEs). Even though it is often crucial for a fluid model under study to satisfy some given properties, a formal verification is usually challenging. This is because parameters are often not known precisely due to finite-precision measurements and stochastic noise. In this paper, we present a novel technique that allows one to efficiently compute formal bounds on the reachable set of time-varying nonlinear ODE systems that are subject to uncertainty. To this end, we a) relate the reachable set of a nonlinear fluid model to a family of inhomogeneous continuous time Markov decision processes and b) provide optimal and suboptimal solutions for the family by relying on optimal control theory. The proposed technique is efficient and can be expected to provide tight bounds. We demonstrate its potential by comparing it with a state-of-the-art over-approximation approach.
Definability and Interpolation within Decidable Fixpoint Logics
Venue: arXiv cs.LO 2019
Year: 2019

We look at characterizing which formulas are expressible in rich decidable logics such as guarded fixpoint logic, unary negation fixpoint logic, and guarded negation fixpoint logic. We consider semantic characterizations of definability, as well as effective characterizations. Our algorithms revolve around a finer analysis of the tree-model property and a refinement of the method of moving back and forth between relational logics and logics over trees.
Polynomial time decodable codes for the binary deletion channel
Venue: arXiv cs.IT 2019
Year: 2019

In the random deletion channel, each bit is deleted independently with probability $p$. For the random deletion channel, the existence of codes of rate $(1-p)/9$, and thus bounded away from $0$ for any $p < 1$, has been known. We give an explicit construction with polynomial time encoding and deletion correction algorithms with rate $c_0 (1-p)$ for an absolute constant $c_0 > 0$.
Solving a Path Planning Problem in a Partially Known Environment using a Swarm Algorithm
Venue: arXiv cs.RO 2019
Year: 2019

This paper proposes a path planning strategy for an Autonomous Ground Vehicle (AGV) navigating in a partially known environment. Global path planning is performed by first using a spatial database of the region to be traversed containing selected attributes such as height data and soil information from a suitable spatial database. The database is processed using a biomimetic swarm algorithm that is inspired by the nest building strategies followed by termites. Local path planning is performed online utilizing information regarding contingencies that affect the safe navigation of the AGV from various sensors. The simulation discussed has been implemented on the open source Player-Stage-Gazebo platform.
Efficient and Scalable View Generation from a Single Image using Fully Convolutional Networks
Venue: arXiv cs.CV 2019
Year: 2019

Single-image-based view generation (SIVG) is important for producing 3D stereoscopic content. Here, handling different spatial resolutions as input and optimizing both reconstruction accuracy and processing speed is desirable. Latest approaches are based on convolutional neural network (CNN), and they generate promising results. However, their use of fully connected layers as well as pre-trained VGG forces a compromise between reconstruction accuracy and processing speed. In addition, this approach is limited to the use of a specific spatial resolution. To remedy these problems, we propose exploiting fully convolutional networks (FCN) for SIVG. We present two FCN architectures for SIVG. The first one is based on combination of an FCN and a view-rendering network called DeepView$_{ren}$. The second one consists of decoupled networks for luminance and chrominance signals, denoted by DeepView$_{dec}$. To train our solutions we present a large dataset of 2M stereoscopic images. Results show that both of our architectures improve accuracy and speed over the state of the art. DeepView$_{ren}$ generates competitive accuracy to the state of the art, however, with the fastest processing speed of all. That is x5 times faster speed and x24 times lower memory consumption compared to the state of the art. DeepView$_{dec}$ has much higher accuracy, but with x2.5 times faster speed and x12 times lower memory consumption. We evaluated our approach with both objective and subjective studies.
Spelling Correction as a Foreign Language
Venue: arXiv cs.CL 2019
Year: 2019

In this paper, we reformulated the spell correction problem as a machine translation task under the encoder-decoder framework. This reformulation enabled us to use a single model for solving the problem that is traditionally formulated as learning a language model and an error model. This model employs multi-layer recurrent neural networks as an encoder and a decoder. We demonstrate the effectiveness of this model using an internal dataset, where the training data is automatically obtained from user logs. The model offers competitive performance as compared to the state of the art methods but does not require any feature engineering nor hand tuning between models.
Near-Feasible Stable Matchings with Budget Constraints
Venue: arXiv cs.GT 2019
Year: 2019

We consider the matching with contracts framework of Hatfield and Milgrom when one side (a firm or hospital) can make monetary transfers (offer wages) to the other (a worker or doctor). In a standard model, monetary transfers are not restricted. However, we assume that each hospital has a fixed budget; that is, the total amount of wages allocated by each hospital to the doctors is constrained. With this constraint, stable matchings may fail to exist and checking for the existence is hard. To deal with the nonexistence, we focus on near-feasible matchings that can exceed each hospital budget by a certain amount, and We introduce a new concept of compatibility. We show that the compatibility condition is a sufficient condition for the existence of a near-feasible stable matching in the matching with contracts framework. Under a slight restriction on hospitals' preferences, we provide mechanisms that efficiently return a near-feasible stable matching with respect to the actual amount of wages allocated by each hospital. By sacrificing strategy-proofness, the best possible bound of budget excess is achieved.