OpenRaiser/Intern-Atlas huggingface dataset:
Static-Memory-Hard Functions and Nonlinear Space-Time Tradeoffs via Pebbling
Venue: arXiv cs.CR 2018
Year: 2018

Pebble games were originally formulated to study time-space tradeoffs in computation, modeled by games played on directed acyclic graphs (DAGs). Close connections between pebbling and cryptography have been known for decades. A series of recent research starting with (Alwen and Serbinenko, STOC 2015) has deepened our understanding of the notion of memory-hardness in cryptography --- a useful property of hash functions for deterring large-scale password-cracking attacks --- and has shown memory-hardness to have intricate connections with the theory of graph pebbling. In this work, we improve upon two main limitations of existing models of memory-hardness. First, existing measures of memory-hardness only account for dynamic (i.e., runtime) memory usage, and do not consider static memory usage. We propose a new definition of static-memory-hard function (SHF) which takes into account static memory usage and allows the formalization of larger memory requirements for efficient functions, than in the dynamic setting (where memory usage is inherently bounded by runtime). We then give two SHF constructions based on pebbling; to prove static-memory-hardness, we define a new pebble game ("black-magic pebble game"), and new graph constructions with optimal complexity under our proposed measure. Secondly, existing memory-hardness models implicitly consider linear tradeoffs between the costs of time and space. We propose a new model to capture nonlinear time-space trade-offs and prove that nonlinear tradeoffs can in fact cause adversaries to employ different strategies from linear tradeoffs. Finally, as an additional contribution of independent interest, we present the first asymptotically tight graph construction that achieves the best possible space complexity up to $\log{\log{n}}$-factors for an existing memory-hardness measure called cumulative complexity in the sequential pebbling model.
Binary Constrained Deep Hashing Network for Image Retrieval without Manual Annotation
Venue: arXiv cs.CV 2018
Year: 2018

Learning compact binary codes for image retrieval task using deep neural networks has attracted increasing attention recently. However, training deep hashing networks for the task is challenging due to the binary constraints on the hash codes, the similarity preserving property, and the requirement for a vast amount of labelled images. To the best of our knowledge, none of the existing methods has tackled all of these challenges completely in a unified framework. In this work, we propose a novel end-to-end deep learning approach for the task, in which the network is trained to produce binary codes directly from image pixels without the need of manual annotation. In particular, to deal with the non-smoothness of binary constraints, we propose a novel pairwise constrained loss function, which simultaneously encodes the distances between pairs of hash codes, and the binary quantization error. In order to train the network with the proposed loss function, we propose an efficient parameter learning algorithm. In addition, to provide similar / dissimilar training images to train the network, we exploit 3D models reconstructed from unlabelled images for automatic generation of enormous training image pairs. The extensive experiments on image retrieval benchmark datasets demonstrate the improvements of the proposed method over the state-of-the-art compact representation methods on the image retrieval problem.
Learning Image Conditioned Label Space for Multilabel Classification
Venue: arXiv cs.CV 2018
Year: 2018

This work addresses the task of multilabel image classification. Inspired by the great success from deep convolutional neural networks (CNNs) for single-label visual-semantic embedding, we exploit extending these models for multilabel images. Specifically, we propose an image-dependent ranking model, which returns a ranked list of labels according to its relevance to the input image. In contrast to conventional CNN models that learn an image representation (i.e. the image embedding vector), the developed model learns a mapping (i.e. a transformation matrix) from an image in an attempt to differentiate between its relevant and irrelevant labels. Despite the conceptual simplicity of our approach, experimental results on a public benchmark dataset demonstrate that the proposed model achieves state-of-the-art performance while using fewer training images than other multilabel classification methods.
Density Weighted Connectivity of Grass Pixels in Image Frames for Biomass Estimation
Venue: arXiv cs.CV 2018
Year: 2018

