Browsar Examensarbeten för masterexamen // Master Theses efter Program "Engineering mathematics and computational science (MPENM), MSc"
Visar 1 - 9 av 9
Sökresultat per sida
- PostDeep Learning in State of the Art Airline Crew Rostering Algorithms(2022) Nillius, Jonathan; Chalmers tekniska högskola / Institutionen för data och informationsteknik; Dubhashi, Devdatt; Brown-Cohen, JonahWhen distributing work among employees in Airline crew planning a problem called the crew rostering problem is formed. It is a combinatorial optimization problem and solving large problem instances commonly utilize column generation. This thesis investigates utilizing machine learning predictions instead of reduced costs in the pricing problem. The machine learning model predicts how likely it is that a task is assigned a crew in a supervised learning fashion, by being trained on historical planning problems. The aim is to then utilize the model to improve computational speed in solving future problems. This thesis presents results suggesting that it is conceptually possible to improve computational time of state of the art crew rostering algorithms with accurate predictions. Training a deep learning model able to make such accurate predictions is found to be very difficult given the techniques and data experimented with. Thus the thesis concludes that further research for improving this concept is needed in two main directions, feature extraction and model techniques
- PostDetecting Metastable States in Proteins using E(3) Equivariant VAMPnets(2023) Arnesen , Sara; Nordström, David; Chalmers tekniska högskola / Institutionen för data och informationsteknik; Chalmers University of Technology / Department of Computer Science and Engineering; Dubhashi, Devdatt; Olsson, SimonAs proteins fold, they encounter intermediary conformations, often denoted metastable states, that are vital to deciphering diseases related to malfunctions in conformational changes. To detect these metastable states, a deep learning framework using the variational approach for Markov processes (VAMP) has been proposed, dubbed VAMPnets. In this master’s thesis, we improve the training of VAMPnets through the use of E(3) equivariant neural networks. These networks incorporate the symmetries of Euclidean space, facilitating faster and more data-efficient learning. To study the effectiveness of these networks, we benchmark two different equivariant Transformer architectures and an equivariant convolutional network against both a simple and an invariant multilayered perceptron. The models are evaluated on molecular dynamics trajectories of alanine dipeptide and protein folding datasets. The use of E(3) equivariant neural networks in training VAMPnets is shown to significantly improve the prediction accuracy on random downsampled data. Using only 1% of the dataset, the equivariant Transformer achieves almost twice the VAMP-2 score as the benchmarks. Furthermore, the model exhibits improved robustness. With only 20% data remaining, the model scores on par with the complete dataset. On average, the model requires significantly fewer backward passes, converging more than twice as fast as the benchmark models, showing enhanced data efficiency. Furthermore, the results highlight the significant computational burden that equivariant neural networks pose, especially for larger molecules, proving almost 1,000 times slower on the protein folding dataset. Finally, we propose a novel algorithm for detecting the number of metastable states of a molecule using the VAMP-2 score and provide estimates for the 12 proteins in the protein folding dataset.
- PostEnergy-Efficient Navigation of Electric Vehicles using Gaussian Processes(2023) Sandberg, Jack; Chalmers tekniska högskola / Institutionen för data och informationsteknik; Chalmers University of Technology / Department of Computer Science and Engineering; Dubhashi, Devdatt; Haghir Chehreghani, MortezaNavigation software that prioritizes energy efficiency could, through simple means, help extend the effective range and adoption rate of electric vehicles (EV). This thesis extends a previously studied online learning framework using Bayesian inference to find energy-efficient routes. In the extended framework, the characteristics of the road segments are combined with observed energy consumption data to provide probabilistic energy consumption estimates using Gaussian processes (GP). The GP uses a graph Matérn kernel extended from  and a feature kernel to model the correlation of energy consumption on separate road segments. The framework is applied to a simple synthetic road network and real-world road networks in the traffic simulator SUMO. The results demonstrate that the GP learns more efficiently in the networks considered than in the Bayesian inference method. Furthermore, we investigate how the GP method is impacted by the number of inducing points, heteroskedastic noise modeling, an informative prior, and the choice of bandit algorithm.
- PostEvaluating the in-the-middle algorithm on max-sum problems(2015) Sigurdhsson, Simon; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)The fields of graphical modelling and constraint satisfaction have been very active in recent years, which is unsurprising given the large range of problems which may be described using such techniques. While many novel algorithms have been presented, there are still areas of the field in which improvements are possible. Reviews have uncovered strong links between the linear programming and graphical modelling fields, and it is therefore of interest to survey the possible application of linear programming methods to graphical models and constraint satisfaction problems. The in-the-middle algorithm, an approximate solution method in linear programming which has seen extensive use in the industry, was extended to max-sum problems by Grohe and Wedelin (2008). Graphical models and constraint satisfaction problems are easily translated into max-sum formulations, and the in-the-middle algorithm is therefore an ideal candidate in reformulating linear programming algorithms to the field of constraint satisfaction. This thesis presents an implementation of the in-the-middle algorithm applied to max-sum problems, which may be applied to general constraint satisfaction instances. The implementation is benchmarked against three existing high-performance exact solvers in the field, using a problem set consisting of several hundred problems. Results indicate that the in-the-middle algorithm may have potential in the fields of constraint satisfaction and graphical model optimization, but that further research is required to make the algorithm competitive. Several avenues for further research on the algorithm are proposed.
- PostEvaluation of Normalization Methods for Metagenomic Data(2016) Wallroth, Mikael; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
- PostLarge-Scale Content Extraction from Heterogeneous Sources(2015) Langkilde, Daniel; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)In this thesis report we describe a novel approach to large scale content extraction from heterogenous web sources. This task is a very important step in a range of web crawling, indexing and data mining tasks. The described approach makes calculations on the Document Object Model (DOM) in order to uncover which nodes contain relevant content, and which do not. We set out with the hypothesis that the DOM tree can be modeled as a hidden Markov tree model where the hidden state of each node indicates if its relevant content or not. Using Gibbs samling we uncover the hidden states of the node, and show that competative performance can be achieved using this approach.
- PostProbabilistic Modelling of Sensors in Autonomous Vehicles Autoregressive Input/Output Hidden Markov Models for Time Series Analysis(2017) Listo Zec, Edvin; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)Testing the quality of sensors in autonomous vehicles is crucial for safety verification. This is usually done by collecting a lot of data in many different settings. However, this can be very time consuming and expensive. Therefore, one is interested in virtual verification methods that simulate these situations, so many scenarios can be tested in parallel without actual hazards. In this thesis a generative model is created for the longitudinal errors in the sensors and an extension to the hidden Markov model, called autoregressive input/output hidden Markov model (AIOHMM) is implemented. In this extension the transition probabilities are conditioned on an input vector and the emissions are conditioned with the emissions at previous time steps, making it better suited for modelling long-term dependencies. We show that conditioning on the previous error is not enough to capture the behaviour of the errors, and that conditioning the transitions on an input is an important aspect of the model.
- PostUnsupervised Disambiguation of Abstract(2018) Kalldal, Oscar; Ludvigsson, Maximilian; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)Disambiguating natural text is the task of choosing the correct meaning among several possible interpretations. This thesis focus on disambiguating parse trees created by Grammatical Framework — a formal language that represent meaning of natural language sentences with abstract syntax trees in order to do machine translation. Since one tree represents a meaning, for every sentence there exists several interpretations for which the most probable one should be chosen. In order to achieve this, a language model on trees is defined. This is then used to compare possible trees and choose the one with the highest probability. In order to estimate the parameters of the model, the probability of the different meanings behind a word needs to be estimated. This is done using the Expectation Maximization algorithm. Experiments are done on seven different languages to show that the method is generalizable. Different smoothing techniques as well as different dictionaries are evaluated. A novel merged Wordnet is constructed in order to avoid sparseness. The method is evaluated by doing word sense disambiguation (a subtask of tree disambiguation) on standard data sets. The model is shown to be comparable to other unsupervised methods in the SemEval 2015.
- PostWTTE-RNN : Weibull Time To Event Recurrent Neural Network A model for sequential prediction of time-to-event in the case of discrete or continuous censored data, recurrent events or time-varying covariates(2017) Martinsson, Egil; Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers); Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)In this thesis we propose a new model for predicting time to events: the Weibull Time To Event RNN. This is a simple framework for time-series prediction of the time to the next event applicable when we have any or all of the problems of continuous or discrete time, right censoring, recurrent events, temporal patterns, time varying covariates or time series of varying lengths. All these problems are frequently encountered in customer churn, remaining useful life, failure, spike-train and event prediction. The proposed model estimates the distribution of time to the next event as having a discrete or continuous Weibull distribution with parameters being the output of a recurrent neural network. The model is trained using a special objective function (log-likelihood-loss for censored data) commonly used in survival analysis. The Weibull distribution is simple enough to avoid sparsity and can easily be regularized to avoid overfitting but is still expressive enough to encode concepts like increasing, stationary or decreasing risk and can converge to a point-estimate if allowed. The predicted Weibull-parameters can be used to predict expected value and quantiles of the time to the next event. It also leads to a natural 2d-embedding of future risk which can be used for monitoring and exploratory analysis. We describe the WTTE-RNN using a general framework for censored data which can easily be extended with other distributions and adapted for multivariate prediction. We show that the common Proportional Hazards model and the Weibull Accelerated Failure time model are special cases of the WTTE-RNN. The proposed model is evaluated on simulated data with varying degrees of censoring and temporal resolution. We compared it to binary fixed window forecast models and naive ways of handling censored data. The model outperforms naive methods and is found to have many advantages and comparable performance to binary fixed-window RNNs without the need to specify window size and the ability to train on more data. Application to the CMAPSS-dataset for PHM-run-to-failure of simulated Jet-Engines gives promising results.