No description available.

This dissertation presents novel approaches to test context aware applications that suffer from a cost prohibitive number of context and GUI events and event combinations. The contributions of this work to test context aware applications under test include: (1) a real-world context events dataset from 82 Android users over a 30-day period, (2) applications of Markov models, Closed Sequential Pattern Mining (CloSPAN), Deep Neural Networks- Long Short Term Memory (LSTM) and Gated Recurrent Units (GRU), and Conditional Random Fields (CRF) applied to predict context patterns, (3) data driven test case generation techniques that insert events at the beginning of each test case in a round-robin manner, iterate through multiple context events at the beginning of each test case in a round-robin manner, and interleave real-world context event sequences and GUI events, and (4) systematically interleaving context with a combinatorial-based approach. The results of our empirical studies indicate (1) CRF outperforms other models thereby predicting context events with F1 score of about 60% for our dataset, (2) the ISFreqOne that iterates over context events at the beginning of each test case in a round-robin manner as well as interleaves real-world context event sequences and GUI events at an interval one achieves up to four times better code coverage than not including context, 0.06 times better coverage than RSContext that inserts random context events at the beginning of each test case, 0.05 times better coverage than ISContext that iterates over context events to insert at the beginning of each test case in a round-robin manner, and 0.04 times better coverage than ISFreqTwo that iterates over context events at the beginning of each test case in a round-robin manner as well as interleaves real-world context event sequences and GUI events at an interval two on an average across four subject applications and, (3) the PairwiseInterleaved technique that selects a different context event at the beginning of each test case by iterating through context covering array in a round-robin manner and systematically interleaves context with GUI events by prioritizing the execution of GUI events in new contexts achieves higher code coverage up to a factor of six when compared to Monkey, up to a factor of 1.3 when compared to a technique that generates test suites without context events, and similar code coverage when compared to ISContext that iterates over context events to insert at the beginning of each test case in a round-robin manner on an average across five subject applications.

While data mining techniques such as frequent itemset and sequence mining are well established as powerful pattern discovery tools in domains from science, medicine to business, a detriment is the lack of support for interactive exploration of high numbers of patterns generated with diverse parameter settings and the relationships among the mined patterns. To enhance the user experience, real-time query turnaround times and improved support for interactive mining are desired. There is also an increasing interest in applying data mining solutions for mobile data. Patterns mined over mobile data may enable context-aware applications ranging from automating frequently repeated tasks to providing personalized recommendations. Overall, this dissertation addresses three problems that limit the utility of data mining, namely, (a.) lack of interactive exploration tools for mined patterns, (b.) insufficient support for mining localized patterns, and (c.) high computational mining requirements prohibiting mining of patterns on smaller compute units such as a smartphone. This dissertation develops interactive frameworks for the guided exploration of mined patterns and their relationships. Contributions include the PARAS pre- processing and indexing framework; enabling analysts to gain key insights into rule relationships in a parameter space view due to the compact storage of rules that enables query-time reconstruction of complete rulesets. Contributions also include the visual rule exploration framework FIRE that presents an interactive dual view of the parameter space and the rule space, that together enable enhanced sense-making of rule relationships. This dissertation also supports the online mining of localized association rules computed on data subsets by selectively deploying alternative execution strategies that leverage multidimensional itemset-based data partitioning index. Finally, we designed OLAPH, an on-device context-aware service that learns phone usage patterns over mobile context data such as app usage, location, call and SMS logs to provide device intelligence. Concepts introduced for modeling mobile data as sequences include compressing context logs to intervaled context events, adding generalized time features, and identifying meaningful sequences via filter expressions.

