OpenRaiser/Intern-Atlas huggingface dataset:
Cross-Domain Visual Recognition via Domain Adaptive Dictionary Learning
Venue: arXiv cs.CV 2018
Year: 2018

In real-world visual recognition problems, the assumption that the training data (source domain) and test data (target domain) are sampled from the same distribution is often violated. This is known as the domain adaptation problem. In this work, we propose a novel domain-adaptive dictionary learning framework for cross-domain visual recognition. Our method generates a set of intermediate domains. These intermediate domains form a smooth path and bridge the gap between the source and target domains. Specifically, we not only learn a common dictionary to encode the domain-shared features, but also learn a set of domain-specific dictionaries to model the domain shift. The separation of the common and domain-specific dictionaries enables us to learn more compact and reconstructive dictionaries for domain adaptation. These dictionaries are learned by alternating between domain-adaptive sparse coding and dictionary updating steps. Meanwhile, our approach gradually recovers the feature representations of both source and target data along the domain path. By aligning all the recovered domain data, we derive the final domain-adaptive features for cross-domain visual recognition. Extensive experiments on three public datasets demonstrates that our approach outperforms most state-of-the-art methods.
Fast Prefix Search in Little Space, with Applications
Venue: arXiv cs.DS 2018
Year: 2018

It has been shown in the indexing literature that there is an essential difference between prefix/range searches on the one hand, and predecessor/rank searches on the other hand, in that the former provably allows faster query resolution. Traditionally, prefix search is solved by data structures that are also dictionaries---they actually contain the strings in $S$. For very large collections stored in slow-access memory, we propose much more compact data structures that support \emph{weak} prefix searches---they return the ranks of matching strings provided that \emph{some} string in $S$ starts with the given prefix. In fact, we show that our most space-efficient data structure is asymptotically space-optimal. Previously, data structures such as String B-trees (and more complicated cache-oblivious string data structures) have implicitly supported weak prefix queries, but they all have query time that grows logarithmically with the size of the string collection. In contrast, our data structures are simple, naturally cache-efficient, and have query time that depends only on the length of the prefix, all the way down to constant query time for strings that fit in one machine word. We give several applications of weak prefix searches, including exact prefix counting and approximate counting of tuples matching conjunctive prefix conditions.
Analytically Modeling Unmanaged Intersections with Microscopic Vehicle Interactions
Venue: arXiv cs.MA 2018
Year: 2018

With the emergence of autonomous vehicles, it is important to understand their impact on the transportation system. However, conventional traffic simulations are time-consuming. In this paper, we introduce an analytical traffic model for unmanaged intersections accounting for microscopic vehicle interactions. The macroscopic property, i.e., delay at the intersection, is modeled as an event-driven stochastic dynamic process, whose dynamics encode the microscopic vehicle behaviors. The distribution of macroscopic properties can be obtained through either direct analysis or event-driven simulation. They are more efficient than conventional (time-driven) traffic simulation, and capture more microscopic details compared to conventional macroscopic flow models. We illustrate the efficiency of this method by delay analyses under two different policies at a two-lane intersection. The proposed model allows for 1) efficient and effective comparison among different policies, 2) policy optimization, 3) traffic prediction, and 4) system optimization (e.g., infrastructure and protocol).
On the Efficiency of Localized Work Stealing
Venue: arXiv cs.DC 2018
Year: 2018

This paper investigates a variant of the work-stealing algorithm that we call the localized work-stealing algorithm. The intuition behind this variant is that because of locality, processors can benefit from working on their own work. Consequently, when a processor is free, it makes a steal attempt to get back its own work. We call this type of steal a steal-back. We show that the expected running time of the algorithm is $T_1/P+O(T_\infty P)$, and that under the "even distribution of free agents assumption", the expected running time of the algorithm is $T_1/P+O(T_\infty\lg P)$. In addition, we obtain another running-time bound based on ratios between the sizes of serial tasks in the computation. If $M$ denotes the maximum ratio between the largest and the smallest serial tasks of a processor after removing a total of $O(P)$ serial tasks across all processors from consideration, then the expected running time of the algorithm is $T_1/P+O(T_\infty M)$.
Deep Motion Boundary Detection
Venue: arXiv cs.CV 2018
Year: 2018

Motion boundary detection is a crucial yet challenging problem. Prior methods focus on analyzing the gradients and distributions of optical flow fields, or use hand-crafted features for motion boundary learning. In this paper, we propose the first dedicated end-to-end deep learning approach for motion boundary detection, which we term as MoBoNet. We introduce a refinement network structure which takes source input images, initial forward and backward optical flows as well as corresponding warping errors as inputs and produces high-resolution motion boundaries. Furthermore, we show that the obtained motion boundaries, through a fusion sub-network we design, can in turn guide the optical flows for removing the artifacts. The proposed MoBoNet is generic and works with any optical flows. Our motion boundary detection and the refined optical flow estimation achieve results superior to the state of the art.
Shifted Coded Slotted ALOHA
Venue: arXiv cs.IT 2018
Year: 2018

