Showing 1–50 of 70 results for author: Schulz, A

Latent Diffusion for Neural Spiking Data

Authors: Jaivardhan Kapoor, Auguste Schulz, Julius Vetter, Felix Pei, Richard Gao, Jakob H. Macke

Abstract: Modern datasets in neuroscience enable unprecedented inquiries into the relationship between complex behaviors and the activity of many simultaneously recorded neurons. While latent variable models can successfully extract low-dimensional embeddings from such recordings, using them to generate realistic spiking data, especially in a behavior-dependent manner, still poses a challenge. Here, we pres… ▽ More Modern datasets in neuroscience enable unprecedented inquiries into the relationship between complex behaviors and the activity of many simultaneously recorded neurons. While latent variable models can successfully extract low-dimensional embeddings from such recordings, using them to generate realistic spiking data, especially in a behavior-dependent manner, still poses a challenge. Here, we present Latent Diffusion for Neural Spiking data (LDNS), a diffusion-based generative model with a low-dimensional latent space: LDNS employs an autoencoder with structured state-space (S4) layers to project discrete high-dimensional spiking data into continuous time-aligned latents. On these inferred latents, we train expressive (conditional) diffusion models, enabling us to sample neural activity with realistic single-neuron and population spiking statistics. We validate LDNS on synthetic data, accurately recovering latent structure, firing rates, and spiking statistics. Next, we demonstrate its flexibility by generating variable-length data that mimics human cortical activity during attempted speech. We show how to equip LDNS with an expressive observation model that accounts for single-neuron dynamics not mediated by the latent state, further increasing the realism of generated samples. Finally, conditional LDNS trained on motor cortical activity during diverse reaching behaviors can generate realistic spiking data given reach direction or unseen reach trajectories. In summary, LDNS simultaneously enables inference of low-dimensional latents and realistic conditional generation of neural spiking datasets, opening up further possibilities for simulating experimentally testable hypotheses. △ Less

Submitted 27 June, 2024; originally announced July 2024.

Expanding Conservation Science through Emerging Interdisciplinary STEM Fields

Authors: Andrew K. Schulz, Adam S. Gouge, Christine L. Madliger

Abstract: Conservation science is an interdisciplinary field that primarily draws on knowledge from the natural sciences, social sciences, and humanities to inform policy, planning, and practice. Since its formalization as a discipline, conservation science has also increasingly incorporated tools from integrative biological fields, such as animal behavior, genetics, and, more recently, physiology. Given th… ▽ More Conservation science is an interdisciplinary field that primarily draws on knowledge from the natural sciences, social sciences, and humanities to inform policy, planning, and practice. Since its formalization as a discipline, conservation science has also increasingly incorporated tools from integrative biological fields, such as animal behavior, genetics, and, more recently, physiology. Given that the biodiversity crisis constitutes one of the greatest challenges of the 21st century, with tremendous consequences for global sustainability and human health, creating a diverse conservation toolbox is important for addressing complex conservation threats. To assess the integration of three emerging integrative biological disciplines (physiology, biomechanics, and technology) into recent conservation science research, we queried publications from five broad-scope conservation-focused journals from 2010-2022. We found that the proportion of published articles incorporating these integrative biological techniques was low, ranging from 0-4% per year. With only 2.1% of total articles accessing tools or techniques from conservation physiology, conservation technology, and conservation biomechanics, we propose that there is still a substantial opportunity for further integration. We provide a case study for each integrative field to illustrate the capacity for its tools to contribute to positive conservation outcomes. We further outline how each field promotes novel or reimagined opportunities for collaborations. Finally, we discuss the interconnectedness of the three fields and how they can support the continuing expansion of conservation science as an evidence-based, action-oriented discipline through the application of a Challenge-Mechanism-Partnership framework. △ Less

Submitted 10 February, 2024; originally announced April 2024.

Intelligent Learning Rate Distribution to reduce Catastrophic Forgetting in Transformers

Authors: Philip Kenneweg, Alexander Schulz, Sarah Schröder, Barbara Hammer

Abstract: Pretraining language models on large text corpora is a common practice in natural language processing. Fine-tuning of these models is then performed to achieve the best results on a variety of tasks. In this paper, we investigate the problem of catastrophic forgetting in transformer neural networks and question the common practice of fine-tuning with a flat learning rate for the entire network in… ▽ More Pretraining language models on large text corpora is a common practice in natural language processing. Fine-tuning of these models is then performed to achieve the best results on a variety of tasks. In this paper, we investigate the problem of catastrophic forgetting in transformer neural networks and question the common practice of fine-tuning with a flat learning rate for the entire network in this context. We perform a hyperparameter optimization process to find learning rate distributions that are better than a flat learning rate. We combine the learning rate distributions thus found and show that they generalize to better performance with respect to the problem of catastrophic forgetting. We validate these learning rate distributions with a variety of NLP benchmarks from the GLUE dataset. △ Less

Submitted 27 March, 2024; originally announced April 2024.

Targeted Visualization of the Backbone of Encoder LLMs

Authors: Isaac Roberts, Alexander Schulz, Luca Hermes, Barbara Hammer

Abstract: Attention based Large Language Models (LLMs) are the state-of-the-art in natural language processing (NLP). The two most common architectures are encoders such as BERT, and decoders like the GPT models. Despite the success of encoder models, on which we focus in this work, they also bear several risks, including issues with bias or their susceptibility for adversarial attacks, signifying the neces… ▽ More Attention based Large Language Models (LLMs) are the state-of-the-art in natural language processing (NLP). The two most common architectures are encoders such as BERT, and decoders like the GPT models. Despite the success of encoder models, on which we focus in this work, they also bear several risks, including issues with bias or their susceptibility for adversarial attacks, signifying the necessity for explainable AI to detect such issues. While there does exist various local explainability methods focusing on the prediction of single inputs, global methods based on dimensionality reduction for classification inspection, which have emerged in other domains and that go further than just using t-SNE in the embedding space, are not widely spread in NLP. To reduce this gap, we investigate the application of DeepView, a method for visualizing a part of the decision function together with a data set in two dimensions, to the NLP domain. While in previous work, DeepView has been used to inspect deep image classification models, we demonstrate how to apply it to BERT-based NLP classifiers and investigate its usability in this domain, including settings with adversarially perturbed input samples and pre-trained, fine-tuned, and multi-task models. △ Less

Submitted 26 March, 2024; originally announced March 2024.

Debiasing Sentence Embedders through Contrastive Word Pairs

Authors: Philip Kenneweg, Sarah Schröder, Alexander Schulz, Barbara Hammer

Abstract: Over the last years, various sentence embedders have been an integral part in the success of current machine learning approaches to Natural Language Processing (NLP). Unfortunately, multiple sources have shown that the bias, inherent in the datasets upon which these embedding methods are trained, is learned by them. A variety of different approaches to remove biases in embeddings exists in the lit… ▽ More Over the last years, various sentence embedders have been an integral part in the success of current machine learning approaches to Natural Language Processing (NLP). Unfortunately, multiple sources have shown that the bias, inherent in the datasets upon which these embedding methods are trained, is learned by them. A variety of different approaches to remove biases in embeddings exists in the literature. Most of these approaches are applicable to word embeddings and in fewer cases to sentence embeddings. It is problematic that most debiasing approaches are directly transferred from word embeddings, therefore these approaches fail to take into account the nonlinear nature of sentence embedders and the embeddings they produce. It has been shown in literature that bias information is still present if sentence embeddings are debiased using such methods. In this contribution, we explore an approach to remove linear and nonlinear bias information for NLP solutions, without impacting downstream performance. We compare our approach to common debiasing methods on classical bias metrics and on bias metrics which take nonlinear information into account. △ Less

Submitted 27 March, 2024; originally announced March 2024.

A Practical Guide to Statistical Distances for Evaluating Generative Models in Science

Authors: Sebastian Bischoff, Alana Darcher, Michael Deistler, Richard Gao, Franziska Gerken, Manuel Gloeckler, Lisa Haxel, Jaivardhan Kapoor, Janne K Lappalainen, Jakob H Macke, Guy Moss, Matthijs Pals, Felix Pei, Rachel Rapp, A Erdem Sağtekin, Cornelius Schröder, Auguste Schulz, Zinovia Stefanidi, Shoji Toyota, Linda Ulmer, Julius Vetter

