OpenRaiser/Intern-Atlas huggingface dataset:
Siamese Cascaded Region Proposal Networks for Real-Time Visual Tracking
Venue: arXiv cs.CV 2018
Year: 2018

Region proposal networks (RPN) have been recently combined with the Siamese network for tracking, and shown excellent accuracy with high efficiency. Nevertheless, previously proposed one-stage Siamese-RPN trackers degenerate in presence of similar distractors and large scale variation. Addressing these issues, we propose a multi-stage tracking framework, Siamese Cascaded RPN (C-RPN), which consists of a sequence of RPNs cascaded from deep high-level to shallow low-level layers in a Siamese network. Compared to previous solutions, C-RPN has several advantages: (1) Each RPN is trained using the outputs of RPN in the previous stage. Such process stimulates hard negative sampling, resulting in more balanced training samples. Consequently, the RPNs are sequentially more discriminative in distinguishing difficult background (i.e., similar distractors). (2) Multi-level features are fully leveraged through a novel feature transfer block (FTB) for each RPN, further improving the discriminability of C-RPN using both high-level semantic and low-level spatial information. (3) With multiple steps of regressions, C-RPN progressively refines the location and shape of the target in each RPN with adjusted anchor boxes in the previous stage, which makes localization more accurate. C-RPN is trained end-to-end with the multi-task loss function. In inference, C-RPN is deployed as it is, without any temporal adaption, for real-time tracking. In extensive experiments on OTB-2013, OTB-2015, VOT-2016, VOT-2017, LaSOT and TrackingNet, C-RPN consistently achieves state-of-the-art results and runs in real-time.
An Empirical Model of Large-Batch Training
Venue: arXiv cs.LG 2018
Year: 2018

In an increasing number of domains it has been demonstrated that deep learning models can be trained using relatively large batch sizes without sacrificing data efficiency. However the limits of this massive data parallelism seem to differ from domain to domain, ranging from batches of tens of thousands in ImageNet to batches of millions in RL agents that play the game Dota 2. To our knowledge there is limited conceptual understanding of why these limits to batch size differ or how we might choose the correct batch size in a new domain. In this paper, we demonstrate that a simple and easy-to-measure statistic called the gradient noise scale predicts the largest useful batch size across many domains and applications, including a number of supervised learning datasets (MNIST, SVHN, CIFAR-10, ImageNet, Billion Word), reinforcement learning domains (Atari and Dota), and even generative model training (autoencoders on SVHN). We find that the noise scale increases as the loss decreases over a training run and depends on the model size primarily through improved model performance. Our empirically-motivated theory also describes the tradeoff between compute-efficiency and time-efficiency, and provides a rough model of the benefits of adaptive batch-size training.
Network Utility Maximization under Maximum Delay Constraints and Throughput Requirements
Venue: arXiv cs.NI 2018
Year: 2018

We consider the problem of maximizing aggregate user utilities over a multi-hop network, subject to link capacity constraints, maximum end-to-end delay constraints, and user throughput requirements. A user's utility is a concave function of the achieved throughput or the experienced maximum delay. The problem is important for supporting real-time multimedia traffic, and is uniquely challenging due to the need of simultaneously considering maximum delay constraints and throughput requirements. We first show that it is NP-complete either (i) to construct a feasible solution strictly meeting all constraints, or (ii) to obtain an optimal solution after we relax maximum delay constraints or throughput requirements up to constant ratios. We then develop a polynomial-time approximation algorithm named PASS. The design of PASS leverages a novel understanding between non-convex maximum-delay-aware problems and their convex average-delay-aware counterparts, which can be of independent interest and suggest a new avenue for solving maximum-delay-aware network optimization problems. Under realistic conditions, PASS achieves constant or problem-dependent approximation ratios, at the cost of violating maximum delay constraints or throughput requirements by up to constant or problem-dependent ratios. PASS is practically useful since the conditions for PASS are satisfied in many popular application scenarios. We empirically evaluate PASS using extensive simulations of supporting video-conferencing traffic across Amazon EC2 datacenters. Compared to existing algorithms and a conceivable baseline, PASS obtains up to $100\%$ improvement of utilities, by meeting the throughput requirements but relaxing the maximum delay constraints that are acceptable for practical video conferencing applications.
Weakly supervised segment annotation via expectation kernel density estimation
Venue: arXiv cs.CV 2018
Year: 2018

