Supervised versus unsupervised learning Machine learning is a branch of artificial intelligence that uses algorithms, for example, to find patterns in data and make predictions about future events. In machine learning a dataset of observations called instances is comprised of a number of variables called attributes. Supervised learning is the modeling of these datasets 46 Table 3.1: An example of a supervised learning dataset Time x1 x2 x3 x4 x5 x6 x7 y 09:30 b n -0.06 -116.9 -21.7 28.6 0.209 up 09:31 b b 0.06 -85.2 -61 -21.7 0.261 unchanged 09:32 b b 0.26 -4.4 -114.7 -61 0.17 down 09:33 n b 0.11 -112.7 -132.5 -114.7 0.089 unchanged 09:34 n n 0.08 -128.5 -101.3 -132.5 0.328 down containing labeled instances. In supervised learning, each instance can be represented as (x, y), where x is a set of independent attributes (these can be discrete or continuous) and y is the dependent target attribute.

The target attribute y can also be either continuous or discrete; however the category of modeling is regression if it contains a continuous target, but classification if it contains a discrete target (which is also called a class label). Table 3.1 demonstrates a dataset for supervised learning with seven independent attributes x1, x2, . . . , x7, and one dependent target attribute y. More specifically, x1, x2 ∈ {b, n} and x3, . . . , x7 ∈ R and the target attribute y ∈ {up,unchanged,down}. The attribute time is used to identify an instance and is not used in the model. Also the training and test datasets are represented in the same way however, where the training set contains a set of vectors of known label (y) values, the labels for the test set is unknown. In unsupervised learning the dataset does not include a target attribute, or a known outcome. Since the class values are not determined a priori, the purpose of this learning technique is to find similarity among the groups or some intrinsic clusters within the data. A very simple two-dimensional (two attributes) demonstration is 47 Figure 3.1: An example of an unsupervised learning technique – clustering shown in Figure 3.1 with the data partitioned into five clusters.

A case could be made however that the data should be partitioned into two clusters or three, etc.; the “correct” answer depends on prior knowledge or biases associated with the dataset to determine the level of similarity required for the underlying problem. Theoretically we can have as many clusters as data instances, although that would defeat the purpose of clustering. Depending on the problem and the data available, the algorithm required can be either a supervised or unsupervised technique. In this thesis, the goal is to predict future price direction of the streaming stock dataset. Since the future direction becomes known after each instance, the training set is constantly expanding 48 with labeled data as time passes. This requires a supervised learning technique. Additionally, we explore the use of different algorithms since some may be better depending on the underlying data. Care should be taken to avoid, “when all you have is a hammer, everything becomes a nail.” 3.3 Supervised learning algorithms 3.3.1 k Nearest-neightbor The k nearest neighbor (kNN) is one of the simplest machine learning methods and is often referred to as a lazy learner because learning is not implemented until actual classification or prediction is required. It takes the most frequent class as measured by the weighted euclidean distance (or some other distance measure) among the k closest training examples in the feature space. In specific problems such as text classification, kNN has been shown to work as well as more complicated models [240]. When nominal attributes are present, it is generally advised to arrive with a “distance” between the different values of the attributes [236]. For our dataset, this could apply to the different trading days, Monday, Tuesday, Wednesday, Thursday, and Friday.