Abstract: Generative models are invaluable in many fields of science because of their ability to capture high-dimensional and complicated distributions, such as photo-realistic images, protein structures, and connectomes. How do we evaluate the samples these models generate? This work aims to provide an accessible entry point to understanding popular notions of statistical distances, requiring only foundati… ▽ More Generative models are invaluable in many fields of science because of their ability to capture high-dimensional and complicated distributions, such as photo-realistic images, protein structures, and connectomes. How do we evaluate the samples these models generate? This work aims to provide an accessible entry point to understanding popular notions of statistical distances, requiring only foundational knowledge in mathematics and statistics. We focus on four commonly used notions of statistical distances representing different methodologies: Using low-dimensional projections (Sliced-Wasserstein; SW), obtaining a distance using classifiers (Classifier Two-Sample Tests; C2ST), using embeddings through kernels (Maximum Mean Discrepancy; MMD), or neural networks (Fréchet Inception Distance; FID). We highlight the intuition behind each distance and explain their merits, scalability, complexity, and pitfalls. To demonstrate how these distances are used in practice, we evaluate generative models from different scientific domains, namely a model of decision making and a model generating medical images. We showcase that distinct distances can give different results on similar data. Through this guide, we aim to help researchers to use, interpret, and evaluate statistical distances for generative models in science. △ Less

Submitted 19 March, 2024; originally announced March 2024.

Zero-shot Sequential Neuro-symbolic Reasoning for Automatically Generating Architecture Schematic Designs

Authors: Milin Kodnongbua, Lawrence H. Curtis, Adriana Schulz

Abstract: This paper introduces a novel automated system for generating architecture schematic designs aimed at streamlining complex decision-making at the multifamily real estate development project's outset. Leveraging the combined strengths of generative AI (neuro reasoning) and mathematical program solvers (symbolic reasoning), the method addresses both the reliance on expert insights and technical chal… ▽ More This paper introduces a novel automated system for generating architecture schematic designs aimed at streamlining complex decision-making at the multifamily real estate development project's outset. Leveraging the combined strengths of generative AI (neuro reasoning) and mathematical program solvers (symbolic reasoning), the method addresses both the reliance on expert insights and technical challenges in architectural schematic design. To address the large-scale and interconnected nature of design decisions needed for designing a whole building, we proposed a novel sequential neuro-symbolic reasoning approach, emulating traditional architecture design processes from initial concept to detailed layout. To remove the need to hand-craft a cost function to approximate the desired objectives, we propose a solution that uses neuro reasoning to generate constraints and cost functions that the symbolic solvers can use to solve. We also incorporate feedback loops for each design stage to ensure a tight integration between neuro and symbolic reasoning. Developed using GPT-4 without further training, our method's effectiveness is validated through comparative studies with real-world buildings. Our method can generate various building designs in accordance with the understanding of the neighborhood, showcasing its potential to transform the realm of architectural schematic design. △ Less

Submitted 25 January, 2024; originally announced February 2024.

Semantic Properties of cosine based bias scores for word embeddings

Authors: Sarah Schröder, Alexander Schulz, Fabian Hinder, Barbara Hammer

Abstract: Plenty of works have brought social biases in language models to attention and proposed methods to detect such biases. As a result, the literature contains a great deal of different bias tests and scores, each introduced with the premise to uncover yet more biases that other scores fail to detect. What severely lacks in the literature, however, are comparative studies that analyse such bias scores… ▽ More Plenty of works have brought social biases in language models to attention and proposed methods to detect such biases. As a result, the literature contains a great deal of different bias tests and scores, each introduced with the premise to uncover yet more biases that other scores fail to detect. What severely lacks in the literature, however, are comparative studies that analyse such bias scores and help researchers to understand the benefits or limitations of the existing methods. In this work, we aim to close this gap for cosine based bias scores. By building on a geometric definition of bias, we propose requirements for bias scores to be considered meaningful for quantifying biases. Furthermore, we formally analyze cosine based scores from the literature with regard to these requirements. We underline these findings with experiments to show that the bias scores' limitations have an impact in the application case. △ Less

Submitted 27 January, 2024; originally announced January 2024.

Comments: 11 pages, 4 figures

FabHacks: Transform Everyday Objects into Functional Fixtures

Authors: Yuxuan Mei, Benjamin Jones, Dan Cascaval, Jennifer Mankoff, Etienne Vouga, Adriana Schulz

Abstract: Storage, organizing, and decorating are an important part of home design. While one can buy commercial items for many of these tasks, this can be costly, and re-use is more sustainable. An alternative is a "home hack", a functional assembly that can be constructed from existing household items. However, coming up with such hacks requires combining objects to make a physically valid design, which m… ▽ More Storage, organizing, and decorating are an important part of home design. While one can buy commercial items for many of these tasks, this can be costly, and re-use is more sustainable. An alternative is a "home hack", a functional assembly that can be constructed from existing household items. However, coming up with such hacks requires combining objects to make a physically valid design, which might be difficult to test if they are large, require nailing or screwing something to the wall, or the designer has mobility limitations. In this work, we present a design and visualization system for creating workable functional assemblies, FabHacks, which is based on a solver-aided domain-specific language (S-DSL) FabHaL. By analyzing existing home hacks shared online, we create a design abstraction for connecting household items using predefined types of connections. We provide a UI for FabHaL that can be used to design assemblies that fulfill a given specification. Our system leverages a physics-based solver that takes an assembly design and finds its expected physical configuration. Our validation includes a user study showing that users can create assemblies successfully using our UI and explore a range of designs. △ Less

Submitted 26 January, 2024; originally announced January 2024.

On the complexity of a maintenance problem for hierarchical systems

Authors: Andreas S. Schulz, Claudio Telha

Abstract: We prove that a maintenance problem on frequency-constrained maintenance jobs with a hierarchical structure is integer-factorization hard. This result holds even on simple systems with just two components to maintain. As a corollary, we provide a first hardness result for Levi et al.'s modular maintenance scheduling problem (Naval Research Logistics 61, 472-488, 2014). We prove that a maintenance problem on frequency-constrained maintenance jobs with a hierarchical structure is integer-factorization hard. This result holds even on simple systems with just two components to maintain. As a corollary, we provide a first hardness result for Levi et al.'s modular maintenance scheduling problem (Naval Research Logistics 61, 472-488, 2014). △ Less

Submitted 29 December, 2023; originally announced December 2023.

MSC Class: 90B25 ACM Class: F.2.2

DeltaLCA: Comparative Life-Cycle Assessment for Electronics Design

Authors: Zhihan Zhang, Felix Hähnlein, Yuxuan Mei, Zachary Englhardt, Shwetak Patel, Adriana Schulz, Vikram Iyer

Abstract: Reducing the environmental footprint of electronics and computing devices requires new tools that empower designers to make informed decisions about sustainability during the design process itself. This is not possible with current tools for life cycle assessment (LCA) which require substantial domain expertise and time to evaluate the numerous chips and other components that make up a device. We… ▽ More Reducing the environmental footprint of electronics and computing devices requires new tools that empower designers to make informed decisions about sustainability during the design process itself. This is not possible with current tools for life cycle assessment (LCA) which require substantial domain expertise and time to evaluate the numerous chips and other components that make up a device. We observe first that informed decision-making does not require absolute metrics and can instead be done by comparing designs. Second, we can use domain-specific heuristics to perform these comparisons. We combine these insights to develop DeltaLCA, an open-source interactive design tool that addresses the dual challenges of automating life cycle inventory generation and data availability by performing comparative analyses of electronics designs. Users can upload standard design files from Electronic Design Automation (EDA) software and the tool will guide them through determining which one has greater carbon footprint. DeltaLCA leverages electronics-specific LCA datasets and heuristics and tries to automatically rank the two designs, prompting users to provide additional information only when necessary. We show through case studies DeltaLCA achieves the same result as evaluating full LCAs, and that it accelerates LCA comparisons from eight expert-hours to a single click for devices with ~30 components, and 15 minutes for more complex devices with ~100 components. △ Less

Submitted 16 November, 2023; originally announced November 2023.

Primal Separation and Approximation for the $\{0, 1/2\}$-closure

Authors: Lukas Brandl, Andreas S. Schulz

Abstract: We advance the theoretical study of $\{0, 1/2\}$-cuts for integer programming problems $\max\{c^T x \colon A x \leq b, x \text{ integer}\}$. Such cuts are Gomory-Chvátal cuts that only need multipliers of value $0$ or $1/2$ in their derivation. The intersection of all $\{0, 1/2\}$-cuts derived from $Ax \le b$ is denoted by $P_{1/2}$ and called the $\{0,1/2\}$-closure of $P = \{x : Ax \le b\}$. The… ▽ More We advance the theoretical study of $\{0, 1/2\}$-cuts for integer programming problems $\max\{c^T x \colon A x \leq b, x \text{ integer}\}$. Such cuts are Gomory-Chvátal cuts that only need multipliers of value $0$ or $1/2$ in their derivation. The intersection of all $\{0, 1/2\}$-cuts derived from $Ax \le b$ is denoted by $P_{1/2}$ and called the $\{0,1/2\}$-closure of $P = \{x : Ax \le b\}$. The primal separation problem for $\{0, 1/2\}$-cuts is: Given a vertex $\hat x$ of the integer hull of $P$ and some fractional point $x^* \in P$, does there exist a $\{0,1/2\}$-cut that is tight at $\hat x$ and violated by $x^*$? Primal separation is the key ingredient of primal cutting-plane approaches to integer programming. In general, primal separation for $\{0,1/2\}$-cuts is NP-hard. We present two cases for which primal separation is solvable in polynomial time. As an interesting side product, we obtain a(nother) simple proof that matching can be solved in polynomial time. Furthermore, since optimization over the Gomory-Chvátal closure is also NP-hard, there has been recent research on solving the optimization problem over the Gomory-Chvátal closure approximately. In a similar spirit, we show that the optimization problem over the $\{0,1/2\}$-closure can be solved in polynomial time up to a factor $(1 + \varepsilon)$, for any fixed $\varepsilon > 0$. △ Less

