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.

Reconciling History and International Law: Territorial and Maritime Claims in the South China Sea and East China Sea

High-ranking Chinese military officials are often quoted in international media as stating that China cannot afford to lose even an inch of Chinese territory, as this territory has been passed down from Chinese ancestors. Such statements are not new in Chinese politics, but recently this narrative has made an important transition. While previously limited to disputes over land borders, such rhetoric is now routinely applied to disputes involving islands and maritime borders. China is increasingly oriented toward its maritime borders and seems unwilling to compromise on delimitation disputes, a transition mirrored by many states across the globe. In a similar vein, scholarship has found that territorial disputes are particularly intractable and volatile when compared with other types of disputes, and a large body of research has grappled with producing systematic knowledge of territorial conflict. Yet in this wide body of literature, an important question has remained largely unanswered - how do states determine which geographical areas will be included in their territorial and maritime claims? In other words, if nations are willing to fight and die for an inch of national territory, how do governments draw the boundaries of the nation? This dissertation uses in-depth case studies of some of the most prominent territorial and maritime disputes in East Asia to argue that domestic political processes play a dominant and previously under-explored role in both shaping claims and determining the nature of territorial and maritime disputes. China and Taiwan are particularly well suited for this type of investigation, as they are separate claimants in multiple disputes, yet they both draw upon the same historical record when establishing and justifying their claims. Leveraging fieldwork in Taiwan, China, and the US, this dissertation includes in-depth case studies of China’s and Taiwan’s respective claims in both the South China Sea and East China Sea disputes. Evidence from this dissertation indicates that officials in both China and Taiwan have struggled with how to reconcile history and international law when establishing their claims, and that this struggle has introduced ambiguity into China's and Taiwan's claims. Amid this process, domestic political dynamics have played a dominant role in shaping the options available and the potential for claims to change in the future. In Taiwan’s democratic system, where national identity is highly contested through party politics, opinions vary along a broad spectrum as to the proper borders of the nation, and there is considerable evidence that Taiwan’s claims may change in the near future. In contrast, within China’s single-party authoritarian political system, where nationalism is source of regime legitimacy, views on the proper interpretation of China’s boundaries do vary, but along a much more narrow range. In the dissertation’s final chapter, additional cases, such as South Korea’s position on Dokdo and Indonesia’s approach to the defense of Natuna are used as points of comparison to further clarify theoretical findings.

Leader Based Cyclic Pursuit

In this work a system of autonomous agents engaged in cyclic pursuit (under constant bearing (CB) strategy) is considered, for which one informed agent (the leader) also senses and responds to a stationary beacon. Building on the framework proposed in a previous work on beacon-referenced cyclic pursuit, necessary and suffi- cient conditions for the existence of circling equilibria in a system with one informed agent are derived, with discussion of stability and performance. In a physical testbed, the leader (robot) is equipped with a sound sensing apparatus composed of a real time embedded system, estimating direction of arrival of sound by an Interaural Level and Phase Difference Algorithm, using empirically determined phase and level signatures, and breaking front-back ambiguity with appropriate sensor placement. Furthermore a simple framework for implementing and evaluating the performance of control laws with the Robot Operating System (ROS) is proposed, demonstrated, and discussed.