42337 research outputs found
Sort by
Stability and dynamics in particle swarms
No full textParticle Swarm Optimization (PSO) is a powerful technique used in computer science and engineering to solve complicated problems, drawing inspiration from the social behavior of fish and birds. This doctoral thesis explores the intricacies of PSO, analyzing the statistical properties of particle trajectories under different parameter combinations and their influence on the optimization procedure. The research starts by examining the movement patterns of particles during iterations, emphasizing the unique behaviors exhibited by the best-performing particle compared to the rest of the swarm. Expanding on this groundwork, the thesis presents an innovative modeling approach for PSO that integrates stochastic difference equations with multiplicative noise.
The study investigates also the significance of stability curves in the literature and explores the conditions that lead to the emergence of criticality and the practical implications of this criticality for optimization tasks. By combining theoretical analysis and empirical evidence, the thesis provides a novel critical curve representing the transition into a state of criticality in swarm behavior, providing insights into the convergence-divergence dilemma.
Additionally, the thesis presents a novel approach to measuring “co-diversity” within swarms by analyzing particle positions and velocities. This metric reveals new insights into swarm dynamics, specifically in terms of how diversity affects the search process and solution quality. In addition, this metric is used to measure the potential for innovation in finding the better solution, demonstrating its effectiveness in optimizing the PSO algorithm by reducing the number of fitness evaluations needed.
The research delves deeper into the parameter heterogeneity in improving PSO performance. The diversity not only enriches the algorithm’s adaptability and resilience to challenges but also underscores the importance of varied particle behaviors in achieving optimal outcomes. This thorough investigation greatly enhances our knowledge of PSO, providing innovative approaches for evaluating and leveraging diversity and heterogeneity in swarm-based optimization algorithms
Development of a viability-based assay to determine antibiotic treatment in urinary tract infections
No full textUrinary tract infections (UTIs) affect over 400 million people globally, with increasing
antimicrobial resistance (AMR) posing a significant healthcare challenge. Most
currently applied diagnostic methods require 48-72 hours for antibiotic susceptibility
testing (AST), leading to empirical antibiotic treatment that contributes to AMR
development. This thesis presents the development and optimisation of a rapid, paperbased colorimetric AST method for UTIs, focusing on trimethoprim resistance
detection. The study utilised resazurin, a metabolic indicator that changes from blue
to pink in the presence of viable bacteria, to create a point-of-care diagnostic platform.
Through systematic optimisation of multiple parameters, including resazurin
concentration (20 µmol/L), bacterial density (10⁶-10⁹ CFU/mL), and antibiotic preincubation time (30 minutes), we developed a reliable colorimetric assay that provides
results within 90 minutes. The optimised assay successfully differentiated between
trimethoprim-sensitive and resistant Escherichia coli isolates, demonstrating clear
colorimetric discrimination at bacterial concentrations as low as 10⁶ CFU/mL. The
assay's performance was validated against standard E-test methods, showing
complete concordance across eight clinical isolates. Notably, the successful
translation to a paper-based format using cellulose acetate filter paper maintained the
assay's discriminatory capabilities while providing a simple, portable readout system.
This work establishes a foundation for rapid, accessible AST in clinical settings,
particularly in resource-limited environments, potentially reducing the time to
appropriate antibiotic treatment from days to under two hours
DNA methylation and electronic health record prediction of incident type 2 diabetes
No full textType 2 diabetes mellitus (T2D) is a highly prevalent disease that presents a substantial burden, both to public health and cost to healthcare systems. Prediction of disease onset years in advance could help inform early intervention and preventative treatments. While standard risk factors have shown good predictive performance, there is increasing interest in incorporating molecular biomarkers and electronic health records (EHRs) in statistical machine learning models to improve the ability to predict future disease onset. This thesis explores the use of DNA methylation (DNAm) and EHR data in prediction models for incident T2D and explores a range of challenges related to using these data types. Moreover, the methods applied in these studies are disease agnostic, with potential application to other incident diseases of interest.
Firstly, the potential for blood-based DNAm data to augment 10-year T2D risk prediction beyond standard risk factors is investigated, utilising data from a large population cohort, Generation Scotland (GS) (Chapter 3).
This study incorporated DNAm and time-to-event information from 14,613 GS participants to train and test a range of statistical and machine learning models. The addition of DNAm data resulted in a significant improvement in predictive performance (AUC=0.872) compared to using standard risk factors only (AUC=0.839). A similar discrimination performance increase was observed in an external validation cohort, the German-based KORA study.
Secondly, the challenge of feature pre-selection in the development of predictive models using array-based DNAm data is explored (Chapter 4). Typically, penalised regression models are used with hundreds of thousands of CpG sites in this context. Feature pre-selection is an important step in this process as in such ultra-high dimensional data, the effectiveness of these models may be reduced. This study introduced Related Trait-based Feature Screening (RTFS), a method for utilising associations between CpG sites and health-related continuous traits to pre-select relevant CpG sites for incident disease prediction. This was compared with commonly-utilised pre-selection methods as well as dimensionality reduction with principal components analysis (PCA). RTFS was competitive with the highest performing method which incorporated CpG sites previously identified in incident T2D epigenome-wide association studies.
Finally, while the first two studies utilised DNAm, the final (Chapter 5) investigated the use of EHRs as predictors. With the increasing availability of EHRs for research and development purposes in recent years, there has been growing interest in utilising this data type for predictive modeling. However, a limited number of studies have focused on the transferability of the resulting models when applied to data generated within a different healthcare system or country. This study utilised a Finland-based cohort, FinnGen, to develop EHR-based risk prediction models for incident T2D and tested a set of feature engineering methods for improving model transferability. These were evaluated in two UK-based cohorts, GS and UK Biobank. Additionally, a large language model embedding-based imputation approach was assessed for addressing the challenge of missing codes in the data when transferring models to other cohorts.
Overall, this work explored a range of challenges in utilising DNAm and EHR data for incident T2D risk prediction and shows improvements in specific aspects key to model performance and generalisability such as CpG pre-selection and transferability of EHR-based models across healthcare systems. The thesis demonstrated that DNAm data can augment incident T2D risk prediction compared to risk factors used in current risk prediction tools and developed a method for pre-selecting relevant CpG sites to help address challenges of using such ultra high-dimensional data. Additionally, this work showed the potential for large language model-based representations of EHR codes to improve transferability of diagnosis code-based risk predictions scores
Life under Occupation in the Russo-Ukrainian War: Insights from Activist Networks
Full text linkThis research report draws on interviews with civic activists conducting evacuations from Russian occupied territories in Ukraine, as well as some evacuees, to shed light on the human rights abuses and totalitarian forms of governance that shape daily life in these territories. It utilises the concept of “civicness” as a form of public authority grounded in mutual obligation among individuals and groups, to highlight the strength of the societal resilience fostered by Ukraine’s “do-it-yourself” culture of active citizenship. In Russian occupied territories, these civic ties and relationships constitute a form of subversion to occupation, and a means of survival for those seeking escape from the threats to life and liberty that the Russian occupation entails.
At the time of writing, a US-brokered negotiation process has begun in the form of bilateral US-Ukraine and US-Russia talks, hosted by Saudi Arabia. In parallel to this process, Ukraine and European states have been engaged in a discussion about the design of post-conflict security guarantees. A plausible outcome of these developments is that Russia will remain in some form of de facto control of at least some of the territories it presently occupies. This makes testimony from humanitarian civic defenders, who run networks operating across both sides of the line of control, important to building a picture about the conditions Ukrainian citizens are facing on the ground, and the human rights monitoring and protection measures that should be included, as an absolute minimum, in any ceasefire agreement. The report makes a number of policy recommendations in this regard, including access for and guaranteeing the safety of independent human rights monitors, establishing freedom of movement across the lines of control, and the release of the thousands of arbitrarily detained captives of the regime
An analysis of greedy methods in integer programming: advancing theory and algorithms, and an application in market equilibrium
No full textGreedy algorithms, known for their simplicity, iteratively improve an objective function
through a sequence of locally optimal choices. Despite their heuristic nature,
they have been successfully applied to problems in scheduling, network design, and
resource allocation. This thesis explores the use of greedy algorithms in diverse settings,
analyzing their structure and developing advanced methods to enhance their
performance.
In integer programming, greedy algorithms operate on the integer lattice, selecting
solutions based on an ordered priority of coordinates. The first study introduces
a framework for constructing heuristic solutions using lexicographic orders, which
systematically prioritize certain coordinates over others. These methods generate
approximate integer solutions, forming an inner approximation of the optimal integer
solution. The study characterizes conditions underwhich these approximations
are tight by analyzing the convex hull of lexicographically ordered integer points.
For problems with a packing or covering structure, the computational complexity
of finding such solutions remains polynomial, whereas in general cases, the problem
is NP-hard. By integrating algebraic geometry with integer programming, this
work offers new insights into the structure of integer solutions.
Beyond inner approximations, the second study investigates outer approximations
of integer programming solutions using monotone sets. It explores whether relaxations
based on monomial orders yield strong dual bounds. While these bounds
are powerful in 0-1 integer programming, constructing them requires handling multiple
lexicographic orders, posing computational challenges. This study establishes
conditions under which these bounds are tight and presents efficient greedy algorithms
for certain structured problems, contributing to the understanding of packing and covering formulations.
The third study extends the analysis of greedy algorithms to randomized settings,
examining their performance in dynamic random graphs. A key application
is the maximum independent set problem, a fundamental combinatorial optimization
problem with a packing structure. Traditional studies focus on Erds–Rényi random
graphs, where greedy selection offers limited guarantees. This research instead
considers dynamically evolving random graphs, generated using a Markov process
that adjusts edge probabilities over time. By analysing asymptotic bounds on stability
numbers, it demonstrates that these graphs contain larger independent sets
compared to classical models, revealing the potential of dynamic structures in optimizing
network-related problems.
The final study focuses on the envy-free equilibrium pricing problem, where
a single seller must allocate multiple items to multiple buyers while maximizing
revenue. This problem is central to online marketplaces and cloud computing resource
allocation. The study explores the combinatorial complexity of envy-free
pricing, proving that under specific assumptions on buyer utility functions, an optimal
pricing scheme can be determined greedily. However, these assumptions are
often unrealistic. To address this, the study extends the classical Walrasian equilibrium
model by considering nonlinear utility functions and allowing sellers to delist
items. By analyzing the structure of optimal solutions, it proves that the problem
remains pseudo-polynomially solvable under certain conditions and introduces a
set of valid inequalities that significantly improve computational efficiency. These
findings have implications for both economic theory and practical market design.
Overall, this thesis provides a comprehensive study of greedy algorithms, examining
their potential and limitations across different applications. By developing
structured approximation techniques and analyzing their performance, this research
contributes to the broader understanding of optimization, integer programming,
and market design
Probing the interactions of meiotic spindle proteins revealed a new phospho-regulated interaction at microtubule plus ends
No full textThe establishment of correct kinetochore-microtubule attachments is a critical aspect of cell division, and one that is particularly error-prone in oocytes. Mutations of the sentin gene in Drosophila have been previously shown to lead to meiosis-specific errors in kinetochore-microtubule attachments in oocytes, but the mechanism by which Sentin promotes error correction has not been previously investigated. In this study, I identified the interactors of 10 Drosophila meiotic spindle proteins by immunoprecipitation followed by mass spectrometry. This revealed a previously uncharacterised direct interaction between the microtubule plus end-binding protein Sentin and the microtubule depolymerase Klp10A. Sentin protein is phosphorylated in a Polo kinase-dependent manner in ovaries, and the Sentin-Klp10A interaction was perturbed upon Polo kinase knockdown. Sentin’s N-terminus contains several predicted and in vivo phosphorylated phosphosites, which predominantly fit a Polo kinase consensus motif. Direct phosphorylation of Sentin by Plk1 furthermore promoted its interaction with Klp10A in vitro. Overall, this research identified a new phosphorylation-regulated protein-protein interaction occurring during meiosis I
Precise control of compilers: a practical approach to principled optimization
Full text linkProduction compilers remain constrained by rigid designs and inflexible optimization strategies that limit their adaptation to evolving hardware designs and application requirements. While academic research continues to produce innovative compilation techniques and intermediate representations that enable more flexibility and control over the compilation process, bridging the gap between these theoretical advances and practical implementation remains a significant challenge. The emergence of the MLIR compiler infrastructure, with its extensible dialect-based architecture, presents a unique opportunity to address two fundamental challenges in modern compiler design: how to integrate principled representations of programs and transformations into production compilers and how to provide users with meaningful control over optimization decisions. For the representation challenge, we first integrate Rise, a functional pattern-based intermediate representation, as an MLIR dialect to establish the foundation for systematic rewrite-based optimizations in a production-ready compiler infrastructure. We demonstrate the practical utility of this integration by leveraging Rise's pattern-based abstractions to compile a machine learning model.
While Rise's functional foundation provides natural guarantees about program properties during transformations, these are lost when integrating with MLIR's largely unconstrained rewriting system. Transformations do not guarantee the preservation of dialect-specific invariants or even the Static Single Assignment (SSA) form beyond dynamic checks. We present an approach for statically validating that a set of MLIR rewrites maintains these critical properties.
For the control challenge, we introduce two distinct approaches to transformation control. The Transform dialect, now part of upstream MLIR, encodes optimization sequences as an MLIR dialect. It exposes previously hidden compiler optimizations, enabling developers to express complex transformation strategies directly in MLIR's infrastructure and moving beyond rigid pass pipelines to provide precise control over which optimizations are applied to specific parts of the program.
To provide a principled foundation for composing complex optimization strategies, we adapt Elevate, a functional language for composing transformations, to the MLIR ecosystem. We extend Elevate with MLIR-specific constructs while making MLIR's IR immutable to enable both approaches to work in unison.
This adaptation enables compiler developers to express sophisticated optimization strategies simply by composing rewrite rules. We show how this approach scales to flexibly match computational structures, such as attention, in machine learning models.
By systematically addressing both representation and control challenges, we establish principled foundations for optimization while maintaining precise control, demonstrating how modern compiler infrastructures can evolve beyond rigid designs
without sacrificing practical applicability
Random projections for semidefinite programming and polynomial optimization with applications in adversarial machine learning
Full text linkRandom projection, a dimensionality reduction technique, has been found useful in recent years to reduce the size of optimization problems. In this thesis, we explore how to use random projections to approximate semidefinite programming (SDP) problems. We present a variable projection method for general SDP problems, a tailored method for polynomial optimization that also aggregates the constraints of the problem, and an application in adversarial machine learning. In the first chapter of this thesis, we explore the use of sparse sub-gaussian random projections to approximate SDP problems by reducing the size of matrix variables, thereby solving the original problem with much less computational effort. We present theoretical bounds on the error of the approximation obtained with the projection in terms of feasibility and optimality that explicitly depend on the sparsity parameter of the projector. We investigate the performance of the approach for semidefinite relaxations of nonconvex quadratically constrained quadratic problems (QCQP), the max-cut problem, and the maximum satisfiability problem (max-2-sat). Overall, our computational experiments show that semidefinite programming problems appearing as relaxations of combinatorial optimization problems can be approximately solved using random projections as long as the number of constraints is not too large. In the second chapter, we propose an algorithm to generate strong poisoning attacks for a ridge regression model containing both numerical and categorical features that explicitly models and poisons categorical features. We model categorical features as special ordered sets of type 1 (SOS1) and formulate the problem of designing poisoning attacks as a bilevel optimization problem that is nonconvex mixed-integer in the upper level and unconstrained convex quadratic in the lower level. We present a mathematical formulation of the problem, introduce a single-level reformulation based on the Karush-Kuhn-Tucker (KKT) conditions of the lower level, find bounds for the lower-level variables to accelerate solver performance, and propose a new algorithm to poison categorical features. Numerical experiments show that our method improves the mean squared error of all datasets compared to the previous benchmark in the literature. In the last chapter, we explore how to apply random projections to relaxations appearing in polynomial optimization (PO). We use this as a tool to obtain upper bounds for the poisoning attack problem from the second chapter and certify the quality of the solution. Following this, we present a tailored random projection method for the sum-of-squares SDP relaxation of polynomial optimization problems, where both the variable size and the constraint number are reduced. We provide new theoretical guarantees and propose a method to retrieve a feasible solution from this combined projection. We then present computational experiments for two PO problems: the optimization over the unit sphere and the stable set problem. For these problems, we can approximate the SDP problem using all three methods as long as the projected dimension is large enough. The last part of the chapter introduces an application of the methodology to bilevel polynomial optimization. We conclude by applying random projections to obtain bounds for the poisoning attack application from the second chapter. We apply the method for a modified version of the SDP problem, for which the constraint aggregation method returns an almost optimal solution in less computational time
Sampling in lattice field theory with flow-based generative models
Full text linkQuantum field theories can be non-perturbatively regularised by discretising the fields on a space-time lattice, and in many cases one can define a corresponding Euclidean theory with real, positive-definite path integral measure by rotating to imaginary time. The path integrals of these lattice field theories may be interpreted as statistical ensembles and sampled from using Markov Chain Monte Carlo (MCMC) techniques. This establishes a rigorous procedure for extracting quantitative predictions from first-principles simulations of Quantum Chromodynamics (QCD), which for the most part is intractable to perturbative methods. In recent years Lattice QCD has played an increasingly central role in precision tests of Standard Model physics. Predicting properties of the continuum theory from the discretised theory requires a systematic extrapolation in which physical scales are held fixed while the lattice spacing is reduced. This continuum limit extrapolation drives the simulated system towards a critical point. Unfortunately this leads to a critical slowing down of the sampling dynamics, characterised by an extreme scaling of autocorrelation times with the inverse lattice spacing. Despite some decades of progress in the field, the exploding sampling costs incurred due to critical slowing down remains a serious barrier to simulating QCD on the large volumes and fine lattices that are needed to resolve many fundamental processes.
One proposal (circa 2009) was to introduce an auxiliary simulation into each Monte Carlo step in which the field variables flow towards the strong coupling limit where sampling is more efficient. These 'trivialising' flows are invertible transformations on the field space whose Jacobian determinant exactly cancels the interaction terms in the path integral, providing a representation of the theory in terms of a deterministic transformation of a trivial theory whose degrees of freedom are decoupled. While the original semi-analytical approach did not prove advantageous in practice due to the low-order approximate construction of the flows and the additional computational overhead, the underlying idea is rather tantalising. Recently (circa 2019) this thread has been picked up once more, drawing on rapid advances in Machine Learning, and specifically so-called generative models. The central idea is that invertible field transformations can be performed by a suitably constrained neural network model with a large number of adjustable parameters. The intractable task of constructing a trivialising flow is instead cast as a variational problem on the function space of the model, to be tackled by stochastic optimisation algorithms. Asymptotically exact sampling from the theory of interest is possible through a simple reweighting procedure involving the Jacobian determinant of the model. Furthermore, these models are able to 'self-train' by evaluating the action of the target theory on model-generated field configurations, circumventing the need for a separate process to provide training data. Flow-based algorithms have the potential to become more efficient than traditional MCMC provided the combined costs of training and any additional sampling overheads are offset by a reduction in autocorrelation times in realistic simulations. While the majority of studies to date have focused on developing architectures that are specialised for lattice field theory applications and testing them on small scales, attention is now turning to the question of scalability.
This thesis develops and explores a number of flow-based generative models for lattice field theory applications. We start from the very beginning, testing the efficacy of the flow-based approach for sampling from scalar field theories, where we quickly discover that unspecialised models lifted from the Machine Learning literature do not work well 'out of the box'. We then turn to field theories whose variables take values on compact manifolds and which crucially possess non-trivial topological properties that make them more suitable proxies for full QCD. On the algorithmic side we focus on two distinct but closely related approaches. The first is based on reweighting samples drawn directly from the generative model, which amounts to passing uncorrelated noise through the inverse of an approximate trivialising flow. The second embeds the flow model in a Hybrid Monte Carlo algorithm in a manner that is analogous to the original formulation of trivialising flows. Flow-based sampling in lattice field theory is a young, fast moving sub-field and consequently the work presented in thesis is of an exploratory nature. The presentation is intentionally pedagogical, with considerable time devoted to gaining clarity and intuition through the study of simple models
Community engagement in conservation and participatory management of cultural heritage sites along the coast of Kenya
No full textThis study aimed to investigate the role of community engagement in the conservation
and participatory management of cultural heritage sites along Kenya's coast. It focused
on four objectives: assessing the impact of development projects on coastal cultural
heritage sites, exploring the integration of community engagement into the
conservation and management of these sites, examining how participatory management
can contribute to sustainable development while safeguarding cultural heritage, and
identifying challenges faced by local communities in engaging with heritage
management authorities.
The study drew on Arnstein’s Ladder of Participation, grounded in Decolonial Heritage
Practice as theoretical framework to elucidate varying levels of community
engagement and the necessity of empowering individuals for meaningful participation.
Data collection involved individual interviews, key informant interviews, and focus
group discussions. Participants were selected from four heritage sites, namely Lamu
Old Town World Heritage Site (LOT), The Historic Town and Archaeological Site of
Gedi (Gedi), Mtwapa Heritage Site (MHS) and Kilepwa Heritage Site (KHS) and eight
focus group discussions were conducted, each comprising of between 7 to 10
respondents’representing men, women, the elderly and youths. In-depth interviews of
16 key informants drawn from the National Museums of Kenya, Kenya –Unesco Focal
Point Representative, Fishermen representative, County government representatives,
Beach Management Unit, Village elders, former National Museums of Kenya Site
Managers, Business personnel, was conducted. The qualitative data was analyzed
thematically and presented using verbatim quotes where appropriate, amplifying the
voices of individual respondents, informants, and focus group participants.
Findings revealed that heritage sites are primarily managed by NMK, with some sites,
like Gedi, involving community members who benefit from their engagement.
However, other sites face threats from infrastructural development or lack proper
frameworks for community involvement. The study highlighted the potential for comanagement
to benefit both local communities and heritage sites.
In conclusion, the research emphasized the critical role of communities in heritage
protection, noting that their participation is key to addressing conservation challenges.
It recommended the establishment of joint advisory committees to enhance community
engagement and called for a reconsideration of the dichotomy between cultural and
natural heritage sites to foster inclusive conservation approaches
Access Repository Dashboard
Do you manage Edinburgh Research Archive? Access insider analytics, issue reports and manage access to outputs from your repository in the CORE Repository Dashboard!