Browsing by study line "Algorithms"

This thesis explores predicting current prices of individual agricultural fields in Finland based on historical data. The task is to predict field prices accurately with the data we have available while keeping model predictions interpretable and well explainable. The research question is to find which out of several different models we try out is most optimal for the task. The motivation behind this research is the growing agricultural land market and the lack of publicly available field valuation services that can assist market participants to determine and identify reasonable asking prices. Previous studies on the topic have used standard statistics to establish relevant factors that affect field prices. Rather than creating a model whose predictions can be used on their own in every case, the primary purpose of previous works has indeed been to identify information that should be considered in manual field valuation. We, on the other hand, focus on the predictive ability of models that do not require any manual labor. Our modelling approaches focus mainly but not exclusively on algorithms based on Markov–Chain Monte Carlo. We create a nearest neighbors model and four hierarchical linear models of varying complexity. Performance comparisons lead us to recommend a nearest neighbor -type model for this task.

There are many computationally difficult problems where the task is to find a solution with the lowest cost possible that fulfills a given set of constraints. Such problems are often NP-hard and are encountered in a variety of real-world problem domains, including planning and scheduling. NP-hard problems are often solved using a declarative approach by encoding the problem into a declarative constraint language and solving the encoding using a generic algorithm for that language. In this thesis we focus on pseudo-Boolean optimization (PBO), a special class of integer programs (IP) that only contain variables that admit the values 0 and 1. We propose a novel approach to PBO that is based on the implicit hitting set (IHS) paradigm, which uses two separate components. An IP solver is used to find an optimal solution under an incomplete set of constraints. A pseudo-Boolean satisfiability solver is used to either validate the feasibility of the solution or to extract more constraints to the integer program. The IHS-based PBO algorithm iteratively invokes the two algorithms until an optimal solution to a given PBO instance is found. In this thesis we lay out the IHS-based PBO solving approach in detail. We implement the algorithm as the PBO-IHS solver by making use of recent advances in reasoning techniques for pseudo-Boolean constraints. Through extensive empirical evaluation we show that our PBO-IHS solver outperforms other available specialized PBO solvers and has complementary performance compared to classical integer programming techniques.

The so-called declarative approach has proven to be a viable paradigm for solving various real-world NP-hard optimization problems in practice. In the declarative approach, the problem at hand is encoded using a mathematical constraint language, and an algorithm for the specific language is employed to obtain optimal solutions to an instance of the problem. One of the most viable declarative optimization paradigms of the last years is maximum satisfiability (MaxSAT) with propositional logic as the constraint language. So-called core-guided MaxSAT algorithms are arguably one of the most effective MaxSAT-solving paradigms in practice today. Core-guided algorithms iteratively detect and rule out (relax) sources of inconsistencies (so-called unsatisfiable cores) in the instance being solved. Especially effective are recent algorithmic variants of the core-guided approach which employ so-called soft cardinality constraints for ruling out inconsistencies. In this thesis, we present a structure-sharing technique for the cardinality-based core relaxation steps performed by core-guided MaxSAT solvers. The technique aims at reducing the inherent growth in the size of the propositional formula resulting from the core relaxation steps. Additionally, it enables more efficient reasoning over the relationships between different cores. We empirically evaluate the proposed technique on two different core-guided algorithms and provide open-source implementations of our solvers employing the technique. Our results show that the proposed structure-sharing can improve the performance of the algorithms both in theory and in practice.

The problem of safety in a general graph is the problem of finding walks in the graph that are subwalks of a walk in any possible solution within a given model (Tomescu and Medvedev, 2017). The problem of safety has proven to be a valuable problem for bioinformatics in the context of genome assembly and other assembly problems. When working with perfect data, safe walks in a graph correspond to correct sequences of the genome. When working with real (erroneous) data, safe walks correspond to close to correct sequences, where the errors correspond only to errors already in the data. Safety has previously been considered in two different models: in a model where the graph holds only the information of graph topology, and in a model where the graph holds the information of graph topology and network flow. Subpath constraints are paths in a graph that restrict the solution set. Restricting a solution set increases the lengths of safe walks, so using a model that holds the information of subpath constraints is advantageous. However, subpath constraints have never been considered with the problem of safety. In this work, we introduce subwalk constraints, which are subpath constraints that can have cycles and are not limited to directed acyclic graphs (DAGs). Then, we present a new model, where the graph holds the information of graph topology, network flow and subwalk constraints. In the new model, we present three methodologies to compute safe walks that become possible because of subwalk constraints. Then, we present an algorithm that computes safe walks in polynomial time in the new model utilizing the three new methodologies. Due to the new model, all safe walks produced by other algorithms are subwalks of the safe walks generated by our new algorithm

