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.

COMPRESSIVE QUANTIZATION FOR SCALABLE CLOUD RADIO ACCESS NETWORKS

With the proliferation of new mobile devices and applications, the demand for ubiquitous wireless services has increased dramatically in recent years. The explosive growth in the wireless traffic requires the wireless networks to be scalable so that they can be efficiently extended to meet the wireless communication demands. In a wireless network, the interference power typically grows with the number of devices without necessary coordination among them. On the other hand, large scale coordination is always difficult due to the low-bandwidth and high-latency interfaces between access points (APs) in traditional wireless networks. To address this challenge, cloud radio access network (C-RAN) has been proposed, where a pool of base band units (BBUs) are connected to the distributed remote radio heads (RRHs) via high bandwidth and low latency links (i.e., the front-haul) and are responsible for all the baseband processing. But the insufficient front-haul link capacity may limit the scale of C-RAN and prevent it from fully utilizing the benefits made possible by the centralized baseband processing. As a result, the front-haul link capacity becomes a bottleneck in the scalability of C-RAN. In this dissertation, we explore the scalable C-RAN in the effort of tackling this challenge. In the first aspect of this dissertation, we investigate the scalability issues in the existing wireless networks and propose a novel time-reversal (TR) based scalable wireless network in which the interference power is naturally mitigated by the focusing effects of TR communications without coordination among APs or terminal devices (TDs). Due to this nice feature, it is shown that the system can be easily extended to serve more TDs. Motivated by the nice properties of TR communications in providing scalable wireless networking solutions, in the second aspect of this dissertation, we apply the TR based communications to the C-RAN and discover the TR tunneling effects which alleviate the traffic load in the front-haul links caused by the increment of TDs. We further design waveforming schemes to optimize the downlink and uplink transmissions in the TR based C-RAN, which are shown to improve the downlink and uplink transmission accuracies. Consequently, the traffic load in the front-haul links is further alleviated by the reducing re-transmissions caused by transmission errors. Moreover, inspired by the TR-based C-RAN, we propose the compressive quantization scheme which applies to the uplink of multi-antenna C-RAN so that more antennas can be utilized with the limited front-haul capacity, which provide rich spatial diversity such that the massive TDs can be served more efficiently.

KNOWING THE ENEMY: NAZI FOREIGN INTELLIGENCE IN WAR, HOLOCAUST, AND POSTWAR

“Knowing the Enemy: Nazi Foreign Intelligence in War, Holocaust and Postwar,” reveals the importance of ideologically-driven foreign intelligence reporting in the wartime radicalization of the Nazi dictatorship, and the continued prominence of Nazi discourses in postwar reports from German intelligence officers working with the U.S. Army and West German Federal Intelligence Service after 1945. For this project, I conducted extensive archival research in Germany and the United States, particularly in overlooked and files pertaining to the wartime activities of the Reichssicherheitshauptamt, Abwehr, Fremde Heere Ost, Auswärtiges Amt, and German General Staff, and the recently declassified intelligence files pertaining to the postwar activities of the Gehlen Organization, Bundesnachrichtendienst, and Foreign Military Studies Program. Applying the technique of close textual analysis to the underutilized intelligence reports themselves, I discovered that wartime German intelligence officials in military, civil service, and Party institutions all lent the appearance of professional objectivity to the racist and conspiratorial foreign policy beliefs held in the highest echelons of the Nazi dictatorship. The German foreign intelligence services’ often erroneous reporting on Great Britain, the Soviet Union, the United States, and international Jewry simultaneously figured in the radicalization of the regime’s military and anti-Jewish policies and served to confirm the ideological preconceptions of Hitler and his most loyal followers. After 1945, many of these same figures found employment with the Cold War West, using their “expertise” in Soviet affairs to advise the West German Government, U.S. Military, and CIA on Russian military and political matters. I chart considerable continuities in personnel and ideas from the wartime intelligence organizations into postwar West German and American intelligence institutions, as later reporting on the Soviet Union continued to reproduce the flawed wartime tropes of innate Russian military and racial inferiority.