OpenRaiser/Intern-Atlas huggingface dataset:
Accelerating Generalized Linear Models with MLWeaving: A One-Size-Fits-All System for Any-precision Learning (Technical Report)
Venue: arXiv cs.DS 2019
Year: 2019

Learning from the data stored in a database is an important function increasingly available in relational engines. Methods using lower precision input data are of special interest given their overall higher efficiency but, in databases, these methods have a hidden cost: the quantization of the real value into a smaller number is an expensive step. To address the issue, in this paper we present MLWeaving, a data structure and hardware acceleration technique intended to speed up learning of generalized linear models in databases. ML-Weaving provides a compact, in-memory representation enabling the retrieval of data at any level of precision. MLWeaving also takes advantage of the increasing availability of FPGA-based accelerators to provide a highly efficient implementation of stochastic gradient descent. The solution adopted in MLWeaving is more efficient than existing designs in terms of space (since it can process any resolution on the same design) and resources (via the use of bit-serial multipliers). MLWeaving also enables the runtime tuning of precision, instead of a fixed precision level during the training. We illustrate this using a simple, dynamic precision schedule. Experimental results show MLWeaving achieves up to16 performance improvement over low-precision CPU implementations of first-order methods.
Research on the pixel-based and object-oriented methods of urban feature extraction with GF-2 remote-sensing images
Venue: arXiv cs.OH 2019
Year: 2019

During the rapid urbanization construction of China, acquisition of urban geographic information and timely data updating are important and fundamental tasks for the refined management of cities. With the development of domestic remote sensing technology, the application of Gaofen-2 (GF-2) high-resolution remote sensing images can greatly improve the accuracy of information extraction. This paper introduces an approach using object-oriented classification methods for urban feature extraction based on GF-2 satellite data. A combination of spectral, spatial attributes and membership functions was employed for mapping the urban features of Qinhuai District, Nanjing. The data preprocessing is carried out by ENVI software, and the subsequent data is exported into the eCognition software for object-oriented classification and extraction of urban feature information. Finally, the obtained raster image classification results are vectorized using the ARCGIS software, and the vector graphics are stored in the library, which can be used for further analysis and modeling. Accuracy assessment was performed using ground truth data acquired by visual interpretation and from other reliable secondary data sources. Compared with the result of pixel-based supervised (neural net) classification, the developed object-oriented method can significantly improve extraction accuracy, and after manual interpretation, an overall accuracy of 95.44% can be achieved, with a Kappa coefficient of 0.9405, which objectively confirmed the superiority of the object-oriented method and the feasibility of the utilization of GF-2 satellite data.
Descriptive Complexity of Deterministic Polylogarithmic Time and Space
Venue: arXiv cs.LO 2019
Year: 2019

We propose logical characterizations of problems solvable in deterministic polylogarithmic time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two-sorted logic that separates the elements of the input domain from the bit positions needed to address these elements. We prove that the inflationary and partial fixed point vartiants of this logic capture PolylogTime and PolylogSpace, respectively. In the course of proving that our logic indeed captures PolylogTime on finite ordered structures, we introduce a variant of random-access Turing machines that can access the relations and functions of a structure directly. We investigate whether an explicit predicate for the ordering of the domain is needed in our PolylogTime logic. Finally, we present the open problem of finding an exact characterization of order-invariant queries in PolylogTime.
El mètode de les línies per a la resolució numèrica d'equacions en derivades parcials. The method of lines for numerical solutions of partial differential equations
Venue: arXiv cs.NA 2019
Year: 2019

In this paper, we describe a semi-discrete method for a numerical resolution of a type of partial differential equations, called the method of lines (MOL). This method is based on the discretization of all but one of the variables of the problem. We illustrate this method by solving the Laplace equation in Cartesian coordinates. We compare the concepts used by the MOL with respect to the analytical method of variable separation. We show that the results obtained with the MOL are very good approximations of the analytical solutions.
Geometry Mapping, Complete Pascal Scheme versus Standard Bilinear Approach
Venue: arXiv cs.NA 2019
Year: 2019

This paper presents a complete Pascal interpolation scheme for use in the plane geometry mapping applied in association with numerical methods. The geometry of a domain element is approximated by a complete Pascal polynomial. The interpolation procedure is formulated in a natural coordinate system. It also presents the methodology of constructing shape functions of Pascal type and establishing a transformation relation between natural and Cartesian variables. The performance of the presented approach is investigated firstly by calculating the geometrical properties of an arbitrary quadrilateral cross-section like area and moments of inertia and comparing the results with the exact values and with those provided by the standard linear approach and a serendipity family approach. Secondly, the assessment of the scheme follows using a straight-sided, compatible quadrilateral finite element for plate bending of which geometry is approximated by a complete set of second order with six free parameters. Triangular and quadrilateral shaped plates with different boundary conditions are computed and compared with well-known results in the literature. The presented procedure is of general applicability for elements with curved edges and not limited to straight-sided edges in the framework of numerical methods.
On the Traffic Impacts of Optimally Controlled Connected and Automated Vehicles
Venue: arXiv cs.SY 2019
Year: 2019

