Hausdorff and Wasserstein metrics on graphs and other structured data, 2019. Evan Patterson.
Optimal transport is widely used in pure and applied mathematics to find probabilistic solutions to hard combinatorial matching problems. We extend the Wasserstein metric and other elements of optimal transport from the matching of sets to the matching of graphs and other structured data. This structure-preserving form of optimal transport relaxes the usual notion of homomorphism between structures. It applies to graphs, directed and undirected, labeled and unlabeled, and to any other structure that can be realized as a C-set for some finitely presented category C. We construct both Hausdorff-style and Wasserstein-style metrics on C-sets and we show that the latter are convex relaxations of the former. Like the classical Wasserstein metric, the Wasserstein metric on C-sets is the value of a linear program and is therefore efficiently computable.
I extend ideas from optimal transport to structured data by probabilistically relaxing the notion of a homomorphism. As an application, I construct Wasserstein-style metrics on graphs, simplicial sets, and other structures.
I talked about this project at the 2019 AMS Special Session on Applied Category Theory (slides).
String diagrams for assembly planning, 2019. Jade Master, Evan Patterson, Shahin Yousfi, Arquimedes Canedo.
Assembly planning is a difficult problem for companies. Many disciplines such as design, planning, scheduling, and manufacturing execution need to be carefully engineered and coordinated to create successful product assembly plans. Recent research in the field of design for assembly has proposed new methodologies to design product structures in such a way that their assembly is easier. However, present assembly planning approaches lack the engineering tool support to capture all the constraints associated to assembly planning in a unified manner. This paper proposes CompositionalPlanning, a string diagram based framework for assembly planning. In the proposed framework, string diagrams and their compositional properties serve as the foundation for an engineering tool where CAD designs interact with planning and scheduling algorithms to automatically create high-quality assembly plans. These assembly plans are then executed in simulation to measure their performance and to visualize their key build characteristics. We demonstrate the versatility of this approach in the LEGO assembly domain. We developed two reference LEGO CAD models that are processed by CompositionalPlanning's algorithmic pipeline. We compare sequential and parallel assembly plans in a Minecraft simulation and show that the time-to-build performance can be optimized by our algorithms.
We propose using monoidal categories and string diagrams as a foundation for assembly planning. Working in the simplified domain of LEGO assembly in Minecraft, we design and implement a proof-of-concept system that spans the whole assembly process, from the object’s CAD description to planning and scheduling to simulation.
Conformalized quantile regression, 2019. Yaniv Romano, Evan Patterson, Emmanuel J. Candès.
Conformal prediction is a technique for constructing prediction intervals that attain valid coverage in finite samples, without making distributional assumptions. Despite this appeal, existing conformal methods can be unnecessarily conservative because they form intervals of constant or weakly varying length across the input space. In this paper we propose a new method that is fully adaptive to heteroscedasticity. It combines conformal prediction with classical quantile regression, inheriting the advantages of both. We establish a theoretical guarantee of valid coverage, supplemented by extensive experiments on popular regression datasets. We compare the efficiency of conformalized quantile regression to other conformal methods, showing that our method tends to produce shorter intervals.
@inproceedings{romano2019,
title={Conformalized quantile regression},
author={Romano, Yaniv and Patterson, Evan and Cand{\`e}s, Emmanuel J.},
booktitle={Thirty-third Conference on Neural Information Processing Systems (NeurIPS-19)},
archivePrefix={arXiv},
eprint={1905.03222},
year={2019}
}
We propose a new method to construct prediction intervals, based on conformal inference. Our philosophy is that if interval estimation is your goal, you should bypass point estimation entirely and directly estimate the interval endpoints by quantile regression. You can then conformalize the intervals to attain valid, distribution-free coverage in finite samples.
Teaching machines to understand data science code by semantic enrichment of dataflow graphs, 2018. Evan Patterson, Ioana Baldini, Aleksandra Mojsilovic, Kush R. Varshney.
Your computer is continuously executing programs, but does it really understand them? Not in any meaningful sense. That burden falls upon human knowledge workers, who are increasingly asked to write and understand code. They deserve to have intelligent tools that reveal the connections between code and its subject matter. Towards this prospect, we develop an AI system that forms semantic representations of computer programs, using techniques from knowledge representation and program analysis. To create the representations, we introduce an algorithm for enriching dataflow graphs with semantic information. The semantic enrichment algorithm is undergirded by a new ontology language for modeling computer programs and a new ontology about data science, written in this language. Throughout the paper, we focus on code written by data scientists and we locate our work within a larger movement towards collaborative, open, and reproducible science.
@inproceedings{patterson2018,
title={Teaching machines to understand data science code by semantic enrichment of dataflow graphs},
author={Patterson, Evan and Baldini, Ioana and Mojsilovi{\'c}, Aleksandra and Varshney, Kush R},
booktitle={Proceedings of 2018 KDD Workshop on the Fragile Earth: Theory Guided Data Science to Enhance Scientific Discovery},
archivePrefix={arXiv},
eprint={1807.05691},
year={2018}
}
We refine our method for creating semantic representations of data science programs. We implement the method for both Python and R and we release the first version of the Data Science Ontology. The ontology is written in a new ontology language called Monocl. All source code is available on GitHub.
We demoed the system at IJCAI-ECAI 2018 and we presented a shorter paper at the 2018 KDD Fragile Earth Workshop. Later, we presented the project at PyData NYC 2019 (slides).
Knowledge representation in bicategories of relations, 2017. Evan Patterson.
We introduce the relational ontology log, or relational olog, a knowledge representation system based on the category of sets and relations. It is inspired by Spivak and Kent's olog, a recent categorical framework for knowledge representation. Relational ologs interpolate between ologs and description logic, the dominant formalism for knowledge representation today. In this paper, we investigate relational ologs both for their own sake and to gain insight into the relationship between the algebraic and logical approaches to knowledge representation. On a practical level, we show by example that relational ologs have a friendly and intuitive—yet fully precise—graphical syntax, derived from the string diagrams of monoidal categories. We explain several other useful features of relational ologs not possessed by most description logics, such as a type system and a rich, flexible notion of instance data. In a more theoretical vein, we draw on categorical logic to show how relational ologs can be translated to and from logical theories in a fragment of first-order logic. Although we make extensive use of categorical language, this paper is designed to be self-contained and has considerable expository content. The only prerequisites are knowledge of first-order logic and the rudiments of category theory.
@article{patterson2017,
title={Knowledge Representation in Bicategories of Relations},
author={Patterson, Evan},
archivePrefix={arXiv},
eprint={1706.00526},
journal={arXiv preprint},
year={2017}
}
I explain how to represent relational knowledge in a mathematical structure called a bicategory of relations. I compare this structure to the more familiar systems of first-order logic and description logic. Despite the heavy dose of monoidal category theory, the paper is supposed to be readable by non-category-theorists. Many pictures and informal explanations are provided.
I talked about this project at the 2017 CSLI Workshop (slides) and later at the 2017 AMS Special Session on Applied Category Theory (slides).
Dataflow representation of data analyses: Toward a platform for collaborative data science, 2017. Evan Patterson, Robert McBurney, Hollie Schmidt, Ioana Baldini, Aleksandra Mojsilovic, Kush R. Varshney.
Data science plays an increasingly important role in solving today's scientific and social challenges. To promote progress toward a cure for multiple sclerosis, the Accelerated Cure Project has created an open repository of biological and survey data on patients with multiple sclerosis. Similar large-scale repositories are being created in other domains. As the open, data-driven model of science proliferates, the research community faces a growing need for a cloud platform for collaborative data science. Such a platform should facilitate collaboration between domain experts and data scientists and possess artificial intelligence capabilities for organizing, recommending, and manipulating data analyses. In this paper, we present some foundational technologies motivated by this vision. Our system automatically extracts a high-level dataflow graph from a data analysis. This graph describes how data flows through an analysis pipeline, including which statistical methods are used and how they fit together. The system requires no special annotations from the data analyst and consumes analyses written in Python using standard tools, such as Scikit-learn and Statsmodels. In this paper, we explain how our system works and how it fits into our larger vision for a collaborative data science platform.
@article{patterson2017,
author={Patterson, Evan and McBurney, Robert and Schmidt, Hollie and Baldini, Ioana and Mojsilovi{\'c}, Aleksandra and Varshney, Kush R.},
journal={IBM Journal of Research and Development},
title={Dataflow representation of data analyses: Toward a platform for collaborative data science},
volume={61},
number={6},
pages={9:1-9:13},
doi={10.1147/JRD.2017.2736278},
year={2017}
}
My collaborators and I argue that:
A cloud platform for data science, powered by artificial intelligence, could accelerate scientific discovery by helping data scientists and domain scientists collaborate. Existing data science platforms do not meet this need.
To enable these AI capabilities, we must create useful, machine-interpretable representations of data analyses. We develop a first version of this technology (largely superseded by our later work).
We presented a shorter paper (slides) at the AAAI 2017 Spring Symposium on Artificial Intelligence for the Social Good.