A downside of using this model is the slow classification times, however we can increase speed by using dimensionality reduction algorithms; for example, reducing the number of attributes from 200 to 20. Since the learning is not implemented until the classification phase though, this is an unsuitable algorithm to use when decisions are needed quickly. 49 3.3.2 Na¨ıve Bayes The na¨ıve Bayes classifier is an efficient probabilistic model based on the Bayes Theorem that examines the likelihood of features appearing in the predicted classes. Given a set of attributes X = {x1, x2, . . . , xn}, the objective is to construct the posterior probability for the event Ck among a set of possible class outcomes C = {c1, c2, . . . , ck}. Therefore, with Bayes’ rule P(Ck|x1, . . . , xn) ∝ P(Ck)P(x1, . . . , xn|Ck), where P(x1, . . . , xn|Ck) is the probability that attribute X belongs to Cj , and assuming independence1 we can rewrite as P(Cj |X) ∝ P(Cj ) �n i=1 P(xi|Cj ). A new instance with a set of attributes X is labeled with the class Cj that achieves the highest posterior probability. 3.3.3 Decision table A decision table classifier is built on the conceptual idea of a lookup table. The classifier returns the majority class of the training set if the decision table (lookup table) cell matching the new instance is empty. In certain datasets, classification performance has been found to be higher when using decision tables than with more complicated models. A further description can be found in [124, 125, 127]. 3.3.4 Support Vector Machines Support vector machines [221] have long been recognized as being able to efficiently handle high-dimensional data. Originally designed as a two-class classifier, it can work with more classes by making multiple binary classifications (one-versus- 1The assumption of independence is the na¨ıve aspect of the algorithm. 50 one between every pair of classes). The algorithm works by classifying instances based on a linear function of the features. Additionally non-linear classification can be performed using a kernel. The classifier is fed with pre-labeled instances and by selecting points as support vectors the SVM searches for a hyperplane that maximizes the margin. More information can be found in [221]. 3.3.5 Artificial Neural Networks An artificial neural network (ANN) is an interconnected group of nodes intended to represent the network of neurons in the brains. They are widely used in literature, because of their ability to learn complex patterns. We present only a short overview of their structure in this section. The artificial neural network is comprised of nodes (shown as circles in Figure 3.2), an input layer represented as x1 . . . , x6, an optional hidden layer, and an output layer y. The objective of the ANN is to determine a set of weights w (between the input, hidden, and output nodes) that minimize the total sum of squared errors. During training these weights wi are adjusted according to a learning parameter λ ∈ [0, 1] until the outputs become consistent with the output. Large values of λ may make changes to the weights that are too drastic, while values that are too small may require more iterations (called epochs) before the model sufficiently learns from the training data. The difficulty of using artificial neural networks is finding parameters that learn from training data without over fitting (i.e. memorizing the training data) and 51 x1 x2 x3 x4 x5 x6 input layer hidden layer output layer y Figure 3.2: Example of a multilayer feed-forward artificial neural network therefore perform poorly on unseen data. If there are too many hidden nodes, the system may overfit the current data, while if there are too few, it can prevent the system from properly fitting the input values. Also, a choice of stopping criterion has to be chosen. This can include stopping based on when the total error of the network falls below some predetermined error level or when a certain number of epochs (iterations) has been completed [16, 25, 177]. To demonstrate this, see Figure 3.3. This plot represents a segment of our high-frequency trade data that will be used later in this thesis. As the epochs increase (by tens), the number of incorrectly identified training instances decreases, as seen by the decrease in the training error. However, the validation error decreases until 30 epochs, and after 30, starts to increase. Around roughly 80 epochs the validation error begins to decrease again, however we need to make a judgment call since an increase in epochs increases the training times dramatically. Yu et al. [245] state that with foreign exchange rate forecasting, which is similar to stocks because of the high degree of noise, volatility and complexity, it is advisable to use the sigmoidal type-transfer function (i.e. logistic or hyperbolic tangent). Tigure 3.3: Artificial neural network classification error versus number of epochs base this on the large number of papers that find predictability using this type of function in the hidden layer. 3.3.6 Decision Trees The decision tree is one of the more widely used classifiers in practice because the algorithm creates rules which are easy to understand and interpret. The version we use in this paper is also one of the most popular forms, the C4.5 [186], which extends the ID3 [185] algorithm. The improvements are: 1) it is more robust to noise, 2) it allows for the use of continuous attribute, and 3) it works with missing data. The C4.5 begins as a recursive divide-and-conquer algorithm, first by selecting an attribute from the training set to place at the root node. Each value of the attribute 53 creates a new branch, with this process repeating recursively using all the instances reaching that branch [236]. An ideal node contains all (or nearly all) of one class. To determine the best attribute to choose for a particular node in the tree, the gain in information entropy for the decision is calculated. More information can be found in [186]. 3.3.7 Ensembles An ensemble is a collection of multiple base classifiers that take a new example, pass it to each of its base classifiers, and then combines those predictions according to some method (such as through voting). The motivation is that by combining the predictions, the ensemble is less likely to misclassify. For example, Figure 3.4a demonstrates an ensemble with 25 hypothetical classifiers, each with an independent error rate of 0.45 (assuming a uniform 2 class problem). The probability of getting k incorrect classifier votes is a binomial distribution, P(k) = �n k � pk(1 − p)n−k. The probability that 13 or more is in error is 0.31, which is less than the error rate of the individual classifier. This is a potential advantage of using multiple models. This advantage of using multiple models (ensembles) is under the assumption that the individual classifier error rate is less than 0.50. If the independent classifier error rate is 0.55, then the probability of 13 or more in error is 0.69 – it would be better not to use an ensemble of classifiers. Figure 3.4b2 demonstrates the error rate of the ensemble for three independent error rates, 0.55, 0.50, and 0.45 for ensembles 2The idea for the visualization came from [59, 82]. 54 Error rate versus number of classifiers in the ensemble (employing majority voting) for three independent error rates Figure 3.4: Ensemble simulation containing an odd number of classifiers, from 3 to 101. From the figure it can be seen that the smaller the independent classifier error rate is, and the larger the number of classifiers in the ensemble is, the less likely a majority of the classifiers will predict incorrectly [59, 82]. The idea of classifier independence may be unreasonable, given that the classifiers may predict in a similar manner due to the training set. Obtaining a base classifier that generates errors as uncorrelated as possible is ideal. Creating a diverse set of classifiers within the ensemble is considered an important property since the likelihood that a majority of the base classifiers misclassify the instance is decreased. Two of the more popular methods used within ensemble learning is bagging [27] and boosting (e.g. the AdaBoost algorithm [78] described in Subsection 3.3.7.2 is the most common). These methods promote diversity by building base classifiers on different subsets of the training data or different weights of classifiers. 55 3.3.7.1 Bagging Bagging, also known as bootstrap aggregation, was proposed by Breiman in 1994 in an early version of [27]. It works by generating k bootstrapped training sets and building a classifier on each (where k is determined by the user). Each training set of size N is created by randomly selecting instances from the original dataset, with each receiving an equal probability of being selected and with replacement. Since every instance has an equal probability of being selected, bagging does not focus on any particular instance of the training data and therefore is less likely to over-fit [177]. Bagging is generally for unstable3 classifiers such as decision trees and neural networks. 3.3.7.2 Boosting The AdaBoost (Adaptive Boosting) algorithm of Freud and Schapire [78] in 1995 is synonymous with boosting. The idea however was proposed in 1988 by Michael Kearns [114] in a class project, where he hypothesized that a “weak” classifier, performing slightly better than average, could be “boosted” into a “strong” classifier. In boosting, instances being classified are assigned a weight; instances that were previously incorrectly classified receive larger weights, with the hope that subsequent models correct the mistake of the previous model. In the AdaBoost algorithm the original training set D has a weight w assigned to each of its N instances {(x1, y1), . . . ,(xn, yn)}, where xi is a vector of inputs and yi is the class label of that 3By unstable, it is meant that small changes in the training set can lead to large changes in the classifier outcome. 56 instance. With the weight added the instances become {(x1, y1, w1), . . . ,(xn, yn, wn)} and the sum of the wi must equal 1. The AdaBoost algorithm then builds k base classifiers with an initial weight wi = 1 N . Upon each iteration of the algorithm (which is determined by the user), the weight wi gets adjusted according to the error �i of the classifier hypothesis4. The points that were incorrectly identified receive higher weights, and the ones that were correctly identified receive less. The desire is that on the next iteration, the re-weighting will help to correctly classify the instances that were misclassified by the previous classifier. When implementing the boosting ensemble on test data, the final class is determined by a weighted vote of the classifiers [78, 149]. Boosting does more to reduce bias than variance. This reduction is due to the algorithm adjusting its weight to learn previously misclassified instances and therefore increasing the probability that these instances will be learned correctly in the future. This has had a tendency to correct biases. However, it tends to perform poorly on noisy datasets and therefore the weights become greater, which causes the model to focus on the noisy instances and over-fit the data [195]. 3.3.7.3 Combining classifiers for ensembles The last step in any ensemble-based system is the method used to combine the individual classifiers; this is often referred to as fusion rules. Classifiers within an ensemble are most commonly combined using a majority voting algorithm. There 4If the error is greater than what would be achieved by guessing the class, then the ensemble is returned to the previously generated base classifier. 57 are however, different methods of combining, which often depend on the underlying classifiers used. For example, the Naive Bayes algorithm provides continuous valued outputs, allowing a wide range of strategies for combining, while an artificial neural network provides a discrete-valued output, allowing for fewer [133, 134, 247]. A description of each follows: • Majority voting – Plurality majority voting – The class that receives the highest number of votes among classifiers (in literature, majority voting typically refers to version) – Simple majority voting – The class that receives one more than fifty percent of all votes among classifiers – Unanimous majority voting – The class that all the classifiers unanimously vote on • Weighted majority voting – If the confidence in among classifiers is not equal, we can weight certain classifiers more heavily. This method is followed in the AdaBoost algorithm. • Algebraic combiners – Mean/Minimum/Maximum/Median rules – The ensemble decision is chosen for the class according to the average/minimum/maximum/median of each classifier’s confidence. 58 Table 3.2: Confusion matrix Predicted class + – Actual + TP FN Class – FP TN While ensembles have shown success in a variety of problems, there are some associated drawbacks. This includes added memory and computation cost in keeping multiple classifiers stored and ready to process. Also the loss of interpretability may be a cause for concern depending on the needs of the problem. For example, a single decision tree can be easily interpreted, while an ensemble of 100 decision trees could be difficult [21]. 3.4 Performance metrics 3.4.1 Confusion matrix and accuracy A confusion matrix, also called a contingency table, is a visualization of the performance of a supervised learning method. A problem with n classes, requires a confusion matrix of size n × n with the rows representing the specific actual class and the columns representing the classifiers predicted class. In a confusion matrix, TP (true positive) is the number of positives correctly identified, TN (true negative) is the number of negatives correctly identified, FP (false positive) is the number of negatives incorrectly identified as positive, and FN (false negative) is the number of positives incorrectly identified as negatives. An example of a confusion matrix can be seen in Table 3.2. 59 From the confusion matrix it is relatively simple to arrive at different measures for comparing models. An example is accuracy, which is a widely used metric and is easy to interpret. From Equation 3.1, accuracy is the total number of correct predictions made over the total number of predictions made. While accuracy is a popular metric, it is also not very descriptive when used to measure the performance of a highly imbalanced dataset. A model may have high levels of accuracy, but may not obtain high levels of identification of the class that we are interested in predicting. For example, if attempting to identify large moves in a stock which is comprised of 99% small moves and 1% large moves, it is trivial to report a model has accuracy of 99% without additional information. A classifier could also have 99% accuracy by simply reporting the class with the largest number of instances (e.g. the majority class is “small moves”). In an imbalanced dataset, a model may misidentify all positive classes and still have high levels of accuracy; pure randomness is not taken into account with the accuracy metric. Accuracy’s complement is the error rate (1 − Accuracy) and can be seen in Equation 3.2. Accuracy = T P + T N T P + T N + F P + F N (3.1) Error rate = F P + F N T P + F P + T N + F N (3.2) There are several approaches to comparing models with imbalanced datasets. First is the precision and recall metrics and the accompanying harmonic mean, the F-measure. The second metric is based on Cohen’s kappa statistic, which takes into account the randomness of the class. The third metric is the receiver operating characteristic which is based on the true positive and false positives rates. The 60 fourth is a cost-based metric which gives specific “costs” to correctly and incorrectly identifying specific classes. And the last method is based not on the ability of the model to make correct decisions, but instead on the profitability of the classifier as it applies to a trading system. A more detailed description of these metrics follows. 3.4.2 Precision and recall Precision and recall are both popular metrics for evaluating classifier performance and will be used extensively in this paper. Precision is the percentage that the model correctly predicts positive when making a decision (Equation 3.3).