Many online fighting games use rollback netcode in order to compensate for network delay. Rollback netcode allows players to experience the game as having reduced delay. A drawback of this is that players will sometimes see the game quickly ”jump” to a different state to adjust for the the remote player’s actions. Rollback netcode implementations require a method for predicting the remote player’s next button inputs. Current implementations use a naive repeatlastframe policy for such prediction. There is a possibility that alternative methods may lead to improved user experience. This project examines the problem of improving input prediction in fighting games. It details the development of a new prediction model based on recurrent neural networks. The model was trained and evaluated using a dataset of several thousand recorded player input sequences. The results show that the new model slightly outperforms the naive method in prediction accuracy, with the difference being greater for longer predictions. However, it has far higher requirements both in terms of memory and computation cost. It seems unlikely that the model would significantly improve on current rollback netcode implementations. However, there may be ways to improve predictions further, and the effects on user experience remains unknown. / Många online fightingspel använder rollback netcode för att kompensera för nätverksfördröjning. Rollback netcode låter spelare uppleva spelet med mindre fördröjning. En nackdel av detta är att spelare ibland ser spelet snabbt ”hoppa” till ett annat tillstånd för att justera för motspelarens handlingar. Rollback netcode implementationer behöver en policy för att förutsäga motspelarens nästa knapptryckningar. Nuvarande implementationer använder en naiv repetera-senaste-frame policy för förutsägelser. Det finns en möjlighet att alternativa metoder kan leda till förbättrad användarupplevelse. Det här projektet undersöker problemet att förbättra förutsägelser av knapptryckningar i fightingspel. Det beskriver utvecklingen av en ny förutsägelsemodell baserad på rekursiva neuronnät. Modellen tränades och evaluerades med ett dataset av flera tusen inspelade knappsekvenser. Resultaten visar att den nya modellen överträffar den naiva metoden i noggrannhet, med större skillnad för längre förutsägelser. Dock har den mycket högre krav i både minne och beräkningskostad. Det verkar osannolikt att modellen skulle avsevärt förbättra nuvarande rollback netcode implementationer. Men det kan finnas sätt att förbättra förutsägelser ytterligare, och påverkan på användarupplevelsen förblir okänd.

