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.

Designing Hydrogels that Transform their Shape in Response to Molecular Cues

There has been considerable interest in developing shape-changing soft materials for potential applications in drug delivery, microfluidics and biosensing. These shape- changing materials are inspired by the morphological changes exhibited by plants in nature, such as the Venus flytrap. One specific class of shape-change is that from a flat sheet to a folded structure (e.g., a tube). Such “self-folding” materials are usually composed of polymer hydrogels, and these typically fold in response to external stimuli such as pH and temperature. In order to develop these hydrogels for the previously described applications, it is necessary to expand the range of triggers. The focus of this dissertation is the advancement of shape-changing polymer hydrogels that are sensitive to uncommon cues such as specific biomolecules (enzymes), the substrates for such enzymes, or specific multivalent cations. First, we describe a hybrid gel that responds to the presence of low concentrations of a class of enzymes known as matrix metalloproteinases (MMPs). The hybrid gel was created by utilizing photolithographic techniques to combine two or more gels with distinct chemical composition into the same material. Certain portions of the hybrid gel are composed of a biopolymer derivative with crosslinkable groups. The hybrid gel is flat in water; however, in the presence of MMPs, the regions containing the biopolymer are degraded and the flat sheet folds to form a 3D structure. We demonstrate that hydrogels with different patterns can transform into different 3D structures such as tubes, helices and pancakes. Furthermore, this shape change can be made to occur at physiological concentrations of enzymes. Next, we report a gel with two layers that undergoes a shape change in the presence of glucose. The enzyme glucose oxidase (GOx) is immobilized in one of the layers. GOx catalyzes the conversion of glucose to gluconic acid. The production of gluconic acid decreases the local pH. The decrease in local pH causes one of the layers to swell. As a result, the flat sheet folds to form a tube. The tube unfolds to form a flat sheet when it is transferred to a solution with no glucose present. Therefore, this biomolecule- triggered shape transformation is reversible, meaning the glucose sensing gel is reusable. Furthermore, this shape change only occurs in the presence of glucose and it does not occur in the presence of other small sugars such as fructose. In our final study, we report the shape change of a gel with two layers in the presence of multivalent ions such as Ca2+ and Sr2+. The gel consists of a passive layer and an active layer. The passive layer is composed of dimethylyacrylamide (DMAA), which does not interact with multivalent ions. The active layer consists of DMAA and the biopolymer alginate. In the presence of Ca2+ ions, the alginate chains crosslink and the active layer shrinks. As a result, the gel converts from a flat sheet to a folded tube. What is particularly unusual is the direction of folding. In most cases, when flat rectangular gels fold, they do so about their short-side. However, our gels typically fold about their long-side. We hypothesize that non-homogeneous swelling determines the folding axis.