Submitted 7 November, 2023; originally announced November 2023.

Comments: 14 pages

A Tight Formulation for the Dial-a-Ride Problem

Authors: Daniela Gaul, Kathrin Klamroth, Christian Pfeiffer, Arne Schulz, Michael Stiglmayr

Abstract: Ridepooling services play an increasingly important role in modern transportation systems. With soaring demand and growing fleet sizes, the underlying route planning problems become increasingly challenging. In this context, we consider the dial-a-ride problem (DARP): Given a set of transportation requests with pick-up and delivery locations, passenger numbers, time windows, and maximum ride times… ▽ More Ridepooling services play an increasingly important role in modern transportation systems. With soaring demand and growing fleet sizes, the underlying route planning problems become increasingly challenging. In this context, we consider the dial-a-ride problem (DARP): Given a set of transportation requests with pick-up and delivery locations, passenger numbers, time windows, and maximum ride times, an optimal routing for a fleet of vehicles, including an optimized passenger assignment, needs to be determined. We present tight mixed-integer linear programming (MILP) formulations for the DARP by combining two state-of-the-art models into novel location-augmented-event-based formulations. Strong valid inequalities and lower and upper bounding techniques are derived to further improve the formulations. We then demonstrate the theoretical and computational superiority of the new model: First, the formulation is tight in the sense that, if time windows shrink to a single point in time, the linear programming relaxation yields integer (and hence optimal) solutions. Second, extensive numerical experiments on benchmark instances show that computational times are on average reduced by 49.7% compared to state-of-the-art event-based approaches. △ Less

Submitted 22 August, 2023; originally announced August 2023.

Side-Contact Representations with Convex Polygons in 3D: New Results for Complete Bipartite Graphs

Authors: André Schulz

Abstract: A polyhedral surface~$\mathcal{C}$ in $\mathbb{R}^3$ with convex polygons as faces is a side-contact representation of a graph~$G$ if there is a bijection between the vertices of $G$ and the faces of~$\mathcal{C}$ such that the polygons of adjacent vertices are exactly the polygons sharing an entire common side in~$\mathcal{C}$. We show that $K_{3,8}$ has a side-contact representation but… ▽ More A polyhedral surface~$\mathcal{C}$ in $\mathbb{R}^3$ with convex polygons as faces is a side-contact representation of a graph~$G$ if there is a bijection between the vertices of $G$ and the faces of~$\mathcal{C}$ such that the polygons of adjacent vertices are exactly the polygons sharing an entire common side in~$\mathcal{C}$. We show that $K_{3,8}$ has a side-contact representation but $K_{3,250}$ has not. The latter result implies that the number of edges of a graph with side-contact representation and $n$ vertices is bounded by $O(n^{5/3})$. △ Less

Submitted 1 August, 2023; originally announced August 2023.

Comments: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

How Can Large Language Models Help Humans in Design and Manufacturing?

Authors: Liane Makatura, Michael Foshey, Bohan Wang, Felix HähnLein, Pingchuan Ma, Bolei Deng, Megan Tjandrasuwita, Andrew Spielberg, Crystal Elaine Owens, Peter Yichen Chen, Allan Zhao, Amy Zhu, Wil J Norton, Edward Gu, Joshua Jacob, Yifei Li, Adriana Schulz, Wojciech Matusik

Abstract: The advancement of Large Language Models (LLMs), including GPT-4, provides exciting new opportunities for generative design. We investigate the application of this tool across the entire design and manufacturing workflow. Specifically, we scrutinize the utility of LLMs in tasks such as: converting a text-based prompt into a design specification, transforming a design into manufacturing instruction… ▽ More The advancement of Large Language Models (LLMs), including GPT-4, provides exciting new opportunities for generative design. We investigate the application of this tool across the entire design and manufacturing workflow. Specifically, we scrutinize the utility of LLMs in tasks such as: converting a text-based prompt into a design specification, transforming a design into manufacturing instructions, producing a design space and design variations, computing the performance of a design, and searching for designs predicated on performance. Through a series of examples, we highlight both the benefits and the limitations of the current LLMs. By exposing these limitations, we aspire to catalyze the continued improvement and progression of these models. △ Less

Submitted 25 July, 2023; originally announced July 2023.

Zero-shot CAD Program Re-Parameterization for Interactive Manipulation

Authors: Milin Kodnongbua, Benjamin T. Jones, Maaz Bin Safeer Ahmad, Vladimir G. Kim, Adriana Schulz

Abstract: Parametric CAD models encode entire families of shapes that should, in principle, be easy for designers to explore. However, in practice, parametric CAD models can be difficult to manipulate due to implicit semantic constraints among parameter values. Finding and enforcing these semantic constraints solely from geometry or programmatic shape representations is not possible because these constraint… ▽ More Parametric CAD models encode entire families of shapes that should, in principle, be easy for designers to explore. However, in practice, parametric CAD models can be difficult to manipulate due to implicit semantic constraints among parameter values. Finding and enforcing these semantic constraints solely from geometry or programmatic shape representations is not possible because these constraints ultimately reflect design intent. They are informed by the designer's experience and semantics in the real world. To address this challenge, we introduce a zero-shot pipeline that leverages pre-trained large language and image model to infer meaningful space of variations for a shape. We then re-parameterize a new constrained parametric CAD program that captures these variations, enabling effortless exploration of the design space along meaningful design axes. △ Less

Submitted 5 June, 2023; originally announced June 2023.

Computational Design of Passive Grippers

Authors: Milin Kodnongbua, Ian Good Yu Lou, Jeffrey Lipton, Adriana Schulz

Abstract: This work proposes a novel generative design tool for passive grippers -- robot end effectors that have no additional actuation and instead leverage the existing degrees of freedom in a robotic arm to perform grasping tasks. Passive grippers are used because they offer interesting trade-offs between cost and capabilities. However, existing designs are limited in the types of shapes that can be gra… ▽ More This work proposes a novel generative design tool for passive grippers -- robot end effectors that have no additional actuation and instead leverage the existing degrees of freedom in a robotic arm to perform grasping tasks. Passive grippers are used because they offer interesting trade-offs between cost and capabilities. However, existing designs are limited in the types of shapes that can be grasped. This work proposes to use rapid-manufacturing and design optimization to expand the space of shapes that can be passively grasped. Our novel generative design algorithm takes in an object and its positioning with respect to a robotic arm and generates a 3D printable passive gripper that can stably pick the object up. To achieve this, we address the key challenge of jointly optimizing the shape and the insert trajectory to ensure a passively stable grasp. We evaluate our method on a testing suite of 22 objects (23 experiments), all of which were evaluated with physical experiments to bridge the virtual-to-real gap. Code and data are at https://homes.cs.washington.edu/~milink/passive-gripper/ △ Less

Submitted 5 June, 2023; originally announced June 2023.

Journal ref: ACM Transactions on Graphics, Volume 41, Issue 4, July 2022, Article No.: 149, pp 2-12

B-rep Matching for Collaborating Across CAD Systems

Authors: Benjamin Jones, James Noeckel, Milin Kodnongbua, Ilya Baran, Adriana Schulz

Abstract: Large Computer-Aided Design (CAD) projects usually require collaboration across many different CAD systems as well as applications that interoperate with them for manufacturing, visualization, or simulation. A fundamental barrier to such collaborations is the ability to refer to parts of the geometry (such as a specific face) robustly under geometric and/or topological changes to the model. Persis… ▽ More Large Computer-Aided Design (CAD) projects usually require collaboration across many different CAD systems as well as applications that interoperate with them for manufacturing, visualization, or simulation. A fundamental barrier to such collaborations is the ability to refer to parts of the geometry (such as a specific face) robustly under geometric and/or topological changes to the model. Persistent referencing schemes are a fundamental aspect of most CAD tools, but models that are shared across systems cannot generally make use of these internal referencing mechanisms, creating a challenge for collaboration. In this work, we address this issue by developing a novel learning-based algorithm that can automatically find correspondences between two CAD models using the standard representation used for sharing models across CAD systems: the Boundary-Representation (B-rep). Because our method works directly on B-reps it can be generalized across different CAD applications enabling collaboration. △ Less

Submitted 5 June, 2023; originally announced June 2023.

Journal ref: ACM Transactions on Graphics, Volume 42, Issue 4, August 2023, Article No.: 1

Utilizing Online and Open-Source Machine Learning Toolkits to Leverage the Future of Sustainable Engineering