The implementation of connected and automated vehicle (CAV) technologies enables a novel computational framework for real-time control actions aimed at optimizing energy consumption and associated benefits. Several research efforts reported in the literature to date have proposed decentralized control algorithms to coordinate CAVs in various traffic scenarios, e.g., highway on-ramps, intersections, and roundabouts. However, the impact of optimally coordinating CAVs on the performance of a transportation network has not been thoroughly analyzed yet. In this paper, we apply a decentralized optimal control framework in a transportation network and compare its performance to a baseline scenario consisting of human-driven vehicles. We show that introducing of CAVs yields radically improved roadway capacity and network performance.
Filling Gender & Number Gaps in Neural Machine Translation with Black-box Context Injection
Venue: arXiv cs.CL 2019
Year: 2019

When translating from a language that does not morphologically mark information such as gender and number into a language that does, translation systems must "guess" this missing information, often leading to incorrect translations in the given context. We propose a black-box approach for injecting the missing information to a pre-trained neural machine translation system, allowing to control the morphological variations in the generated translations without changing the underlying model or training data. We evaluate our method on an English to Hebrew translation task, and show that it is effective in injecting the gender and number information and that supplying the correct information improves the translation accuracy in up to 2.3 BLEU on a female-speaker test set for a state-of-the-art online black-box system. Finally, we perform a fine-grained syntactic analysis of the generated translations that shows the effectiveness of our method.
An adaptive strategy based on conforming quadtree meshes for kinematic limit analysis
Venue: arXiv cs.CE 2019
Year: 2019

We propose a simple and efficient scheme based on adaptive finite elements over conforming quadtree meshes for collapse plastic analysis of structures. Our main interest in kinematic limit analysis is concerned with both purely cohesive-frictional and cohesive materials. It is shown that the most computational efficiency for collapse plastic problems is to employ an adaptive mesh strategy on quadtree meshes. However, a major difficulty in finite element formulations is the appearance of hanging nodes during adaptive process. This can be resolved by a definition of conforming quadtree meshes in the context of polygonal elements. Piecewise-linear shape functions enhanced with generalized bubble functions in barycentric coordinates are used to approximate the velocity field. Numerical results prove the reliability and benefit of the present approach.
Auto-Encoding Progressive Generative Adversarial Networks For 3D Multi Object Scenes
Venue: arXiv cs.CV 2019
Year: 2019

3D multi object generative models allow us to synthesize a large range of novel 3D multi object scenes and also identify objects, shapes, layouts and their positions. But multi object scenes are difficult to create because of the dataset being multimodal in nature. The conventional 3D generative adversarial models are not efficient in generating multi object scenes, they usually tend to generate either one object or generate fuzzy results of multiple objects. Auto-encoder models have much scope in feature extraction and representation learning using the unsupervised paradigm in probabilistic spaces. We try to make use of this property in our proposed model. In this paper we propose a novel architecture using 3DConvNets trained with the progressive training paradigm that has been able to generate realistic high resolution 3D scenes of rooms, bedrooms, offices etc. with various pieces of furniture and objects. We make use of the adversarial auto-encoder along with the WGAN-GP loss parameter in our discriminator loss function. Finally this new approach to multi object scene generation has also been able to generate more number of objects per scene.
Genetic Algorithm for a class of Knapsack Problems
Venue: arXiv cs.NE 2019
Year: 2019

The 0/1 knapsack problem is weakly NP-hard in that there exist pseudo-polynomial time algorithms based on dynamic programming that can solve it exactly. There are also the core branch and bound algorithms that can solve large randomly generated instances in a very short amount of time. However, as the correlation between the variables is increased, the difficulty of the problem increases. Recently a new class of knapsack problems was introduced by D. Pisinger called the spanner knapsack instances. These instances are unsolvable by the core branch and bound instances; and as the size of the coefficients and the capacity constraint increase, the spanner instances are unsolvable even by dynamic programming based algorithms. In this paper, a genetic algorithm is presented for spanner knapsack instances. Results show that the algorithm is capable of delivering optimum solutions within a reasonable amount of computational duration.
OpenCL-based FPGA accelerator for disparity map generation with stereoscopic event cameras
Venue: arXiv cs.CV 2019
Year: 2019