Since the labelling for the positive images/videos is ambiguous in weakly supervised segment annotation, negative mining based methods that only use the intra-class information emerge. In these methods, negative instances are utilized to penalize unknown instances to rank their likelihood of being an object, which can be considered as a voting in terms of similarity. However, these methods 1) ignore the information contained in positive bags, 2) only rank the likelihood but cannot generate an explicit decision function. In this paper, we propose a voting scheme involving not only the definite negative instances but also the ambiguous positive instances to make use of the extra useful information in the weakly labelled positive bags. In the scheme, each instance votes for its label with a magnitude arising from the similarity, and the ambiguous positive instances are assigned soft labels that are iteratively updated during the voting. It overcomes the limitations of voting using only the negative bags. We also propose an expectation kernel density estimation (eKDE) algorithm to gain further insight into the voting mechanism. Experimental results demonstrate the superiority of our scheme beyond the baselines.
On the impact of pull request decisions on future contributions
Venue: arXiv cs.SE 2018
Year: 2018

The pull-based development process has become prevalent on platforms such as GitHub as a form of distributed software development. Potential contributors can create and submit a set of changes to a software project through pull requests. These changes can be accepted, discussed or rejected by the maintainers of the software project, and can influence further contribution proposals. As such, it is important to examine the practices that encourage contributors to a project to submit pull requests. Specifically, we consider the impact of prior pull requests on the acceptance or rejection of subsequent pull requests. We also consider the potential effect of rejecting or ignoring pull requests on further contributions. In this preliminary research, we study three large projects on \textsf{GitHub}, using pull request data obtained through the \textsf{GitHub} API, and we perform empirical analyses to investigate the above questions. Our results show that continued contribution to a project is correlated with higher pull request acceptance rates and that pull request rejections lead to fewer future contributions.
On Virtual Network Embedding: Paths and Cycles
Venue: arXiv cs.NI 2018
Year: 2018

Network virtualization provides a promising solution to overcome the ossification of current networks, allowing multiple Virtual Network Requests (VNRs) embedded on a common infrastructure. The major challenge in network virtualization is the Virtual Network Embedding (VNE) problem, which is to embed VNRs onto a shared substrate network and known to be $\mathcal{NP}$-hard. The topological heterogeneity of VNRs is one important factor hampering the performance of the VNE. However, in many specialized applications and infrastructures, VNRs are of some common structural features $\textit{e.g.}$, paths and cycles. To achieve better outcomes, it is thus critical to design dedicated algorithms for these applications and infrastructures by taking into accounting topological characteristics. Besides, paths and cycles are two of the most fundamental topologies that all network structures consist of. Exploiting the characteristics of path and cycle embeddings is vital to tackle the general VNE problem. In this paper, we investigated the path and cycle embedding problems. For path embedding, we proved its $\mathcal{NP}$-hardness and inapproximability. Then, by utilizing Multiple Knapsack Problem (MKP) and Multi-Dimensional Knapsack Problem (MDKP), we proposed an efficient and effective MKP-MDKP-based algorithm. For cycle embedding, we proposed a Weighted Directed Auxiliary Graph (WDAG) to develop a polynomial-time algorithm to determine the least-resource-consuming embedding. Numerical results showed our customized algorithms can boost the acceptance ratio and revenue compared to generic embedding algorithms in the literature.
Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices
Venue: arXiv cs.DS 2018
Year: 2018

In this paper we show how to recover a spectral approximations to broad classes of structured matrices using only a polylogarithmic number of adaptive linear measurements to either the matrix or its inverse. Leveraging this result we obtain faster algorithms for variety of linear algebraic problems. Key results include: $\bullet$ A nearly linear time algorithm for solving the inverse of symmetric $M$-matrices, a strict superset of Laplacians and SDD matrices. $\bullet$ An $\tilde{O}(n^2)$ time algorithm for solving $n \times n$ linear systems that are constant spectral approximations of Laplacians or more generally, SDD matrices. $\bullet$ An $\tilde{O}(n^2)$ algorithm to recover a spectral approximation of a $n$-vertex graph using only $\tilde{O}(1)$ matrix-vector multiplies with its Laplacian matrix. The previous best results for each problem either used a trivial number of queries to exactly recover the matrix or a trivial $O(n^ω)$ running time, where $ω$ is the matrix multiplication constant. We achieve these results by generalizing recent semidefinite programming based linear sized sparsifier results of Lee and Sun (2017) and providing iterative methods inspired by the semistreaming sparsification results of Kapralov, Lee, Musco, Musco and Sidford (2014) and input sparsity time linear system solving results of Li, Miller, and Peng (2013). We hope that by initiating study of these natural problems, expanding the robustness and scope of recent nearly linear time linear system solving research, and providing general matrix recovery machinery this work may serve as a stepping stone for faster algorithms.
Arm Manipulation Planning of Tethered Tools with the Help of a Tool Balancer
Venue: arXiv cs.RO 2018
Year: 2018

