OpenRaiser/Intern-Atlas huggingface dataset:
Improving Distantly Supervised Relation Extraction using Word and Entity Based Attention
Venue: arXiv cs.CL 2018
Year: 2018

Relation extraction is the problem of classifying the relationship between two entities in a given sentence. Distant Supervision (DS) is a popular technique for developing relation extractors starting with limited supervision. We note that most of the sentences in the distant supervision relation extraction setting are very long and may benefit from word attention for better sentence representation. Our contributions in this paper are threefold. Firstly, we propose two novel word attention models for distantly- supervised relation extraction: (1) a Bi-directional Gated Recurrent Unit (Bi-GRU) based word attention model (BGWA), (2) an entity-centric attention model (EA), and (3) a combination model which combines multiple complementary models using weighted voting method for improved relation extraction. Secondly, we introduce GDS, a new distant supervision dataset for relation extraction. GDS removes test data noise present in all previous distant- supervision benchmark datasets, making credible automatic evaluation possible. Thirdly, through extensive experiments on multiple real-world datasets, we demonstrate the effectiveness of the proposed methods.
Metamorphs: Bistable Planar Structures
Venue: arXiv cs.GR 2018
Year: 2018

Extreme deformation can drastically morph a structure from one structural form into another. Programming such deformation properties into the structure is often challenging and in many cases an impossible task. The morphed forms do not hold and usually relapse to the original form, where the structure is in its lowest energy state. For example, a stick, when bent, resists its bent form and tends to go back to its initial straight form, where it holds the least amount of potential energy. In this project, we present a computational design method which can create fabricable planar structure that can morph into two different bistable forms. Once the user provides the initial desired forms, the method automatically creates support structures (internal springs), such that, the structure can not only morph, but also hold the respective forms under external force application. We achieve this through an iterative nonlinear optimization strategy for shaping the potential energy of the structure in the two forms simultaneously. Our approach guarantees first and second-order stability with respect to the potential energy of the bistable structure.
A Trajectory Calculus for Qualitative Spatial Reasoning Using Answer Set Programming
Venue: arXiv cs.AI 2018
Year: 2018

Spatial information is often expressed using qualitative terms such as natural language expressions instead of coordinates; reasoning over such terms has several practical applications, such as bus routes planning. Representing and reasoning on trajectories is a specific case of qualitative spatial reasoning that focuses on moving objects and their paths. In this work, we propose two versions of a trajectory calculus based on the allowed properties over trajectories, where trajectories are defined as a sequence of non-overlapping regions of a partitioned map. More specifically, if a given trajectory is allowed to start and finish at the same region, 6 base relations are defined (TC-6). If a given trajectory should have different start and finish regions but cycles are allowed within, 10 base relations are defined (TC-10). Both versions of the calculus are implemented as ASP programs; we propose several different encodings, including a generalised program capable of encoding any qualitative calculus in ASP. All proposed encodings are experimentally evaluated using a real-world dataset. Experiment results show that the best performing implementation can scale up to an input of 250 trajectories for TC-6 and 150 trajectories for TC-10 for the problem of discovering a consistent configuration, a significant improvement compared to previous ASP implementations for similar qualitative spatial and temporal calculi. This manuscript is under consideration for acceptance in TPLP.
Loop Restricted Existential Rules and First-order Rewritability for Query Answering
Venue: arXiv cs.AI 2018
Year: 2018

In ontology-based data access (OBDA), the classical database is enhanced with an ontology in the form of logical assertions generating new intensional knowledge. A powerful form of such logical assertions is the tuple-generating dependencies (TGDs), also called existential rules, where Horn rules are extended by allowing existential quantifiers to appear in the rule heads. In this paper we introduce a new language called loop restricted (LR) TGDs (existential rules), which are TGDs with certain restrictions on the loops embedded in the underlying rule set. We study the complexity of this new language. We show that the conjunctive query answering (CQA) under the LR TGDs is decid- able. In particular, we prove that this language satisfies the so-called bounded derivation-depth prop- erty (BDDP), which implies that the CQA is first-order rewritable, and its data complexity is in AC0 . We also prove that the combined complexity of the CQA is EXPTIME complete, while the language membership is PSPACE complete. Then we extend the LR TGDs language to the generalised loop restricted (GLR) TGDs language, and prove that this class of TGDs still remains to be first-order rewritable and properly contains most of other first-order rewritable TGDs classes discovered in the literature so far.
Estimation of Tissue Oxygen Saturation from RGB Images based on Pixel-level Image Translation
Venue: arXiv cs.CV 2018
Year: 2018

