OpenRaiser/Intern-Atlas huggingface dataset:
Knowledge Authoring and Question Answering with KALM
Venue: arXiv cs.AI 2019
Year: 2019

Knowledge representation and reasoning (KRR) is one of the key areas in artificial intelligence (AI) field. It is intended to represent the world knowledge in formal languages (e.g., Prolog, SPARQL) and then enhance the expert systems to perform querying and inference tasks. Currently, constructing large scale knowledge bases (KBs) with high quality is prohibited by the fact that the construction process requires many qualified knowledge engineers who not only understand the domain-specific knowledge but also have sufficient skills in knowledge representation. Unfortunately, qualified knowledge engineers are in short supply. Therefore, it would be very useful to build a tool that allows the user to construct and query the KB simply via text. Although there is a number of systems developed for knowledge extraction and question answering, they mainly fail in that these system don't achieve high enough accuracy whereas KRR is highly sensitive to erroneous data. In this thesis proposal, I will present Knowledge Authoring Logic Machine (KALM), a rule-based system which allows the user to author knowledge and query the KB in text. The experimental results show that KALM achieved superior accuracy in knowledge authoring and question answering as compared to the state-of-the-art systems.
The Declining Price Anomaly is not Universal in Multi-Buyer Sequential Auctions (but almost is)
Venue: arXiv cs.GT 2019
Year: 2019

The declining price anomaly states that the price weakly decreases when multiple copies of an item are sold sequentially over time. The anomaly has been observed in a plethora of practical applications. On the theoretical side, Gale and Stegeman proved that the anomaly is guaranteed to hold in full information sequential auctions with exactly two buyers. We prove that the declining price anomaly is not guaranteed in full information sequential auctions with three or more buyers. This result applies to both first-price and second-price sequential auctions. Moreover, it applies regardless of the tie-breaking rule used to generate equilibria in these sequential auctions. To prove this result we provide a refined treatment of subgame perfect equilibria that survive the iterative deletion of weakly dominated strategies and use this framework to experimentally generate a very large number of random sequential auction instances. In particular, our experiments produce an instance with three bidders and eight items that, for a specific tie-breaking rule, induces a non-monotonic price trajectory. Theoretic analyses are then applied to show that this instance can be used to prove that for every possible tie-breaking rule there is a sequential auction on which it induces a non-monotonic price trajectory. On the other hand, our experiments show that non-monotonic price trajectories are extremely rare. In over six million experiments only a 0.000183 proportion of the instances violated the declining price anomaly.
3GPP-inspired Stochastic Geometry-based Mobility Model for a Drone Cellular Network
Venue: arXiv cs.IT 2019
Year: 2019

This paper deals with the stochastic geometry-based characterization of the time-varying performance of a drone cellular network in which the initial locations of drone base stations (DBSs) are modeled as a Poisson point process (PPP) and each DBS is assumed to move on a straight line in a random direction. This drone placement and trajectory model closely emulates the one used by the third generation partnership project (3GPP) for drone-related studies. Assuming the nearest neighbor association policy for a typical user equipment (UE) on the ground, we consider two models for the mobility of the serving DBS: (i) UE independent model, and (ii) UE dependent model. Using displacement theorem from stochastic geometry, we characterize the time-varying interference field as seen by the typical UE, using which we derive the time-varying coverage probability and data rate at the typical UE. We also compare our model with more sophisticated mobility models where the DBSs may move in nonlinear trajectories and demonstrate that the coverage probability and rate estimated by our model act as lower bounds to these more general models. To the best of our knowledge, this is the first work to perform a rigorous analysis of the 3GPP-inspired drone mobility model and establish connection between this model and the more general non-linear mobility models.
Benchmark Instances and Branch-and-Cut Algorithm for the Hashiwokakero Puzzle
Venue: arXiv cs.DM 2019
Year: 2019

Hashiwokakero, or simply Hashi, is a Japanese single-player puzzle played on a rectangular grid with no standard size. Some cells of the grid contain a circle, called island, with a number inside it ranging from one to eight. The remaining positions of the grid are empty. The player must connect all of the islands by drawing a series of horizontal or vertical bridges between them, respecting a series of rules: the number of bridges incident to an island equals the number indicated in the circle, at most two bridges are incident to any side of an island, bridges cannot cross each other or pass through islands, and each island must eventually be reachable from any other island. In this paper, we present some complexity results and relationships between Hashi and well-known graph theory problems. We give a formulation of the problem by means of an integer linear mathematical programming model, and apply a branch-and-cut algorithm to solve the model in which connectivity constraints are dynamically generated. We also develop a puzzle generator. Our experiments on 1440 Hashi puzzles show that the algorithm can consistently solve hard puzzles with up to 400 islands.
Context awareness and embedding for biomedical event extraction
Venue: arXiv cs.CL 2019
Year: 2019

