Probabilistic Models for Scalable Knowledge Graph Construction

In the past decade, systems that extract information from millions of Internet documents have become commonplace. Knowledge graphs -- structured knowledge bases that describe entities, their attributes and the relationships between them -- are a powerful tool for understanding and organizing this vast amount of information. However, a significant obstacle to knowledge graph construction is the unreliability of the extracted information, due to noise and ambiguity in the underlying data or errors made by the extraction system and the complexity of reasoning about the dependencies between these noisy extractions. My dissertation addresses these challenges by exploiting the interdependencies between facts to improve the quality of the knowledge graph in a scalable framework. I introduce a new approach called knowledge graph identification (KGI), which resolves the entities, attributes and relationships in the knowledge graph by incorporating uncertain extractions from multiple sources, entity co-references, and ontological constraints. I define a probability distribution over possible knowledge graphs and infer the most probable knowledge graph using a combination of probabilistic and logical reasoning. Such probabilistic models are frequently dismissed due to scalability concerns, but my implementation of KGI maintains tractable performance on large problems through the use of hinge-loss Markov random fields, which have a convex inference objective. This allows the inference of large knowledge graphs using 4M facts and 20M ground constraints in 2 hours. To further scale the solution, I develop a distributed approach to the KGI problem which runs in parallel across multiple machines, reducing inference time by 90%. Finally, I extend my model to the streaming setting, where a knowledge graph is continuously updated by incorporating newly extracted facts. I devise a general approach for approximately updating inference in convex probabilistic models, and quantify the approximation error by defining and bounding inference regret for online models. Together, my work retains the attractive features of probabilistic models while providing the scalability necessary for large-scale knowledge graph construction. These models have been applied on a number of real-world knowledge graph projects, including the NELL project at Carnegie Mellon and the Google Knowledge Graph.

Motion Planning and Controls with Safety and Temporal Constraints

Motion planning, or trajectory planning, commonly refers to a process of converting high-level task specifications into low-level control commands that can be executed on the system of interest. For different applications, the system will be different. It can be an autonomous vehicle, an Unmanned Aerial Vehicle(UAV), a humanoid robot, or an industrial robotic arm. As human machine interaction is essential in many of these systems, safety is fundamental and crucial. Many of the applications also involve performing a task in an optimal manner within a given time constraint. Therefore, in this thesis, we focus on two aspects of the motion planning problem. One is the verification and synthesis of the safe controls for autonomous ground and air vehicles in collision avoidance scenarios. The other part focuses on the high-level planning for the autonomous vehicles with the timed temporal constraints. In the first aspect of our work, we first propose a verification method to prove the safety and robustness of a path planner and the path following controls based on reachable sets. We demonstrate the method on quadrotor and automobile applications. Secondly, we propose a reachable set based collision avoidance algorithm for UAVs. Instead of the traditional approaches of collision avoidance between trajectories, we propose a collision avoidance scheme based on reachable sets and tubes. We then formulate the problem as a convex optimization problem seeking control set design for the aircraft to avoid collision. We apply our approach to collision avoidance scenarios of quadrotors and fixed-wing aircraft. In the second aspect of our work, we address the high level planning problems with timed temporal logic constraints. Firstly, we present an optimization based method for path planning of a mobile robot subject to timed temporal constraints, in a dynamic environment. Temporal logic (TL) can address very complex task specifications such as safety, coverage, motion sequencing etc. We use metric temporal logic (MTL) to encode the task specifications with timing constraints. We then translate the MTL formulae into mixed integer linear constraints and solve the associated optimization problem using a mixed integer linear program solver. We have applied our approach on several case studies in complex dynamical environments subjected to timed temporal specifications. Secondly, we also present a timed automaton based method for planning under the given timed temporal logic specifications. We use metric interval temporal logic (MITL), a member of the MTL family, to represent the task specification, and provide a constructive way to generate a timed automaton and methods to look for accepting runs on the automaton to find an optimal motion (or path) sequence for the robot to complete the task.

Essays on Financial Constraints, R&D Investments, and Competition

This dissertation consists of two chapters of theoretical studies that investigate the effect of financial constraints and market competition on research and development (R&D) investments. In the first chapter, I explore the impact of financial constraints on two different types of R&D investments. In the second chapter, I examine the impact of market competition on the relationship between financial constraints and R&D investments. In the first chapter, I develop a dynamic monopoly model to study a firm’s R&D strategy. Contrary to intuition, I show that a financially constrained firm may invest more aggressively in R&D projects than an unconstrained firm. Financial constraints introduce a risk that a firm may run out of money before its project bears fruit, which leads to involuntary termination on an otherwise positive-NPV project. For a company that relies on cash flow from assets in place to keep its R&D project alive, early success can be relatively important. I find that when the discovery process can be expedited by heavier investment (“accelerable” projects), a financially constrained company may find it optimal to “over”-invest in order to raise the probability of project survival. The over-investment will not happen if the project is only “scalable” (investment scales up payoffs). The model generates several testable implications regarding over-investment and project values. In the second chapter, I study the effects of competition on R&D investments in a duopoly framework. Using a homogeneous duopoly model where two unconstrained firms compete head to head in an R&D race, I find that competition has no effect on R&D investment if the project is not accelerable, and the competing firms are not constrained. In a heterogeneous duopoly model where a financially constrained firm competes against an unconstrained firm, I discover interesting strategic interactions that lead to preemption by the constrained firm in equilibrium. The unconstrained competitor responds to its constrained rival’s investment in an inverted-U shape fashion. When the constrained competitor has high cash flow risk, it accelerates the innovation in equilibrium, while the unconstrained firm invests less aggressively and waits for its rival to quit the race due to shortage of funds.