Intra-operative measurement of tissue oxygen saturation (StO2) has been widely explored by pulse oximetry or hyperspectral imaging (HSI) to assess the function and viability of tissue. In this paper we propose a pixel- level image-to-image translation approach based on conditional Generative Adversarial Networks (cGAN) to estimate tissue oxygen saturation (StO2) directly from RGB images. The real-time performance and non-reliance on additional hardware, enable a seamless integration of the proposed method into surgical and diagnostic workflows with standard endoscope systems. For validation, RGB images and StO2 ground truth were simulated and estimated from HSI images collected by a liquid crystal tuneable filter (LCTF) endoscope for three tissue types (porcine bowel, lamb uterus and rabbit uterus). The result show that the proposed method can achieve visually identical images with comparable accuracy.
Finite Biased Teaching with Infinite Concept Classes
Venue: arXiv cs.AI 2018
Year: 2018

We investigate the teaching of infinite concept classes through the effect of the learning bias (which is used by the learner to prefer some concepts over others and by the teacher to devise the teaching examples) and the sampling bias (which determines how the concepts are sampled from the class). We analyse two important classes: Turing machines and finite-state machines. We derive bounds for the biased teaching dimension when the learning bias is derived from a complexity measure (Kolmogorov complexity and minimal number of states respectively) and analyse the sampling distributions that lead to finite expected biased teaching dimensions. We highlight the existing trade-off between the bound and the representativeness of the sample, and its implications for the understanding of what teaching rich concepts to machines entails.
Human Activity Recognition using Recurrent Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

Human activity recognition using smart home sensors is one of the bases of ubiquitous computing in smart environments and a topic undergoing intense research in the field of ambient assisted living. The increasingly large amount of data sets calls for machine learning methods. In this paper, we introduce a deep learning model that learns to classify human activities without using any prior knowledge. For this purpose, a Long Short Term Memory (LSTM) Recurrent Neural Network was applied to three real world smart home datasets. The results of these experiments show that the proposed approach outperforms the existing ones in terms of accuracy and performance.
Large-scale Nonlinear Variable Selection via Kernel Random Features
Venue: arXiv cs.LG 2018
Year: 2018

We propose a new method for input variable selection in nonlinear regression. The method is embedded into a kernel regression machine that can model general nonlinear functions, not being a priori limited to additive models. This is the first kernel-based variable selection method applicable to large datasets. It sidesteps the typical poor scaling properties of kernel methods by mapping the inputs into a relatively low-dimensional space of random features. The algorithm discovers the variables relevant for the regression task together with learning the prediction model through learning the appropriate nonlinear random feature maps. We demonstrate the outstanding performance of our method on a set of large-scale synthetic and real datasets.
Vehicle Communication Strategies for Simulated Highway Driving
Venue: arXiv cs.MA 2018
Year: 2018

Interest in emergent communication has recently surged in Machine Learning. The focus of this interest has largely been either on investigating the properties of the learned protocol or on utilizing emergent communication to better solve problems that already have a viable solution. Here, we consider self-driving cars coordinating with each other and focus on how communication influences the agents' collective behavior. Our main result is that communication helps (most) with adverse conditions.
Industrial Symbiotic Networks as Coordinated Games
Venue: arXiv cs.MA 2018
Year: 2018

We present an approach for implementing a specific form of collaborative industrial practices-called Industrial Symbiotic Networks (ISNs)-as MC-Net cooperative games and address the so called ISN implementation problem. This is, the characteristics of ISNs may lead to inapplicability of fair and stable benefit allocation methods even if the collaboration is a collectively desired one. Inspired by realistic ISN scenarios and the literature on normative multi-agent systems, we consider regulations and normative socioeconomic policies as two elements that in combination with ISN games resolve the situation and result in the concept of coordinated ISNs.
Multiprecision Arithmetic for Cryptology in C++ - Compile-Time Computations and Beating the Performance of Hand-Optimized Assembly at Run-Time
Venue: arXiv cs.CR 2018
Year: 2018

We describe a new C++ library for multiprecision arithmetic for numbers in the order of 100--500 bits, i.e., representable with just a few limbs. The library is written in "optimizing-compiler-friendly" C++, with an emphasis on the use of fixed-size arrays and particular function-argument-passing styles (including the avoidance of naked pointers) to allow the limbs to be allocated on the stack or even in registers. Depending on the particular functionality, we get close to, or significantly beat the performance of existing libraries for multiprecision arithmetic that employ hand-optimized assembly code. Most functions in the library are constant-time, which is a necessity for secure implementations of cryptographic protocols. Beyond the favorable runtime performance, our library is, to the best of the author's knowledge, the first library that offers big-integer computations during compile-time. For example, when implementing finite-field arithmetic with a fixed modulus, this feature enables the automatic precomputation (at compile time) of the special modulus-dependent constants required for Barrett and Montgomery reduction. Another application is to parse (at compile-time) a base-10-encoded big-integer literal.
Nonlinear system modeling based on constrained Volterra series estimates
Venue: arXiv cs.SY 2018
Year: 2018