Accurate estimation of the biomass of roadside grasses plays a significant role in applications such as fire-prone region identification. Current solutions heavily depend on field surveys, remote sensing measurements and image processing using reference markers, which often demand big investments of time, effort and cost. This paper proposes Density Weighted Connectivity of Grass Pixels (DWCGP) to automatically estimate grass biomass from roadside image data. The DWCGP calculates the length of continuously connected grass pixels along a vertical orientation in each image column, and then weights the length by the grass density in a surrounding region of the column. Grass pixels are classified using feedforward artificial neural networks and the dominant texture orientation at every pixel is computed using multi-orientation Gabor wavelet filter vote. Evaluations on a field survey dataset show that the DWCGP reduces Root-Mean-Square Error from 5.84 to 5.52 by additionally considering grass density on top of grass height. The DWCGP shows robustness to non-vertical grass stems and to changes of both Gabor filter parameters and surrounding region widths. It also has performance close to human observation and higher than eight baseline approaches, as well as promising results for classifying low vs. high fire risk and identifying fire-prone road regions.
Planning Nonlinear Access Paths for Temporal Bone Surgery
Venue: arXiv cs.RO 2018
Year: 2018

Purpose: Interventions at the otobasis operate in the narrow region of the temporal bone where several highly sensitive organs define obstacles with minimal clearance for surgical instruments. Nonlinear trajectories for potential minimally-invasive interventions can provide larger distances to risk structures and optimized orientations of surgical instruments, thus improving clinical outcomes when compared to existing linear approaches. In this paper, we present fast and accurate planning methods for such nonlinear access paths. Methods: We define a specific motion planning problem in SE(3) = R3 x SO(3) with notable constraints in computation time and goal pose that reflect the requirements of temporal bone surgery.We then present k-RRT-Connect: two suitable motion planners based on bidirectional Rapidly-exploring Random Trees (RRT) to solve this problem efficiently. Results: The benefits of k-RRT-Connect are demonstrated on real CT data of patients. Their general performance is shown on a large set of realistic synthetic anatomies. We also show that these new algorithms outperform state of the art methods based on circular arcs or Bezier-Splines when applied to this specific problem. Conclusion: With this work we demonstrate that pre- and intra-operative planning of nonlinear access paths is possible for minimally-invasive surgeries at the otobasis.
Liver segmentation in CT images using three dimensional to two dimensional fully convolutional network
Venue: arXiv cs.CV 2018
Year: 2018

The need for CT scan analysis is growing for pre-diagnosis and therapy of abdominal organs. Automatic organ segmentation of abdominal CT scan can help radiologists analyze the scans faster and segment organ images with fewer errors. However, existing methods are not efficient enough to perform the segmentation process for victims of accidents and emergencies situations. In this paper we propose an efficient liver segmentation with our 3D to 2D fully connected network (3D-2D-FCN). The segmented mask is enhanced by means of conditional random field on the organ's border. Consequently, we segment a target liver in less than a minute with Dice score of 93.52.
Convergent Actor-Critic Algorithms Under Off-Policy Training and Function Approximation
Venue: arXiv cs.AI 2018
Year: 2018

We present the first class of policy-gradient algorithms that work with both state-value and policy function-approximation, and are guaranteed to converge under off-policy training. Our solution targets problems in reinforcement learning where the action representation adds to the-curse-of-dimensionality; that is, with continuous or large action sets, thus making it infeasible to estimate state-action value functions (Q functions). Using state-value functions helps to lift the curse and as a result naturally turn our policy-gradient solution into classical Actor-Critic architecture whose Actor uses state-value function for the update. Our algorithms, Gradient Actor-Critic and Emphatic Actor-Critic, are derived based on the exact gradient of averaged state-value function objective and thus are guaranteed to converge to its optimal solution, while maintaining all the desirable properties of classical Actor-Critic methods with no additional hyper-parameters. To our knowledge, this is the first time that convergent off-policy learning methods have been extended to classical Actor-Critic methods with function approximation.
Driver Hand Localization and Grasp Analysis: A Vision-based Real-time Approach
Venue: arXiv cs.CV 2018
Year: 2018