More specifically, precision is the number of correctly identified positive examples divided by the total number of examples that are classified as positive. Recall is the percentage of positives correctly identified out of all the existing positives (Equation 3.4); it is the number of correctly classified positive examples divided by the total number of true positive examples in the test set. From our imbalanced example above with the 99% small moves and 1% large moves, precision would be how often a large move was correctly identified as such, while recall would be the total number of large moves that are correctly identified out of all the large moves in the dataset. Precision = T P T P + F P (3.3) Sensitivity (Recall) = T P T P + F N (3.4) Specificity = T N T N + F P (3.5) F-measure = 2(precision)(recall) precision + recall (3.6) Precision and recall are often achieved at the expense of the other, i.e. high 61 precision is achieved at the expense of recall and high recall is achieved at the expense of precision. An ideal model would have both high recall and high precision. The F-measure5, which can be seen in Equation 3.6, is the harmonic measure of precision and recall in a single measurement. The F-measure ranges from 0 to 1, with a measure of 1 being a classifier perfectly capturing precision and recall. 3.4.3 Kappa The second approach to comparing imbalanced datasets is based on Cohen’s kappa statistic. This metric takes into consideration randomness of the class and provides an intuitive result. From [14], the metric can be observed in Equation 3.7 where P0 is the total agreement probability and Pc is the agreement probability which is due to chance. κ = P0 − Pc 1 − Pc (3.7) P0 = � I i=1 P(xii) (3.8) Pc = � I i=1 P(xi.)P(x.i) (3.9) The total agreement probability P0 (i.e. the classifier’s accuracy) can be be computed according to Equation 3.8, where I is the number of class values, P(xi.) is the row marginal probability and P(x.i) is the column marginal probability, with both obtained from the confusion matrix. The probability due to chance, Pc, can be computed according to Equation 3.9. The kappa statistic is constrained to the interval 5The F-measure, in the literature is also called the F-score and the F1-score. 62 Table 3.3: Computing the Kappa statistic from the confusion matrix (a) Confusion matrix – Numbers Predicted class up down flat Actual up 139 80 89 308 class down 10 298 13 323 flat 40 16 313 369 189 396 4157 1000 (b) Confusion matrix – Probabilities Predicted class up down flat Actual up 0.14 0.08 0.09 0.31 class down 0.01 0.30 0.01 0.32 flat 0.04 0.02 0.31 0.37 0.19 0.40 0.42 1.00 [−1, 1], with a kappa κ = 0 meaning that agreement is equal to random chance, and a kappa κ equaling 1 and -1 meaning perfect agreement and perfect disagreement respectively. For example, in Table 3.3a the results of a three-class problem are shown, with the marginal probabilities calculated in Table 3.3b. The total agreement probability, also known as accuracy, is computed as P0 = 0.14 + 0.30 + 0.31 = 0.75, while the probability by chance is Pc = (0.19×0.31) + (0.40×0.32) + (0.42×0.37) = 0.34. The kappa statistic is therefore κ = (0.75 − 0.34)/(1 − 0.34) = 0.62. 3.4.4 ROC The third approach to comparing classifiers is the Receiver Operating Characteristic (ROC) curve. This is a plot of the true positive rate, which is also called recall or 63 Figure 3.5: ROC curve example sensitivity (Equation 3.10), against the false positive rate, which is also known as 1-specificity (3.11). T P R = T P T P + F N (3.10) F P R = F P T N + F P (3.11) The best performance is noted by a curve close to the top left corner (i.e. a small false positive rate and a large true positive rate), with a curve along the diagonal reflecting a purely random classifier. As a demonstration, in Figure 3.5 three ROC curves are displayed for three classifiers. Classifier 1 has a more ideal ROC curve than Classifier 2 or 3. Classifier 2 is slightly better than random, while Classifier 3 is worse. In Classifier 3’s case, it would be better to choose as a solution that is opposite of what the classifier predicts. 64 For single number comparison, the Area Under the ROC Curve (AUC) is calculated by integrating the ROC curve. Random would therefore have an AUC of 0.50 and a classifier better and worse than random would have an AUC greater than and less than 0.50 respectively. It is most commonly used with two-class problems although with multi-class examples the AUC can be weighted according to the class distribution. AUC is also equal to the Wilcoxon statistic. 3.4.5 Cost-based The cost-based method of evaluating classifiers is based on the “cost” associated with making incorrect decisions [61, 65, 102]. The performance metrics seen thus far do not take into consideration the possibility that not all classification errors are equal. For example, an opportunity cost can be associated with missing a large move in a stock. A cost can also be provided for initiating an incorrect trade. A model can be built with a high recall, which misses no large moves in the stock, but the precision would most likely suffer. The cost-based approach gives an associated cost to this decision which can be evaluated to determine the suitability of the model. A cost matrix is used to represent the associated cost of each decision with the goal of minimizing the total cost associated with the model. This can be formalized with a cost matrix C and the entry (i, j) with the actual cost i and the predicted class j. When i = j the prediction is correct and when i �= j the prediction is incorrect. An advantage of using a cost-based evaluation metric for trading models is the cost associated with making incorrect decisions is known by analyzing empirical 65 data.