A simple nonlinear system modeling algorithm designed to work with limited \emph{a priori }knowledge and short data records, is examined. It creates an empirical Volterra series-based model of a system using an $l_{q}$-constrained least squares algorithm with $q\geq 1$. If the system $m\left( \cdot \right) $ is a continuous and bounded map with a finite memory no longer than some known $τ$, then (for a $D$ parameter model and for a number of measurements $N$) the difference between the resulting model of the system and the best possible theoretical one is guaranteed to be of order $\sqrt{N^{-1}\ln D}$, even for $D\geq N$. The performance of models obtained for $q=1,1.5$ and $2$ is tested on the Wiener-Hammerstein benchmark system. The results suggest that the models obtained for $q>1$ are better suited to characterize the nature of the system, while the sparse solutions obtained for $q=1$ yield smaller error values in terms of input-output behavior.
A Basic Model of KBS Software
Venue: arXiv cs.SE 2018
Year: 2018

The Euclid 6.2 project MOSES addressed quality issues in the development of military KBS. A contribution to this project was to develop a computational model of KBS that could be used to define and analyze aspects of KBS quality. Since a key characteristic of KBS is search, a computational model based on non-determinism was developed and used to express terms relating to quality. This research report describes the approach.
Static and Dynamic Path Planning Using Incremental Heuristic Search
Venue: arXiv cs.RO 2018
Year: 2018

Path planning is an important component in any highly automated vehicle system. In this report, the general problem of path planning is considered first in partially known static environments where only static obstacles are present but the layout of the environment is changing as the agent acquires new information. Attention is then given to the problem of path planning in dynamic environments where there are moving obstacles in addition to the static ones. Specifically, a 2D car-like agent traversing in a 2D environment was considered. It was found that the traditional configuration-time space approach is unsuitable for producing trajectories consistent with the dynamic constraints of a car. A novel scheme is then suggested where the state space is 4D consisting of position, speed and time but the search is done in the 3D space composed by position and speed. Simulation tests shows that the new scheme is capable of efficiently producing trajectories respecting the dynamic constraint of a car-like agent with a bound on their optimality.
Functional Generative Design: An Evolutionary Approach to 3D-Printing
Venue: arXiv cs.NE 2018
Year: 2018

Consumer-grade printers are widely available, but their ability to print complex objects is limited. Therefore, new designs need to be discovered that serve the same function, but are printable. A representative such problem is to produce a working, reliable mechanical spring. The proposed methodology for discovering solutions to this problem consists of three components: First, an effective search space is learned through a variational autoencoder (VAE); second, a surrogate model for functional designs is built; and third, a genetic algorithm is used to simultaneously update the hyperparameters of the surrogate and to optimize the designs using the updated surrogate. Using a car-launcher mechanism as a test domain, spring designs were 3D-printed and evaluated to update the surrogate model. Two experiments were then performed: First, the initial set of designs for the surrogate-based optimizer was selected randomly from the training set that was used for training the VAE model, which resulted in an exploitative search behavior. On the other hand, in the second experiment, the initial set was composed of more uniformly selected designs from the same training set and a more explorative search behavior was observed. Both of the experiments showed that the methodology generates interesting, successful, and reliable spring geometries robust to the noise inherent in the 3D printing process. The methodology can be generalized to other functional design problems, thus making consumer-grade 3D printing more versatile.
Individual Security and Network Design with Malicious Nodes
Venue: arXiv cs.GT 2018
Year: 2018

Networks are beneficial to those being connected but can also be used as carriers of contagious hostile attacks. These attacks are often facilitated by exploiting corrupt network users. To protect against the attacks, users can resort to costly defense. The decentralized nature of such protection is known to be inefficient but the inefficiencies can be mitigated by a careful network design. Is network design still effective when not all users can be trusted? We propose a model of network design and defense with byzantine nodes to address this question. We study the optimal defended networks in the case of centralized defense and, for the case of decentralized defense, we show that the inefficiencies due to decentralization can be fully mitigated, despite the presence of the byzantine nodes.
Nonparametric Stochastic Compositional Gradient Descent for Q-Learning in Continuous Markov Decision Problems
Venue: arXiv cs.LG 2018
Year: 2018

