Browsing by study line "Algoritmer"

Improving the monitoring of health and well-being of dairy cows through the use of computer vision based systems is a topic of ongoing research. A reliable and low-cost method for identifying cow individuals would enable automatic detection of stress, sickness or injury, and the daily observation of the animals would be made easier. Neural networks have been used successfully in the identification of cow individuals, but methods are needed that do not require incessant annotation work to generate training datasets when there are changes within a group. Methods for person re-identification and tracking have been researched extensively, with the aim of generalizing beyond the training set. These methods have been found suitable also for re-identifying and tracking previously unseen dairy cows in video frames. In this thesis, a metric-learning based re-identification model pre-trained on an existing cow dataset is compared to a similar model that has been trained on new video data recorded at Luke Maaninka research farm in Spring 2021, which contains 24 individually labelled cow individuals. The models are evaluated in tracking context as appearance descriptors in Kalman filter based tracking algorithm. The test data is video footage from a separate enclosure in Maaninka and a group of 24 previously unseen cow individuals. In addition, a simple procedure is proposed for the automatic labeling of cow identities in images based on RFID data collected from cow ear tags and feeding stations, and the known feeding station locations.

This thesis presents a scalable method for identifying anomalous periods of non-activity in short periodic event sequences. The method is tested with real world point-of-sale (POS) data from grocery retail setting. However, the method can be applied also to other problem domains which produce similar sequential data. The proposed method models the underlying event sequence as a non-homogeneous Poisson process with a piecewise constant rate function. The rate function for the piecewise homogeneous Poisson process can be estimated with a change point detection algorithm that minimises a cost function consisting of the negative Poisson log-likelihood and a penalty term that is linear to the number of change points. The resulting model can be queried for anomalously long periods of time with no events, i.e., waiting times, by defining a threshold below which the waiting time observations are deemed anomalies. The first experimental part of the thesis focuses on model selection, i.e., in finding a penalty value that results in the change point detection algorithm detecting the true changes in the intensity of the arrivals of the events while not reacting to random fluctuations in the data. In the second experimental part the performance of the anomaly detection methodology is measured against stock-out data, which gives an approximate ground truth for the termination of a POS event sequence. The performance of the anomaly detector is found to be subpar in terms of precision and recall, i.e., the true positive rate and the positive predictive value. The number of false positives remains high even with small threshold values. This needs to be taken into account when considering applying the anomaly detection procedure in practice. Nevertheless, the methodology may have practical value in the retail setting, e.g., in guiding the store personnel where to focus their resources in ensuring the availability of the products.

The maximum constraint satisfaction problem (MaxCSP) is a combinatorial optimization problem in which the set of feasible solutions is expressed using decision variables and constraints on how the variables can be assigned. It can be used to represent a wide range of other combinatorial optimization problems. The maximum satisfiability problem (MaxSAT) is a restricted variant of the maximum constraint satisfaction problem with the additional restrictions that all variables must be Boolean variables, and all constraints must be logical Boolean formulas. Because of this, expressing problems using MaxSAT can be unintuitive. The known solving methods for the MaxSAT problem are more efficient than the known solving methods for MaxCSP. Therefore, it is desirable to express problems using MaxSAT. However, every MaxCSP instance that only has finite-domain variables can be encoded into an equivalent MaxSAT instance. Encoding a MaxCSP instance to a MaxSAT instance allows users to combine the strengths of both approaches by expressing problems using the more intuitive MaxCSPs but solving them using the more efficient MaxSAT solving methods. In this thesis, we overview three common MaxCSP to MaxSAT encodings, the sparse, log, and order encodings, that differ in how they encode an integer variable into a set of Boolean variables. We use correlation clustering as a practical example for comparing the encodings. We first represent correlation clustering problems using MaxCSPs, and then encode them into MaxSATs instances. State-of-the-art MaxSAT solvers are then used to solve the MaxSAT instances. We compare the encodings by measuring the time it takes to encode a MaxCSP instance into a MaxSAT instance and the time it takes to solve the MaxSAT instance. The scope of our experiments is too small to draw general conclusions but in our experiments, the log encoding was the best overall choice.

In independent component analysis the data is decomposed into its statistically independent components. In recent years, statistical models have been developed that solve a non-linear version of the independent component analysis. This thesis focuses on the estimation methods of a particular non-linear independent component analysis model called iVAE. It is shown on simulated data that the generative adversarial networks can significantly improve the iVAE model estimation compared with the previously used default iVAE estimation method. The improved model estimation might enable new applications for the iVAE model.

Air pollution is considered to be one of the biggest environmental risks to health, causing symptoms from headache to lung diseases, cardiovascular diseases and cancer. To improve awareness of pollutants, air quality needs to be measured more densely. Low-cost air quality sensors offer one solution to increase the number of air quality monitors. However, they suffer from low accuracy of measurements compared to professional-grade monitoring stations. This thesis applies machine learning techniques to calibrate the values of a low-cost air quality sensor against a reference monitoring station. The calibrated values are then compared to a reference station’s values to compute error after calibration. In the past, the evaluation phase has been carried out very lightly. A novel method of selecting data is presented in this thesis to ensure diverse conditions in training and evaluation data, that would yield a more realistic impression about the capabilities of a calibration model. To better understand the level of performance, selected calibration models were trained with data corresponding to different levels of air pollution and meteorological conditions. Regarding pollution level, using homogeneous training and evaluation data, the error of a calibration model was found to be even 85% lower than when using diverse training and evaluation pollution environment. Also, using diverse meteorological training data instead of more homogeneous data was shown to reduce the size of the error and provide stability on the behavior of calibration models.

