Methods for Efficient, Exact Combinatorial Computation in Machine Learning - Doctor of Philosophy thesis

Aug 3, 2026

Upload by Anda

Combinatorial problems arise frequently in machine learning, yet they often involve large-scale optimization with exponential or factorial complexity, making exhaustive search impractical. Heuristic methods may yield usable solutions quickly, but they are not guaranteed to be optimal. Dynamic programming offers efficient, broadly applicable exact solutions, though related algorithms are commonly developed in an ad-hoc manner. This thesis presents a rigorous algebraic approach that systematically derives exact DP algorithms from functional recurrences or existing ones. The resulting methods are provably correct and polymorphic over any semiring.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages120

Reading Time5 h 2 min

AccessFree to download

Introduction

Motivation

Contributions

Thesis Structure

Background

Related Work

Machine Learning

Mathematical Optimization

Concepts in Computational Complexity

Combinatorial Machine Learning (ML) Problems

Abstract algebra: monoids, groups and semirings

Dynamic programming (DP) and Directed Acyclic Computation Graphs (DAG)

Methods and Techniques

Preliminaries

A Generalized Bellman’s Recursion

Embedding a Constraint

Tupling semirings to avoid backtracking

Applications

Segmented Linear Regression

Sequence Alignment

Clustering

Methods for Efficient, Exact Combinatorial Computation in Machine Learning by Ugur Kayas A thesis submitted to the University of Birmingham for the degree of DOCTOR OF PHILOSOPHY School of Computer Science College of Engineering and Physical Sciences University of Birmingham July 2022 University of Birmingham Research Archive e-theses repository This unpublished thesis/dissertation is copyright of the author and/or third parties. The intellectual property rights of the author or third parties in respect of this work are as defined by The Copyright Designs and Patents Act 1988 or as modified by any successor legislation. Any use made of information contained in this thesis/dissertation must be in accordance with that legislation and must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the permission of the copyright holder. Abstract Combinatorial problems are common in machine learning, but they are often large-scale, exponential or factorial complexity optimization problems, for which exhaustive methods are impractical. Heuristics are typically used instead but these are not provably optimal, although they may produce a workable compromise solution in a reasonable time. On the other hand, dynamic programming (DP) is an efficient and broadly applicable tool that finds exact solutions to combinatorial problems. However, DP lacks systematicity as most algorithms are derived in an ad-hoc, problem-specific manner. In the literature, there are attempts to standardize DP algorithms, but they are either unnecessarily general (constructive algorithmics) or have limited applications to different problems (Emoto’s GTA) . In this thesis, we propose a rigorous algebraic approach that systematically solves DP problems either by deriving algorithms from existing ones, or by deriving them from simple functional recurrences. The main contribution is providing novel, exact solutions for combinatorial optimization problems in machine learning and artificial intelligence. Our novel formalism largely bypasses the need to invoke the often quite high level of abstraction present in classical constructive algorithmics, as well as providing algorithms that are provably correct and polymorphic over any semiring. These algorithms can be applied to any combinatorial problem expressible in terms of semirings as a consequence of polymorphism. This approach also contributes to systematicity in embedding combinatorial constraints applying tupling to avoid the need for ad-hoc backtracking. Acknowledgment During my PhD, I have been extremely lucky with the people I have stumbled upon. I would like to thank Dr Max A. Little firstly for accepting me as his PhD student; and then for all the support, and guidance that he has given me throughout my PhD journey. I also could not have undertaken this journey without the academic support and great friendship of Dr Yordan Raykov. Of course this journey would not have been possible without the generous funding provided by the Ministry of National Education/Turkiye. Apparently the Turkish tax payer made a good investment. I have also been blessed with meeting some truly kind and supportive friends. First of all, I would like to thank Adele for being my English advisor, for all the walks that we had together and for making me feel like I am the best chef in the world (as indicated by me never having any food left) . Meeting with Ellen was also a great pleasure and thank you Ellen for checking the reference list of this thesis (so you know who to blame if you spot a mistake) . I also need to mention Dorine for being an amazing flatmate and for teaching me how to clean the right way. Reham was an amazing mentor, she provided me with exceptional support throughout my first year (then she disappeared suddenly) . It would be rude of me not to mention that I am so thankful for Yazan, Adam and Hakan (although none of them thanked me in their t

FAQs

Why are exhaustive methods often impractical for combinatorial machine learning problems?

They typically have large-scale optimization objectives with exponential or factorial complexity, so exhaustive search becomes too costly. As a result, heuristics are commonly used instead.

What limitation of dynamic programming does the thesis address?

Dynamic programming can find exact solutions efficiently, but many DP algorithms lack systematic construction because they are usually derived in an ad-hoc, problem-specific way.

How does the proposed algebraic approach ensure correctness and generality?

It derives a rigorous algebraic formulation that produces provably correct algorithms. The algorithms are polymorphic over any semiring and apply to combinatorial problems expressible in semiring terms.

Aug 3, 2026

Upload by Anda