From e18a0eb38f108d103239ae6ff6badafc852b4f4a Mon Sep 17 00:00:00 2001 From: jklai Date: Thu, 4 Dec 2008 16:40:43 -0500 Subject: [PATCH] commit --- writeup/conclusion.tex | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-) rewrite writeup/conclusion.tex (66%) diff --git a/writeup/conclusion.tex b/writeup/conclusion.tex dissimilarity index 66% index 19032ec..39beb84 100644 --- a/writeup/conclusion.tex +++ b/writeup/conclusion.tex @@ -1,6 +1,10 @@ -\section{Conclusion} -We have implemented a method of extracting method traces from any Java JAR executable, implemented a $k$-Markov mixture model, developed metrics for evaluating our classifier and methods from extracting information from it, and shown that the $k$-Markov chains may be effective in identifying general modes of interaction with Java \texttt{ArrayList} library. The fact that there is one larger cluster for all values of $k$ and the way in which clusters separated suggests we could use this method to separate common usage modes from other ones. Though interactions with the \texttt{ArrayList} library are fairly simplistic, our results suggest that we can apply this method to learning interactions with more complex and obscure libraries. One possible caveat is that we may be over-clustering because a single Markov chain can capture distinct interaction sequences if the sequences have disjoint states. As a result, we may need to perform some post-processing in order to automatically use the learned model. - -The results of this work has many applications. Given that we know that there are common use cases of an API, we could generate a useful set of example use cases for the programmer. We could also use this information in code synthesis: knowing about different usage modes, and perhaps about the common cases, could greatly optimize the search space. This information is also useful in test generation: we might be able to predict interactions with the code we write and make sure our code is robust to those cases. - -If there had been no time constraints, we would have loved to look closely at other libraries, constructs traces from more programs, and used variations in classification such as collapsing repeated states into a single states or a set of states. +\section{Conclusion} +We have explored applying machine learning techniques learned in class to the problem of clustering program traces. On the implementation side, we have developed a method for extracting java util method traces from any Java JAR executable, and we wrote an implementation of the $k$ Markov chains mixture model in MATLAB. + +In terms of theory, we developed the $k$ Markov chain model on our own, based heavily off of the GMM mixture model and variable length HMM model developed in class. We also explored the problem of determining the number of underlying mixtures to use by running cross-validation for different values of $k$ and examining the BIC score. As expected, after a certain point, increasing $k$ does not yield better results, and both cross-validation and the BIC score agree on this tipping point. + +In terms of results, we saw that individual programs did not appear to have their own, specific ways of interacting with the libraries we examined. In retrospect, this is sensible since we expect there to be a fixed number of ways to interact with a library, so it is implausible for each program to be recovered just by looking at its traces. Moreover, our model appeared to assign most traces to a single cluster, indicating that there may be a dominant mode of interaction. Balancing this observation, however, is the observation that a single Markov chain can actually account for multiple modes of interaction, especially if those modes consist of disjoint sets of function calls. This may cause our model to include more than one mode of interaction in a single cluster, and we may need some post-processing to break this into more useful clusters. While the model may suffer from this, we were still able to gain insights on different types of interaction by examining both the contents of the clusters and the actual parameters of the underlying Markov chains. + +The results of this work has many applications. Given that we know that there are common use cases of an API, we could generate a useful set of example use cases for the programmer. We could also use this information in code synthesis: knowing about different usage modes, and perhaps about the common cases, could greatly optimize the search space. This information is also useful in test generation: we might be able to predict interactions with the code we write and make sure our code is robust to those cases. + +If there had been no time constraints, we would have loved to look closely at other libraries, constructed traces from more programs, and used variations in classification such as collapsing repeated states into a single states or a set of states and handling variable length clusters in a more clever way. \ No newline at end of file -- 2.11.4.GIT