K-mer counting is the process of building a histogram of all substrings of length k for an input string S. The problem itself is quite simple, but counting k-mers efficiently for a very large input string is a difficult task that has been researched extensively. In recent years the performance of k-mer counting algorithms have improved significantly, and there have been efforts to use graphics processing units (GPUs) in k-mer counting. The goal for this thesis was to design, implement and benchmark a GPU accelerated k-mer counting algorithm SNCGPU. The results showed that SNCGPU compares reasonably well to the Gerbil k-mer counting algorithm on a mid-range desktop computer, but does not utilize the resources of a high-end computing platform as efficiently. The implementation of SNCGPU is available as open-source software.

In this thesis, we discuss the Relative Lempel-Ziv (RLZ) lossless compression algorithm, our implementation of it, and the performance of RLZ in comparison to more traditional lossless compression programs such as gzip. Like the LZ77 compression algorithm, the RLZ algorithm compresses its input by parsing it into a series of phrases, which are then encoded as a position+length number pair describing the location of the phrase within the text. Unlike ordinary LZ77, where these pairs refer to earlier points in the same text and thus decompression must happen sequentially, in RLZ the pairs point to an external text called the dictionary. The benefit of this approach is faster random access to the original input given its compressed form: with RLZ, we can rapidly (in linear time with respect to the compressed length of the text) begin decompression from anywhere. With non-repetitive data, such as the text of a single book, website, or one version of a program's source code, RLZ tends to perform poorer than traditional compression methods, both in terms of compression ratio and in terms of runtime. However, with very similar or highly repetitive data, such as the entire version history of a Wikipedia article or many versions of a genome sequence assembly, RLZ can compress data better than gzip and approximately as well as xz. Dictionary selection requires care, though, as compression performance relies entirely on it.

Coupled empowerment maximization (CEM) is an action selection policy for artificial agents. It utilizes the empowerment values of different agents in order to determine the best possible action to take. Empowerment quantifies the potential an agent has to impact the world around it. For example, an agent in an open field has a higher empowerment compared to an agent that is locked in a cage as in an open field the agent has a higher freedom of movement. This kind of action selection policy does not rely on the agent behavior to be explicitly programmed which makes it particularly promising as a non-player character policy for procedurally generated video games. To research the feasibility of CEM agents in practice, they should be studied in a large variety of different situations and games. Some studies have already been performed with a CEM agent that is implemented in the Python programming language. The agent ran in small game environments built on top of the Griddly game engine, but the computational performance of the agent has not been the focus. Scaling the experiments to larger environments using the old implementation is not feasible as conducting the experiments would take an enormous amount of time. Thus, the focus in this thesis is on lowering the time complexity of the agent so that there are more avenues for further research. This is reached with a new CEM agent implementation that (1) has a more modular architecture making future changes easier, (2) simulates future game states with an improved forward model which keeps track of already visited game states, and (3) uses an optimized Griddly version which has improved environment cloning performance. Our approach is around 200 times faster compared to the old implementation using environments and parametrization that potentially are used in future quantitative and qualitative experiments. The old implementation also has some bugs that are now resolved in the new implementation.

In many real-world problems, the task is to find an optimal solution within a finite set of solutions. Many of the problems, also known as combinatorial optimization problems, are NPhard. In other words, finding an optimal solution for the problems is computationally difficult. However, being important for many real-world applications, there is a demand for efficient ways to solve the problems. One approach is the declarative approach, where the problems are first encoded into a mathematical constraint language. Then, the encoded problem instance is solved by an algorithm developed for that constraint language. In this thesis, we focus on declarative pseudo-Boolean optimization (PBO). PBO is the set of integer programs (IP) where the variables can only be assigned to 0 or 1. For many real-world applications, finding an optimal solution is too time-consuming. Instead of finding an optimal solution, incomplete methods attempt to find good enough solutions in a given time limit. To the best of our knowledge, there are not many incomplete algorithms developed specifically for PBO. In this thesis, we adapt an incomplete method developed for the maximum satisfiability problem to PBO. In the adapted algorithm, which we call LS-ORACLE-PBO, a given PBO instance is solved using a form of local search that utilizes a pseudo-Boolean decision oracle when moving from one solution to another. We implement and empirically compare LS-ORACLE-PBO to another recent incomplete PBO algorithm called LS-PBO. The results show that, in general, our implementation is not competitive against LS-PBO. However, for some problem instances, our implementation provides better results than LS-PBO.

Kielimallit ovat tilastollisia malleja, jotka ennustavat kuinka todennäköinen annettu jono sanoja on. Kielimallin tuottamasta jakaumasta on mahdollista arpoa sanoja, lauseita ja kokonaisia tekstejä. Viime aikoina kielimalleja on onnistuneesti käytetty taiteen, kuten tarinoiden, runojen ja musiikkikappaleiden generointiin. Tutkijat ovat kutsuneet kielimallien tuottamia tekstejä erinomaisiksi, mutta samalla niiden luovuutta on myös kyseenalaistettu. Tutkielmassa esittelen riittävän kriteeristön kielimallien luovuuden arviointiin. Kriteereiksi määrittelen teosten arvokkuus ja uutuus sekä kielimallin ennustamattomuus. Tutkin kriteerit täyttävän kielimallin luovia tekoja FACE-mallin avulla. Poissuljen sen mahdollisuuden, että kaikki luovat teot olisivat mallin kouluttajan tai lähdeaineston tai koulutusalgoritmin tekijöiden tekemiä. Lopputulokseni on, että kriteerit täyttävä kielimalli tekee useita luovia tekoja. Kriteerien toteutumisen mittaaminen voi olla käytännössä haastavaa, sillä kriteerien tarkka määrittely on tehtävä tapauskohtaisesti, eikä niiden mittaamiseen ole yhtä selkeää tapaa.