For example all trades incur a cost in the form of a trade commission and money used in a trade is temporarily unavailable, thus incurring an opportunity cost. Additionally, a loss associated with an incorrect decision can be averaged over similar previous losses; gains can be computed similarly. Consider, for example, a trading firm is attempting to predict the directional price move of a stock with the objective to trade on the decision. At time t, the stock can move up, down, or have no change in price; at time t+n, the direction is unknown (this can be observed in Figure 3.6). For time t + 1, a prediction of up might result in the firm purchasing the stock. Different errors in classification however would have different associated cost. A firm expecting a move up would purchase the stock in anticipation of the move, but a subsequent move down would be more harmful than no change in price. A actual move down would immediately result in a trading loss, whereas no change in price would result in an temporary opportunity cost with the stock still having the potential to go in the desired direction. Additionally an incorrect prediction of “no change” would merely result in an opportunity lost, but no actual money being put to risk since a firm would not trade based on the anticipation of a unchanged market (no change). Table 3.4 represents a theoretical cost matrix of the problem, with three separate error amounts represented: 0.25, 0.50, and 1.25. 3.4.6 Profitability of the model While the end result of predicting stock price direction is to increase profitability, the performance metrics discussed thus far (with the exception of the cost-based 66 Predicted class Down No change Up Actual Down 0 0.25 1.25 class No change 0.50 0 0.50 Up 1.25 0.25 0 metric) evaluate classifiers based on the ability to correctly classify and not on overall profitability of a trading system. As an example, a classifier may have very high accuracy, kappa, AUC, etc. but this may not necessarily equate to a profitable trading strategy, since profitability of individual trades may be more important than being “right” a majority of times; e.g. making $0.50 on each of one hundred trades is not as profitable as losing $0.05 95 times and then making $12 on each of five trades6. Figure 3.7 represents a trading model represented in much of the academic literature, where the classifier is built on the data with a prediction of up, down, or no change in the market price with the outcome passed to a second set of rules. These 6An argument can also be made that a less volatile approach is more ideal (i.e. making small sums consistently). This depends on the overall objective of the trader – maximizing stability or overall profitability. 67 Figure 3.7: Trading algorithm process rules provide direction if a prediction of “up”, for example, should equate to buying stock, buying more stock, or buying back a position that was previously shorted. The rules also address the amount of stock to be purchased, how much to risk, etc. When considering profitability of a model, the literature generally follows the form of an automated trading model, which is “buy when the model says to buy, then sell after n number of minutes/hours/days [161]” or “buy when the model says to buy, then sell if the position is up x% or else sell after n minutes/days/hours [138, 164, 202].” Teixeira et al. [214] added another rule (called a “stop loss” within trading), which prevented losses from going past a certain dollar amount during an individual trade. The goal of this thesis is not to provide an “out of the box” trading system with proven profitability, but to instead help the user make trading decisions with the help of machine learning techniques. Additionally, there are many different rules in the trading literature relating to how much stock to buy or sell, how much money to risk in a position, how often trades should take place, and when to buy and sell; each of these questions are enough for entire dissertations. In practice, trading systems often involve many layers of controls such as forecasting and optimization methodologies 68 Table 3.5: Importance of using an unbiased estimate of its generalizability – trained using the dataset from Appendix B for January 3, 2012 January 3, 2012 (training data) January 4, 2012 (unseen data) Accuracy 94.713% 37.31% that are filtered through multiple layers of risk management. This typically involves a human supervisor (risk manager) that can make decisions such as when to override the system [69]. The focus of this paper therefore, will remain on the classifier itself; maximizing predictability when faced with different market conditions.