Authors: Andrew Schulz, Suzanne Stathatos, Cassandra Shriver, Roxanne Moore

Abstract: Recently, there has been a national push to use machine learning (ML) and artificial intelligence (AI) to advance engineering techniques in all disciplines ranging from advanced fracture mechanics in materials science to soil and water quality testing in the civil and environmental engineering fields. Using AI, specifically machine learning, engineers can automate and decrease the processing or hu… ▽ More Recently, there has been a national push to use machine learning (ML) and artificial intelligence (AI) to advance engineering techniques in all disciplines ranging from advanced fracture mechanics in materials science to soil and water quality testing in the civil and environmental engineering fields. Using AI, specifically machine learning, engineers can automate and decrease the processing or human labeling time while maintaining statistical repeatability via trained models and sensors. Edge Impulse has designed an open-source TinyML-enabled Arduino education tool kit for engineering disciplines. This paper discusses the various applications and approaches engineering educators have taken to utilize ML toolkits in the classroom. We provide in-depth implementation guides and associated learning outcomes focused on the Environmental Engineering Classroom. We discuss five specific examples of four standard Environmental Engineering courses for freshman and junior-level engineering. There are currently few programs in the nation that utilize machine learning toolkits to prepare the next generation of ML and AI-educated engineers for industry and academic careers. This paper will guide educators to design and implement ML/AI into engineering curricula (without a specific AI or ML focus within the course) using simple, cheap, and open-source tools and technological aid from an online platform in collaboration with Edge Impulse. △ Less

Submitted 21 April, 2023; originally announced April 2023.

Comments: 11 pages,2 figures, A.S. and S.S. are co-first authors

Neurosymbolic Models for Computer Graphics

Authors: Daniel Ritchie, Paul Guerrero, R. Kenny Jones, Niloy J. Mitra, Adriana Schulz, Karl D. D. Willis, Jiajun Wu

Abstract: Procedural models (i.e. symbolic programs that output visual data) are a historically-popular method for representing graphics content: vegetation, buildings, textures, etc. They offer many advantages: interpretable design parameters, stochastic variations, high-quality outputs, compact representation, and more. But they also have some limitations, such as the difficulty of authoring a procedural… ▽ More Procedural models (i.e. symbolic programs that output visual data) are a historically-popular method for representing graphics content: vegetation, buildings, textures, etc. They offer many advantages: interpretable design parameters, stochastic variations, high-quality outputs, compact representation, and more. But they also have some limitations, such as the difficulty of authoring a procedural model from scratch. More recently, AI-based methods, and especially neural networks, have become popular for creating graphic content. These techniques allow users to directly specify desired properties of the artifact they want to create (via examples, constraints, or objectives), while a search, optimization, or learning algorithm takes care of the details. However, this ease of use comes at a cost, as it's often hard to interpret or manipulate these representations. In this state-of-the-art report, we summarize research on neurosymbolic models in computer graphics: methods that combine the strengths of both AI and symbolic programs to represent, generate, and manipulate visual data. We survey recent work applying these techniques to represent 2D shapes, 3D shapes, and materials & textures. Along the way, we situate each prior work in a unified design space for neurosymbolic models, which helps reveal underexplored areas and opportunities for future research. △ Less

Submitted 20 April, 2023; originally announced April 2023.

Comments: Eurographics 2023 State-of-the-art report (STAR)

On the geometric thickness of 2-degenerate graphs

Authors: Rahul Jain, Marco Ricci, Jonathan Rollin, André Schulz

Abstract: A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and hence the geometric thickness, of 2-degenerate graphs is at most 4. On the other hand, we show that there are 2-degenerate graphs that do not admit any… ▽ More A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and hence the geometric thickness, of 2-degenerate graphs is at most 4. On the other hand, we show that there are 2-degenerate graphs that do not admit any straight-line drawing with a decomposition of the edge set into 2 plane graphs. That is, there are 2-degenerate graphs with geometric thickness, and hence geometric arboricity, at least 3. This answers two questions posed by Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004]. △ Less

Submitted 28 February, 2023; originally announced February 2023.

Comments: 25 pages, 23 figures. Full version of extended abstracts appearing at EuroCG 2023 and SoCG 2023

Conservation Tools: The Next Generation of Engineering--Biology Collaborations

Authors: Andrew Schulz, Cassie Shriver, Suzanne Stathatos, Benjamin Seleb, Emily Weigel, Young-Hui Chang, M. Saad Bhamla, David Hu, Joseph R. Mendelson III, .

Abstract: The recent increase in public and academic interest in preserving biodiversity has led to the growth of the field of conservation technology. This field involves designing and constructing tools that utilize technology to aid in the conservation of wildlife. In this article, we will use case studies to demonstrate the importance of designing conservation tools with human-wildlife interaction in mi… ▽ More The recent increase in public and academic interest in preserving biodiversity has led to the growth of the field of conservation technology. This field involves designing and constructing tools that utilize technology to aid in the conservation of wildlife. In this article, we will use case studies to demonstrate the importance of designing conservation tools with human-wildlife interaction in mind and provide a framework for creating successful tools. These case studies include a range of complexities, from simple cat collars to machine learning and game theory methodologies. Our goal is to introduce and inform current and future researchers in the field of conservation technology and provide references for educating the next generation of conservation technologists. Conservation technology not only has the potential to benefit biodiversity but also has broader impacts on fields such as sustainability and environmental protection. By using innovative technologies to address conservation challenges, we can find more effective and efficient solutions to protect and preserve our planet's resources. △ Less

Submitted 3 January, 2023; originally announced January 2023.

Self-Supervised Representation Learning for CAD

Authors: Benjamin T. Jones, Michael Hu, Vladimir G. Kim, Adriana Schulz

Abstract: The design of man-made objects is dominated by computer aided design (CAD) tools. Assisting design with data-driven machine learning methods is hampered by lack of labeled data in CAD's native format; the parametric boundary representation (B-Rep). Several data sets of mechanical parts in B-Rep format have recently been released for machine learning research. However, large scale databases are lar… ▽ More The design of man-made objects is dominated by computer aided design (CAD) tools. Assisting design with data-driven machine learning methods is hampered by lack of labeled data in CAD's native format; the parametric boundary representation (B-Rep). Several data sets of mechanical parts in B-Rep format have recently been released for machine learning research. However, large scale databases are largely unlabeled, and labeled datasets are small. Additionally, task specific label sets are rare, and costly to annotate. This work proposes to leverage unlabeled CAD geometry on supervised learning tasks. We learn a novel, hybrid implicit/explicit surface representation for B-Rep geometry, and show that this pre-training significantly improves few-shot learning performance and also achieves state-of-the-art performance on several existing B-Rep benchmarks. △ Less

Submitted 19 October, 2022; originally announced October 2022.

Mates2Motion: Learning How Mechanical CAD Assemblies Work

Authors: James Noeckel, Benjamin T. Jones, Karl Willis, Brian Curless, Adriana Schulz

Abstract: We describe our work on inferring the degrees of freedom between mated parts in mechanical assemblies using deep learning on CAD representations. We train our model using a large dataset of real-world mechanical assemblies consisting of CAD parts and mates joining them together. We present methods for re-defining these mates to make them better reflect the motion of the assembly, as well as narrow… ▽ More We describe our work on inferring the degrees of freedom between mated parts in mechanical assemblies using deep learning on CAD representations. We train our model using a large dataset of real-world mechanical assemblies consisting of CAD parts and mates joining them together. We present methods for re-defining these mates to make them better reflect the motion of the assembly, as well as narrowing down the possible axes of motion. We also conduct a user study to create a motion-annotated test set with more reliable labels. △ Less

Submitted 4 May, 2023; v1 submitted 2 August, 2022; originally announced August 2022.

Comments: Contains 5 pages, 2 figures. Presented at the ICML 2022 Workshop on Machine Learning in Computational Design

"Why Here and Not There?" -- Diverse Contrasting Explanations of Dimensionality Reduction

Authors: André Artelt, Alexander Schulz, Barbara Hammer

Abstract: Dimensionality reduction is a popular preprocessing and a widely used tool in data mining. Transparency, which is usually achieved by means of explanations, is nowadays a widely accepted and crucial requirement of machine learning based systems like classifiers and recommender systems. However, transparency of dimensionality reduction and other data mining tools have not been considered in much de… ▽ More Dimensionality reduction is a popular preprocessing and a widely used tool in data mining. Transparency, which is usually achieved by means of explanations, is nowadays a widely accepted and crucial requirement of machine learning based systems like classifiers and recommender systems. However, transparency of dimensionality reduction and other data mining tools have not been considered in much depth yet, still it is crucial to understand their behavior -- in particular practitioners might want to understand why a specific sample got mapped to a specific location. In order to (locally) understand the behavior of a given dimensionality reduction method, we introduce the abstract concept of contrasting explanations for dimensionality reduction, and apply a realization of this concept to the specific application of explaining two dimensional data visualization. △ Less