The random access scheme is a fundamental scenario in which users transmit through a shared channel and cannot coordinate each other. In recent years, successive interference cancellation (SIC) was introduced into the random access scheme. It is possible to decode transmitted packets using collided packets by the SIC. The coded slotted ALOHA (CSA) is a random access scheme using the SIC. The CSA encodes each packet using a local code prior to transmission. It is known that the CSA achieves excellent throughput. On the other hand, it is reported that in the coding theory time shift improves the decoding performance for packet-oriented erasure correcting codes. In this paper, we propose a random access scheme which applies the time shift to the CSA in order to achieve better throughput. Numerical examples show that our proposed random access scheme achieves better throughput and packet loss rate than the CSA.
Learning Contracting Vector Fields For Stable Imitation Learning
Venue: arXiv cs.RO 2018
Year: 2018

We propose a new non-parametric framework for learning incrementally stable dynamical systems x' = f(x) from a set of sampled trajectories. We construct a rich family of smooth vector fields induced by certain classes of matrix-valued kernels, whose equilibria are placed exactly at a desired set of locations and whose local contraction and curvature properties at various points can be explicitly controlled using convex optimization. With curl-free kernels, our framework may also be viewed as a mechanism to learn potential fields and gradient flows. We develop large-scale techniques using randomized kernel approximations in this context. We demonstrate our approach, called contracting vector fields (CVF), on imitation learning tasks involving complex point-to-point human handwriting motions.
Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm
Venue: arXiv cs.LO 2018
Year: 2018

Simple stochastic games can be solved by value iteration (VI), which yields a sequence of under-approximations of the value of the game. This sequence is guaranteed to converge to the value only in the limit. Since no stopping criterion is known, this technique does not provide any guarantees on its results. We provide the first stopping criterion for VI on simple stochastic games. It is achieved by additionally computing a convergent sequence of over-approximations of the value, relying on an analysis of the game graph. Consequently, VI becomes an anytime algorithm returning the approximation of the value and the current error bound. As another consequence, we can provide a simulation-based asynchronous VI algorithm, which yields the same guarantees, but without necessarily exploring the whole game graph.
Pose estimation of a single circle using default intrinsic calibration
Venue: arXiv cs.CV 2018
Year: 2018

Circular markers are planar markers which offer great performances for detection and pose estimation. For an uncalibrated camera with an unknown focal length, at least the images of at least two coplanar circles are generally required to recover their poses. Unfortunately, detecting more than one ellipse in the image must be tricky and time-consuming, especially regarding concentric circles. On the other hand, when the camera is calibrated, one circle suffices but the solution is twofold and can hardly be disambiguated. Our contribution is to put beyond this limit by dealing with the uncalibrated case of a camera seeing one circle and discussing how to remove the ambiguity. We propose a new problem formulation that enables to show how to detect geometric configurations in which the ambiguity can be removed. Furthermore, we introduce the notion of default camera intrinsics and show, using intensive empirical works, the surprising observation that very approximate calibration can lead to accurate circle pose estimation.
Understanding Soft-Tissue Behavior for Application to Microlaparoscopic Surface Scan
Venue: arXiv cs.RO 2018
Year: 2018

This paper presents an approach for understanding the soft tissue behavior in surface contact with a probe scanning the tissue. The application domain is confocal microlaparoscopy, mostly used for imaging the outer surface of the organs in the abdominal cavity. The probe is swept over the tissue to collect sequential images to obtain a large field of view with mosaicking. The problem we address is that the tissue also moves with the probe due to its softness; therefore the resulting mosaic is not in the same shape and dimension as traversed by the probe. Our approach is inspired by the finger slip studies and adapts the idea of load-slip phenomenon that explains the movement of the soft part of the finger when dragged on a hard surface. We propose the concept of loading-distance and perform measurements on beef liver and chicken breast tissues. We propose a protocol to determine the loading-distance prior to an automated scan and introduce an approach to compensate the tissue movement in raster scans. Our implementation and experiments show that we can have an image-mosaic of the tissue surface in a desired rectangular shape with this approach.
Detection of Compromised Smart Grid Devices with Machine Learning and Convolution Techniques
Venue: arXiv cs.CR 2018
Year: 2018