Robotic manipulation of tethered tools is widely seen in robotic work cells. They may cause excess strain on the tool's cable or undesired entanglements with the robot's arms. This paper presents a manipulation planner with cable orientation constraints for tethered tools suspended by tool balancers. The planner uses orientation constraints to limit the bending of the balancer's cable while the robot manipulates a tool and places it in a desired pose. The constraints reduce entanglements and decrease the torque induced by the cable on the robot joints. Simulation and real-world experiments show that the constrained planner can successfully plan robot motions for the manipulation of suspended tethered tools preventing the robot from damaging the cable or getting its arms entangled, potentially avoiding accidents. The planner is expected to play promising roles in manufacturing cells.
Searching with Consistent Prioritization for Multi-Agent Path Finding
Venue: arXiv cs.AI 2018
Year: 2018

We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing prioritized MAPF algorithms depend on rule-of-thumb heuristics and random assignment to determine a fixed total priority ordering of all agents a priori. We instead explore the space of all possible partial priority orderings as part of a novel systematic and conflict-driven combinatorial search framework. In a variety of empirical comparisons, we demonstrate state-of-the-art solution qualities and success rates, often with similar runtimes to existing algorithms. We also develop new theoretical results that explore the limitations of prioritized planning, in terms of completeness and optimality, for the first time.
Trust Region Based Adversarial Attack on Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Deep Neural Networks are quite vulnerable to adversarial perturbations. Current state-of-the-art adversarial attack methods typically require very time consuming hyper-parameter tuning, or require many iterations to solve an optimization based adversarial attack. To address this problem, we present a new family of trust region based adversarial attacks, with the goal of computing adversarial perturbations efficiently. We propose several attacks based on variants of the trust region optimization method. We test the proposed methods on Cifar-10 and ImageNet datasets using several different models including AlexNet, ResNet-50, VGG-16, and DenseNet-121 models. Our methods achieve comparable results with the Carlini-Wagner (CW) attack, but with significant speed up of up to $37\times$, for the VGG-16 model on a Titan Xp GPU. For the case of ResNet-50 on ImageNet, we can bring down its classification accuracy to less than 0.1\% with at most $1.5\%$ relative $L_\infty$ (or $L_2$) perturbation requiring only $1.02$ seconds as compared to $27.04$ seconds for the CW attack. We have open sourced our method which can be accessed at [1].
Embedding Push and Pull Search in the Framework of Differential Evolution for Solving Constrained Single-objective Optimization Problems
Venue: arXiv cs.NE 2018
Year: 2018

This paper proposes a push and pull search method in the framework of differential evolution (PPS-DE) to solve constrained single-objective optimization problems (CSOPs). More specifically, two sub-populations, including the top and bottom sub-populations, are collaborated with each other to search global optimal solutions efficiently. The top sub-population adopts the pull and pull search (PPS) mechanism to deal with constraints, while the bottom sub-population use the superiority of feasible solutions (SF) technique to deal with constraints. In the top sub-population, the search process is divided into two different stages --- push and pull stages.An adaptive DE variant with three trial vector generation strategies is employed in the proposed PPS-DE. In the top sub-population, all the three trial vector generation strategies are used to generate offsprings, just like in CoDE. In the bottom sub-population, a strategy adaptation, in which the trial vector generation strategies are periodically self-adapted by learning from their experiences in generating promising solutions in the top sub-population, is used to choose a suitable trial vector generation strategy to generate one offspring. Furthermore, a parameter adaptation strategy from LSHADE44 is employed in both sup-populations to generate scale factor $F$ and crossover rate $CR$ for each trial vector generation strategy. Twenty-eight CSOPs with 10-, 30-, and 50-dimensional decision variables provided in the CEC2018 competition on real parameter single objective optimization are optimized by the proposed PPS-DE. The experimental results demonstrate that the proposed PPS-DE has the best performance compared with the other seven state-of-the-art algorithms, including AGA-PPS, LSHADE44, LSHADE44+IDE, UDE, IUDE, $ε$MAg-ES and C$^2$oDE.
TET-GAN: Text Effects Transfer via Stylization and Destylization
Venue: arXiv cs.CV 2018
Year: 2018

Text effects transfer technology automatically makes the text dramatically more impressive. However, previous style transfer methods either study the model for general style, which cannot handle the highly-structured text effects along the glyph, or require manual design of subtle matching criteria for text effects. In this paper, we focus on the use of the powerful representation abilities of deep neural features for text effects transfer. For this purpose, we propose a novel Texture Effects Transfer GAN (TET-GAN), which consists of a stylization subnetwork and a destylization subnetwork. The key idea is to train our network to accomplish both the objective of style transfer and style removal, so that it can learn to disentangle and recombine the content and style features of text effects images. To support the training of our network, we propose a new text effects dataset with as much as 64 professionally designed styles on 837 characters. We show that the disentangled feature representations enable us to transfer or remove all these styles on arbitrary glyphs using one network. Furthermore, the flexible network design empowers TET-GAN to efficiently extend to a new text style via one-shot learning where only one example is required. We demonstrate the superiority of the proposed method in generating high-quality stylized text over the state-of-the-art methods.
PAC Learning Guarantees Under Covariate Shift
Venue: arXiv cs.LG 2018
Year: 2018