Compression methods are widely used in modern computing. With the amount of data stored and transferred by database systems constantly increasing, the implementation of compression methods into database systems has been studied from different angles during the past four decades. This thesis studies the scientific methods used in relational database research. The goal of the thesis is to evaluate the methods employed and to gain an understanding into how research into the subject should be conducted. A literature review is conducted. 14 papers are identified for review and their methodology is described and analysed. The papers reviewed are used to answer four research question and classified according to insights gained during the review process. There are similarities in methods of different papers that can be described to use as a starting point for conducting research in the field of database compression.

Foundation models have the potential to reduce the level of supervision required for medical image segmentation tasks. Currently, the medical image segmentation field still largely relies on supervised, task specific models. The aim of this thesis is to investigate if a foundation model, the Segment Anything Model (SAM), can be used to reduce the level of supervision needed for medical image segmentation. The main goal of this thesis is to see if the annotation workload required to generate labeled medical segmentation datasets can be significantly reduced with the help of Segment Anything Model. The second goal of this thesis is to validate the zero-shot performance of the Segment Anything Model on a medical segmentation dataset. A UNet model is used as a baseline. The results of this thesis give positive feedback on SAM's ability to be used as a tool for medical image annotation. During the experiments, it was found that especially for homogeneous, clearly outlined tasks, like organs, using ''pseudo labels'' generated by SAM for training a UNet model resulted in comparable accuracy with training a UNet model on human-annotated labels. Furthermore, the results show that zero-shot SAM has somewhat comparable performance to UNet, and even beats UNet in two of the experimented tasks. For one complexly structured task, SAM and UNet with pseudo labels, trained using SAM's masks, fail to produce accurate results. It is notable that some of the tasks have small training dataset sizes, which limits the test accuracy of UNet. The results are in accordance with recent literature which shows that zero-shot SAM can have comparable performance to state-of-the-art models with large and distinct objects, but when it comes to small, complex structures, SAM is not up to par accuracy-wise to the state-of-the-art medical segmentation models.

This thesis is an integral part of an interdisciplinary research endeavor that provides computer science-driven approaches and deep learning methodologies that seamlessly integrate into the broader research conducted by scholars in the field of digital humanities and historians. Utilizing deep learning techniques, this research investigates the printers and publishers of 18th-century books, with a specific focus on the prominent family-based printing dynasty called Tonson. By identifying common visual elements, the thesis facilitates a comparative analysis of associations between different printers, providing valuable insights into the historical context and artistic characteristics of the Tonson dynasty. The thesis begins by discussing various deep learning models trained on an expert-annotated dataset, enabling the extraction of five main categories and sixteen subcategories of visual elements. Notably, the MaskRCNN model demonstrates superior performance, particularly in detecting headpieces and initials. The study then delves into the grouping of initials and headpieces within the dataset. The Sim CLR model is employed using data augmentation techniques that simulate the inherent noise present in the dataset. This enables the generation of distinct embeddings for each initial and headpiece. Various unsupervised learning methods are applied, with Hierarchical Clustering emerging as the most effective technique. Higher similarity scores for headpieces compared to initials indicate greater ease in identifying similar headpieces. We further discuss the potential applications from a historical perspective including book pricing, future avenues for accurately identifying related printers, and temporal research concerning the Tonson dynasty. In conclusion, this thesis presents a novel integration of computer science and deep learning methodologies within the field of digital humanities and historical studies. By focusing on the Tonson dynasty, it provides a comprehensive analysis of printers and publishers in 18th-century books, ultimately contributing to a deeper understanding of this historical period.