Spatiotemporal Predictive Learning (SPL) is an essential research topic involving many practical and real-world applications, e.g., motion detection, video generation, precipitation forecasting, and traffic flow prediction. The problems and challenges of this field come from numerous data characteristics in both time and space domains, and they vary depending on the specific task. For instance, spatial analysis refers to the study of spatial features, such as spatial location, latitude, elevation, longitude, the shape of objects, and other patterns. From the time domain perspective, the temporal analysis generally illustrates the time steps and time intervals of data points in the sequence, also known as interval recording or time sampling. Typically, there are two types of time sampling in temporal analysis: regular time sampling (i.e., the time interval is assumed to be fixed) and the irregular time sampling (i.e., the time interval is considered arbitrary) related closely to the continuous-time prediction task when data are in continuous space. Therefore, an efficient spatiotemporal predictive method has to model spatial features properly at the given time sampling types. In this thesis, by taking advantage of Machine Learning (ML) and Deep Learning (DL) methods, which have achieved promising performance in many complicated computational tasks, we propose three DL-based models used for Spatiotemporal Sequence Prediction (SSP) with several types of time sampling. First, we design the Trajectory Gated Recurrent Unit Attention (TrajGRU-Attention) with novel attention mechanisms, namely Motion-based Attention (MA), to improve the performance of the standard Convolutional Recurrent Neural Networks (ConvRNNs) in the SSP tasks. In particular, the TrajGRU-Attention model can alleviate the impact of the vanishing gradient, which leads to the blurry effect in the long-term predictions and handle both regularly sampled and irregularly sampled time series. Consequently, this model can work effectively with different scenarios of spatiotemporal sequential data, especially in the case of time series with missing time steps. Second, by taking the idea of Neural Ordinary Differential Equations (NODEs), we propose Trajectory Gated Recurrent Unit integrating Ordinary Differential Equation techniques (TrajGRU-ODE) as a continuous time-series model. With Ordinary Differential Equation (ODE) techniques and the TrajGRU neural network, this model can perform continuous-time spatiotemporal prediction tasks and generate resulting output with high accuracy. Compared to TrajGRU-Attention, TrajGRU-ODE benefits from the development of efficient and accurate ODE solvers. Ultimately, we attempt to combine those two models to create TrajGRU-Attention-ODE. NODEs are still in their early stage of research, and recent ODE-based models were designed for many relatively simple tasks. In this thesis, we will train the models with several video datasets to verify the ability of the proposed models in practical applications. To evaluate the performance of the proposed models, we select four available spatiotemporal datasets based on the complexity level, including the MovingMNIST, MovingMNIST++, and two real-life datasets: the weather radar HKO-7 and KTH Action. With each dataset, we train, validate, and test with distinct types of time sampling to justify the prediction ability of our models. In summary, the experimental results on the four datasets indicate the proposed models can generate predictions properly with high accuracy and sharpness. Significantly, the proposed models outperform state-of-the-art ODE-based approaches under SSP tasks with different circumstances of interval recording.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-10-23T17:05:10Z No. of bitstreams: 1 renanmottagoulart.pdf: 506891 bytes, checksum: 01d7b3b82d2bc0af0d295fc75de17b91 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-11-09T13:52:19Z (GMT) No. of bitstreams: 1 renanmottagoulart.pdf: 506891 bytes, checksum: 01d7b3b82d2bc0af0d295fc75de17b91 (MD5) / Made available in DSpace on 2017-11-09T13:52:19Z (GMT). No. of bitstreams: 1 renanmottagoulart.pdf: 506891 bytes, checksum: 01d7b3b82d2bc0af0d295fc75de17b91 (MD5) Previous issue date: 2017-09-01 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Jogos de repetição é um ramo de Teoria dos Jogos, em que um jogo é jogado repetidas vezes pelos jogadores. Neste cenário, assume-se que os jogadores nem sempre jogam de modo ótimo ou podem estar dispostos, se possível, a colaborar. Neste contexto é possível um jogador analisar o comportamento dos oponentes para encontrar padrões. Estes padrões podem ser usados para aumentar o lucro obtido pelo jogador ou detectar se o oponente está disposto a realizar uma colaboração mutualmente benéfica. Nesta dissertação é proposto um novo algoritmo baseado em kernel de similaridade capaz de prever as ações de jogadores em jogos de repetição. A predição não se limita a ação do próximo round, podendo prever as ações de uma sequência finita de rounds consecutivos. O algoritmo consegue se adaptar rapidamente caso os outros jogadores mudem suas estratégias durante o jogo. É mostrado empiricamente que o algoritmo proposto obtém resultados superiores ao estado da arte atual. / Repeated games is a branch of game theory, where a game can be played several times by the players involved. In this setting, it is assumed that the players do not always play the optimal strategy or that they may be willing to collaborate. In this context it is possible for a player to analyze the opponent’s behaviour to find patters. These patterns can be used to maximize the player’s profit or to detect if the opponent is willing to collaborate. On this dissertation it is proposed a new algorithm based on similarity kernel capable of predicting the opponent’s actions on repeated games. The prediction is not limited to the next round’s action, being able to predict actions on a finite sequence of rounds. It is able to adapt rapidly if the opponents change their strategies during the course of a game. It is shown empirically that the proposed algorithm achieves better results than the current state of the art.

With an increasing demand for bandwidth and lower latency in mobile communication networks it becomes gradually more important to improve current mobile network management solutions using available network data. To improve the network management it can for instance be of interest to infer future available bandwidth to the end user of the network. This can be done by utilizing the current knowledge of real-time user equipment (UE) behaviour in the network. In the scope of this thesis interest lies in, given a set of visited radio access points (cells), to predict what the next one is going to be. For this reason the aim is to investigate the prediction performance when utilizing the All-K-Order Markov (AKOM) model, with some added variations, on collected data generated from train trajectories. Moreover a method for testing the suitability of modeling the sequence of cells as a time-homogeneous Markov chain is proposed, in order to determine the goodness-of- t with the available data. Lastly, the elapsed time in each cell is attempted to be predicted using linear regression given the prior history window of previous cell and elapsed times pairs. The results show that moderate to good prediction accuracy on the upcoming cell can be achieved with AKOM and associated variations. For predicting the upcoming sojourn time in future cells the results reveal that linear regression does not yield satisfactory results and possibly another regression model should be utilized. / Med en ökande efterfrågan på banbredd och kortare latens i mobila nätverk har det gradvis blivit viktigare att förbättra nuvarande lösningar för hantering av nätverk genom att använda tillgänglig nätverksdata. Specifikt är det av intresse att kunna dra slutsatser kring vad framtida bandbredsförhållanden kommer vara, samt övriga parametrar av intresse genom att använda tillgänglig information om aktuell mobil användarutrustnings (UE) beteende i det mobila nätverket. Inom ramen av detta masterarbete ligger fokus på att, givet tidigare besökta radio accesspunkter (celler), kunna förutspå vilken nästkommande besökta cell kommer att vara. Av denna anledning är målet att undersöka vilken prestanda som kan uppnås när All-$K$-Order Markov (AKOM) modellen, med associerade varianter av denna, används på samlad data från tågfärder. Dessutom ges det förslag på test som avgör hur lämpligt det är att modelera observerade sekvenser av celler som en homogen Markovkedja med tillgänglig data. Slutligen undersöks även om besökstiden i en framtida cell kan förutspås med linjär regression givet ett historiskt fönster av tidigare cell och besökstids par. Erhållna resultat visar att måttlig till bra prestanda kan uppnås när kommande celler förutspås med AKOM modellen och associerade variationer. För prediktering av besökstid i kommande cell med linjär regression erhålles det däremot inte tillfredsställande resultat, vilket tyder på att en alternativ regressionsmetod antagligen är bättre lämpad för denna data.