Motivation: Biomedical event detection is fundamental for information extraction in molecular biology and biomedical research. The detected events form the central basis for comprehensive biomedical knowledge fusion, facilitating the digestion of massive information influx from literature. Limited by the feature context, the existing event detection models are mostly applicable for a single task. A general and scalable computational model is desiderated for biomedical knowledge management. Results: We consider and propose a bottom-up detection framework to identify the events from recognized arguments. To capture the relations between the arguments, we trained a bi-directional Long Short-Term Memory (LSTM) network to model their context embedding. Leveraging the compositional attributes, we further derived the candidate samples for training event classifiers. We built our models on the datasets from BioNLP Shared Task for evaluations. Our method achieved the average F-scores of 0.81 and 0.92 on BioNLPST-BGI and BioNLPST-BB datasets respectively. Comparing with 7 state-of-the-art methods, our method nearly doubled the existing F-score performance (0.92 vs 0.56) on the BioNLPST-BB dataset. Case studies were conducted to reveal the underlying reasons. Availability: https://github.com/cskyan/evntextrc
Enterprise Cyber Resiliency Against Lateral Movement: A Graph Theoretic Approach
Venue: arXiv cs.CR 2019
Year: 2019

Lateral movement attacks are a serious threat to enterprise security. In these attacks, an attacker compromises a trusted user account to get a foothold into the enterprise network and uses it to attack other trusted users, increasingly gaining higher and higher privileges. Such lateral attacks are very hard to model because of the unwitting role that users play in the attack and even harder to detect and prevent because of their low and slow nature. In this paper, a theoretical framework is presented for modeling lateral movement attacks and for proposing a methodology for designing resilient cyber systems against such attacks. The enterprise is modeled as a tripartite graph capturing the interaction between users, machines, and applications, and a set of procedures is proposed to harden the network by increasing the cost of lateral movement. Strong theoretical guarantees on system resilience are established and experimentally validated for large enterprise networks.
Stability and Generalization of Graph Convolutional Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Inspired by convolutional neural networks on 1D and 2D data, graph convolutional neural networks (GCNNs) have been developed for various learning tasks on graph data, and have shown superior performance on real-world datasets. Despite their success, there is a dearth of theoretical explorations of GCNN models such as their generalization properties. In this paper, we take a first step towards developing a deeper theoretical understanding of GCNN models by analyzing the stability of single-layer GCNN models and deriving their generalization guarantees in a semi-supervised graph learning setting. In particular, we show that the algorithmic stability of a GCNN model depends upon the largest absolute eigenvalue of its graph convolution filter. Moreover, to ensure the uniform stability needed to provide strong generalization guarantees, the largest absolute eigenvalue must be independent of the graph size. Our results shed new insights on the design of new & improved graph convolution filters with guaranteed algorithmic stability. We evaluate the generalization gap and stability on various real-world graph datasets and show that the empirical results indeed support our theoretical findings. To the best of our knowledge, we are the first to study stability bounds on graph learning in a semi-supervised setting and derive generalization bounds for GCNN models.
HADES-IoT: A Practical Host-Based Anomaly Detection System for IoT Devices (Extended Version)
Venue: arXiv cs.CR 2019
Year: 2019

Internet of Things (IoT) devices have become ubiquitous and are spread across many application domains including the industry, transportation, healthcare, and households. However, the proliferation of the IoT devices has raised the concerns about their security, especially when observing that many manufacturers focus only on the core functionality of their products due to short time to market and low-cost pressures, while neglecting security aspects. Moreover, it does not exist any established or standardized method for measuring and ensuring the security of IoT devices. Consequently, vulnerabilities are left untreated, allowing attackers to exploit IoT devices for various purposes, such as compromising privacy, recruiting devices into a botnet, or misusing devices to perform cryptocurrency mining. In this paper, we present a practical Host-based Anomaly DEtection System for IoT (HADES-IoT) that represents the last line of defense. HADES-IoT has proactive detection capabilities, provides tamper-proof resistance, and it can be deployed on a wide range of Linux-based IoT devices. The main advantage of HADES-IoT is its low performance overhead, which makes it suitable for the IoT domain, where state-of-the-art approaches cannot be applied due to their high-performance demands. We deployed HADES-IoT on seven IoT devices to evaluate its effectiveness and performance overhead. Our experiments show that HADES-IoT achieved 100% effectiveness in the detection of current IoT malware such as VPNFilter and IoTReaper; while on average, requiring only 5.5% of available memory and causing only a low CPU load.
Planning as Optimization: Dynamically Discovering Optimal Configurations for Runtime Situations
Venue: arXiv cs.SE 2019
Year: 2019