We consider the Domain Adaptation problem, also known as the covariate shift problem, where the distributions that generate the training and test data differ while retaining the same labeling function. This problem occurs across a large range of practical applications, and is related to the more general challenge of transfer learning. Most recent work on the topic focuses on optimization techniques that are specific to an algorithm or practical use case rather than a more general approach. The sparse literature attempting to provide general bounds seems to suggest that efficient learning even under strong assumptions is not possible for covariate shift. Our main contribution is to recontextualize these results by showing that any Probably Approximately Correct (PAC) learnable concept class is still PAC learnable under covariate shift conditions with only a polynomial increase in the number of training samples. This approach essentially demonstrates that the Domain Adaptation learning problem is as hard as the underlying PAC learning problem, provided some conditions over the training and test distributions. We also present bounds for the rejection sampling algorithm, justifying it as a solution to the Domain Adaptation problem in certain scenarios.
Human Pose and Path Estimation from Aerial Video using Dynamic Classifier Selection
Venue: arXiv cs.CV 2018
Year: 2018

We consider the problem of estimating human pose and trajectory by an aerial robot with a monocular camera in near real time. We present a preliminary solution whose distinguishing feature is a dynamic classifier selection architecture. In our solution, each video frame is corrected for perspective using projective transformation. Then, two alternative feature sets are used: (i) Histogram of Oriented Gradients (HOG) of the silhouette, (ii) Convolutional Neural Network (CNN) features of the RGB image. The features (HOG or CNN) are classified using a dynamic classifier. A class is defined as a pose-viewpoint pair, and a total of 64 classes are defined to represent a forward walking and turning gait sequence. Our solution provides three main advantages: (i) Classification is efficient due to dynamic selection (4-class vs. 64-class classification). (ii) Classification errors are confined to neighbors of the true view-points. (iii) The robust temporal relationship between poses is used to resolve the left-right ambiguities of human silhouettes. Experiments conducted on both fronto-parallel videos and aerial videos confirm our solution can achieve accurate pose and trajectory estimation for both scenarios. We found using HOG features provides higher accuracy than using CNN features. For example, applying the HOG-based variant of our scheme to the 'walking on a figure 8-shaped path' dataset (1652 frames) achieved estimation accuracies of 99.6% for viewpoints and 96.2% for number of poses.
Quine's Fluted Fragment Revisited
Venue: arXiv cs.LO 2018
Year: 2018

We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originally identified in 1968 by W.V. Quine. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NExpTime. More precisely, we consider $\mathcal{FL}^m$, the intersection of the fluted fragment and the $m$-variable fragment of first-order logic, for all $m \geq 1$. We show that, for $m \geq 2$, this sub-fragment forces $\lfloor m/2\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\lfloor m/2\rfloor$-NExpTime-hard. We further establish that, for $m \geq 3$, any satisfiable $\mathcal{FL}^m$-formula has a model of at most ($m-2$)-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in ($m-2$)-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for $\mathcal{FL}^m$ for all $m \leq 4$.
Interest-Aware Delivery for Mobile Social Networks: A TRACE-driven Approach
Venue: arXiv cs.SI 2018
Year: 2018

We envision future mobile networks to be human-centric supporting interest-aware delivery, where an interest maybe based on behavior, such as mobility pattern, location, or web browsing (or user profile) such as affiliation, attributes, or activity. An essential capability in future networks will be the ability to provide scalable group communication. Current communication paradigms, including unicast and multicast, require explicit identification of destination nodes (through node IDs or group membership protocols), while directory services translate logical, interest-specific queries into destination IDs where parties are then connected using interest-oblivious protocols. The power and scalability of such paradigms is quite limited in the context of future, highly dynamic mobile social networks, where it is desirable in many scenarios to support implicit membership based on interest. In such scenarios, membership in interest-groups is not explicitly expressed by users, it is rather autonomously inferred by network protocols based on behavioral profiles. This removes the dependence on third parties (via directory lookup), the need for explicit expression of interest (or human intervention), and minimizes delivery overhead to uninterested users. While existing types of social networks will likely evolve in the context of mobile networks, we provide a novel paradigm of communication, deviating significantly from existing approaches and subsequently enabling qualitatively different capabilities for future services in mobile societies. In addition, our services and protocol design philosophy begins by analyzing the context in which the service is to be deployed, unlike most existing wireless networking approaches of designing general purpose protocols.