Submitted 22 February, 2023; v1 submitted 15 June, 2022; originally announced June 2022.

Comments: Accepted and presented as a full conference paper at ICPRAM 2023

The SAME score: Improved cosine based bias score for word embeddings

Authors: Sarah Schröder, Alexander Schulz, Philip Kenneweg, Robert Feldhans, Fabian Hinder, Barbara Hammer

Abstract: Over the last years, word and sentence embeddings have established as text preprocessing for all kinds of NLP tasks and improved performances in these tasks significantly. Unfortunately, it has also been shown that these embeddings inherit various kinds of biases from the training data and thereby pass on biases present in society to NLP solutions. Many papers attempted to quantify bias in word or… ▽ More Over the last years, word and sentence embeddings have established as text preprocessing for all kinds of NLP tasks and improved performances in these tasks significantly. Unfortunately, it has also been shown that these embeddings inherit various kinds of biases from the training data and thereby pass on biases present in society to NLP solutions. Many papers attempted to quantify bias in word or sentence embeddings to evaluate debiasing methods or compare different embedding models, often with cosine-based scores. However, some works have raised doubts about these scores showing that even though they report low biases, biases persist and can be shown with other tests. In fact, there is a great variety of bias scores or tests proposed in the literature without any consensus on the optimal solutions. We lack works that study the behavior of bias scores and elaborate their advantages and disadvantages. In this work, we will explore different cosine-based bias scores. We provide a bias definition based on the ideas from the literature and derive novel requirements for bias scores. Furthermore, we thoroughly investigate the existing cosine-based scores and their limitations in order to show why these scores fail to report biases in some situations. Finally, we propose a new bias score, SAME, to address the shortcomings of existing bias scores and show empirically that SAME is better suited to quantify biases in word embeddings. △ Less

Submitted 24 October, 2022; v1 submitted 28 March, 2022; originally announced March 2022.

Comments: 17 pages, 5 figures. arXiv admin note: substantial text overlap with arXiv:2111.07864

BERT WEAVER: Using WEight AVERaging to enable lifelong learning for transformer-based models in biomedical semantic search engines

Authors: Lisa Kühnel, Alexander Schulz, Barbara Hammer, Juliane Fluck

Abstract: Recent developments in transfer learning have boosted the advancements in natural language processing tasks. The performance is, however, dependent on high-quality, manually annotated training data. Especially in the biomedical domain, it has been shown that one training corpus is not enough to learn generic models that are able to efficiently predict on new data. Therefore, in order to be used in… ▽ More Recent developments in transfer learning have boosted the advancements in natural language processing tasks. The performance is, however, dependent on high-quality, manually annotated training data. Especially in the biomedical domain, it has been shown that one training corpus is not enough to learn generic models that are able to efficiently predict on new data. Therefore, in order to be used in real world applications state-of-the-art models need the ability of lifelong learning to improve performance as soon as new data are available - without the need of re-training the whole model from scratch. We present WEAVER, a simple, yet efficient post-processing method that infuses old knowledge into the new model, thereby reducing catastrophic forgetting. We show that applying WEAVER in a sequential manner results in similar word embedding distributions as doing a combined training on all data at once, while being computationally more efficient. Because there is no need of data sharing, the presented method is also easily applicable to federated learning settings and can for example be beneficial for the mining of electronic health records from different clinics. △ Less

Submitted 31 October, 2023; v1 submitted 21 February, 2022; originally announced February 2022.

Evaluating Metrics for Bias in Word Embeddings

Authors: Sarah Schröder, Alexander Schulz, Philip Kenneweg, Robert Feldhans, Fabian Hinder, Barbara Hammer

Abstract: Over the last years, word and sentence embeddings have established as text preprocessing for all kinds of NLP tasks and improved the performances significantly. Unfortunately, it has also been shown that these embeddings inherit various kinds of biases from the training data and thereby pass on biases present in society to NLP solutions. Many papers attempted to quantify bias in word or sentence e… ▽ More Over the last years, word and sentence embeddings have established as text preprocessing for all kinds of NLP tasks and improved the performances significantly. Unfortunately, it has also been shown that these embeddings inherit various kinds of biases from the training data and thereby pass on biases present in society to NLP solutions. Many papers attempted to quantify bias in word or sentence embeddings to evaluate debiasing methods or compare different embedding models, usually with cosine-based metrics. However, lately some works have raised doubts about these metrics showing that even though such metrics report low biases, other tests still show biases. In fact, there is a great variety of bias metrics or tests proposed in the literature without any consensus on the optimal solutions. Yet we lack works that evaluate bias metrics on a theoretical level or elaborate the advantages and disadvantages of different bias metrics. In this work, we will explore different cosine based bias metrics. We formalize a bias definition based on the ideas from previous works and derive conditions for bias metrics. Furthermore, we thoroughly investigate the existing cosine-based metrics and their limitations to show why these metrics can fail to report biases in some cases. Finally, we propose a new metric, SAME, to address the shortcomings of existing metrics and mathematically prove that SAME behaves appropriately. △ Less

Submitted 15 November, 2021; originally announced November 2021.

Differentiable 3D CAD Programs for Bidirectional Editing

Authors: Dan Cascaval, Mira Shalah, Phillip Quinn, Rastislav Bodik, Maneesh Agrawala, Adriana Schulz

Abstract: Modern CAD tools represent 3D designs not only as geometry, but also as a program composed of geometric operations, each of which depends on a set of parameters. Program representations enable meaningful and controlled shape variations via parameter changes. However, achieving desired modifications solely through parameter editing is challenging when CAD models have not been explicitly authored to… ▽ More Modern CAD tools represent 3D designs not only as geometry, but also as a program composed of geometric operations, each of which depends on a set of parameters. Program representations enable meaningful and controlled shape variations via parameter changes. However, achieving desired modifications solely through parameter editing is challenging when CAD models have not been explicitly authored to expose select degrees of freedom in advance. We introduce a novel bidirectional editing system for 3D CAD programs. In addition to editing the CAD program, users can directly manipulate 3D geometry and our system infers parameter updates to keep both representations in sync. We formulate inverse edits as a set of constrained optimization objectives, returning plausible updates to program parameters that both match user intent and maintain program validity. Our approach implements an automatically differentiable domain-specific language for CAD programs, providing derivatives for this optimization to be performed quickly on any expressed program. Our system enables rapid, interactive exploration of a constrained 3D design space by allowing users to manipulate the program and geometry interchangeably during design iteration. While our approach is not designed to optimize across changes in geometric topology, we show it is expressive and performant enough for users to produce a diverse set of design variants, even when the CAD program contains a large number of parameters. △ Less

Submitted 4 October, 2021; originally announced October 2021.

Comments: 13 pages, 8 figures

Rewrite Rule Inference Using Equality Saturation

Authors: Chandrakana Nandi, Max Willsey, Amy Zhu, Yisu Remy Wang, Brett Saiki, Adam Anderson, Adriana Schulz, Dan Grossman, Zachary Tatlock

Abstract: Many compilers, synthesizers, and theorem provers rely on rewrite rules to simplify expressions or prove equivalences. Developing rewrite rules can be difficult: rules may be subtly incorrect, profitable rules are easy to miss, and rulesets must be rechecked or extended whenever semantics are tweaked. Large rulesets can also be challenging to apply: redundant rules slow down rule-based search and… ▽ More Many compilers, synthesizers, and theorem provers rely on rewrite rules to simplify expressions or prove equivalences. Developing rewrite rules can be difficult: rules may be subtly incorrect, profitable rules are easy to miss, and rulesets must be rechecked or extended whenever semantics are tweaked. Large rulesets can also be challenging to apply: redundant rules slow down rule-based search and frustrate debugging. This paper explores how equality saturation, a promising technique that uses e-graphs to apply rewrite rules, can also be used to infer rewrite rules. E-graphs can compactly represent the exponentially large sets of enumerated terms and potential rewrite rules. We show that equality saturation efficiently shrinks both sets, leading to faster synthesis of smaller, more general rulesets. We prototyped these strategies in a tool dubbed ruler. Compared to a similar tool built on CVC4, ruler synthesizes 5.8X smaller rulesets 25X faster without compromising on proving power. In an end-to-end case study, we show ruler-synthesized rules which perform as well as those crafted by domain experts, and addressed a longstanding issue in a popular open source tool. △ Less

Submitted 23 August, 2021; originally announced August 2021.

Co-Optimization of Design and Fabrication Plans for Carpentry: Supplemental Material

Authors: Haisen Zhao, Max Willsey, Amy Zhu, Chandrakana Nandi, Zachary Tatlock, Justin Solomon, Adriana Schulz