The smart grid concept has transformed the traditional power grid into a massive cyber-physical system that depends on advanced two-way communication infrastructure to integrate a myriad of different smart devices. While the introduction of the cyber component has made the grid much more flexible and efficient with so many smart devices, it also broadened the attack surface of the power grid. Particularly, compromised devices pose a great danger to the healthy operations of the smart-grid. For instance, the attackers can control the devices to change the behaviour of the grid and can impact the measurements. In this paper, to detect such misbehaving malicious smart grid devices, we propose a machine learning and convolution-based classification framework. Our framework specifically utilizes system and library call lists at the kernel level of the operating system on both resource-limited and resource-rich smart grid devices such as RTUs, PLCs, PMUs, and IEDs. Focusing on the types and other valuable features extracted from the system calls, the framework can successfully identify malicious smart-grid devices. In order to test the efficacy of the proposed framework, we built a representative testbed conforming to the IEC-61850 protocol suite and evaluated its performance with different system calls. The proposed framework in different evaluation scenarios yields very high accuracy (avg. 91%) which reveals that the framework is effective to overcome compromised smart grid devices problem.
Robust Dual View Deep Agent
Venue: arXiv cs.LG 2018
Year: 2018

Motivated by recent advance of machine learning using Deep Reinforcement Learning this paper proposes a modified architecture that produces more robust agents and speeds up the training process. Our architecture is based on Asynchronous Advantage Actor-Critic (A3C) algorithm where the total input dimensionality is halved by dividing the input into two independent streams. We use ViZDoom, 3D world software that is based on the classical first person shooter video game, Doom, as a test case. The experiments show that in comparison to single input agents, the proposed architecture succeeds to have the same playing performance and shows more robust behavior, achieving significant reduction in the number of training parameters of almost 30%.
Mining the Relationship between Emoji Usage Patterns and Personality
Venue: arXiv cs.SI 2018
Year: 2018

Emojis have been widely used in textual communications as a new way to convey nonverbal cues. An interesting observation is the various emoji usage patterns among different users. In this paper, we investigate the correlation between user personality traits and their emoji usage patterns, particularly on overall amounts and specific preferences. To achieve this goal, we build a large Twitter dataset which includes 352,245 users and over 1.13 billion tweets associated with calculated personality traits and emoji usage patterns. Our correlation and emoji prediction results provide insights into the power of diverse personalities that lead to varies emoji usage patterns as well as its potential in emoji recommendation tasks.
On Asynchronous Non-Dominated Sorting for Steady-State Multiobjective Evolutionary Algorithms
Venue: arXiv cs.DS 2018
Year: 2018

In parallel and distributed environments, generational evolutionary algorithms often do not exploit the full potential of the computation system since they have to wait until the entire population is evaluated before starting selection procedures. Steady-state algorithms are often seen as a solution to this problem, since fitness evaluation can be done by multiple threads in an asynchronous way. However, if the algorithm updates its state in a complicated way, the threads will eventually have to wait until this update finishes. State update procedures that are computationally expensive are common in multiobjective evolutionary algorithms. We have implemented an asynchronous steady-state version of the NSGA-II algorithm. Its most expensive part, non-dominated sorting, determines the time needed to update the state. We turned the existing incremental non-dominated sorting algorithm into an asynchronous one using several concurrency techniques: a single entry-level lock, finer-grained locks working with non-domination levels, and a non-blocking approach using compare-and-set operations. Our experimental results reveal the trade-off between the work-efficiency of the algorithm and the achieved amount of parallelism.
Non-Malleable Extractors and Codes for Composition of Tampering, Interleaved Tampering and More
Venue: arXiv cs.CR 2018
Year: 2018

Non-malleable codes were introduced by Dziembowski, Pietrzak, and Wichs (JACM 2018) as a generalization of standard error correcting codes to handle severe forms of tampering on codewords. This notion has attracted a lot of recent research, resulting in various explicit constructions, which have found applications in tamper-resilient cryptography and connections to other pseudorandom objects in theoretical computer science. We continue the line of investigation on explicit constructions of non-malleable codes in the information theoretic setting, and give explicit constructions for several new classes of tampering functions. (1) Interleaved split-state tampering: Here the codeword is partitioned in an unknown way by an adversary, and then tampered with by a split-state tampering function. (2) Linear function composed with split-state tampering: In this model, the codeword is first tampered with by a split-state adversary, and then the whole tampered codeword is further tampered with by a linear function. In fact our results are stronger, and we can handle linear function composed with interleaved split-state tampering. (3) Bounded communication split-state tampering: In this model, the two split-state tampering adversaries are allowed to participate in a communication protocol with a bounded communication budget. Our results are the first explicit constructions of non-malleable codes in any of these tampering models. We derive all these results from explicit constructions of seedless non-malleable extractors, which we believe are of independent interest. Using our techniques, we also give an improved seedless extractor for an unknown interleaving of two independent sources.
A Collective Neurodynamic Approach to Survivable Virtual Network Embedding
Venue: arXiv cs.DC 2018
Year: 2018