Although event-based cameras are already commercially available. Vision algorithms based on them are still not common. As a consequence, there are few Hardware Accelerators for them. In this work we present some experiments to create FPGA accelerators for a well-known vision algorithm using event-based cameras. We present a stereo matching algorithm to create a stream of disparity events disparity map and implement several accelerators using the Intel FPGA OpenCL tool-chain. The results show that multiple designs can be easily tested and that a performance speedup of more than 8x can be achieved with simple code transformations.
Prediction and Sampling with Local Graph Transforms for Quasi-Lossless Light Field Compression
Venue: arXiv cs.CV 2019
Year: 2019

Graph-based transforms have been shown to be powerful tools in terms of image energy compaction. However, when the support increases to best capture signal dependencies, the computation of the basis functions becomes rapidly untractable. This problem is in particular compelling for high dimensional imaging data such as light fields. The use of local transforms with limited supports is a way to cope with this computational difficulty. Unfortunately, the locality of the support may not allow us to fully exploit long term signal dependencies present in both the spatial and angular dimensions in the case of light fields. This paper describes sampling and prediction schemes with local graph-based transforms enabling to efficiently compact the signal energy and exploit dependencies beyond the local graph support. The proposed approach is investigated and is shown to be very efficient in the context of spatio-angular transforms for quasi-lossless compression of light fields.
Analyzing GPU Tensor Core Potential for Fast Reductions
Venue: arXiv cs.DC 2019
Year: 2019