Abstract: Past work on optimizing fabrication plans given a carpentry design can provide Pareto-optimal plans trading off between material waste, fabrication time, precision, and other considerations. However, when developing fabrication plans, experts rarely restrict to a single design, instead considering families of design variations, sometimes adjusting designs to simplify fabrication. Jointly exploring… ▽ More Past work on optimizing fabrication plans given a carpentry design can provide Pareto-optimal plans trading off between material waste, fabrication time, precision, and other considerations. However, when developing fabrication plans, experts rarely restrict to a single design, instead considering families of design variations, sometimes adjusting designs to simplify fabrication. Jointly exploring the design and fabrication plan spaces for each design is intractable using current techniques. We present a new approach to jointly optimize design and fabrication plans for carpentered objects. To make this bi-level optimization tractable, we adapt recent work from program synthesis based on equality graphs (e-graphs), which encode sets of equivalent programs. Our insight is that subproblems within our bi-level problem share significant substructures. By representing both designs and fabrication plans in a new bag of parts(BOP) e-graph, we amortize the cost of optimizing design components shared among multiple candidates. Even using BOP e-graphs, the optimization space grows quickly in practice. Hence, we also show how a feedback-guided search strategy dubbed Iterative Contraction and Expansion on E-graphs (ICEE) can keep the size of the e-graph manage-able and direct the search toward promising candidates. We illustrate the advantages of our pipeline through examples from the carpentry domain. △ Less

Submitted 30 July, 2021; originally announced July 2021.

Comments: 20 pages, 18 figure

ACM Class: I.3; I.3.8

Co-Optimization of Design and Fabrication Plans for Carpentry

Authors: Haisen Zhao, Max Willsey, Amy Zhu, Chandrakana Nandi, Zachary Tatlock, Justin Solomon, Adriana Schulz

Abstract: Past work on optimizing fabrication plans given a carpentry design can provide Pareto-optimal plans trading off between material waste, fabrication time, precision, and other considerations. However, when developing fabrication plans, experts rarely restrict to a single design, instead considering families of design variations, sometimes adjusting designs to simplify fabrication. Jointly exploring… ▽ More Past work on optimizing fabrication plans given a carpentry design can provide Pareto-optimal plans trading off between material waste, fabrication time, precision, and other considerations. However, when developing fabrication plans, experts rarely restrict to a single design, instead considering families of design variations, sometimes adjusting designs to simplify fabrication. Jointly exploring the design and fabrication plan spaces for each design is intractable using current techniques. We present a new approach to jointly optimize design and fabrication plans for carpentered objects. To make this bi-level optimization tractable, we adapt recent work from program synthesis based on equality graphs (e-graphs), which encode sets of equivalent programs. Our insight is that subproblems within our bi-level problem share significant substructures. By representing both designs and fabrication plans in a new bag of parts(BOP) e-graph, we amortize the cost of optimizing design components shared among multiple candidates. Even using BOP e-graphs, the optimization space grows quickly in practice. Hence, we also show how a feedback-guided search strategy dubbed Iterative Contraction and Expansion on E-graphs(ICEE) can keep the size of the e-graph manage-able and direct the search toward promising candidates. We illustrate the advantages of our pipeline through examples from the carpentry domain. △ Less

Submitted 3 August, 2021; v1 submitted 26 July, 2021; originally announced July 2021.

Comments: 14 pages, 13 figure, Supplemental material: arXiv:2107.14745

ACM Class: I.3; I.3.8

Fabrication-Aware Reverse Engineering for Carpentry

Authors: James Noeckel, Haisen Zhao, Brian Curless, Adriana Schulz

Abstract: We propose a novel method to generate fabrication blueprints from images of carpentered items. While 3D reconstruction from images is a well-studied problem, typical approaches produce representations that are ill-suited for computer-aided design and fabrication applications. Our key insight is that fabrication processes define and constrain the design space for carpentered objects, and can be lev… ▽ More We propose a novel method to generate fabrication blueprints from images of carpentered items. While 3D reconstruction from images is a well-studied problem, typical approaches produce representations that are ill-suited for computer-aided design and fabrication applications. Our key insight is that fabrication processes define and constrain the design space for carpentered objects, and can be leveraged to develop novel reconstruction methods. Our method makes use of domain-specific constraints to recover not just valid geometry, but a semantically valid assembly of parts, using a combination of image-based and geometric optimization techniques. We demonstrate our method on a variety of wooden objects and furniture, and show that we can automatically obtain designs that are both easy to edit and accurate recreations of the ground truth. We further illustrate how our method can be used to fabricate a physical replica of the captured object as well as a customized version, which can be produced by directly editing the reconstructed model in CAD software. △ Less

Submitted 21 July, 2021; originally announced July 2021.

Comments: 24 pages, plus 6 pages of supplemental material. 14 figures. To be published in Eurographics Symposium on Geometry Processing, Volume 40 (2021), Number 5

Arrangements of orthogonal circles with many intersections

Authors: Sarah Carmesin, André Schulz

Abstract: An arrangement of circles in which circles intersect only in angles of $π/2$ is called an \emph{arrangement of orthogonal circles}. We show that in the case that no two circles are nested, the intersection graph of such an arrangement is planar. The same result holds for arrangement of circles that intersect in an angle of at most $π/2$. For the general case we prove that the maximal number of e… ▽ More An arrangement of circles in which circles intersect only in angles of $π/2$ is called an \emph{arrangement of orthogonal circles}. We show that in the case that no two circles are nested, the intersection graph of such an arrangement is planar. The same result holds for arrangement of circles that intersect in an angle of at most $π/2$. For the general case we prove that the maximal number of edges in an intersection graph of an arrangement of orthogonal circles lies in between $4n - O\left(\sqrt{n}\right)$ and $\left(4+\frac{5}{11}\right)n$, for $n$ being the number of circles. Based on the lower bound we can also improve the bound for the number of triangles in arrangements of orthogonal circles to $(3 + 5/9)n-O\left(\sqrt{n}\right)$. △ Less

Submitted 16 August, 2021; v1 submitted 7 June, 2021; originally announced June 2021.

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

MSC Class: 52C45 ACM Class: G.2.1

AutoMate: A Dataset and Learning Approach for Automatic Mating of CAD Assemblies

Authors: Benjamin Jones, Dalton Hildreth, Duowen Chen, Ilya Baran, Vladimir G. Kim, Adriana Schulz

Abstract: Assembly modeling is a core task of computer aided design (CAD), comprising around one third of the work in a CAD workflow. Optimizing this process therefore represents a huge opportunity in the design of a CAD system, but current research of assembly based modeling is not directly applicable to modern CAD systems because it eschews the dominant data structure of modern CAD: parametric boundary re… ▽ More Assembly modeling is a core task of computer aided design (CAD), comprising around one third of the work in a CAD workflow. Optimizing this process therefore represents a huge opportunity in the design of a CAD system, but current research of assembly based modeling is not directly applicable to modern CAD systems because it eschews the dominant data structure of modern CAD: parametric boundary representations (BREPs). CAD assembly modeling defines assemblies as a system of pairwise constraints, called mates, between parts, which are defined relative to BREP topology rather than in world coordinates common to existing work. We propose SB-GCN, a representation learning scheme on BREPs that retains the topological structure of parts, and use these learned representations to predict CAD type mates. To train our system, we compiled the first large scale dataset of BREP CAD assemblies, which we are releasing along with benchmark mate prediction tasks. Finally, we demonstrate the compatibility of our model with an existing commercial CAD system by building a tool that assists users in mate creation by suggesting mate completions, with 72.2% accuracy. △ Less

Submitted 4 October, 2021; v1 submitted 25 May, 2021; originally announced May 2021.

Comments: 16 pages, 17 figures, 4 tables

ACM Class: I.3.5; I.2.10

Reservoir Stack Machines

Authors: Benjamin Paaßen, Alexander Schulz, Barbara Hammer

Abstract: Memory-augmented neural networks equip a recurrent neural network with an explicit memory to support tasks that require information storage without interference over long times. A key motivation for such research is to perform classic computation tasks, such as parsing. However, memory-augmented neural networks are notoriously hard to train, requiring many backpropagation epochs and a lot of data.… ▽ More Memory-augmented neural networks equip a recurrent neural network with an explicit memory to support tasks that require information storage without interference over long times. A key motivation for such research is to perform classic computation tasks, such as parsing. However, memory-augmented neural networks are notoriously hard to train, requiring many backpropagation epochs and a lot of data. In this paper, we introduce the reservoir stack machine, a model which can provably recognize all deterministic context-free languages and circumvents the training problem by training only the output layer of a recurrent net and employing auxiliary information during training about the desired interaction with a stack. In our experiments, we validate the reservoir stack machine against deep and shallow networks from the literature on three benchmark tasks for Neural Turing machines and six deterministic context-free languages. Our results show that the reservoir stack machine achieves zero error, even on test sequences longer than the training data, requiring only a few seconds of training time and 100 training sequences. △ Less

Submitted 26 July, 2021; v1 submitted 4 May, 2021; originally announced May 2021.

Comments: in print at the Journal Neurocomputing

On the Complexity of Recognizing Integrality and Total Dual Integrality of the $\{0,1/2\}$-Closure