Les travaux présentés sont dédiés à la possibilité de faire de l'inférence statistique à partir de données séquentielles. Le problème est le suivant. Étant donnée une suite d'observations x_1,...,x_n,..., on cherche à faire de l'inférence sur le processus aléatoire ayant produit la suite. Plusieurs problèmes, qui d'ailleurs ont des applications multiples dans différents domaines des mathématiques et de l'informatique, peuvent être formulés ainsi. Par exemple, on peut vouloir prédire la probabilité d'apparition de l'observation suivante, x_{n+1} (le problème de prédiction séquentielle); ou répondre à la question de savoir si le processus aléatoire qui produit la suite appartient à un certain ensemble H_0 versus appartient à un ensemble différent H_1 (test d'hypothèse) ; ou encore, effectuer une action avec le but de maximiser une certain fonction d'utilité. Dans chacun de ces problèmes, pour rendre l'inférence possible il faut d'abord faire certaines hypothèses sur le processus aléatoire qui produit les données. La question centrale adressée dans les travaux présentés est la suivante : sous quelles hypothèses l'inférence est-elle possible ? Cette question est posée et analysée pour des problèmes d'inférence différents, parmi lesquels se trouvent la prédiction séquentielle, les tests d'hypothèse, la classification et l'apprentissage par renforcement.

This thesis investigates decision-making in two-player imperfect information games against opponents whose actions can affect our rewards, and whose strategies may be based on memories of interaction, or may be changing, or both. The focus is on modelling these dynamic opponents, and using the models to learn high-reward strategies. The main contributions of this work are: 1. An approach to learn high-reward strategies in small simultaneous-move games against these opponents. This is done by using a model of the opponent learnt from sequence prediction, with (possibly discounted) rewards learnt from reinforcement learning, to lookahead using explicit tree search. Empirical results show that this gains higher average rewards per game than state-of-the-art reinforcement learning agents in three simultaneous-move games. They also show that several sequence prediction methods model these opponents effectively, supporting the idea of using them from areas such as data compression and string matching; 2. An online expectation-maximisation algorithm that infers an agent's hidden information based on its behaviour in imperfect information games; 3. An approach to learn high-reward strategies in medium-size sequential-move poker games against these opponents. This is done by using a model of the opponent learnt from sequence prediction, which needs its hidden information (inferred by the online expectation-maximisation algorithm), to train a state-of-the-art no-regret learning algorithm by simulating games between the algorithm and the model. Empirical results show that this improves the no-regret learning algorithm's rewards when playing against popular and state-of-the-art algorithms in two simplified poker games; 4. Demonstrating that several change detection methods can effectively model changing categorical distributions with experimental results comparing their accuracies to empirical distributions. These results also show that their models can be used to outperform state-of-the-art reinforcement learning agents in two simultaneous-move games. This supports the idea of modelling changing opponent strategies with change detection methods; 5. Experimental results for the self-play convergence to mixed strategy Nash equilibria of the empirical distributions of plays of sequence prediction and change detection methods. The results show that they converge faster, and in more cases for change detection, than fictitious play.