The large number of possible configurations of modern software-based systems, combined with the large number of possible environmental situations of such systems, prohibits enumerating all adaptation options at design time and necessitates planning at run time to dynamically identify an appropriate configuration for a situation. While numerous planning techniques exist, they typically assume a detailed state-based model of the system and that the situations that warrant adaptations are known. Both of these assumptions can be violated in complex, real-world systems. As a result, adaptation planning must rely on simple models that capture what can be changed (input parameters) and observed in the system and environment (output and context parameters). We therefore propose planning as optimization: the use of optimization strategies to discover optimal system configurations at runtime for each distinct situation that is also dynamically identified at runtime. We apply our approach to CrowdNav, an open-source traffic routing system with the characteristics of a real-world system. We identify situations via clustering and conduct an empirical study that compares Bayesian optimization and two types of evolutionary optimization (NSGA-II and novelty search) in CrowdNav.
Performance Evaluation of LTE-CommSense System for Discrimination of Presence of Multiple Objects in Outdoor Environment
Venue: arXiv cs.NI 2019
Year: 2019

LTE-CommSense is a novel instrumentation scheme which analyzes channel affected reference signals of LTE downlink signal to obtain knowledge about the environmental change. This work presents the characterization of LTE-CommSense instrument to detect presence or absence of objects in outdoor environment. Additionally, we analyze its capability of detecting and distinguishing when multiple objects are present. For performance evaluation and characterization of this instrument, we derive object detection accuracy, FAR, FRR and resolution which we believe are the most important figures of merit in this case. As the operation of LTE-CommSense is to detect events instead of objects, we redefine the concept of resolution for LTE-CommSense. Two different proposals to represent the redefined resolution viz. Neyman Pearson principle based and Cramer Rao principle based resolution are presented here. All the performance metrics are derived using practical data captured using an SDR platform modeled as a LTE-CommSense receiver. We observe that, LTE-CommSense provides better performance in detecting presence or absence of objects at near range.
An Efficient Approach to Achieve Compositionality using Optimized Multi-Version Object Based Transactional Systems
Venue: arXiv cs.DC 2019
Year: 2019

In the modern era of multi-core systems, the main aim is to utilize the cores properly. This utilization can be done by concurrent programming. But developing a flawless and well-organized concurrent program is difficult. Software Transactional Memory Systems (STMs) are a convenient programming interface which assist the programmer to access the shared memory concurrently without worrying about consistency issues such as priority-inversion, deadlock, livelock, etc. Another important feature that STMs facilitate is compositionality of concurrent programs with great ease. It composes different concurrent operations in a single atomic unit by encapsulating them in a transaction. Many STMs available in the literature execute read/write primitive operations on memory buffers. We represent them as Read-Write STMs or RWSTMs. Whereas, there exist some STMs (transactional boosting and its variants) which work on higher level operations such as insert, delete, lookup, etc. on a hash-table. We refer these STMs as Object Based STMs or OSTMs. The literature of databases and RWSTMs say that maintaining multiple versions ensures greater concurrency. This motivates us to maintain multiple version at higher level with object semantics and achieves greater concurrency. So, this paper pro-poses the notion of Optimized Multi-version Object Based STMs or OPT-MVOSTMs which encapsulates the idea of multiple versions in OSTMs to harness the greater concurrency efficiently.
Collective Dynamics and Control for Multiple Unmanned Surface Vessels
Venue: arXiv cs.SY 2019
Year: 2019

A multi-unmanned surface vessel (USV) formation control system is established on a novel platform composed of three 1.2 meter-long hydraulic jet propulsion surface vessels, a differential GPS reference station, and inter-vessel Zigbee communication modules. The system is also equipped with an upper level collective multi-USV protocol and a lower level vessel dynamics controller. The system is capable of chasing and surrounding a target vessel. The results are supported by rigorous theoretical analysis in terms of asymptotical surrounding behavior and trajectory regulation. Extensive experiments are conducted to demonstrate the effectiveness and efficiency of the proposed hardware and software architectures.
A Lyapunov-Based Approach to Exploit Asymmetries in Robotic Dual-Arm Task Resolution
Venue: arXiv cs.SY 2019
Year: 2019