We consider Markov Decision Problems defined over continuous state and action spaces, where an autonomous agent seeks to learn a map from its states to actions so as to maximize its long-term discounted accumulation of rewards. We address this problem by considering Bellman's optimality equation defined over action-value functions, which we reformulate into a nested non-convex stochastic optimization problem defined over a Reproducing Kernel Hilbert Space (RKHS). We develop a functional generalization of stochastic quasi-gradient method to solve it, which, owing to the structure of the RKHS, admits a parameterization in terms of scalar weights and past state-action pairs which grows proportionately with the algorithm iteration index. To ameliorate this complexity explosion, we apply Kernel Orthogonal Matching Pursuit to the sequence of kernel weights and dictionaries, which yields a controllable error in the descent direction of the underlying optimization method. We prove that the resulting algorithm, called KQ-Learning, converges with probability 1 to a stationary point of this problem, yielding a fixed point of the Bellman optimality operator under the hypothesis that it belongs to the RKHS. Under constant learning rates, we further obtain convergence to a small Bellman error that depends on the chosen learning rates. Numerical evaluation on the Continuous Mountain Car and Inverted Pendulum tasks yields convergent parsimonious learned action-value functions, policies that are competitive with the state of the art, and exhibit reliable, reproducible learning behavior.
A Rank-Preserving Generalized Matrix Inverse for Consistency with Respect to Similarity
Venue: arXiv cs.NA 2018
Year: 2018

There has recently been renewed recognition of the need to understand the consistency properties that must be preserved when a generalized matrix inverse is required. The most widely known generalized inverse, the Moore-Penrose pseudoinverse, provides consistency with respect to orthonormal transformations (e.g., rotations of a coordinate frame), and a recently derived inverse provides consistency with respect to diagonal transformations (e.g., a change of units on state variables). Another well-known and theoretically important generalized inverse is the Drazin inverse, which preserves consistency with respect to similarity transformations. In this paper we note a limitation of the Drazin inverse is that it does not generally preserve the rank of the linear system of interest. We then introduce an alternative generalized inverse that both preserves rank and provides consistency with respect to similarity transformations. Lastly we provide an example and discuss experiments which suggest the need for algorithms with improved numerical stability.
Survey of Face Detection on Low-quality Images
Venue: arXiv cs.CV 2018
Year: 2018

Face detection is a well-explored problem. Many challenges on face detectors like extreme pose, illumination, low resolution and small scales are studied in the previous work. However, previous proposed models are mostly trained and tested on good-quality images which are not always the case for practical applications like surveillance systems. In this paper, we first review the current state-of-the-art face detectors and their performance on benchmark dataset FDDB, and compare the design protocols of the algorithms. Secondly, we investigate their performance degradation while testing on low-quality images with different levels of blur, noise, and contrast. Our results demonstrate that both hand-crafted and deep-learning based face detectors are not robust enough for low-quality images. It inspires researchers to produce more robust design for face detection in the wild.
VeriTable: Fast Equivalence Verification of Multiple Large Forwarding Tables
Venue: arXiv cs.NI 2018
Year: 2018

Due to network practices such as traffic engineering and multi-homing, the number of routes---also known as IP prefixes---in the global forwarding tables has been increasing significantly in the last decade and continues growing in a super linear trend. One of the most promising solutions is to use smart Forwarding Information Base (FIB) aggregation algorithms to aggregate the prefixes and convert a large table into a small one. Doing so poses a research question, however, i.e., how can we quickly verify that the original table yields the same forwarding behaviors as the aggregated one? We answer this question in this paper, including addressing the challenges caused by the longest prefix matching (LPM) lookups. In particular, we propose the VeriTable algorithm that can employ a single tree/trie traversal to quickly check if multiple forwarding tables are forwarding equivalent, as well as if they could result in routing loops or black holes. The VeriTable algorithm significantly outperforms the state-of-the-art work for both IPv4 and IPv6 tables in every aspect, including the total running time, memory access times and memory consumption.
Making Change in 2048
Venue: arXiv cs.DM 2018
Year: 2018

The 2048 game involves tiles labeled with powers of two that can be merged to form bigger powers of two; variants of the same puzzle involve similar merges of other tile values. We analyze the maximum score achievable in these games by proving a min-max theorem equating this maximum score (in an abstract generalized variation of 2048 that allows all the moves of the original game) with the minimum value that causes a greedy change-making algorithm to use a given number of coins. A widely-followed strategy in 2048 maintains tiles that represent the move number in binary notation, and a similar strategy in the Fibonacci number variant of the game (987) maintains the Zeckendorf representation of the move number as a sum of the fewest possible Fibonacci numbers; our analysis shows that the ability to follow these strategies is intimately connected with the fact that greedy change-making is optimal for binary and Fibonacci coinage. For variants of 2048 using tile values for which greedy change-making is suboptimal, it is the greedy strategy, not the optimal representation as sums of tile values, that controls the length of the game. In particular, the game will always terminate whenever the sequence of allowable tile values has arbitrarily large gaps between consecutive values.