conversations.from: human
conversations.value: Give me a description for a story titled Probability and Statistics for Computer Science about Computing, Reviews with the genre: Science & Math, Mathematics.
conversations.from: assistant
conversations.value: "This text will fill a gap in the education of a sophisticatedcomputer science student who has a firm base in mathematics andstatistics." ( Computing Reviews, May 7, 2009)
conversations.from: human
conversations.value: Give me the first paragraph for this story.
conversations.from: assistant
conversations.value: Probability and Statistics for Computer Science
  This chapter contains some mathematical material that you will likely have seen, but some may not have stayed with you. I have also relegated the detailed discussion of how one splits a node in a decision tree to this chapter.
conversations.from: human
conversations.value: Give me five more paragraphs.
conversations.from: assistant
conversations.value: Diagonalizing a symmetric matrix: This gives us a particularly important procedure. We can convert any symmetric matrix ![
  Notice that there is a relationship between forming an SVD and diagonalizing a matrix. In particular, ![
  By doing this, we get a function on positive real numbers that is a smooth interpolate of the factorial function. We won't do any real work with this function, so won't expand on this definition. In practice, we'll either look up a value in tables or require a software environment to produce it.
  We want to choose a split that yields the most information about the classes. To do so, we need to be able to account for information. The proper measure is entropy (described in more detail below). You should think of entropy as the number of bits, on average, that would be required to determine the value of a random variable. Filling in the details will allow us to determine which of two splits is better, and to tell whether it is worth splitting at all. At a high level, it is easy to compute which of two splits is better. We determine the entropy of the class conditioned on each split, then take the split which yields the lowest entropy. This works because less information (fewer bits) are required to determine the value of the class once we have that split. Similarly, it is easy to compute whether to split or not. We compare the entropy of the class conditioned on each split to the entropy of the class without a split, and choose the case with the lowest entropy, because less information (fewer bits) are required to determine the value of the class in that case.
  It turns out to be straightforward to keep track of information, in simple cases. We will start with an example. Assume I have 4 classes. There are 8 examples in class 1, 4 in class 2, 2 in class 3, and 2 in class 4. How much information on average will you need to send me to tell me the class of a given example? Clearly, this depends on how you communicate the information. You could send me the complete works of Edward Gibbon to communicate class 1; the Encyclopaedia for class 2; and so on. But this would be redundant. The question is how little can you send me. Keeping track of the amount of information is easier if we encode it with bits (i.e. you can send me sequences of '0's and '1's).
conversations.from: human
conversations.value: Give me the last five paragraphs.
conversations.from: assistant
conversations.value: Generally, the entropy is larger if the class of an item is more uncertain. Imagine we have two classes and p(1) = 0. 5, then the entropy is 1, and this is the largest possible value for a probability distribution on two classes. You can always tell which of two classes an object belongs to with just one bit (though you might be able to tell with even less than one bit).
  Recall that our decision function is to choose a feature at random, then test its value against a threshold. Any data point where the value is larger goes to the left pool; where the value is smaller goes to the right. This may sound much too simple to work, but it is actually effective and popular. Assume that we are at a node, which we will label k. We have the pool of training examples that have reached that node. The i'th example has a feature vector x i , and each of these feature vectors is a d dimensional vector.
  We choose an integer j in the range 1...d uniformly and at random. We will split on this feature, and we store j in the node. Recall we write x i (j) for the value of the j'th component of the i'th feature vector. We will choose a threshold t k , and split by testing the sign of x i (j) − t k. Choosing the value of t k is easy. Assume there are N k examples in the pool. Then there are N k − 1 possible values of t k that lead to different splits. To see this, sort the N k examples by x (j), then choose values of t k halfway between example values. For each of these values, we compute the information gain of the split. We then keep the threshold with the best information gain.
  We can elaborate this procedure in a useful way, by choosing m features at random, finding the best split for each, then keeping the feature and threshold value that is best. It is important that m is a lot smaller than the total number of features—a usual root of thumb is that m is about the square root of the total number of features. It is usual to choose a single m, and choose that for all the splits.
  Testing whether two populations have the same mean, for same but unknown population standard deviations