Browsing by study line "Algorithms"

NP-hard optimization problems can be found in various real-world settings such as scheduling, planning and data analysis. Coming up with algorithms that can efficiently solve these problems can save various rescources. Instead of developing problem domain specific algorithms we can encode a problem instance as an instance of maximum satisfiability (MaxSAT), which is an optimization extension of Boolean satisfiability (SAT). We can then solve instances resulting from this encoding using MaxSAT specific algorithms. This way we can solve instances in various different problem domains by focusing on developing algorithms to solve MaxSAT instances. Computing an optimal solution and proving optimality of the found solution can be time-consuming in real-world settings. Finding an optimal solution for problems in these settings is often not feasible. Instead we are only interested in finding a good quality solution fast. Incomplete solvers trade guaranteed optimality for better scalability. In this thesis, we study an incomplete solution approach for solving MaxSAT based on linear programming relaxation and rounding. Linear programming (LP) relaxation and rounding has been used for obtaining approximation algorithms on various NP-hard optimization problems. As such we are interested in investigating the effectiveness of this approach on MaxSAT. We describe multiple rounding heuristics that are empirically evaluated on random, crafted and industrial MaxSAT instances from yearly MaxSAT Evaluations. We compare rounding approaches against each other and to state-of-the-art incomplete solvers SATLike and Loandra. The LP relaxation based rounding approaches are not competitive in general against either SATLike or Loandra However, for some problem domains our approach manages to be competitive against SATLike and Loandra.

Judgment aggregation (JA) offers a generic formal framework for modeling various settings involving information aggregation by social choice mechanisms. For many judgment aggregation rules, computing collective judgments is computationally notoriously hard. The central outcome determination problem, in particular, is often complete for higher levels of the polynomial hierarchy. This complexity barrier makes it challenging to develop practical, generic algorithmic approaches to outcome determination. In this work, we develop practical algorithms for outcome determination by harnessing Boolean satisfiability (SAT) based solvers as the underlying reasoning engines, under a range of the most central JA rules. For the Kemeny, Slater, MaxHamming, Young, and Dodgson rules, we detail a direct approach based on maximum satisfiability (MaxSAT) solving, using propositional logic as a declarative language. For the Reversal scoring, Condorcet, Ranked agenda, and LexiMax rules, we develop iterative SAT-based algorithms, including algorithms based on the counterexample-guided abstraction refinement (CEGAR) paradigm. The procedures we develop for these settings make use of recent advances in incremental MaxSAT solving and preferential SAT-based reasoning. We provide an open-source implementation of the algorithms, and empirically evaluate them using both real-world and synthetic preference data. We compare the performance of our implementation to a recent approach which makes use of declarative solver technology for answer set programming (ASP). The results demonstrate that our SAT-based approaches scale significantly beyond the reach of the ASP-based algorithms for all of the judgment aggregation rules considered.

Building a Neural Language Model from scratch involves a big number of different design decisions. You need to decide, among other things, the network structure, input and output encodings, regularization methods and optimization algorithm. In addition, the number of options for each decision is constantly increasing due to new ones being invented. The trend when it comes to Neural Language Models is also to simply increase the number of parameters in the model in order to increase the performance of inference. With more and more parameters to learn, a growing amount of expensive hardware is needed to teach the models. A method called Knowledge Distillation can be used to start from an existing, already trained, Neural Language Model instead. The existing model is used as a teacher in a way that aligns the knowledge of the student model with it. We build a student Neural Language Model that uses multiple teacher models. In this scenario each teacher model is seen as an expert in a specific language. The student model is taught all the languages of the teacher models. In our experiment we use four existing language models, each specialized in a different language. We train the student model using Knowledge Distillations with some additional techniques which enable using multiple teachers. We use the XNLI benchmark to show that the student model is able to successfully learn all of the languages.