Dual-arm manipulation tasks can be prescribed to a robotic system in terms of desired absolute and relative motion of the robot's end-effectors. These can represent, e.g., jointly carrying a rigid object or performing an assembly task. When both types of motion are to be executed concurrently, the symmetric distribution of the relative motion between arms prevents task conflicts. Conversely, an asymmetric solution to the relative motion task will result in conflicts with the absolute task. In this work, we address the problem of designing a control law for the absolute motion task together with updating the distribution of the relative task among arms. Through a set of numerical results, we contrast our approach with the classical symmetric distribution of the relative motion task to illustrate the advantages of our method.
A Personalized Subreddit Recommendation Engine
Venue: arXiv cs.IR 2019
Year: 2019

This paper aims to improve upon the generic recommendations that Reddit provides for its users. We propose a novel personalized recommender system that learns from both, the presence and the content of user-subreddit interaction, using implicit and explicit signals to provide robust recommendations.
Big Data Model "Entity and Features"
Venue: arXiv cs.DB 2019
Year: 2019

The article deals with the problem which led to Big Data. Big Data information technology is the set of methods and means of processing different types of structured and unstructured dynamic large amounts of data for their analysis and use of decision support. Features of NoSQL databases and categories are described. The developed Big Data Model "Entity and Features" allows determining the distance between the sources of data on the availability of information about a particular entity. The information structure of Big Data has been devised. It became a basis for further research and for concentrating on a problem of development of diverse data without their preliminary integration.
Skynet: A Top Deep RL Agent in the Inaugural Pommerman Team Competition
Venue: arXiv cs.MA 2019
Year: 2019

The Pommerman Team Environment is a recently proposed benchmark which involves a multi-agent domain with challenges such as partial observability, decentralized execution (without communication), and very sparse and delayed rewards. The inaugural Pommerman Team Competition held at NeurIPS 2018 hosted 25 participants who submitted a team of 2 agents. Our submission nn_team_skynet955_skynet955 won 2nd place of the "learning agents'' category. Our team is composed of 2 neural networks trained with state of the art deep reinforcement learning algorithms and makes use of concepts like reward shaping, curriculum learning, and an automatic reasoning module for action pruning. Here, we describe these elements and additionally we present a collection of open-sourced agents that can be used for training and testing in the Pommerman environment. Code available at: https://github.com/BorealisAI/pommerman-baseline
Exploring Differential Obliviousness
Venue: arXiv cs.CR 2019
Year: 2019

In a recent paper Chan et al. [SODA '19] proposed a relaxation of the notion of (full) memory obliviousness, which was introduced by Goldreich and Ostrovsky [J. ACM '96] and extensively researched by cryptographers. The new notion, differential obliviousness, requires that any two neighboring inputs exhibit similar memory access patterns, where the similarity requirement is that of differential privacy. Chan et al. demonstrated that differential obliviousness allows achieving improved efficiency for several algorithmic tasks, including sorting, merging of sorted lists, and range query data structures. In this work, we continue the exploration and mapping of differential obliviousness, focusing on algorithms that do not necessarily examine all their input. This choice is motivated by the fact that the existence of logarithmic overhead ORAM protocols implies that differential obliviousness can yield at most a logarithmic improvement in efficiency for computations that need to examine all their input. In particular, we explore property testing, where we show that differential obliviousness yields an almost linear improvement in overhead in the dense graph model, and at most quadratic improvement in the bounded degree model. We also explore tasks where a non-oblivious algorithm would need to explore different portions of the input, where the latter would depend on the input itself, and where we show that such a behavior can be maintained under differential obliviousness, but not under full obliviousness. Our examples suggest that there would be benefits in further exploring which class of computational tasks are amenable to differential obliviousness.
Steadiface: Real-Time Face-Centric Stabilization on Mobile Phones
Venue: arXiv cs.CV 2019
Year: 2019

We present Steadiface, a new real-time face-centric video stabilization method that simultaneously removes hand shake and keeps subject's head stable. We use a CNN to estimate the face landmarks and use them to optimize a stabilized head center. We then formulate an optimization problem to find a virtual camera pose that locates the face to the stabilized head center while retains smooth rotation and translation transitions across frames. We test the proposed method on fieldtest videos and show it stabilizes both the head motion and background. It is robust to large head pose, occlusion, facial appearance variations, and different kinds of camera motions. We show our method advances the state of art in selfie video stabilization by comparing against alternative methods. The whole process runs very efficiently on a modern mobile phone (8.1 ms/frame).