Extracting hand regions and their grasp information from images robustly in real-time is critical for occupants' safety and in-vehicular infotainment applications. It must however, be noted that naturalistic driving scenes suffer from rapidly changing illumination and occlusion. This is aggravated by the fact that hands are highly deformable objects, and change in appearance frequently. This work addresses the task of accurately localizing driver hands and classifying the grasp state of each hand. We use a fast ConvNet to first detect likely hand regions. Next, a pixel-based skin classifier that takes into account the global illumination changes is used to refine the hand detections and remove false positives. This step generates a pixel-level mask for each hand. Finally, we study each such masked regions and detect if the driver is grasping the wheel, or in some cases a mobile phone. Through evaluation we demonstrate that our method can outperform state-of-the-art pixel based hand detectors, while running faster (at 35 fps) than other deep ConvNet based frameworks even for grasp analysis. Hand mask cues are shown to be crucial when analyzing a set of driver hand gestures (wheel/mobile phone grasp and no-grasp) in naturalistic driving settings. The proposed detection and localization pipeline hence can act as a general framework for real-time hand detection and gesture classification.
Multi-Sensor Integration for Indoor 3D Reconstruction
Venue: arXiv cs.CV 2018
Year: 2018

Outdoor maps and navigation information delivered by modern services and technologies like Google Maps and Garmin navigators have revolutionized the lifestyle of many people. Motivated by the desire for similar navigation systems for indoor usage from consumers, advertisers, emergency rescuers/responders, etc., many indoor environments such as shopping malls, museums, casinos, airports, transit stations, offices, and schools need to be mapped. Typically, the environment is first reconstructed by capturing many point clouds from various stations and defining their spatial relationships. Currently, there is a lack of an accurate, rigorous, and speedy method for relating point clouds in indoor, urban, satellite-denied environments. This thesis presents a novel and automatic way for fusing calibrated point clouds obtained using a terrestrial laser scanner and the Microsoft Kinect by integrating them with a low-cost inertial measurement unit. The developed system, titled the Scannect, is the first joint static-kinematic indoor 3D mapper.
Nonlinear Online Learning with Adaptive Nyström Approximation
Venue: arXiv cs.LG 2018
Year: 2018

Use of nonlinear feature maps via kernel approximation has led to success in many online learning tasks. As a popular kernel approximation method, Nyström approximation, has been well investigated, and various landmark points selection methods have been proposed to improve the approximation quality. However, these improved Nyström methods cannot be directly applied to the online learning setting as they need to access the entire dataset to learn the landmark points, while we need to update model on-the-fly in the online setting. To address this challenge, we propose Adaptive Nyström approximation for solving nonlinear online learning problems. The key idea is to adaptively modify the landmark points via online kmeans and adjust the model accordingly via solving least square problem followed by a gradient descent step. We show that the resulting algorithm outperforms state-of-the-art online learning methods under the same budget.
Numerical integration in arbitrary-precision ball arithmetic
Venue: arXiv cs.MS 2018
Year: 2018

We present an implementation of arbitrary-precision numerical integration with rigorous error bounds in the Arb library. Rapid convergence is ensured for piecewise complex analytic integrals by use of the Petras algorithm, which combines adaptive bisection with adaptive Gaussian quadrature where error bounds are determined via complex magnitudes without evaluating derivatives. The code is general, easy to use, and efficient, often outperforming existing non-rigorous software.
Stereo obstacle detection for unmanned surface vehicles by IMU-assisted semantic segmentation
Venue: arXiv cs.RO 2018
Year: 2018