The Nvidia GPU architecture has introduced new computing elements such as the \textit{tensor cores}, which are special processing units dedicated to perform fast matrix-multiply-accumulate (MMA) operations and accelerate \textit{Deep Learning} applications. In this work we present the idea of using tensor cores for a different purpose such as the parallel arithmetic reduction problem, and propose a new GPU tensor-core based algorithm as well as analyze its potential performance benefits in comparison to a traditional GPU-based one. The proposed method, encodes the reduction of $n$ numbers as a set of $m\times m$ MMA tensor-core operations (for Nvidia's Volta architecture $m=16$) and takes advantage from the fact that each MMA operation takes just one GPU cycle. When analyzing the cost under a simplified GPU computing model, the result is that the new algorithm manages to reduce a problem of $n$ numbers in $T(n) = 5\log_{m^2}(n)$ steps with a speedup of $S = \frac{4}{5}\log_2(m^2)$.
Recognizing and Tracking High-Level, Human-Meaningful Navigation Features of Occupancy Grid Maps
Venue: arXiv cs.RO 2019
Year: 2019

This paper describes a system whereby a robot detects and track human-meaningful navigational cues as it navigates in an indoor environment. It is intended as the sensor front-end for a mobile robot system that can communicate its navigational context with human users. From simulated LiDAR scan data we construct a set of 2D occupancy grid bitmaps, then hand-label these with human-scale navigational features such as closed doors, open corridors and intersections. We train a Convolutional Neural Network (CNN) to recognize these features on input bitmaps. In our demonstration system, these features are detected at every time step then passed to a tracking module that does frame-to-frame data association to improve detection accuracy and identify stable unique features. We evaluate the system in both simulation and the real world. We compare the performance of using input occupancy grids obtained directly from LiDAR data, or incrementally constructed with SLAM, and their combination.
Trace Equivalence and Epistemic Logic to Express Security Properties
Venue: arXiv cs.LO 2019
Year: 2019

In process algebras, security properties are expressed as equivalences between processes, but which equivalence is suitable is not clear. This means that there is a gap between an intuitive security notion and the formulation. Appropriate formalization is essential for verification, and our purpose is bridging this gap. By chasing scope extrusions, we prove that trace equivalence is congruent. Moreover, we construct an epistemic logic for the applied pi calculus and show that its logical equivalence agrees with the trace equivalence. We use the epistemic logic to show that trace equivalence is pertinent in the presence of a non-adaptive attacker.
Learning Quantum Graphical Models using Constrained Gradient Descent on the Stiefel Manifold
Venue: arXiv cs.LG 2019
Year: 2019

Quantum graphical models (QGMs) extend the classical framework for reasoning about uncertainty by incorporating the quantum mechanical view of probability. Prior work on QGMs has focused on hidden quantum Markov models (HQMMs), which can be formulated using quantum analogues of the sum rule and Bayes rule used in classical graphical models. Despite the focus on developing the QGM framework, there has been little progress in learning these models from data. The existing state-of-the-art approach randomly initializes parameters and iteratively finds unitary transformations that increase the likelihood of the data. While this algorithm demonstrated theoretical strengths of HQMMs over HMMs, it is slow and can only handle a small number of hidden states. In this paper, we tackle the learning problem by solving a constrained optimization problem on the Stiefel manifold using a well-known retraction-based algorithm. We demonstrate that this approach is not only faster and yields better solutions on several datasets, but also scales to larger models that were prohibitively slow to train via the earlier method.
RadegastXDB - Prototype of Native XML Database Management System: Technical Report
Venue: arXiv cs.DB 2019
Year: 2019

A lot of advances in the processing of XML data have been proposed in last two decades. There were many approaches focused on the efficient processing of twig pattern queries (TPQ). However, including the TPQ into an XQuery compiler is not a straightforward task and current XML DBMSs process XQueries without any TPQ detection. In this paper, we demonstrate our prototype of a native XML DBMS called RadegastXDB that uses a TPQ detection to accelerate structural XQueries. Such a detection allows us to utilize state-of-the-art TPQ processing algorithms. Our experiments show that, for the structural queries, these algorithms and state-of-the-art XML indexing techniques make our prototype faster than all of the current XML DBMSs, especially for large data collections. We also show that using the same techniques is also efficient for the processing of queries with value predicates.
Strengthened Information-theoretic Bounds on the Generalization Error
Venue: arXiv cs.IT 2019
Year: 2019

The following problem is considered: given a joint distribution $P_{XY}$ and an event $E$, bound $P_{XY}(E)$ in terms of $P_XP_Y(E)$ (where $P_XP_Y$ is the product of the marginals of $P_{XY}$) and a measure of dependence of $X$ and $Y$. Such bounds have direct applications in the analysis of the generalization error of learning algorithms, where $E$ represents a large error event and the measure of dependence controls the degree of overfitting. Herein, bounds are demonstrated using several information-theoretic metrics, in particular: mutual information, lautum information, maximal leakage, and $J_\infty$. The mutual information bound can outperform comparable bounds in the literature by an arbitrarily large factor.
Program Classification Using Gated Graph Attention Neural Network for Online Programming Service
Venue: arXiv cs.AI 2019
Year: 2019

The online programing services, such as Github,TopCoder, and EduCoder, have promoted a lot of social interactions among the service users. However, the existing social interactions is rather limited and inefficient due to the rapid increasing of source-code repositories, which is difficult to explore manually. The emergence of source-code mining provides a promising way to analyze those source codes, so that those source codes can be relatively easy to understand and share among those service users. Among all the source-code mining attempts,program classification lays a foundation for various tasks related to source-code understanding, because it is impossible for a machine to understand a computer program if it cannot classify the program correctly. Although numerous machine learning models, such as the Natural Language Processing (NLP) based models and the Abstract Syntax Tree (AST) based models, have been proposed to classify computer programs based on their corresponding source codes, the existing works cannot fully characterize the source codes from the perspective of both the syntax and semantic information. To address this problem, we proposed a Graph Neural Network (GNN) based model, which integrates data flow and function call information to the AST,and applies an improved GNN model to the integrated graph, so as to achieve the state-of-art program classification accuracy. The experiment results have shown that the proposed work can classify programs with accuracy over 97%.
Successive Over Relaxation Q-Learning
Venue: arXiv cs.LG 2019
Year: 2019

In a discounted reward Markov Decision Process (MDP), the objective is to find the optimal value function, i.e., the value function corresponding to an optimal policy. This problem reduces to solving a functional equation known as the Bellman equation and a fixed point iteration scheme known as the value iteration is utilized to obtain the solution. In literature, a successive over-relaxation based value iteration scheme is proposed to speed-up the computation of the optimal value function. The speed-up is achieved by constructing a modified Bellman equation that ensures faster convergence to the optimal value function. However, in many practical applications, the model information is not known and we resort to Reinforcement Learning (RL) algorithms to obtain optimal policy and value function. One such popular algorithm is Q-learning. In this paper, we propose Successive Over-Relaxation (SOR) Q-learning. We first derive a modified fixed point iteration for SOR Q-values and utilize stochastic approximation to derive a learning algorithm to compute the optimal value function and an optimal policy. We then prove the almost sure convergence of the SOR Q-learning to SOR Q-values. Finally, through numerical experiments, we show that SOR Q-learning is faster compared to the standard Q-learning algorithm.
Data-Driven Model Predictive Control for Food-Cutting
Venue: arXiv cs.RO 2019
Year: 2019

Modelling of contact-rich tasks is challenging and cannot be entirely solved using classical control approaches due to the difficulty of constructing an analytic description of the contact dynamics. Additionally, in a manipulation task like food-cutting, purely learning-based methods such as Reinforcement Learning, require either a vast amount of data that is expensive to collect on a real robot, or a highly realistic simulation environment, which is currently not available. This paper presents a data-driven control approach that employs a recurrent neural network to model the dynamics for a Model Predictive Controller. We build upon earlier work limited to torque-controlled robots and redefine it for velocity controlled ones. We incorporate force/torque sensor measurements, reformulate and further extend the control problem formulation. We evaluate the performance on objects used for training, as well as on unknown objects, by means of the cutting rates achieved and demonstrate that the method can efficiently treat different cases with only one dynamic model. Finally we investigate the behavior of the system during force-critical instances of cutting and illustrate its adaptive behavior in difficult cases.