Authors: Matthias Brugger, Andreas S. Schulz

Abstract: The $\{0,\frac{1}{2}\}$-closure of a rational polyhedron $\{ x \colon Ax \le b \}$ is obtained by adding all Gomory-Chvátal cuts that can be derived from the linear system $Ax \le b$ using multipliers in $\{0,\frac{1}{2}\}$. We show that deciding whether the $\{0,\frac{1}{2}\}$-closure coincides with the integer hull is strongly NP-hard. A direct consequence of our proof is that, testing whether t… ▽ More The $\{0,\frac{1}{2}\}$-closure of a rational polyhedron $\{ x \colon Ax \le b \}$ is obtained by adding all Gomory-Chvátal cuts that can be derived from the linear system $Ax \le b$ using multipliers in $\{0,\frac{1}{2}\}$. We show that deciding whether the $\{0,\frac{1}{2}\}$-closure coincides with the integer hull is strongly NP-hard. A direct consequence of our proof is that, testing whether the linear description of the $\{0,\frac{1}{2}\}$-closure derived from $Ax \le b$ is totally dual integral, is strongly NP-hard. △ Less

Submitted 29 April, 2021; originally announced April 2021.

Comments: 7 pages

Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems

Authors: Gero Friesecke, Andreas S. Schulz, Daniela Vögler