A new obstacle detection algorithm for unmanned surface vehicles (USVs) is presented. A state-of-the-art graphical model for semantic segmentation is extended to incorporate boat pitch and roll measurements from the on-board inertial measurement unit (IMU), and a stereo verification algorithm that consolidates tentative detections obtained from the segmentation is proposed. The IMU readings are used to estimate the location of horizon line in the image, which automatically adjusts the priors in the probabilistic semantic segmentation model. We derive the equations for projecting the horizon into images, propose an efficient optimization algorithm for the extended graphical model, and offer a practical IMU-camera-USV calibration procedure. Using an USV equipped with multiple synchronized sensors, we captured a new challenging multi-modal dataset, and annotated its images with water edge and obstacles. Experimental results show that the proposed algorithm significantly outperforms the state of the art, with nearly 30% improvement in water-edge detection accuracy, an over 21% reduction of false positive rate, an almost 60% reduction of false negative rate, and an over 65% increase of true positive rate, while its Matlab implementation runs in real-time.
Near Isometric Terminal Embeddings for Doubling Metrics
Venue: arXiv cs.DS 2018
Year: 2018

Given a metric space $(X,d)$, a set of terminals $K\subseteq X$, and a parameter $t\ge 1$, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in $K\times X$ up to a factor of $t$, and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, i.e., $t=1+ε$ for some small $0<ε<1$, is currently known. Here we devise such terminal metric structures for {\em doubling} metrics, and show that essentially any metric structure with distortion $1+ε$ and size $s(|X|)$ has its terminal counterpart, with distortion $1+O(ε)$ and size $s(|K|)+1$. In particular, for any doubling metric on $n$ points, a set of $k=o(n)$ terminals, and constant $0<ε<1$, there exists: (1) A spanner with stretch $1+ε$ for pairs in $K\times X$, with $n+o(n)$ edges. (2) A labeling scheme with stretch $1+ε$ for pairs in $K\times X$, with label size $\approx \log k$. (3) An embedding into $\ell_\infty^d$ with distortion $1+ε$ for pairs in $K\times X$, where $d=O(\log k)$. Moreover, surprisingly, the last two results apply if only $K$ is a doubling metric, while $X$ can be arbitrary.
On Rational Delegations in Liquid Democracy
Venue: arXiv cs.MA 2018
Year: 2018

Liquid democracy is a proxy voting method where proxies are delegable. We propose and study a game-theoretic model of liquid democracy to address the following question: when is it rational for a voter to delegate her vote? We study the existence of pure-strategy Nash equilibria in this model, and how group accuracy is affected by them. We complement these theoretical results by means of agent-based simulations to study the effects of delegations on group's accuracy on variously structured social networks.
Inverse analysis of traction-separation relationship based on sequentially linear approach
Venue: arXiv cs.CE 2018
Year: 2018

Traction-separation relationship is an important material characteristic describing the fracture behaviour of quasi-brittle solids. A new numerical scheme for identification of the traction-separation relation by inverse analysis of data obtained from various types of fracture tests is proposed. Due to employing the concept of sequentially linear analysis, the method exhibits a superior numerical stability and versatility. The applicability and effectiveness of the proposed method is demonstrated on examples involving identification of the traction-separation relationship using experimental data from various test configurations.
When Renewable Energy Meets Building Thermal Mass: A Real-time Load Management Scheme
Venue: arXiv cs.SY 2018
Year: 2018

We consider the optimal power management in renewable driven smart building MicroGrid under noise corrupted conditions as a stochastic optimization problem. We first propose our user satisfaction and electricity consumption balanced (USECB) profit model as the objective for optimal power management. We then cast the problem in noise corrupted conditions into the class of expectation maximizing in stochastic optimization problem with convex constraints. For this task, we design a Bregemen projection based mirror decent algorithm as an approximation solution to our stochastic optimization problem. Convergence and upper-bound of our algorithm with proof are also provided in our paper. We then conduct a broad type of experiment in our simulation to test the justification of our model as well as the effectiveness of our algorithm.
A Learning Based Approach for Uncertainty Analysis in Numerical Weather Prediction Models
Venue: arXiv cs.NA 2018
Year: 2018