Atmospheric new-particle formation (NPF) plays a crucial role in generating climate-influencing aerosol particles. Direct observation of NPF is achievable by tracking the evolution of aerosol particle size distributions in the environment. Such analysis allows researchers to determine the occurrence of NPF on specific days. Currently, the most dependable method for categorizing days into NPF event (class Ia, class Ib, class II) or non-event categories relies on manual visual analysis. However, this manual process is labor-intensive and subjective, particularly with long- term data series. These issues underscore the need for an automated classification system to classify these days more objectively. This paper introduces feature-engineering based machine learning classifiers to discern NPF event and non-event days at the SMEAR II station in Hyytiälä, Finland. The classification utilizes a suite of informative features derived from the multi-modal log-normal distribution fitted to the aerosol particle concentration data and time series analysis at various scales. The proposed machine learning classifiers can achieve an accuracy of more than 90% in identifying NPF event and non-event days. Moreover, they are able to reach an accuracy of around 80% in further categorizing days into detailed subcategories including class Ia, class Ib, class II, and non-event. Notably, the machine learning classifiers reliably predict all event Ia days where particle growth and formation rates are confidently measurable. Moreover, a comparative analysis is conducted between feature-engineering machine learning methods and image-based deep learning in terms of time efficiency and overall performance. The conclusion drawn is that through reasonable feature engineering, machine learning methods can match or even surpass deep learning approaches, particularly in scenarios where time efficiency is paramount. The results of this study strongly support further investigation into this area to improve our knowledge and proficiency in automating New Particle Formation (NPF) event detection.

Understanding Machine Learning models’ behaviour is becoming increasingly important as models are growing in complexity. This thesis proposes a framework for validating machine learned signals using performance metrics and model explainability tools, applied to the context of Digital Humanities and Social Sciences. The framework allows for investigation whether the real-world problem that the model tries to represent is well-defined and whether the model accurately captures the phenomena at hand. Explainability techniques such as SHAP, LIME and Gradient-based methods have been used. These produce feature importance scores that the model bases its decisions on. The cases presented in this thesis are related to the research in Computational History and Historical Discourse Analysis with High Performance Computing. The subject of analysis is the large language model BERT fine-tuned on Eighteenth Century Collections Online (ECCO) documents that classifies books into genres. Investigating the performance of the classifier with precision-recall curves suggests that the class signals might be overlapping and not clearly delineated. Further results do not suggest that the noise elements present in the data caused by the OCR digitising process have significant importance for the decision making of the model. The explainability techniques helped uncover the model’s inner workings by showing that the model gets its signal mostly from the beginnings of samples. In a proxy task, a simpler linear model was trained to perform a projection from keywords to genres and showed inconsistency in the explainability method. Different subsets of data have been investigated as given by cells of a confusion matrix, the confidence in prediction probability or additional metadata. Investigating individual samples allows for qualitative analysis as well as more detailed signal understanding.

Artificial intelligence (AI) is being increasingly applied in the field of intelligent tutoring systems (ITS). Knowledge space theory (KST) aims to model the main features of the process of learning new skills. Two basic components of ITS are the domain model and the student model. The student model provides an estimation of the state of the student’s knowledge or proficiency, based on the student’s performance on exercises. The domain model provides a model of relations between the concepts/skills in the domain. To learn the student model from data, some ITSs use the Bayesian Knowledge Tracing (BKT) algorithm, which is based on hidden Markov models (HMM). This thesis investigates the applicability of KST to constructing these models. The contribution of the thesis is twofold. Firstly, we learn the student model by a modified BKT algorithm, which models forgetting of skills (which the standard BKT model does not do). We build one BKT model for each concept. However, rather than treating a single question as a step in the HMM, we treat an entire practice session as one step, on which the student receives a score between 0 and 1, which we assume to be normally distributed. Secondly, we propose algorithms to learn the “surmise” graph—the prerequisite relation between concepts—from “mastery data,” estimated by the student model. The mastery data tells us the knowledge state of a student on a given concept. The learned graph is a representation of the knowledge domain. We use the student model to track the advancement of students, and use the domain model to propose the optimal study plan for students based on their current proficiency and targets of study.

3D Object detection and tracking are computer vision methods used in many applications. It is necessary for autonomous vehicles and robots to be able to reliably extract 3D localization information about objects in their environment to operate safely. Currently most 3D object detection and tracking algorithms use high quality LiDAR-sensors which are very expensive. This is why research into methods that use cheap monocular camera images as inputs is an active field in computer vision research. Most current research into monocular 3D object detection and tracking is focused in autonomous driving. This thesis investigates how well current monocular methods are suited for use in industrial settings where the environment and especially the camera perspective can be very different compared to what it is in an automobile. This thesis introduces some of the most used 3D object detection and tracking methods and techniques and tests one detection method on a dataset where the environment and the point of view differs from what it would be in autonomous driving. This thesis also analyzes the technical requirements for a detection and tracking system that could be be used for autonomous robots in an industrial setting and what future research would be necessary to develop such a system.