Abstract: We introduce a simple, accurate, and extremely efficient method for numerically solving the multi-marginal optimal transport (MMOT) problems arising in density functional theory. The method relies on (i) the sparsity of optimal plans [for $N$ marginals discretized by $\ell$ gridpoints each, general Kantorovich plans require $\ell^N$ gridpoints but the support of optimizers is of size… ▽ More We introduce a simple, accurate, and extremely efficient method for numerically solving the multi-marginal optimal transport (MMOT) problems arising in density functional theory. The method relies on (i) the sparsity of optimal plans [for $N$ marginals discretized by $\ell$ gridpoints each, general Kantorovich plans require $\ell^N$ gridpoints but the support of optimizers is of size $O(\ell\cdot N)$ [FV18]], (ii) the method of column generation (CG) from discrete optimization which to our knowledge has not hitherto been used in MMOT, and (iii) ideas from machine learning. The well-known bottleneck in CG consists in generating new candidate columns efficiently; we prove that in our context, finding the best new column is an NP-complete problem. To overcome this bottleneck we use a genetic learning method tailormade for MMOT in which the dual state within CG plays the role of an "adversary", in loose similarity to Wasserstein GANs. On a sequence of benchmark problems with up to 120 gridpoints and up to 30 marginals, our method always found the exact optimizers. Moreover, empirically the number of computational steps needed to find them appears to scale only polynomially when both $N$ and $\ell$ are simultaneously increased (while keeping their ratio fixed to mimic a thermodynamic limit of the particle system). △ Less

Submitted 23 March, 2021; originally announced March 2021.

Adjacency Graphs of Polyhedral Surfaces

Authors: Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, Alexander Wolff

Abstract: We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $\mathbb{R}^3$. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $K_5$, $K_{5,81}$, or any nonplanar $3$-tree as a subgraph, no… ▽ More We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in $\mathbb{R}^3$. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $K_5$, $K_{5,81}$, or any nonplanar $3$-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $K_{4,4}$, and $K_{3,5}$ can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable $n$-vertex graphs is in $Ω(n \log n)$. From the non-realizability of $K_{5,81}$, we obtain that any realizable $n$-vertex graph has $O(n^{9/5})$ edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense. △ Less

Submitted 15 May, 2023; v1 submitted 17 March, 2021; originally announced March 2021.

Comments: The conference version of this paper appeared in Proc. SoCG 2021

Reservoir Memory Machines as Neural Computers

Authors: Benjamin Paaßen, Alexander Schulz, Terrence C. Stewart, Barbara Hammer

Abstract: Differentiable neural computers extend artificial neural networks with an explicit memory without interference, thus enabling the model to perform classic computation tasks such as graph traversal. However, such models are difficult to train, requiring long training times and large datasets. In this work, we achieve some of the computational capabilities of differentiable neural computers with a m… ▽ More Differentiable neural computers extend artificial neural networks with an explicit memory without interference, thus enabling the model to perform classic computation tasks such as graph traversal. However, such models are difficult to train, requiring long training times and large datasets. In this work, we achieve some of the computational capabilities of differentiable neural computers with a model that can be trained very efficiently, namely an echo state network with an explicit memory without interference. This extension enables echo state networks to recognize all regular languages, including those that contractive echo state networks provably can not recognize. Further, we demonstrate experimentally that our model performs comparably to its fully-trained deep version on several typical benchmark tasks for differentiable neural computers. △ Less

Submitted 19 July, 2021; v1 submitted 14 September, 2020; originally announced September 2020.

Comments: In print at the special issue 'New Frontiers in Extremely Efficient Reservoir Computing' of IEEE TNNLS

Journal ref: IEEE Transactions on Neural Networks and Learning Systems 33 (2022) 2575-2585

Augmenting Geometric Graphs with Matchings

Authors: Alexander Pilz, Jonathan Rollin, Lena Schlipf, André Schulz

Abstract: We study noncrossing geometric graphs and their disjoint compatible geometric matchings. Given a cycle (a polygon) P we want to draw a set of pairwise disjoint straight-line edges with endpoints on the vertices of P such that these new edges neither cross nor contain any edge of the polygon. We prove NP-completeness of deciding whether there is such a perfect matching. For any n-vertex polygon, wi… ▽ More We study noncrossing geometric graphs and their disjoint compatible geometric matchings. Given a cycle (a polygon) P we want to draw a set of pairwise disjoint straight-line edges with endpoints on the vertices of P such that these new edges neither cross nor contain any edge of the polygon. We prove NP-completeness of deciding whether there is such a perfect matching. For any n-vertex polygon, with n > 3, we show that such a matching with less than n/7 edges is not maximal, that is, it can be extended by another compatible matching edge. We also construct polygons with maximal compatible matchings with n/7 edges, demonstrating the tightness of this bound. Tight bounds on the size of a minimal maximal compatible matching are also obtained for the families of d-regular geometric graphs for each d in {0,1,2}. Finally we consider a related problem. We prove that it is NP-complete to decide whether a noncrossing geometric graph G admits a set of compatible noncrossing edges such that G together with these edges has minimum degree five. △ Less

Submitted 19 August, 2020; originally announced August 2020.

Comments: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Integer factorization and Riemann's hypothesis: Why two-item joint replenishment is hard

Authors: Andreas S. Schulz, Claudio Telha

Abstract: Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are a fundamental model in inventory management, manufacturing, and logistics that capture these effects. However, finding an efficient algorithm that optimally solves these models, or showing that none may exist, has long been open, regardless of whether em… ▽ More Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are a fundamental model in inventory management, manufacturing, and logistics that capture these effects. However, finding an efficient algorithm that optimally solves these models, or showing that none may exist, has long been open, regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint replenishment instances with just two products is at least as difficult as integer factorization. To the best of the authors' knowledge, this is the first time that integer factorization is used to explain the computational hardness of any kind of optimization problem. Under the assumption that Riemann's Hypothesis is correct, we can actually prove that the two-item joint replenishment problem with possibly empty joint ordering points is NP-complete under randomized reductions, which implies that not even quantum computers may be able to solve it efficiently. By relating the computational complexity of joint replenishment to cryptography, prime decomposition, and other aspects of prime numbers, a similar approach may help to establish (integer factorization) hardness of additional open periodic problems in supply chain management and beyond, whose solution has eluded standard methods. △ Less

Submitted 17 July, 2020; originally announced July 2020.

Comments: 20 pages, 4 figures

ACM Class: F.2

Reservoir memory machines

Authors: Benjamin Paassen, Alexander Schulz

Abstract: In recent years, Neural Turing Machines have gathered attention by joining the flexibility of neural networks with the computational capabilities of Turing machines. However, Neural Turing Machines are notoriously hard to train, which limits their applicability. We propose reservoir memory machines, which are still able to solve some of the benchmark tests for Neural Turing Machines, but are much… ▽ More In recent years, Neural Turing Machines have gathered attention by joining the flexibility of neural networks with the computational capabilities of Turing machines. However, Neural Turing Machines are notoriously hard to train, which limits their applicability. We propose reservoir memory machines, which are still able to solve some of the benchmark tests for Neural Turing Machines, but are much faster to train, requiring only an alignment algorithm and linear regression. Our model can also be seen as an extension of echo state networks with an external memory, enabling arbitrarily long storage without interference. △ Less

Submitted 11 February, 2020; originally announced March 2020.

Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover

Authors: Felix Happach, Andreas S. Schulz

Abstract: We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set cover problem and the min-sum vertex cover problem. For each of these problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed LP relaxations. We show how a variant of alpha-point scheduling leads to the best-known approximation ratios, including a g… ▽ More We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set cover problem and the min-sum vertex cover problem. For each of these problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed LP relaxations. We show how a variant of alpha-point scheduling leads to the best-known approximation ratios, including a guarantee of 4 for an interesting special case of the so-called generalized min-sum set cover problem. We also make explicit the connection between the greedy algorithm for min-sum set cover and the concept of Sidney decomposition for precedence-constrained single-machine scheduling, and show how this leads to a 4-approximation algorithm for single-machine scheduling with so-called bipartite OR-precedence constraints. △ Less

Submitted 20 January, 2020; originally announced January 2020.

MSC Class: 90B35; 90C05; 68W25

DeepView: Visualizing Classification Boundaries of Deep Neural Networks as Scatter Plots Using Discriminative Dimensionality Reduction

Authors: Alexander Schulz, Fabian Hinder, Barbara Hammer

Abstract: Machine learning algorithms using deep architectures have been able to implement increasingly powerful and successful models. However, they also become increasingly more complex, more difficult to comprehend and easier to fool. So far, most methods in the literature investigate the decision of the model for a single given input datum. In this paper, we propose to visualize a part of the decision f… ▽ More Machine learning algorithms using deep architectures have been able to implement increasingly powerful and successful models. However, they also become increasingly more complex, more difficult to comprehend and easier to fool. So far, most methods in the literature investigate the decision of the model for a single given input datum. In this paper, we propose to visualize a part of the decision function of a deep neural network together with a part of the data set in two dimensions with discriminative dimensionality reduction. This enables us to inspect how different properties of the data are treated by the model, such as outliers, adversaries or poisoned data. Further, the presented approach is complementary to the mentioned interpretation methods from the literature and hence might be even more useful in combination with those. Code is available at https://github.com/LucaHermes/DeepView . △ Less

Submitted 19 August, 2020; v1 submitted 19 September, 2019; originally announced September 2019.

Comments: This is published at IJCAI 2020

Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses

Authors: Yiannis Giannakopoulos, Georgy Noarov, Andreas S. Schulz

Abstract: We present a deterministic polynomial-time algorithm for computing $d^{d+o(d)}$-approximate (pure) Nash equilibria in (proportional sharing) weighted congestion games with polynomial cost functions of degree at most $d$. This is an exponential improvement of the approximation factor with respect to the previously best deterministic algorithm. An appealing additional feature of the algorithm is tha… ▽ More We present a deterministic polynomial-time algorithm for computing $d^{d+o(d)}$-approximate (pure) Nash equilibria in (proportional sharing) weighted congestion games with polynomial cost functions of degree at most $d$. This is an exponential improvement of the approximation factor with respect to the previously best deterministic algorithm. An appealing additional feature of the algorithm is that it only uses best-improvement steps in the actual game, as opposed to the previously best algorithms, that first had to transform the game itself. Our algorithm is an adaptation of the seminal algorithm by Caragiannis et al. [FOCS'11, TEAC 2015], but we utilize an approximate potential function directly on the original game instead of an exact one on a modified game. A critical component of our analysis, which is of independent interest, is the derivation of a novel bound of $[d/\mathcal{W}(d/ρ)]^{d+1}$ for the Price of Anarchy (PoA) of $ρ$-approximate equilibria in weighted congestion games, where $\mathcal{W}$ is the Lambert-W function. More specifically, we show that this PoA is exactly equal to $Φ_{d,ρ}^{d+1}$, where $Φ_{d,ρ}$ is the unique positive solution of the equation $ρ(x+1)^d=x^{d+1}$. Our upper bound is derived via a smoothness-like argument, and thus holds even for mixed Nash and correlated equilibria, while our lower bound is simple enough to apply even to singleton congestion games. △ Less

Submitted 25 November, 2020; v1 submitted 30 October, 2018; originally announced October 2018.

Comments: To be published in Mathematics of Operations Research

The Partition Spanning Forest Problem

Authors: Philipp Kindermann, Boris Klemz, Ignaz Rutter, Patrick Schnider, André Schulz

Abstract: Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly the points of one color class. We show that the problem is NP-complete, even if every color class contains at most five points, but it is solvable in $O(n^2)$ time when each color class contains at most three points. If w… ▽ More Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly the points of one color class. We show that the problem is NP-complete, even if every color class contains at most five points, but it is solvable in $O(n^2)$ time when each color class contains at most three points. If we require that the spanning forest is a linear forest, then the problem becomes NP-complete even if every color class contains at most four points. △ Less

Submitted 7 September, 2018; originally announced September 2018.

Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles

Authors: Philipp Kindermann, Fabrizio Montecchiani, Lena Schlipf, André Schulz

Abstract: We show that the 1-planar slope number of 3-connected cubic 1-planar graphs is at most 4 when edges are drawn as polygonal curves with at most 1 bend each. This bound is obtained by drawings whose vertex and crossing resolution is at least $π/4$. On the other hand, if the embedding is fixed, then there is a 3-connected cubic 1-planar graph that needs 3 slopes when drawn with at most 1 bend per edg… ▽ More We show that the 1-planar slope number of 3-connected cubic 1-planar graphs is at most 4 when edges are drawn as polygonal curves with at most 1 bend each. This bound is obtained by drawings whose vertex and crossing resolution is at least $π/4$. On the other hand, if the embedding is fixed, then there is a 3-connected cubic 1-planar graph that needs 3 slopes when drawn with at most 1 bend per edge. We also show that 2 slopes always suffice for 1-planar drawings of subcubic 1-planar graphs with at most 2 bends per edge. This bound is obtained with vertex resolution $π/2$ and the drawing is RAC (crossing resolution $π/2$). Finally, we prove lower bounds for the slope number of straight-line 1-planar drawings in terms of number of vertices and maximum degree. △ Less

Submitted 25 August, 2018; originally announced August 2018.

Comments: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

Expectation maximization transfer learning and its application for bionic hand prostheses

Authors: Benjamin Paaßen, Alexander Schulz, Janne Hahne, Barbara Hammer

Abstract: Machine learning models in practical settings are typically confronted with changes to the distribution of the incoming data. Such changes can severely affect the model performance, leading for example to misclassifications of data. This is particularly apparent in the domain of bionic hand prostheses, where machine learning models promise faster and more intuitive user interfaces, but are hindere… ▽ More Machine learning models in practical settings are typically confronted with changes to the distribution of the incoming data. Such changes can severely affect the model performance, leading for example to misclassifications of data. This is particularly apparent in the domain of bionic hand prostheses, where machine learning models promise faster and more intuitive user interfaces, but are hindered by their lack of robustness to everyday disturbances, such as electrode shifts. One way to address changes in the data distribution is transfer learning, that is, to transfer the disturbed data to a space where the original model is applicable again. In this contribution, we propose a novel expectation maximization algorithm to learn linear transformations that maximize the likelihood of disturbed data after the transformation. We also show that this approach generalizes to discriminative models, in particular learning vector quantization models. In our evaluation on data from the bionic prostheses domain we demonstrate that our approach can learn a transformation which improves classification accuracy significantly and outperforms all tested baselines, if few data or few classes are available in the target domain. △ Less

Submitted 25 November, 2017; originally announced November 2017.

Comments: accepted for publication in a special issue of the Journal 'Neurocomputing' for extended contributions of the 25h European Symposium on Artificial Neural Networks (ESANN 2017)

Journal ref: Neurocomputing 298 (2018) 122-133

Lombardi Drawings of Knots and Links

Authors: Philipp Kindermann, Stephen Kobourov, Maarten Löffler, Martin Nöllenburg, André Schulz, Birgit Vogtenhuber

Abstract: Knot and link diagrams are projections of one or more 3-dimensional simple closed curves into $R^2$, such that no more than two points project to the same point in $R^2$. These diagrams are drawings of 4-regular plane multigraphs. Knots are typically smooth curves in $R^3$, so their projections should be smooth curves in $R^2$ with good continuity and large crossing angles: exactly the properties… ▽ More Knot and link diagrams are projections of one or more 3-dimensional simple closed curves into $R^2$, such that no more than two points project to the same point in $R^2$. These diagrams are drawings of 4-regular plane multigraphs. Knots are typically smooth curves in $R^3$, so their projections should be smooth curves in $R^2$ with good continuity and large crossing angles: exactly the properties of Lombardi graph drawings (defined by circular-arc edges and perfect angular resolution). We show that several knots do not allow plane Lombardi drawings. On the other hand, we identify a large class of 4-regular plane multigraphs that do have Lombardi drawings. We then study two relaxations of Lombardi drawings and show that every knot admits a plane 2-Lombardi drawing (where edges are composed of two circular arcs). Further, every knot is near-Lombardi, that is, it can be drawn as Lombardi drawing when relaxing the angular resolution requirement by an arbitrary small angular offset $\varepsilon$, while maintaining a $180^\circ$ angle between opposite edges. △ Less

Submitted 11 March, 2019; v1 submitted 31 August, 2017; originally announced August 2017.

Comments: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)