Complex numerical weather prediction models incorporate a variety of physical processes, each described by multiple alternative physical schemes with specific parameters. The selection of the physical schemes and the choice of the corresponding physical parameters during model configuration can significantly impact the accuracy of model forecasts. There is no combination of physical schemes that works best for all times, at all locations, and under all conditions. It is therefore of considerable interest to understand the interplay between the choice of physics and the accuracy of the resulting forecasts under different conditions. This paper demonstrates the use of machine learning techniques to study the uncertainty in numerical weather prediction models due to the interaction of multiple physical processes. The first problem addressed herein is the estimation of systematic model errors in output quantities of interest at future times, and the use of this information to improve the model forecasts. The second problem considered is the identification of those specific physical processes that contribute most to the forecast uncertainty in the quantity of interest under specified meteorological conditions. The discrepancies between model results and observations at past times are used to learn the relationships between the choice of physical processes and the resulting forecast errors. Numerical experiments are carried out with the Weather Research and Forecasting (WRF) model. The output quantity of interest is the model precipitation, a variable that is both extremely important and very challenging to forecast. The physical processes under consideration include various micro-physics schemes, cumulus parameterizations, short wave, and long wave radiation schemes. The experiments demonstrate the strong potential of machine learning approaches to aid the study of model errors.
Learning Hyperedge Replacement Grammars for Graph Generation
Venue: arXiv cs.SI 2018
Year: 2018

The discovery and analysis of network patterns are central to the scientific enterprise. In the present work, we developed and evaluated a new approach that learns the building blocks of graphs that can be used to understand and generate new realistic graphs. Our key insight is that a graph's clique tree encodes robust and precise information. We show that a Hyperedge Replacement Grammar (HRG) can be extracted from the clique tree, and we develop a fixed-size graph generation algorithm that can be used to produce new graphs of a specified size. In experiments on large real-world graphs, we show that graphs generated from the HRG approach exhibit a diverse range of properties that are similar to those found in the original networks. In addition to graph properties like degree or eigenvector centrality, what a graph "looks like" ultimately depends on small details in local graph substructures that are difficult to define at a global level. We show that the HRG model can also preserve these local substructures when generating new graphs.
Novel differential quadrature element method for higher order strain gradient elasticity theory
Venue: arXiv cs.CE 2018
Year: 2018

In this paper, we propose a novel and efficient differential quadrature element based on Lagrange interpolation to solve a sixth order partial differential equations encountered in non-classical beam theories. These non-classical theories render displacement, slope and curvature as degrees of freedom for an Euler-Bernoulli beam. A generalize scheme is presented herein to implementation the multi-degrees degrees of freedom associated with these non-classical theories in a simplified and efficient way. The proposed element has displacement as the only degree of freedom in the domain, whereas, at the boundaries it has displacement, slope and curvature. Further, we extend this methodology and formulate two novel versions of plate element for gradient elasticity theory. In the first version, Lagrange interpolation is assumed in $x$ and $y$ directions and the second version is based on mixed interpolation, with Lagrange interpolation in $x$ direction and Hermite interpolation in $y$ direction. The procedure to compute the modified weighting coefficients by incorporating the classical and non-classical boundary conditions is explained. The efficiency of the proposed elements is demonstrated through numerical examples on static analysis of gradient elastic beams and plates for different boundary conditions.
LIDIOMS: A Multilingual Linked Idioms Data Set
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we describe the LIDIOMS data set, a multilingual RDF representation of idioms currently containing five languages: English, German, Italian, Portuguese, and Russian. The data set is intended to support natural language processing applications by providing links between idioms across languages. The underlying data was crawled and integrated from various sources. To ensure the quality of the crawled data, all idioms were evaluated by at least two native speakers. Herein, we present the model devised for structuring the data. We also provide the details of linking LIDIOMS to well-known multilingual data sets such as BabelNet. The resulting data set complies with best practices according to Linguistic Linked Open Data Community.