Bayesian inference tells us how we can incorporate information from the data into the parameters. In practice, this can be carried out using Markov Chain Monte Carlo (MCMC) methods which draw approximate samples from the posterior distribution, but using them for complex models like neural networks remains challenging. The most commonly used methods in these cases are Stochastic Gradient Markov Chain Monte Carlo (SGMCMC) methods based on mini-batches. This thesis presents improvements for this family of algorithms. We focus on the specific algorithm of Stochastic Gradient Riemannian Langevin Dynamics (SGRLD). The core idea of it is to perform sampling on a suitably defined Riemannian manifold characterized by a Riemannain metric, which allows utilizing information of the curvature of the target distribution for improved efficiency. While SGRLD has nice theoretical properties, for arbitrary Riemannian geometries, the algorithm is slow due to the need of repeatedly calculating the inverse and inverse square root of the metric, which is high-dimensional for large neural networks. For the task of efficiently sampling from an arbitrary neural network with a large number of parameters, the current algorithms overcome the issue by using diagonal metrics, which enable fast computations, but unfortunately lose some advantages of the Riemannian formulation. This thesis proposes the first computationally efficient algorithms with non-diagonal metrics applicable for training an arbitrary large neural network for this task. We propose two alternative metrics, and name the resulting algorithms MongeSGLD and ShampooSGLD, respectively. We demonstrate that with both of them we can achieve improvements upon the existing ones in terms of convergence, especially when using neural networks with priors that result in good performances. We also propose to use the average curvature of the obtained samples as an evaluation measure.

Semantic segmentation is a computer vision problem of partitioning an image based on what type of an object each part represents, with pixel-level precision. Producing labeled datasets to train deep learning models for semantic segmentation can be laborious due to the demand for pixel-level precision. On the other hand, a deep learning model trained on one dataset might have inferior performance when applied on another dataset, depending on how different those datasets are. Unsupervised domain adaptation attempts to narrow this performance gap by adapting the model to the other dataset, even if ground-truth labels for that dataset are not available. In this work, we review some of the pre-existing methods for unsupervised domain adaptation in semantic segmentation. We then present our own efforts to develop novel methods for the problem. Those include a new type of loss function for unsupervised output shaping, unsupervised training of the model backbone based on the feature statistics and a method for unsupervised adaptation of the model backbone using an auxiliary network that attempts to mimic the gradients of supervised training. We present empirical results of the performance of these methods. We additionally present our findings on the effects of changes in the statistics of the batch normalization layers on domain adaptation performance.

Inverted indices is a core index structure for different low-level structures, like search engines and databases. It stores a mapping from terms, numbers etc. to list of location in document, set of documents, database, table etc. and allows efficient full-text searches on indexed structure. Mapping location in the inverted indicies is usually called a postings list. In real life applications, scale of the inverted indicies size can grow huge. Therefore efficient representation of it is needed, but at the same time, efficient queries must be supported. This thesis explores ways to represent postings lists efficiently, while allowing efficient nextGEQ queries on the set. Efficient nextGEQ queries is needed to implement inverted indicies. First we convert postings lists into one bitvector, which concatenates each postings list's characteristic bitvector. Then representing an integer set efficiently converts to representing this bitvector efficiently, which is expected to have long runs of 0s and 1s. Run-length encoding of bitvector have recently led to promising results. Therefore in this thesis we experiment two encoding methods (Top-k Hybrid coder, RLZ) that encode postings lists via run-length encodes of the bitvector. We also investigate another new bitvector compression method (Zombit-vector), which encodes bitvectors by finding redundancies of runs of 0/1s. We compare all encoding to current state-of-the-art Partitioned Elisa-Fano (PEF) coding. Compression results on all encodings were more efficient than the current state-of-the-art PEF encoding. Zombit-vector nextGEQ query results were slighty more efficient than PEF's, which make it more attractive with bitvectors that have long runs of 0s and 1s. More work is needed with Top-k Hybrid coder and RLZ, so that those encodings nextGEQ can be compared to Zombit-vector and PEF.