Network virtualization has attracted significant amount of attention in the last few years as one of the key features of cloud computing. Network virtualization allows multiple virtual networks to share physical resources of single substrate network. However, sharing substrate network resources increases impact of single substrate resource failure. One of the commonly applied mechanisms to protect against such failures is provisioning redundant substrate resources for each virtual network to be used to recover affected virtual resources. However, redundant resources decreases cloud revenue by increasing virtual network embedding cost. In this paper, a collective neurodynamic approach has been proposed to reduce amount of provisioned redundant resources and reduce cost of embedding virtual networks. The proposed approach has been evaluated by using simulation and compared against some existing survivable virtual network embedding techniques.
Applying Distributed Ledgers to Manage Workflow Provenance
Venue: arXiv cs.DC 2018
Year: 2018

Sharing provenance across workflow management systems automatically is not currently possible, but the value of such a capability is high since it could greatly reduce the amount of duplicated workflows, accelerate the discovery of new knowledge, and verify the integrity of past and present analyses. Although numerous technological challenges exist to efficiently share provenance information across workflow management systems, permissioned distributed ledgers could surmount many of them. The primary benefit of permissioned distributed ledgers over other technologies is that their distribution is over a peer-to-peer network that encodes transactions across the network into an immutable hash list and achieves consensus on the validity of the new data through a common consensus mechanism. This work discusses provenance and distributed ledgers on their own and then presents an argument that distributed ledgers naturally satisfy many of the requirements of workflow provenance, that provenance information can exist in the ledger in multiple ways, and that a number of novel research areas exist based on this strategy.
FDMO: Feature Assisted Direct Monocular Odometry
Venue: arXiv cs.CV 2018
Year: 2018

Visual Odometry (VO) can be categorized as being either direct or feature based. When the system is calibrated photometrically, and images are captured at high rates, direct methods have shown to outperform feature-based ones in terms of accuracy and processing time; they are also more robust to failure in feature-deprived environments. On the downside, Direct methods rely on heuristic motion models to seed the estimation of camera motion between frames; in the event that these models are violated (e.g., erratic motion), Direct methods easily fail. This paper proposes a novel system entitled FDMO (Feature assisted Direct Monocular Odometry), which complements the advantages of both direct and featured based techniques. FDMO bootstraps indirect feature tracking upon the sub-pixel accurate localized direct keyframes only when failure modes (e.g., large baselines) of direct tracking occur. Control returns back to direct odometry when these conditions are no longer violated. Efficiencies are introduced to help FDMO perform in real time. FDMO shows significant drift (alignment, rotation & scale) reduction when compared to DSO & ORB SLAM when evaluated using the TumMono and EuroC datasets.
Gnowee: A Hybrid Metaheuristic Optimization Algorithm for Constrained, Black Box, Combinatorial Mixed-Integer Design
Venue: arXiv cs.NE 2018
Year: 2018

This paper introduces Gnowee, a modular, Python-based, open-source hybrid metaheuristic optimization algorithm (Available from https://github.com/SlaybaughLab/Gnowee). Gnowee is designed for rapid convergence to nearly globally optimum solutions for complex, constrained nuclear engineering problems with mixed-integer and combinatorial design vectors and high-cost, noisy, discontinuous, black box objective function evaluations. Gnowee's hybrid metaheuristic framework is a new combination of a set of diverse, robust heuristics that appropriately balance diversification and intensification strategies across a wide range of optimization problems. This novel algorithm was specifically developed to optimize complex nuclear design problems; the motivating research problem was the design of material stack-ups to modify neutron energy spectra to specific targeted spectra for applications in nuclear medicine, technical nuclear forensics, nuclear physics, etc. However, there are a wider range of potential applications for this algorithm both within the nuclear community and beyond. To demonstrate Gnowee's behavior for a variety of problem types, comparisons between Gnowee and several well-established metaheuristic algorithms are made for a set of eighteen continuous, mixed-integer, and combinatorial benchmarks. These results demonstrate Gnoweee to have superior flexibility and convergence characteristics over a wide range of design spaces. We anticipate this wide range of applicability will make this algorithm desirable for many complex engineering applications.
The Subfield Codes of Ovoid Codes
Venue: arXiv cs.IT 2018
Year: 2018

Ovoids in $\PG(3, \gf(q))$ have been an interesting topic in coding theory, combinatorics, and finite geometry for a long time. So far only two families of ovoids are known. The first is the elliptic quadratics and the second is the Tits ovoids. It is known that an ovoid in $\PG(3, \gf(q))$ corresponds to a $[q^2+1, 4, q^2-q]$ code over $\gf(q)$, which is called an ovoid code. The objectives of this paper is to study the subfield codes of the two families of ovoid codes. The dimensions, minimum weights, and the weight distributions of the subfield codes of the elliptic quadric codes and Tits ovoid codes are settled. The parameters of the duals of these subfield codes are also studied. Some of the codes presented in this paper are optimal, and some are distance-optimal. The parameters of the subfield codes are new.