Showing posts with label learning_boosting. Show all posts
Showing posts with label learning_boosting. Show all posts
Friday, December 7, 2018
Principal component analysis
Today I've learned about the existence of the Principal component analysis. It's supposed to find the orthogonal dimensions that best describe the variance of the data set. Perhaps this is the real answer for removing the duplication in the dimensions that I've been thinking about some time ago. And it had been invented in 1901! I haven't understood it yet, will need to read up on it. For now just making a note so that I won't forget about it.
Saturday, September 30, 2017
removing the duplication in Bayesian & AdaBoost
I've been thinking some more on how to remove the duplication between the Bayesian events/AdaBoost partial hypotheses. Here are some notes. They're not some final results, just some thinking aloud.
I think the problem of removing the commonality can be boiled down to the following: Suppose we have an event A that gives the prediction with some effect a on the training cases, and an event B that gives the prediction b on the training cases. These predictions have some part ab (that's a 2-letter identifier, not multiplication of a and b) in common. Then the effects can be written as:
A: a = a' + ab
B: b = b' + ab
Where a' and b' are the differences between the original a and ab, and b and ab. Here the operator "+" means not the addition but application of the events in the deduction one after another. So "a + b" means "apply a, then apply b". The reason why I chose the sign "+" is that this combined application should act like addition. I.e. have the commutative and distributive properties like
x + y = y + x
(x + y) + z = x + (y + z)
No, I don't have a proof why they do. But the problem with the AdaBoost hypotheses that I'm trying to solve is that the result there depends on the order of partial hypotheses (i.e. Bayesian events). I want to be able to decompose these events in such a way as to make the result independent of the order, hence the commutative requirement. The exact operation that satisfies these rules will need to be found but for now we can follow through the results of these rules.
So, going by these rules, if we apply both events, that will be:
a + b = a' + ab + b' + ab = a' + b' + 2*ab
The part ab gets applied twice. To remove this duplication we've got rid of one copy of ab. We can do this by splitting the original two events into three events A', B' and AB (again, that's a 2-letter identifier, not a multiplication):
A': a'
B': b'
AB:ab
a = a' + ab; b = b' +ab
The new event AB gets the common part, while A and B lose it and become A' and B'. Then with all events applied we get the result without duplication:
a' + b' +ab
If we want to add the fourth event C, we've got to get its overlap with all 3 previous events. This requires a whole bunch of multi-letter identifiers:
a'c would be the overlap between a' andc
b'c would be the overlap between b' and c
abc would be the overlap between ab and c
And the double-primes would be the "remainders":
a' = a'' + a'c
b' = b'' + b'c
ab = ab' +abc
c = c' + a'c + b'c +abc
Then the result of applying all these events without duplication will be:
a'' + a'c + b'' + b'c + ab' + abc + c'
This gives the outline of the solution but it still has two problems: the number of events after splitting grows exponentially (a power of 2) with the number of the original events, and the concrete meaning of the operation "+" needs to be defined. And actually there is one more operation that needs to be defined: what does the "overlap" mean and how do we compute the value of ab from the values of a and b?
The answers to both problems might be connected. One way to define the overlap would be to associate each training case with exactly one event that predicts it well. Then when we split a and b into a', b', and ab, we would be splitting the whole set of training cases into 3 parts: one part gets predicted well by both A and B, one only by A, and one only by B.
Then the problem with the exponential growth can be answered in a two-fold way. First, the number of the events after splitting can't grow higher than the number of the training cases. Second, we can put an artificial cap on the number of events that we're willing to use (Emax), and select up to this many events, ones that predict the most training cases each. We can then either sweep the remaining training cases under the carpet, saying that they are one-offs that would cause overfitting, or split them somehow with partial strength among the events that get included.
The last sentence also suggests the third way of tackling the growth: if we define some way to do the splitting, instead of multiplying the events we could just split the power they have on a particular training case. But I think this would create issues in case of the partial confidence during the execution of the model that can be handled better with the combined events.
Returning to the definition of "+", I couldn't figure out yet how to make such an operation directly in AdaBoost. Maybe it can be done through logarithms, that will need some more thinking. It requires the ability to say that some training case doesn't get affected by a partial hypothesis/event. But there seems to be an easy way to do it in the Bayesian way: mark the confidence of that event for that training case as 0.5. And then these transformed events/partial hypotheses can be fed into AdaBoost too.
This fits very well with the underlying goal of boosting: to find the approximately equal rate of the predominantly correct votes for each training case. After the transformation there will be exactly one right vote for each training case, and the rest of votes will be "undecided" (or at least sort of, subject to the limitations introduced by the mixing of training cases).
Another consequence is that such splitting would make the produced events fully independent of each other: each event would have an exactly 50% correlation with each other event, meaning that they can be applied in any order. And this is exactly what we've been aiming for.
So it all looks good and simple but I'm not sure yet if I've missed something important that will take the whole construction apart. There might well be.
P.S. After a little thinking I've realized that the idea of number of events being limited by the number of training cases is pretty much equivalent to the computation directly on the training cases by weight.
I think the problem of removing the commonality can be boiled down to the following: Suppose we have an event A that gives the prediction with some effect a on the training cases, and an event B that gives the prediction b on the training cases. These predictions have some part ab (that's a 2-letter identifier, not multiplication of a and b) in common. Then the effects can be written as:
A: a = a' + ab
B: b = b' + ab
Where a' and b' are the differences between the original a and ab, and b and ab. Here the operator "+" means not the addition but application of the events in the deduction one after another. So "a + b" means "apply a, then apply b". The reason why I chose the sign "+" is that this combined application should act like addition. I.e. have the commutative and distributive properties like
x + y = y + x
(x + y) + z = x + (y + z)
No, I don't have a proof why they do. But the problem with the AdaBoost hypotheses that I'm trying to solve is that the result there depends on the order of partial hypotheses (i.e. Bayesian events). I want to be able to decompose these events in such a way as to make the result independent of the order, hence the commutative requirement. The exact operation that satisfies these rules will need to be found but for now we can follow through the results of these rules.
So, going by these rules, if we apply both events, that will be:
a + b = a' + ab + b' + ab = a' + b' + 2*ab
The part ab gets applied twice. To remove this duplication we've got rid of one copy of ab. We can do this by splitting the original two events into three events A', B' and AB (again, that's a 2-letter identifier, not a multiplication):
A': a'
B': b'
AB:ab
a = a' + ab; b = b' +ab
The new event AB gets the common part, while A and B lose it and become A' and B'. Then with all events applied we get the result without duplication:
a' + b' +ab
If we want to add the fourth event C, we've got to get its overlap with all 3 previous events. This requires a whole bunch of multi-letter identifiers:
a'c would be the overlap between a' andc
b'c would be the overlap between b' and c
abc would be the overlap between ab and c
And the double-primes would be the "remainders":
a' = a'' + a'c
b' = b'' + b'c
ab = ab' +abc
c = c' + a'c + b'c +abc
Then the result of applying all these events without duplication will be:
a'' + a'c + b'' + b'c + ab' + abc + c'
This gives the outline of the solution but it still has two problems: the number of events after splitting grows exponentially (a power of 2) with the number of the original events, and the concrete meaning of the operation "+" needs to be defined. And actually there is one more operation that needs to be defined: what does the "overlap" mean and how do we compute the value of ab from the values of a and b?
The answers to both problems might be connected. One way to define the overlap would be to associate each training case with exactly one event that predicts it well. Then when we split a and b into a', b', and ab, we would be splitting the whole set of training cases into 3 parts: one part gets predicted well by both A and B, one only by A, and one only by B.
Then the problem with the exponential growth can be answered in a two-fold way. First, the number of the events after splitting can't grow higher than the number of the training cases. Second, we can put an artificial cap on the number of events that we're willing to use (Emax), and select up to this many events, ones that predict the most training cases each. We can then either sweep the remaining training cases under the carpet, saying that they are one-offs that would cause overfitting, or split them somehow with partial strength among the events that get included.
The last sentence also suggests the third way of tackling the growth: if we define some way to do the splitting, instead of multiplying the events we could just split the power they have on a particular training case. But I think this would create issues in case of the partial confidence during the execution of the model that can be handled better with the combined events.
Returning to the definition of "+", I couldn't figure out yet how to make such an operation directly in AdaBoost. Maybe it can be done through logarithms, that will need some more thinking. It requires the ability to say that some training case doesn't get affected by a partial hypothesis/event. But there seems to be an easy way to do it in the Bayesian way: mark the confidence of that event for that training case as 0.5. And then these transformed events/partial hypotheses can be fed into AdaBoost too.
This fits very well with the underlying goal of boosting: to find the approximately equal rate of the predominantly correct votes for each training case. After the transformation there will be exactly one right vote for each training case, and the rest of votes will be "undecided" (or at least sort of, subject to the limitations introduced by the mixing of training cases).
Another consequence is that such splitting would make the produced events fully independent of each other: each event would have an exactly 50% correlation with each other event, meaning that they can be applied in any order. And this is exactly what we've been aiming for.
So it all looks good and simple but I'm not sure yet if I've missed something important that will take the whole construction apart. There might well be.
P.S. After a little thinking I've realized that the idea of number of events being limited by the number of training cases is pretty much equivalent to the computation directly on the training cases by weight.
AdaBoost conjunctions & XOR
I've been thinking recently about the better ways to extract the commonality from two Bayesian events (hope to find time to write about that soon), and that brought me back to the XOR problem: how to handle the situation when two events indicate a certain hypothesis when they are the same and another hypothesis when they are different.
BTW, I took a class on machine learning recently, and it turns out that even with the neural network this problem doesn't have a great solution. The neural networks are subject to the random initial state before the training, and sometimes they do find the good combinations and sometimes they don't. This tends to get solved more reliably by the human intervention: a data scientist stares at the data, maybe does a few training attempts to see what happens, and then manually adds a new event that represents the XOR of the original events.
So, thinking about it, I've remembered again about the concept of conjunctions that I've read in the AdaBoost book. I picked up the book and tried to find the conjunctions but couldn't: they're not anywhere in the index. Fortunately, an Internet search turned up the online copy of the book, and the conjunctions are in the chapter 9.
The idea there is that the quality of AdaBoost partial hypotheses can be improved by forming them as conjunctions of two or more raw partial hypotheses. The idea is to take the two best choices and try a conjunction on them. If it gets better, try adding the third one.
For a simple example, consider the data with two parameters, with values 1 collected in the upper-right quarter, and 0 in the remaining three quarters:
The two partial hypotheses (x > 0) and (y > 0) taken together but separately will identify the upper right quarter quite decently. Each of them will have a 75% success rate. But the values in the upper-left and lower-right corner will get one vote "for" and one vote "against" from these hypotheses and will be left undecided. I actually think that the classic AdaBoost would not be able to decide well for them. It would probably crowd the field with the extra hypotheses in the upper-right corner like (x > 1), (y > 1), (x > 2), (y > 2) and so on so that the upper-left and lower-right quarters would get better but the parts of the upper-right close to the boundary would get worse. If we take the classic Bayesian approach and consider that the prior probability of encountering a 0 is 75% (assuming that all the quarters are filled at the same density), the "undecided" result would leave the probability of 0 at the same 75%, and it would be a vote for 0. So this is probably a good example of how AdaBoost could benefit from using the prior probabilities.
The conjunctions are good at handling such situations: if these partial hypotheses are combined into one conjunction (x > 0) & (y > 0), we get a hypothesis with 100% success.
They can be used to handle the XOR situation as well. Let's look at the situation with 1s in upper-right and lower-left corners:
The two partial hypotheses formed by conjunctions, ((x > 0) & (y > 0)) and ((x < 0) & (y < 0)), would each give the 75% success rate. The quadrants with 0s would get correctly voted by both hypotheses but 1s would get one vote for and one vote against. But the similar hypotheses can be added for the other two quarter: !((x > 0) & (y < 0)), !((x < 0) & (y > 0)). These would add two correct votes for the quadrants with 1s, and two opposite voted canceling each other for the 0s, and taken together these 4 hypotheses can identify everything correctly.
An interesting thing to note here is that the raw hypotheses like (x > 0) aren't the best ones at selectivity in this example. They're actually the worst ones, having the exact 50% correctness. But then again, pretty much all the hypotheses with vertical and horizontal boundaries here will have about 50% selectivity. Hunting for slightly better than 50% by selecting boundaries that fit the random density fluctuations would actually make things worse, not hitting the right center. I actually see no way to select the right boundaries by choosing the raw hypotheses independently. Only taken together in a conjunction they become optimizable.
The other way to do it would be to use XORs instead of conjunctions. The case with two diagonal quadrants of 1s is trivial with XORs, since it can be described perfectly by one XOR, just as the case with one quadrant of 1s is trivial with conjunctions. Let's look at the one quadrant with XOR:
If we use one XORed hypotheses, !((x > 0) XOR (y > 0)) and two simple ones (x > 0) and (y > 0), each of the three will have the 75% success rate. The upper-right corner will get all three votes for 1, and the rest of the quadrants will get two votes for the right value 0 and one against it, so the right vote would win in them too.
The way I described it, it looks like the XORed hypothesis in this example isn't clearly better than the simple ones. But that's not how it will work with AdaBoost. After the two simple hypotheses are picked, the relative weights of the upper-left and lower-right quadrants would grow, and the XOR clearly is better at fitting them.
Overall, it looks like XORing is better at producing the useful combined hypotheses than conjunctions: the conjunctions required 4 complex hypotheses to fit the XOR case but XOR required only 3 hypotheses to fit the conjunction case, 2 of them simple hypotheses.
BTW, I took a class on machine learning recently, and it turns out that even with the neural network this problem doesn't have a great solution. The neural networks are subject to the random initial state before the training, and sometimes they do find the good combinations and sometimes they don't. This tends to get solved more reliably by the human intervention: a data scientist stares at the data, maybe does a few training attempts to see what happens, and then manually adds a new event that represents the XOR of the original events.
So, thinking about it, I've remembered again about the concept of conjunctions that I've read in the AdaBoost book. I picked up the book and tried to find the conjunctions but couldn't: they're not anywhere in the index. Fortunately, an Internet search turned up the online copy of the book, and the conjunctions are in the chapter 9.
The idea there is that the quality of AdaBoost partial hypotheses can be improved by forming them as conjunctions of two or more raw partial hypotheses. The idea is to take the two best choices and try a conjunction on them. If it gets better, try adding the third one.
For a simple example, consider the data with two parameters, with values 1 collected in the upper-right quarter, and 0 in the remaining three quarters:
.
^y
0 | 1
|
-------+------>
| x
0 | 0
The two partial hypotheses (x > 0) and (y > 0) taken together but separately will identify the upper right quarter quite decently. Each of them will have a 75% success rate. But the values in the upper-left and lower-right corner will get one vote "for" and one vote "against" from these hypotheses and will be left undecided. I actually think that the classic AdaBoost would not be able to decide well for them. It would probably crowd the field with the extra hypotheses in the upper-right corner like (x > 1), (y > 1), (x > 2), (y > 2) and so on so that the upper-left and lower-right quarters would get better but the parts of the upper-right close to the boundary would get worse. If we take the classic Bayesian approach and consider that the prior probability of encountering a 0 is 75% (assuming that all the quarters are filled at the same density), the "undecided" result would leave the probability of 0 at the same 75%, and it would be a vote for 0. So this is probably a good example of how AdaBoost could benefit from using the prior probabilities.
The conjunctions are good at handling such situations: if these partial hypotheses are combined into one conjunction (x > 0) & (y > 0), we get a hypothesis with 100% success.
They can be used to handle the XOR situation as well. Let's look at the situation with 1s in upper-right and lower-left corners:
.
^y
0 | 1
|
-------+------>
| x
1 | 0
The two partial hypotheses formed by conjunctions, ((x > 0) & (y > 0)) and ((x < 0) & (y < 0)), would each give the 75% success rate. The quadrants with 0s would get correctly voted by both hypotheses but 1s would get one vote for and one vote against. But the similar hypotheses can be added for the other two quarter: !((x > 0) & (y < 0)), !((x < 0) & (y > 0)). These would add two correct votes for the quadrants with 1s, and two opposite voted canceling each other for the 0s, and taken together these 4 hypotheses can identify everything correctly.
An interesting thing to note here is that the raw hypotheses like (x > 0) aren't the best ones at selectivity in this example. They're actually the worst ones, having the exact 50% correctness. But then again, pretty much all the hypotheses with vertical and horizontal boundaries here will have about 50% selectivity. Hunting for slightly better than 50% by selecting boundaries that fit the random density fluctuations would actually make things worse, not hitting the right center. I actually see no way to select the right boundaries by choosing the raw hypotheses independently. Only taken together in a conjunction they become optimizable.
The other way to do it would be to use XORs instead of conjunctions. The case with two diagonal quadrants of 1s is trivial with XORs, since it can be described perfectly by one XOR, just as the case with one quadrant of 1s is trivial with conjunctions. Let's look at the one quadrant with XOR:
.
^y
0 | 1
|
-------+------>
| x
0 | 0
If we use one XORed hypotheses, !((x > 0) XOR (y > 0)) and two simple ones (x > 0) and (y > 0), each of the three will have the 75% success rate. The upper-right corner will get all three votes for 1, and the rest of the quadrants will get two votes for the right value 0 and one against it, so the right vote would win in them too.
The way I described it, it looks like the XORed hypothesis in this example isn't clearly better than the simple ones. But that's not how it will work with AdaBoost. After the two simple hypotheses are picked, the relative weights of the upper-left and lower-right quadrants would grow, and the XOR clearly is better at fitting them.
Overall, it looks like XORing is better at producing the useful combined hypotheses than conjunctions: the conjunctions required 4 complex hypotheses to fit the XOR case but XOR required only 3 hypotheses to fit the conjunction case, 2 of them simple hypotheses.
Monday, September 25, 2017
Boosting book reference
I've accidentally found the Freund and Schapire's book on AdaBoost online:
https://mitpress.mit.edu/sites/default/files/titles/content/boosting_foundations_algorithms/toc.html
Great for searching.
https://mitpress.mit.edu/sites/default/files/titles/content/boosting_foundations_algorithms/toc.html
Great for searching.
Wednesday, September 6, 2017
AdaBoost 10: a better metric?
Here is one more consequence I've noticed from the application of AdaBoost approach to the Bayesian one: it can be applied the other way around too.
I.e. AdaBoost provides the list of partial hypotheses and weights for them. But at some point it tends to start repeating the same hypotheses over and over again, because a set of hypotheses taken together gives some gain, and applying it multiple times seemingly increases this gain. This gain is subject to the same problems as the Bayesian computations with the duplicate events: it increases the confidence only seemingly. So the same solution can be applied to it:
After the set of partial AdaBoost hypotheses has been computed, they can be re-ordered in such a way as to remove the duplication, by selecting on every step the partial hypotheses with the smallest effect. This "run order" can be kept and updated on every step, instead of the AdaBoost's "selection order". So when the sequence will start repeating, a duplicate hypothesis would add nothing to the cumulative effect of the "run order", and at this point the selection algorithm should try a different hypothesis (or simply stop).
I guess, in case if the selection algorithm doesn't stop but tries to do the next best pick (and then maybe another one if the second choice is no good either), it becomes fundamentally more complicated: on each iteration of AdaBoost it should select not simply the hypotheses that maximizes the effect of the whole sequence when appended to the end of it but one that maximizes the effect of the whole sequence when inserted at the position in the sequence where it adds the least effect. Each such insert could also cause a re-ordering of the part of the sequence that follows it.
Which sounds even more heavy-weight than the original AdaBoost selection of the hypothesis. On the other hand, since the AdaBoost selection is already so heavy-weight, maybe this would make little extra overhead. I don't know how to analyze it yet.
I.e. AdaBoost provides the list of partial hypotheses and weights for them. But at some point it tends to start repeating the same hypotheses over and over again, because a set of hypotheses taken together gives some gain, and applying it multiple times seemingly increases this gain. This gain is subject to the same problems as the Bayesian computations with the duplicate events: it increases the confidence only seemingly. So the same solution can be applied to it:
After the set of partial AdaBoost hypotheses has been computed, they can be re-ordered in such a way as to remove the duplication, by selecting on every step the partial hypotheses with the smallest effect. This "run order" can be kept and updated on every step, instead of the AdaBoost's "selection order". So when the sequence will start repeating, a duplicate hypothesis would add nothing to the cumulative effect of the "run order", and at this point the selection algorithm should try a different hypothesis (or simply stop).
I guess, in case if the selection algorithm doesn't stop but tries to do the next best pick (and then maybe another one if the second choice is no good either), it becomes fundamentally more complicated: on each iteration of AdaBoost it should select not simply the hypotheses that maximizes the effect of the whole sequence when appended to the end of it but one that maximizes the effect of the whole sequence when inserted at the position in the sequence where it adds the least effect. Each such insert could also cause a re-ordering of the part of the sequence that follows it.
Which sounds even more heavy-weight than the original AdaBoost selection of the hypothesis. On the other hand, since the AdaBoost selection is already so heavy-weight, maybe this would make little extra overhead. I don't know how to analyze it yet.
Tuesday, August 1, 2017
Bayes 27 & AdaBoost: another problem with partial confidence
The solution from the previous installment can handle the partial confidence but it has its own issue. To demonstrate it, let's look at a run with the table from the part 26 but where both of the fully-correlated events E1 and E2 get a confidence of 0.7:
The probabilities move after applying E1, after E2 they move again. The interesting question is, should have they moved after E2? It really depends on how E1 and E2 have been measured: are their confidences derived independently or tracking back to the same measurement?
The code assumes that they are independent, so if both are independently measured at the confidence of 0.7, together they provide a higher confidence. But if they both come from the same test, this assumption is wrong.
If they came from the same test then E2 carries no additional information after E1 has been processed. In this case we should have treated the value C(E2)=0.7 (i.e. C(E2)=C(E1)) as having the meaning "I don't know", and then the differences from it would carry the new information.
But this approach has its own problems. First of all, it's fine if the confidence values C(E) represent the measured probabilities. But if they represent some expert estimation then an expert saying "I don't know" and giving the confidence of 0.5 would shift the probabilities instead of leaving them unchanged. Well, it it could be re-scaled automatically but then how do we know that the expert means "I don't know" and not "I've carefully considered everything and I think that it's a 50-50 chance"? So it sounds like getting it right would require using two separate numbers: the absolute confidence that tells how sure we are of the estimation, and separately the estimation. Which would create all kinds of messes.
The second problem, if we want to do such a re-scaling, to which value do we re-scale? It's reasonably easy if two events are copies of each other but what if the correlation is only partial? There actually is an a rather easy answer to the problem: the needed value would be P(E), the probability that the event is true at that point (after the previous events have been considered). I've actually went and modified the code to compute the P(E) based on the weights only to find out that I've forgotten an important property of the AdaBoost logic. Let me show its output:
The computation table now has one more element printed after "@", the estimation of event's probablity for the particular branch based on the previous events. During the computation these values get mixed together based on the weight of the branches. But notice that when applying E2, the message says:
It's 0.513333, not 0.7! The reason is two-fold. First, AdaBoost works by adjusting the weights of the training cases such as to bring the probability of the last seen event to 0.5. It just does the correction opposite to what I was trying to achieve. Second, these are the wrong probabilities in the table. These probabilities are computed per-branch based on the absolute confidence. They don't care if the actual confidence was 0.7 or 0.3, these values are the same from the standpoint of the absolute confidence. But this difference matters a lot when trying to predict P(E)!
Instead we need to honestly compute the P(E) based on the previous events, not per the AdaBoostian table but per the original training cases. But if we do that, we end up again with a table of exponential size. The trick with ignoring all the events but the last few might still work though. The idea would be similar: since we try to order the closely-correlated events close to each other, the previous few events would be the ones with the strongest effects. And if the farther events aren't closely correlated, they won't have a big effect anyway, so they can be ignored. Maybe I'll try this next. Or maybe it's simply not worth the trouble.
$ perl ex26_01run.pl -n -p 1 tab24_01.txt in27_01_02.txt Original training cases: ! , ,E1 ,E2 ,E3 , hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00, AdaBoostian table: ! , ,E1 ,E2 ,E3 , hyp1 ,3.00000,0.66667^0.66667,0.66667^0.66667,0.40000^0.33333, + , , ,0.50000^0.50000,0.40000^0.33333, hyp2 ,3.00000,0.33333^0.33333,0.33333^0.33333,0.60000^0.66667, + , , ,0.50000^0.50000,0.60000^0.66667, --- Initial weights hyp1 w=3.00000 p=0.50000 hyp2 w=3.00000 p=0.50000 --- Applying event E1, c=0.700000 hyp1 w=1.70000 p=0.56667 hyp2 w=1.30000 p=0.43333 --- Applying event E2, c=0.700000 hyp1 w=0.91800 p=0.60554 hyp2 w=0.59800 p=0.39446 --- Applying event E3, c=1.000000$ perl ex27_01run.pl -n -p 1 tab24_01.txt in27_01_02.txt hyp1 w=0.36720 p=0.50579 hyp2 w=0.35880 p=0.49421
The probabilities move after applying E1, after E2 they move again. The interesting question is, should have they moved after E2? It really depends on how E1 and E2 have been measured: are their confidences derived independently or tracking back to the same measurement?
The code assumes that they are independent, so if both are independently measured at the confidence of 0.7, together they provide a higher confidence. But if they both come from the same test, this assumption is wrong.
If they came from the same test then E2 carries no additional information after E1 has been processed. In this case we should have treated the value C(E2)=0.7 (i.e. C(E2)=C(E1)) as having the meaning "I don't know", and then the differences from it would carry the new information.
But this approach has its own problems. First of all, it's fine if the confidence values C(E) represent the measured probabilities. But if they represent some expert estimation then an expert saying "I don't know" and giving the confidence of 0.5 would shift the probabilities instead of leaving them unchanged. Well, it it could be re-scaled automatically but then how do we know that the expert means "I don't know" and not "I've carefully considered everything and I think that it's a 50-50 chance"? So it sounds like getting it right would require using two separate numbers: the absolute confidence that tells how sure we are of the estimation, and separately the estimation. Which would create all kinds of messes.
The second problem, if we want to do such a re-scaling, to which value do we re-scale? It's reasonably easy if two events are copies of each other but what if the correlation is only partial? There actually is an a rather easy answer to the problem: the needed value would be P(E), the probability that the event is true at that point (after the previous events have been considered). I've actually went and modified the code to compute the P(E) based on the weights only to find out that I've forgotten an important property of the AdaBoost logic. Let me show its output:
$ perl ex27_01run.pl -n -p 1 tab24_01.txt in27_01_02.txt Original training cases: ! , ,E1 ,E2 ,E3 , hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00, AdaBoostian table: ! , ,E1 ,E2 ,E3 , hyp1 ,3.00000,0.66667^0.66667@0.66667,0.66667^0.66667@0.66667,0.40000^0.33333@0.50000, + , , ,0.50000^0.50000@0.50000,0.40000^0.33333@0.50000, hyp2 ,3.00000,0.33333^0.33333@0.33333,0.33333^0.33333@0.33333,0.60000^0.66667@0.75000, + , , ,0.50000^0.50000@0.50000,0.60000^0.66667@0.75000, --- Initial weights hyp1 w=3.00000 p=0.50000 hyp2 w=3.00000 p=0.50000 --- Applying event E1, c=0.700000 Expected P(E)=0.500000 hyp1 w=1.70000 p=0.56667 hyp2 w=1.30000 p=0.43333 --- Applying event E2, c=0.700000 Expected P(E)=0.513333 hyp1 w=0.91800 p=0.60554 hyp2 w=0.59800 p=0.39446 --- Applying event E3, c=1.000000 Expected P(E)=0.598615 hyp1 w=0.36720 p=0.50579 hyp2 w=0.35880 p=0.49421
The computation table now has one more element printed after "@", the estimation of event's probablity for the particular branch based on the previous events. During the computation these values get mixed together based on the weight of the branches. But notice that when applying E2, the message says:
Expected P(E)=0.513333
It's 0.513333, not 0.7! The reason is two-fold. First, AdaBoost works by adjusting the weights of the training cases such as to bring the probability of the last seen event to 0.5. It just does the correction opposite to what I was trying to achieve. Second, these are the wrong probabilities in the table. These probabilities are computed per-branch based on the absolute confidence. They don't care if the actual confidence was 0.7 or 0.3, these values are the same from the standpoint of the absolute confidence. But this difference matters a lot when trying to predict P(E)!
Instead we need to honestly compute the P(E) based on the previous events, not per the AdaBoostian table but per the original training cases. But if we do that, we end up again with a table of exponential size. The trick with ignoring all the events but the last few might still work though. The idea would be similar: since we try to order the closely-correlated events close to each other, the previous few events would be the ones with the strongest effects. And if the farther events aren't closely correlated, they won't have a big effect anyway, so they can be ignored. Maybe I'll try this next. Or maybe it's simply not worth the trouble.
Monday, July 10, 2017
Bayes 26 & AdaBoost: more on the partial confidence
I think I've found at least a partial solution to the problem of partial confidence that avoids going exponential.
It grows right out of the problem definition: the problem really exists only for the closely related events. If two events are unrelated, then the confidence of one wouldn't affect the other in any noticeable way. But for the related events, the first one takes up the bulk of the effect, and then the effect of the following events becomes greatly diminished. If two events are actually the same (like E1 and E2 in tab24_01.txt in the part 24), the second event gets stripped of any effect whatsoever. But if at the execution time we find that we have no information about the first event and good information about the second event, it's too late to make use of the second event because its probabilities are already hardcoded in the table and condemn it to having no effect. But if we could change the probability at run time then we could use the second event instead. Better yet, the probabilities of the following events would be unaffected because they don't care which one of the duplicate events provided the information. For a sequence of not equal but closely correlated events, if the first one is excluded from the table preparation, the others still seem to converge in their effects to something close to the original sequence, and the following events don't get affected that much.
Since the logic in the part 24 assumes that the closely-related events would be placed in the sequence next to each other, the solution might be to compute an event's table entry in multiple versions, depending on whether the values of a limited number of the previous events are known or not. It would still be exponential for this number of previous events. But since we expect a fast convergence and hope that not too many event values will be unknown, this number of previous events can be small, and the exponent of it would be reasonably small too.
By the way, I've come up with a name for the K(E) described in the previous part: the "absolute confidence". The confidence C(E) has the range from 0 showing that we're completely sure that the event is false, though 0.5 showing that we have no idea, to 1 showing that the event is true. The absolute confidence
K(E) = abs(2*C(E) - 1)
has the range from 0 showing that we have no idea to 1 showing that we're completely sure that the event is true or false.
I had to draw a picture to figure it out how it would work. Suppose that we want to take 3 previous events into the consideration. The datapoints with the probability values for these events can then be seen as nodes of a tree, with the nodes for each event aligned vertically under the event name:
E1 still has only one probability value because it has no preceding events. But E2 has two possible probabilities, depending on whether E1 was known (K(E1)=0) or unknown (K(E1)=1). E3 has four probabilities, depending on the possible combinations of E1 and E2. And E4 has eight probabilities.
When we come to E5, it can't just continue branching exponentially.It should depend on only three previous events, so we drop the dependency on E1. This is done by abandoning the subtree with K(E1)=0 and continuing branching the subtree with K(E1)=1. This is a reasonable thing to do because we assume that the combination {0, 0, 0} "should never happen" (i.e no more than 3 events in a row would be unknown, otherwise use a higher value of depth), and the other mirroring pairs of branches of {0, b, c} and {1, b, c} would converge to about the same probability value. Thus the events starting from E5 would also have 8 probability values each.
Then when we do the computation on the built table, we can have any K(E) in range [0, 1], so we do an interpolation between the branches. Suppose we're computing E4, and have 8 branches {E1, E2, E3} to interpolate. We do it by adding them up with the following weights:
W{0, 0, 0} = (1-K(E1))*(1-K(E2))*(1-K(E3))
W{0, 0, 1} = (1-K(E1))*(1-K(E2))*K(E3)
W{0, 1, 0} = (1-K(E1))*K(E2)*(1-K(E3))
W{0, 1, 1} = (1-K(E1))*K(E2)*K(E3)
W{1, 0, 0} = K(E1)*(1-K(E2))*(1-K(E3))
W{1, 0, 1} = K(E1)*(1-K(E2))*K(E3)
W{1, 1, 0} = K(E1)*K(E2)*(1-K(E3))
W{1, 1, 1} = K(E1)*K(E2)*K(E3)
Or the other way to look at it is that we start with the weight of 1 for every branch, then for E1 multiply the weight of every branch where K(E1)=0 by the actual 1-K(E1), and where K(E1)=1 by the actual K(E1). Then similarly for E2, multiply the weight of every branch where K(E2)=0 by the actual 1-K(E2), and where K(E2)=1 by the actual K(E2). And so on. The sum of all the weights will always be 1.
The physical meaning of this interpolation is that we split the computation into multiple branches and finally add them up together. Since the computation is additive, we can put them back together right away rather than waiting for the end.
And since I was implementing the partial confidences in the final computation, I've also implemented the support for the partial confidences in training: it's done by logically splitting the training case into two weighted sub-cases with the event values of 0 and 1.
All this is implemented in the script ex26_01run.pl, as a further modification of ex24_01run.pl. Without the extra parameters it works just as ex24_01 does. The new parameter -p sets the number of previous events whose absolute confidence affect the current event. Here is an example of a run with the same training table as before and the same input:
The option -n disables the normalization of the weight of the hypotheses, just as before. The output is the same as ex24_01 produced. In the training data E1 and E2 are duplicates, so the probabilities computed for E2 in the adaboostian table (P(H|E) and P(~H|~E), they are separated by "^") are at 0.5, meaning that it has no effect.
And here is the same training data but with support for one previous unknown event, and the input data having E1 unknown (i.e. C(E1) = 0.5):
Here E2 and E3 have not one pair of probabilities in the adaboostian table but two pairs, as shown in the branching picture above. The extra branches are shown on the continuation lines that start with a "+". The branches for E2 show that if E1 is known (the second branch), E2 will have no effect as in the previous example, but if E1 is unknown (the first branch), E2's probabilities would be the same as for E1, so E2 would replace it and converge to the same values.
As you can see in the run log, after E1 with confidence 0.5 (i.e. absolute confidence 0) is applied, both hypotheses still have the equal weight. But then after E2 gets applied, the weights and probabilities of hypotheses become the same as in the previous example, thus the knowledge of E2 compensating for the absent knowledge of E1.
An interesting thing to notice is that the probabilities for E3 are the same in either case. This is because this table can handle only one unknown event in a row, which means that at least one of E1 or E2 should be known, and E2 is able to fully compensate for the unknown E1, so both ways converge to the same probabilities of E3.
Now some information about how it all is implemented:
Some of the arrays have gained an extra dimensions, to be able to keep track of the multiple branches.The weight of the training case {wt} has become an array instead of a scalar, and the probabilities {ppos} and {pneg} of the hypotheses became 2-dimensional arrays.
The function compute_abtable() that computes the adaboostean table had gained an extra nested loop that goes through all the branches. As the final step of processing every event it prunes the branches coming from the previous event and then splits each of these branches in two. The support of the partial confidence in the training data is done by replacing the statement
with
The function apply_abevent() that does the computation based on the table has been updated to manage the branches during this step. It had gained the extra argument of an array that keeps the history of the absolute confidence of the few previous events. This history is used to compute the weights of the branches:
Then an update based on the current event is computed for each branch, and the weight of the hypothesis is updated per these weighted bracnhes:
And of course the functions that print the tables and normalize the data have been updated too.
All this stuff works on the small examples. I'm not sure yet if it would work well in the real world, I'd need a bigger example for that, and I don't have one yet. Also, I've noticed one potential issue even on the small examples but more about it in the next installment.
It grows right out of the problem definition: the problem really exists only for the closely related events. If two events are unrelated, then the confidence of one wouldn't affect the other in any noticeable way. But for the related events, the first one takes up the bulk of the effect, and then the effect of the following events becomes greatly diminished. If two events are actually the same (like E1 and E2 in tab24_01.txt in the part 24), the second event gets stripped of any effect whatsoever. But if at the execution time we find that we have no information about the first event and good information about the second event, it's too late to make use of the second event because its probabilities are already hardcoded in the table and condemn it to having no effect. But if we could change the probability at run time then we could use the second event instead. Better yet, the probabilities of the following events would be unaffected because they don't care which one of the duplicate events provided the information. For a sequence of not equal but closely correlated events, if the first one is excluded from the table preparation, the others still seem to converge in their effects to something close to the original sequence, and the following events don't get affected that much.
Since the logic in the part 24 assumes that the closely-related events would be placed in the sequence next to each other, the solution might be to compute an event's table entry in multiple versions, depending on whether the values of a limited number of the previous events are known or not. It would still be exponential for this number of previous events. But since we expect a fast convergence and hope that not too many event values will be unknown, this number of previous events can be small, and the exponent of it would be reasonably small too.
By the way, I've come up with a name for the K(E) described in the previous part: the "absolute confidence". The confidence C(E) has the range from 0 showing that we're completely sure that the event is false, though 0.5 showing that we have no idea, to 1 showing that the event is true. The absolute confidence
K(E) = abs(2*C(E) - 1)
has the range from 0 showing that we have no idea to 1 showing that we're completely sure that the event is true or false.
I had to draw a picture to figure it out how it would work. Suppose that we want to take 3 previous events into the consideration. The datapoints with the probability values for these events can then be seen as nodes of a tree, with the nodes for each event aligned vertically under the event name:
E1 E2 E3 E4 E5
+------o
0/
+-----o
0/ 1\
/ +------o
+----o
/ \ +------o
0/ 1\ 0/
/ +-----o
/ 1\
/ +------o
o
\ 0+-------o
\ +------o<
\ 0/ 1+-------o
1\ +----o
\ / 1\ 0+-------o
\ 0/ +------o<
\ / 1+-------o
+--o
\ 0+-------o
1\ +------o<
\ 0/ 1+-------o
+----o
1\ 0+-------o
+------o<
1+-------o
E1 still has only one probability value because it has no preceding events. But E2 has two possible probabilities, depending on whether E1 was known (K(E1)=0) or unknown (K(E1)=1). E3 has four probabilities, depending on the possible combinations of E1 and E2. And E4 has eight probabilities.
When we come to E5, it can't just continue branching exponentially.It should depend on only three previous events, so we drop the dependency on E1. This is done by abandoning the subtree with K(E1)=0 and continuing branching the subtree with K(E1)=1. This is a reasonable thing to do because we assume that the combination {0, 0, 0} "should never happen" (i.e no more than 3 events in a row would be unknown, otherwise use a higher value of depth), and the other mirroring pairs of branches of {0, b, c} and {1, b, c} would converge to about the same probability value. Thus the events starting from E5 would also have 8 probability values each.
Then when we do the computation on the built table, we can have any K(E) in range [0, 1], so we do an interpolation between the branches. Suppose we're computing E4, and have 8 branches {E1, E2, E3} to interpolate. We do it by adding them up with the following weights:
W{0, 0, 0} = (1-K(E1))*(1-K(E2))*(1-K(E3))
W{0, 0, 1} = (1-K(E1))*(1-K(E2))*K(E3)
W{0, 1, 0} = (1-K(E1))*K(E2)*(1-K(E3))
W{0, 1, 1} = (1-K(E1))*K(E2)*K(E3)
W{1, 0, 0} = K(E1)*(1-K(E2))*(1-K(E3))
W{1, 0, 1} = K(E1)*(1-K(E2))*K(E3)
W{1, 1, 0} = K(E1)*K(E2)*(1-K(E3))
W{1, 1, 1} = K(E1)*K(E2)*K(E3)
Or the other way to look at it is that we start with the weight of 1 for every branch, then for E1 multiply the weight of every branch where K(E1)=0 by the actual 1-K(E1), and where K(E1)=1 by the actual K(E1). Then similarly for E2, multiply the weight of every branch where K(E2)=0 by the actual 1-K(E2), and where K(E2)=1 by the actual K(E2). And so on. The sum of all the weights will always be 1.
The physical meaning of this interpolation is that we split the computation into multiple branches and finally add them up together. Since the computation is additive, we can put them back together right away rather than waiting for the end.
And since I was implementing the partial confidences in the final computation, I've also implemented the support for the partial confidences in training: it's done by logically splitting the training case into two weighted sub-cases with the event values of 0 and 1.
All this is implemented in the script ex26_01run.pl, as a further modification of ex24_01run.pl. Without the extra parameters it works just as ex24_01 does. The new parameter -p sets the number of previous events whose absolute confidence affect the current event. Here is an example of a run with the same training table as before and the same input:
$ perl ex26_01run.pl -n tab24_01.txt in24_01_01.txt Original training cases: ! , ,E1 ,E2 ,E3 , hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00, AdaBoostian table: ! , ,E1 ,E2 ,E3 , hyp1 ,3.00000,0.66667^0.66667,0.50000^0.50000,0.40000^0.33333, hyp2 ,3.00000,0.33333^0.33333,0.50000^0.50000,0.60000^0.66667, --- Initial weights hyp1 w=3.00000 p=0.50000in a row hyp2 w=3.00000 p=0.50000 --- Applying event E1, c=1.000000 hyp1 w=2.00000 p=0.66667 hyp2 w=1.00000 p=0.33333 --- Applying event E2, c=1.000000 hyp1 w=1.00000 p=0.66667 hyp2 w=0.50000 p=0.33333 --- Applying event E3, c=1.000000 hyp1 w=0.40000 p=0.57143 hyp2 w=0.30000 p=0.42857
The option -n disables the normalization of the weight of the hypotheses, just as before. The output is the same as ex24_01 produced. In the training data E1 and E2 are duplicates, so the probabilities computed for E2 in the adaboostian table (P(H|E) and P(~H|~E), they are separated by "^") are at 0.5, meaning that it has no effect.
And here is the same training data but with support for one previous unknown event, and the input data having E1 unknown (i.e. C(E1) = 0.5):
$ perl ex26_01run.pl -n -p 1 tab24_01.txt in26_01_01.txt
Original training cases: ! , ,E1 ,E2 ,E3 , hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00, AdaBoostian table: ! , ,E1 ,E2 ,E3 , hyp1 ,3.00000,0.66667^0.66667,0.66667^0.66667,0.40000^0.33333, + , , ,0.50000^0.50000,0.40000^0.33333, hyp2 ,3.00000,0.33333^0.33333,0.33333^0.33333,0.60000^0.66667, + , , ,0.50000^0.50000,0.60000^0.66667, --- Initial weights hyp1 w=3.00000 p=0.50000 hyp2 w=3.00000 p=0.50000 --- Applying event E1, c=0.500000 hyp1 w=1.50000 p=0.50000 hyp2 w=1.50000 p=0.50000 --- Applying event E2, c=1.000000 hyp1 w=1.00000 p=0.66667 hyp2 w=0.50000 p=0.33333 --- Applying event E3, c=1.000000 hyp1 w=0.40000 p=0.57143 hyp2 w=0.30000 p=0.42857
Here E2 and E3 have not one pair of probabilities in the adaboostian table but two pairs, as shown in the branching picture above. The extra branches are shown on the continuation lines that start with a "+". The branches for E2 show that if E1 is known (the second branch), E2 will have no effect as in the previous example, but if E1 is unknown (the first branch), E2's probabilities would be the same as for E1, so E2 would replace it and converge to the same values.
As you can see in the run log, after E1 with confidence 0.5 (i.e. absolute confidence 0) is applied, both hypotheses still have the equal weight. But then after E2 gets applied, the weights and probabilities of hypotheses become the same as in the previous example, thus the knowledge of E2 compensating for the absent knowledge of E1.
An interesting thing to notice is that the probabilities for E3 are the same in either case. This is because this table can handle only one unknown event in a row, which means that at least one of E1 or E2 should be known, and E2 is able to fully compensate for the unknown E1, so both ways converge to the same probabilities of E3.
Now some information about how it all is implemented:
Some of the arrays have gained an extra dimensions, to be able to keep track of the multiple branches.The weight of the training case {wt} has become an array instead of a scalar, and the probabilities {ppos} and {pneg} of the hypotheses became 2-dimensional arrays.
The function compute_abtable() that computes the adaboostean table had gained an extra nested loop that goes through all the branches. As the final step of processing every event it prunes the branches coming from the previous event and then splits each of these branches in two. The support of the partial confidence in the training data is done by replacing the statement
if ($c->{tc}[$i] >= 0.5) {
$c->{wt} /= $abhyp{$hyp}->{ppos}[$i];
} else {
$c->{wt} /= (1. - $abhyp{$hyp}->{pneg}[$i]);
}
with
push @{$c->{wt}},
$c->{tc}[$i] * $oldwt->[$br] / $abhyp{$hyp}->{ppos}[$i][$br]
+ (1. - $c->{tc}[$i]) * $oldwt->[$br] / (1. - $abhyp{$hyp}->{pneg}[$i][$br]);
The function apply_abevent() that does the computation based on the table has been updated to manage the branches during this step. It had gained the extra argument of an array that keeps the history of the absolute confidence of the few previous events. This history is used to compute the weights of the branches:
for (my $br = 0; $br <= $maxbr; $br++) {
my $w = 1.;
for (my $bit = 0; $bit <= $#$evhist; $bit++) {
if ($br & (1 << $bit)) {
$w *= $evhist->[$bit];
} else {
$w *= 1. - $evhist->[$bit];
}
}
push @brwt, $w;
}
Then an update based on the current event is computed for each branch, and the weight of the hypothesis is updated per these weighted bracnhes:
my $p = 0.;
# each branch is weighed per the observed history
for (my $br = 0; $br <= $maxbr; $br++) {
$p += $brwt[$br] * (
$conf * $hyp->{ppos}[$evi][$br]
+ (1. - $conf) * (1. - $hyp->{pneg}[$evi][$br])
);
}
$hyp->{cwt} *= $p;
And of course the functions that print the tables and normalize the data have been updated too.
All this stuff works on the small examples. I'm not sure yet if it would work well in the real world, I'd need a bigger example for that, and I don't have one yet. Also, I've noticed one potential issue even on the small examples but more about it in the next installment.
Sunday, June 4, 2017
Neuron in the Bayesian terms, part 3
I want to elaborate on why the second trick is so important. Basically, because in general the necessary condition of the chances changing on an event in the opposite way (by dividing or multiplying by the same number) is not true. It takes a specifically defined event to make it true.
In general if an event is true, the chance of a hypothesis after applying this event is:
Chance(H|E) = P(H/E) / P(~H|E)
The probabilities change on an event as follows:
P(H|E) = P(H) * P(E|H) / P(E)
P(~H|E) = P(~H) * P(E|~H) / P(E)
So then the chance changes (after substituting and reducing the formula):
Chance(H|E) = Chance(H) * P(E|H) / P(E|~H)
If an event is false, the chance changes in a similar but different way:
Chance(H|~E) = P(H/~E) / P(~H|~E)
= Chance(H) * P(~E|H) / P(~E|~H)
Being able to do the "opposites" requires that
Chance(H|E) / Chance(H) = 1/ ( Chance(H|~E) / Chance(H) )
Chance(H|E) / Chance(H) = Chance(H) / Chance(H|~E)
Which then means after doing the substitution:
P(E|H) / P(E|~H) = P(~E|~H) / P(~E|H)
Which is not always true. But if we take a page from the AdaBoost's book and define an event such that
P(E|H) = P(~E|~H)
and
P(E|~H) = P(~E|H)
Then it all magically works. Again, this magic is not needed for the Bayesian computation in general, it's needed only to fit it to the formula used in the neural networks and in AdaBoost.
There are versions of AdaBoost that use the different multipliers for when x[i] < 0 and x[i] > 0. Which means that
l[i]^x[i]
gets replaced with
if (x[i] > 0) {
lpos[i]^x[i]
} else {
lneg[i]^x[i]
}
AdaBoost in this situation still uses the same definition of E=(x == y) for the reasons of its internal logic, but if we don't require this logic then we can define E=(x > 0) and easily implement the chance computation for it, since the requirement of both multipliers being the opposites would disappear.
This opens two possibilities for variations of the neurons:
(1) One with still the definition E=(x==y) but different multipliers for x[i] of different sign.
(2) One with the definition E=(x > 0)
A network with such neurons would obviously take twice the memory space for its trained multipliers (but not for the data being computed). I'm not even sure if it would be trainable at all, especially the version (2), since AdaBoost has good reasons to keep its definition of E for the convergence. But maybe it would, and considering that AdaBoost in this modification converges faster, maybe the training of the neural network would converge faster too. Might be worth a try.
In general if an event is true, the chance of a hypothesis after applying this event is:
Chance(H|E) = P(H/E) / P(~H|E)
The probabilities change on an event as follows:
P(H|E) = P(H) * P(E|H) / P(E)
P(~H|E) = P(~H) * P(E|~H) / P(E)
So then the chance changes (after substituting and reducing the formula):
Chance(H|E) = Chance(H) * P(E|H) / P(E|~H)
If an event is false, the chance changes in a similar but different way:
Chance(H|~E) = P(H/~E) / P(~H|~E)
= Chance(H) * P(~E|H) / P(~E|~H)
Being able to do the "opposites" requires that
Chance(H|E) / Chance(H) = 1/ ( Chance(H|~E) / Chance(H) )
Chance(H|E) / Chance(H) = Chance(H) / Chance(H|~E)
Which then means after doing the substitution:
P(E|H) / P(E|~H) = P(~E|~H) / P(~E|H)
Which is not always true. But if we take a page from the AdaBoost's book and define an event such that
P(E|H) = P(~E|~H)
and
P(E|~H) = P(~E|H)
Then it all magically works. Again, this magic is not needed for the Bayesian computation in general, it's needed only to fit it to the formula used in the neural networks and in AdaBoost.
There are versions of AdaBoost that use the different multipliers for when x[i] < 0 and x[i] > 0. Which means that
l[i]^x[i]
gets replaced with
if (x[i] > 0) {
lpos[i]^x[i]
} else {
lneg[i]^x[i]
}
AdaBoost in this situation still uses the same definition of E=(x == y) for the reasons of its internal logic, but if we don't require this logic then we can define E=(x > 0) and easily implement the chance computation for it, since the requirement of both multipliers being the opposites would disappear.
This opens two possibilities for variations of the neurons:
(1) One with still the definition E=(x==y) but different multipliers for x[i] of different sign.
(2) One with the definition E=(x > 0)
A network with such neurons would obviously take twice the memory space for its trained multipliers (but not for the data being computed). I'm not even sure if it would be trainable at all, especially the version (2), since AdaBoost has good reasons to keep its definition of E for the convergence. But maybe it would, and considering that AdaBoost in this modification converges faster, maybe the training of the neural network would converge faster too. Might be worth a try.
emergents
I've attended a talk about the commercial use of the pre-trained neural networks. The idea is that you take a pre-trained network, throw away the top couple of layers, then put the blank layers on top instead and train only these new layers for your purpose.
The presenter gave an example of taking the Google's general image classifier network and teaching it to recognize your specific images instead: "huggable" vs "non-huggable". It was smart enough to recognize that a knitted cactus is huggable while a real one is not.
Well, it's kind of not surprising: the top layers of the classifier network are trained to recognize the various kinds of images but to do that the layer below it must produce the characteristics that allow to recognize these various kinds of images. If the original classifier has the wide knowledge (and it does), the previous layer would know what is important to recognize a very wide rage of images. They call the output of that previous layer "the emergents". And then when you use them as inputs, the new top layer would have an easy job classifying them for the new goal. You could probably even do a Bayesian classifier on top of them without much difference.
The presenter gave an example of taking the Google's general image classifier network and teaching it to recognize your specific images instead: "huggable" vs "non-huggable". It was smart enough to recognize that a knitted cactus is huggable while a real one is not.
Well, it's kind of not surprising: the top layers of the classifier network are trained to recognize the various kinds of images but to do that the layer below it must produce the characteristics that allow to recognize these various kinds of images. If the original classifier has the wide knowledge (and it does), the previous layer would know what is important to recognize a very wide rage of images. They call the output of that previous layer "the emergents". And then when you use them as inputs, the new top layer would have an easy job classifying them for the new goal. You could probably even do a Bayesian classifier on top of them without much difference.
Saturday, June 3, 2017
Neuron in the Bayesian terms, part 2
I've been trying to describe in proper formulas my insight that a neuron in neural networks is a kind of a Bayesian machine(OK, this is apparently known to the people who do the neural networks professionally but it was an insight for me), and I think that I've finally succeeded. Let's start from the beginning:
A neuron implements the function
y = nonlinear(sum(w[i] * x[i]))
Here y is the output of the neuron, x[i] is the array of its inputs, w[i] is the array of some weights determined by training. Let's define the range of y and x[i] as [-1, 1] (if the values are in the other ranges, they can be trivially scaled to the range [-1, 1] by adjusting the weights w[i]).
The nonlinear function is generally some kind of a sigmoid function that matches what we do at the end of the Bayesian computations: if the probability of a hypothesis is above some level, we accept it as true, i.e. in other words pull it up to 1, if it's below some equal or lower level we reject it, i.e. pull it down to 0, and if these levels are not the same and the probability is in the middle then we leave it as some value in the middle, probably modified in some way from the original value. Except of course that this nonlinear function deals not with the probabilities in range [0, 1] but with the values in range [-1, 1], -1 meaning "false" and 1 meaning "true".
The Bayesian formula uses the multiplication, not addition, so the first trick here is that one can be converted into another using a logarithm. To do that let's introduce a new value l[i], of which w[i] will be the logarithm:
l[i] = exp(w[i])
w[i] = ln(l[i])
This can be substituted into the expression for the sum:
sum (w[i] * x[i]) = sum( ln(l[i]) * x[i] )
Using the rule ln(a)*b = ln(a^b), the sum can be converted further:
sum( ln(l[i]) * x[i] ) = sum( ln(l[i]^x[i]) )
Then using the rule ln(a)+ln(b) = ln(a * b) the sum can be converted into a product:
sum( ln(l[i]^x[i]) ) = ln( product( l[i]^x[i] ) )
Now let's see how this product can be connected to the Bayesian computation. The classic Bayesian formula for probabilities is:
P(H|E) = P(H) * P(E|H) / P(E)
So as each Bayesian event E[i] gets applied, we can say that the final probability will be:
P(H) = P0(H) * product( P(E[i]|H) / P(E[i]) )
Well, technically I maybe should have used another letter instead of i for the index, maybe j, but since the i in both formulas will be soon connected to each other, I'll just use it in both places from the start.
Instead of computing with probabilities we will be computing with chances. In case if you haven't used the chances before nor seen my mentioning of them in the previous posts, a chance is a relation of the probability of the hypothesis being true to the probability of it being false. For a simple example, if we have 5 doors, with prizes behind 2 of them and no prizes behind the remaining 3, then the chance of getting a prize by opening a random door is 2 to 3, or 2/3 (but the probability is 2/5). In a formula this gets expressed as:
Chance(H) = P(H) / P(~H) = P(H) / (1 - P(H))
So if we have two mutually exclusive hypotheses H and ~H, the probabilities for them will be:
P(H) = P0(H) * product( P(E[i]|H) / P(E[i]) )
P(~H) = P0(~H) * product( P(E[i]|~H) / P(E[i]) )
And the chances will be:
Chance(H) = P(H) / P(~H)
= ( P0(H) * product( P(E[i]|H) / P(E[i]) ) ) / ( P0(~H) * product( P(E[i]|~H) / P(E[i]) ) )
= (P0(H)/P0(~H)) * product( P(E[i]|H) / P(E[i]|~H) )
If the initial probabilities of both hypotheses are equal, P0(H) = P0(~H) = 0.5, then their relation will be 1 and can be thrown out of the formula:
Chance(H) = product( P(E[i]|H) / P(E[i]|~H) )
Well, almost. The consideration above glanced over the question of what do we do if the event is false? The answer is that in this case the factor in the product should use the probabilities of ~E instead of E:
Chance(H) = product(
if (E is true) {
P(E[i]|H) / P(E[i]|~H)
} else {
P(~E[i]|H) / P(~E[i]|~H)
}
)
Now comes the turn of the second major trick: what kind of events to use for the Bayesian formula. We'll use the same kind of events as for AdaBoost, the event being "x[i] accurately predicts y", so if H is "y > 0" and thus ~H is "y < 0", the conditional probability will be:
P(E[i]|H) = P(y == x[i])
P(~E[i]|~H) = P(y == x[i])
An interesting property of this definition is that the conditional probabilities of these events get computed across the whole range of the training data, without differentiation between x[i] < 0 and x[i] > 0. This means that
P(E|H) = P(~E|~H)
P(E|~H) = P(~E|H)
We then use the general property that
P(E|H) = 1 - P(~E|H)
P(E|H~) = 1 - P(~E|~H)
and get
P(E|~H) = P(~E|H) = 1 - P(E|H)
So after substituting all these equivalencies the computation of the chances becomes nicely symmetrical:
Chance(H) = product(
if (E is true) {
P(E[i]|H) / (1 - P(E[i]|H))
} else {
(1 - P(E[i]|H)) / P(E[i]|H)
}
)
When x[i] is in range [-1, 1], and especially if x[i] is in the set {-1, 1}, the if/else can be replaced by the power of x[i]: when x[i]==1, it will leave the expression as-is, when x==-1, the expression will be "turned over":
Chance(H) = product( ( P(E[i]|H) / (1 - P(E[i]|H)) )^x[i] )
We can now interpret the original formula in terms of the chances. That formula was:
y = nonlinear(sum(w[i] * x[i]))
= nonlinear( ln( product( l[i]^x[i] ) ) )
Here we can substitute the product:
y = nonlinear( ln( Chance(y > 0) ) )
A logarithm is a very convenient thing to apply on the chance to obtain a symmetric range of values (-infinity, +infinity) centered at 0 instead of [0, +infinity) "centered" at 1. And if the weights are properly selected, the actual range of y will be not (-infinity, +infinity) but [-1, 1].
This substitution of the product will mean:
l[i] = P(E[i]|H) / (1 - P(E[i]|H))
w[i] = ln( P(E[i]|H) / (1 - P(E[i]|H)) )
So the original weights in the neuron have the "physical meaning" of the logarithms of the chance multipliers.
A neuron implements the function
y = nonlinear(sum(w[i] * x[i]))
Here y is the output of the neuron, x[i] is the array of its inputs, w[i] is the array of some weights determined by training. Let's define the range of y and x[i] as [-1, 1] (if the values are in the other ranges, they can be trivially scaled to the range [-1, 1] by adjusting the weights w[i]).
The nonlinear function is generally some kind of a sigmoid function that matches what we do at the end of the Bayesian computations: if the probability of a hypothesis is above some level, we accept it as true, i.e. in other words pull it up to 1, if it's below some equal or lower level we reject it, i.e. pull it down to 0, and if these levels are not the same and the probability is in the middle then we leave it as some value in the middle, probably modified in some way from the original value. Except of course that this nonlinear function deals not with the probabilities in range [0, 1] but with the values in range [-1, 1], -1 meaning "false" and 1 meaning "true".
The Bayesian formula uses the multiplication, not addition, so the first trick here is that one can be converted into another using a logarithm. To do that let's introduce a new value l[i], of which w[i] will be the logarithm:
l[i] = exp(w[i])
w[i] = ln(l[i])
This can be substituted into the expression for the sum:
sum (w[i] * x[i]) = sum( ln(l[i]) * x[i] )
Using the rule ln(a)*b = ln(a^b), the sum can be converted further:
sum( ln(l[i]) * x[i] ) = sum( ln(l[i]^x[i]) )
Then using the rule ln(a)
sum( ln(l[i]^x[i]) ) = ln( product( l[i]^x[i] ) )
Now let's see how this product can be connected to the Bayesian computation. The classic Bayesian formula for probabilities is:
P(H|E) = P(H) * P(E|H) / P(E)
So as each Bayesian event E[i] gets applied, we can say that the final probability will be:
P(H) = P0(H) * product( P(E[i]|H) / P(E[i]) )
Well, technically I maybe should have used another letter instead of i for the index, maybe j, but since the i in both formulas will be soon connected to each other, I'll just use it in both places from the start.
Instead of computing with probabilities we will be computing with chances. In case if you haven't used the chances before nor seen my mentioning of them in the previous posts, a chance is a relation of the probability of the hypothesis being true to the probability of it being false. For a simple example, if we have 5 doors, with prizes behind 2 of them and no prizes behind the remaining 3, then the chance of getting a prize by opening a random door is 2 to 3, or 2/3 (but the probability is 2/5). In a formula this gets expressed as:
Chance(H) = P(H) / P(~H) = P(H) / (1 - P(H))
So if we have two mutually exclusive hypotheses H and ~H, the probabilities for them will be:
P(H) = P0(H) * product( P(E[i]|H) / P(E[i]) )
P(~H) = P0(~H) * product( P(E[i]|~H) / P(E[i]) )
And the chances will be:
Chance(H) = P(H) / P(~H)
= ( P0(H) * product( P(E[i]|H) / P(E[i]) ) ) / ( P0(~H) * product( P(E[i]|~H) / P(E[i]) ) )
= (P0(H)/P0(~H)) * product( P(E[i]|H) / P(E[i]|~H) )
If the initial probabilities of both hypotheses are equal, P0(H) = P0(~H) = 0.5, then their relation will be 1 and can be thrown out of the formula:
Chance(H) = product( P(E[i]|H) / P(E[i]|~H) )
Well, almost. The consideration above glanced over the question of what do we do if the event is false? The answer is that in this case the factor in the product should use the probabilities of ~E instead of E:
Chance(H) = product(
if (E is true) {
P(E[i]|H) / P(E[i]|~H)
} else {
P(~E[i]|H) / P(~E[i]|~H)
}
)
Now comes the turn of the second major trick: what kind of events to use for the Bayesian formula. We'll use the same kind of events as for AdaBoost, the event being "x[i] accurately predicts y", so if H is "y > 0" and thus ~H is "y < 0", the conditional probability will be:
P(E[i]|H) = P(y == x[i])
P(~E[i]|~H) = P(y == x[i])
An interesting property of this definition is that the conditional probabilities of these events get computed across the whole range of the training data, without differentiation between x[i] < 0 and x[i] > 0. This means that
P(E|H) = P(~E|~H)
P(E|~H) = P(~E|H)
We then use the general property that
P(E|H) = 1 - P(~E|H)
P(E|H~) = 1 - P(~E|~H)
and get
P(E|~H) = P(~E|H) = 1 - P(E|H)
So after substituting all these equivalencies the computation of the chances becomes nicely symmetrical:
Chance(H) = product(
if (E is true) {
P(E[i]|H) / (1 - P(E[i]|H))
} else {
(1 - P(E[i]|H)) / P(E[i]|H)
}
)
When x[i] is in range [-1, 1], and especially if x[i] is in the set {-1, 1}, the if/else can be replaced by the power of x[i]: when x[i]==1, it will leave the expression as-is, when x==-1, the expression will be "turned over":
Chance(H) = product( ( P(E[i]|H) / (1 - P(E[i]|H)) )^x[i] )
We can now interpret the original formula in terms of the chances. That formula was:
y = nonlinear(sum(w[i] * x[i]))
= nonlinear( ln( product( l[i]^x[i] ) ) )
Here we can substitute the product:
y = nonlinear( ln( Chance(y > 0) ) )
A logarithm is a very convenient thing to apply on the chance to obtain a symmetric range of values (-infinity, +infinity) centered at 0 instead of [0, +infinity) "centered" at 1. And if the weights are properly selected, the actual range of y will be not (-infinity, +infinity) but [-1, 1].
This substitution of the product will mean:
l[i] = P(E[i]|H) / (1 - P(E[i]|H))
w[i] = ln( P(E[i]|H) / (1 - P(E[i]|H)) )
So the original weights in the neuron have the "physical meaning" of the logarithms of the chance multipliers.
Sunday, March 5, 2017
Bayes 25 & AdaBoost: the partial confidence problem
The code in the previous example works only with the full-confidence events, those that have the confidence of 0 or 1. Unfortunately I haven't found a good way to handle the partial confidence yet. I've found a way but it has problems. Let me show you.
Previously I was treating the partial confidence as a superposition of 0 and 1. This approach cannot be properly used here because it doesn't cover the connections between the events. To give an example, in the previous post the code had correctly found that in tab24_01.txt the events E1and E2 are the same, so after E1 is applied, E2 becomes ignored (it's AdaBoost probabilities become 0.5). So now if we then do a computation and find that E1 is unknown (i.e. its confidence is 0.5) but E2 is known, E2 will still be ignored because its table entry says to always ignore it.
The correct way should handle this situation properly: if E1 is unknown, this should bring up the table values for E2 to compensate for it and treat E2 as E1 was formerly.
The obvious way to do it is to treat the partial confidence as a superposition of "the event is unknown" and "the event is known". So if the event is known, we process it as before. If the event is unknown, we would follow the unknown branch and then apply all the following events as if this events wasn't there. And if the event is partially known, we would split the weights of all the outcomes proportionally and handle one part with the known branch and another one with the unknown branch.
So the confidence of 0.7 would mean a superposition of 0.4 of unknown and 0.6 of the known value "1". The confidence 0.1 would mean a superposition of 0.8 of unknown and 0.2 of the known value "0". So if we denote C(E) as the event confidence, K(E) as the known weight in the superposition, and U(E) as the unknown weight in the superposition, we can write them as:
K(E) = abs(C(E) - 0.5) * 2
U(E) = 1 - K(E)
The downside of this obvious approach is that the table and computation becomes more complex. As we go through more events, two branches become four, then eight, then sixteen, and so on. The formerly quadratic complexity O(Noutcomes * Nevents) becomes exponential O(Noutcomes*Nevents*2^Nevents). I don't know yet if there is a better way.
Maybe it would be possible to build a table of "gradients" between the events: i.e. if the confidence of the event A changes, how are the probabilities of another event B affected. The problem though is that this gradient depends on all the events in the sequence between A and B, so tis idea doesn't seem to really fly.
Maybe another idea is workable, that would reduce the exponential cost to a cubic one: after splitting the superposition, instead of following two branches, just take the probabilities for each following event from both branches and mix them by the weight of the branches:
P(H|Ei) = K(Ej) * P(H|KjEi) + U(Ej) * P(H|UjEi)
It's better than exponential but still not great, with the run time O(Noutcomes*Nevents*Nevents). And the table of these pre-computed values would still seem to be exponential, each event depending on all the possible combinations of the previous events.
Previously I was treating the partial confidence as a superposition of 0 and 1. This approach cannot be properly used here because it doesn't cover the connections between the events. To give an example, in the previous post the code had correctly found that in tab24_01.txt the events E1and E2 are the same, so after E1 is applied, E2 becomes ignored (it's AdaBoost probabilities become 0.5). So now if we then do a computation and find that E1 is unknown (i.e. its confidence is 0.5) but E2 is known, E2 will still be ignored because its table entry says to always ignore it.
The correct way should handle this situation properly: if E1 is unknown, this should bring up the table values for E2 to compensate for it and treat E2 as E1 was formerly.
The obvious way to do it is to treat the partial confidence as a superposition of "the event is unknown" and "the event is known". So if the event is known, we process it as before. If the event is unknown, we would follow the unknown branch and then apply all the following events as if this events wasn't there. And if the event is partially known, we would split the weights of all the outcomes proportionally and handle one part with the known branch and another one with the unknown branch.
So the confidence of 0.7 would mean a superposition of 0.4 of unknown and 0.6 of the known value "1". The confidence 0.1 would mean a superposition of 0.8 of unknown and 0.2 of the known value "0". So if we denote C(E) as the event confidence, K(E) as the known weight in the superposition, and U(E) as the unknown weight in the superposition, we can write them as:
K(E) = abs(C(E) - 0.5) * 2
U(E) = 1 - K(E)
The downside of this obvious approach is that the table and computation becomes more complex. As we go through more events, two branches become four, then eight, then sixteen, and so on. The formerly quadratic complexity O(Noutcomes * Nevents) becomes exponential O(Noutcomes*Nevents*2^Nevents). I don't know yet if there is a better way.
Maybe it would be possible to build a table of "gradients" between the events: i.e. if the confidence of the event A changes, how are the probabilities of another event B affected. The problem though is that this gradient depends on all the events in the sequence between A and B, so tis idea doesn't seem to really fly.
Maybe another idea is workable, that would reduce the exponential cost to a cubic one: after splitting the superposition, instead of following two branches, just take the probabilities for each following event from both branches and mix them by the weight of the branches:
P(H|Ei) = K(Ej) * P(H|KjEi) + U(Ej) * P(H|UjEi)
It's better than exponential but still not great, with the run time O(Noutcomes*Nevents*Nevents). And the table of these pre-computed values would still seem to be exponential, each event depending on all the possible combinations of the previous events.
Wednesday, March 1, 2017
Bayes 24: AdaBoost as a solution to the correlated events
When writing the whitepaper, I've realized that AdaBoost is very good at finding the cross-correlation of its partial hypotheses (that map to the Bayesian events), and it always picks the next step with the minimal cross-correlation. The Bayesian computations do have an issue with cross-correlation, as described in the whitepaper and near the end of Part 8 of my notes: if there are multiple events that duplicate or mirror each other, all of them are treated as independent and drive the probabilities off. This looked like AdaBoost could give a hint of how to solve this problem, so I've started thinking about it, and I think I've found a solution.
In retrospect the solution is pretty obvious: instead of computing the Bayesian model directly, treat it as an AdaBoost model whose set of the partial hypotheses equals to the set of the Bayesian events, with an extra limitation that each one of them must be used exactly once. If there are multiple equivalent events and they happen to go one after another, AdaBoost will treat the first one as real, and the following ones will get their error rate of 0.5 and will be effectively no-ops.
Well, if there are other events interspersed in between these equivalent copies, they won't be no-ops. These other events will shift the weights of the training cases, so that the second an further copies will find themselves drifted away from 0.5. The good news here is that AdaBoost is pretty good at removing the partial correlation too but the bad news is that the order matters, to fully remove the duplication the equivalent events should go one after another. And in general, it looks like the best removal of the cross-correlation happens when the closely related events follow closely one after another. This kind of order can be implemented if we reverse the AdaBoost preference of the partial hypotheses and make it always pick the one that has its training error rate closest to 0.5. Since (unlike the classic AdaBoost) the set of partial hypotheses is limited and each element from it must be used only once, the better ones will eventually be used as well.
To experiment with these ideas, I wrote the code example ex24_01run.pl. It doesn't reorder the events, just computes the AdaBoost values for whatever order it's given, allowing to experiment with the various orders. But it has a couple of advanced features from the later chapters of the book on AdaBoost: it does the multi-class (but single-label) version that also partitions the error rate computation for the sign of the value of the partial hypothesis.
The multi-class means that it can work not only with two outcomes (a yes/no decision) but with multiple possible outcomes (i.e. Bayesian hypotheses), just like the normal Bayesian table. And just like the normal Bayesian table, these outcomes must be mutually exclusive, so each case may have only one outcome (single-label). The multi-class logic works in the way that is similar to the one described in Part 10: the resulting table is just a combination of the individual per-outcome tables. From the standpoint of each outcome, the single-label property means that the rest of the rows of the table taken together represent the opposite of this outcome, so there is no need to compute that opposite explicitly.
The partitioning of the error rate computation not only makes the result better but also comes very handy to prove that the opposite of one outcome is equivalent to the rest of the rows of the table. The AdaBoost training error e is the ratio of the total weights of the training cases where the value of the event E (that is, the Bayesian event, in AdaBoost terms it's a partial hypothesis) is not equal to the value of the outcome (Bayesian hypothesis) H. And we'll compute it separately for E (i.e. E=1) and ~E (i.e. E=0). It ends up expressable as probabilities that can be computed by summing and dividing weights W of the training cases:
e(H,E) = P(~H|E) = (sum for cases i where H(i)=0 and E=1 (Wi))/(sum for cases j where E=1 (Wj))
e(H,~E) = P(H|~E) = (sum for cases i where H(i)=1 and E=0 (Wi))/(sum for cases j where E=0 (Wj))
So if we pick a particular outcome and denote it H1, we can show that its opposite ~H1 is equivalent to the sum of the rest of hypotheses H2...HN by showing that
P(~H1|E) = sum for i in [2, N] (P(Hi|E))
which after removing the common denominator means
(sum for cases j where H1(E)=0 and E=1 (Wj)) = (sum for i in [2, N] (sum for cases k where Hi(E)=1 and E=1 (Wk))
The single-label property means that each case is marked with exactly one outcome, and all the cases where the outcome H1 is absent must have some other outcome Hi present, so these sums are indeed equal.
So it is all self-consistent. The key part of the computation is:
And the matching part of the table building is:
The training undoes the weight change that will be done in the computation.
Now let's try some examples. Here is the example that I used in the whitepaper:
Here the option "-n" means "don't normalize the weights" (or when normalized to the sum of 1 they will be the same as probabilities). The two values printed in the AdaBoostian table separated by a "^" are the P(H|E) and P(~H|~E).
As you can see, the result is not correct either (because of the XOR problem) but it's better than with the plain Bayes version that gave hyp1 the probability 0.667. And since E1 and E2 are the same, E2 ended up with the values of 0.5 in the table, and applying it didn't change the weight.
If we change the order of events, E2 gains some use back:
Rather surprisingly, the result ended up more correct. Or maybe it's not that surprising: after all, AdaBoost is designed to gain more information from available data.
Yet another interesting result get produced from repeating the same pair of events multiple times:
AdaBoost converges pretty quickly to the weights that make both events get the probability 0.5 and stop the further changes.
This seems to work, although it needs more testing. One more limitation of this implementation is that it works only with the events that have the value of either 0 or 1, not anything in between. I'll talk more about this in the next post.
In retrospect the solution is pretty obvious: instead of computing the Bayesian model directly, treat it as an AdaBoost model whose set of the partial hypotheses equals to the set of the Bayesian events, with an extra limitation that each one of them must be used exactly once. If there are multiple equivalent events and they happen to go one after another, AdaBoost will treat the first one as real, and the following ones will get their error rate of 0.5 and will be effectively no-ops.
Well, if there are other events interspersed in between these equivalent copies, they won't be no-ops. These other events will shift the weights of the training cases, so that the second an further copies will find themselves drifted away from 0.5. The good news here is that AdaBoost is pretty good at removing the partial correlation too but the bad news is that the order matters, to fully remove the duplication the equivalent events should go one after another. And in general, it looks like the best removal of the cross-correlation happens when the closely related events follow closely one after another. This kind of order can be implemented if we reverse the AdaBoost preference of the partial hypotheses and make it always pick the one that has its training error rate closest to 0.5. Since (unlike the classic AdaBoost) the set of partial hypotheses is limited and each element from it must be used only once, the better ones will eventually be used as well.
To experiment with these ideas, I wrote the code example ex24_01run.pl. It doesn't reorder the events, just computes the AdaBoost values for whatever order it's given, allowing to experiment with the various orders. But it has a couple of advanced features from the later chapters of the book on AdaBoost: it does the multi-class (but single-label) version that also partitions the error rate computation for the sign of the value of the partial hypothesis.
The multi-class means that it can work not only with two outcomes (a yes/no decision) but with multiple possible outcomes (i.e. Bayesian hypotheses), just like the normal Bayesian table. And just like the normal Bayesian table, these outcomes must be mutually exclusive, so each case may have only one outcome (single-label). The multi-class logic works in the way that is similar to the one described in Part 10: the resulting table is just a combination of the individual per-outcome tables. From the standpoint of each outcome, the single-label property means that the rest of the rows of the table taken together represent the opposite of this outcome, so there is no need to compute that opposite explicitly.
The partitioning of the error rate computation not only makes the result better but also comes very handy to prove that the opposite of one outcome is equivalent to the rest of the rows of the table. The AdaBoost training error e is the ratio of the total weights of the training cases where the value of the event E (that is, the Bayesian event, in AdaBoost terms it's a partial hypothesis) is not equal to the value of the outcome (Bayesian hypothesis) H. And we'll compute it separately for E (i.e. E=1) and ~E (i.e. E=0). It ends up expressable as probabilities that can be computed by summing and dividing weights W of the training cases:
e(H,E) = P(~H|E) = (sum for cases i where H(i)=0 and E=1 (Wi))/(sum for cases j where E=1 (Wj))
e(H,~E) = P(H|~E) = (sum for cases i where H(i)=1 and E=0 (Wi))/(sum for cases j where E=0 (Wj))
So if we pick a particular outcome and denote it H1, we can show that its opposite ~H1 is equivalent to the sum of the rest of hypotheses H2...HN by showing that
P(~H1|E) = sum for i in [2, N] (P(Hi|E))
which after removing the common denominator means
(sum for cases j where H1(E)=0 and E=1 (Wj)) = (sum for i in [2, N] (sum for cases k where Hi(E)=1 and E=1 (Wk))
The single-label property means that each case is marked with exactly one outcome, and all the cases where the outcome H1 is absent must have some other outcome Hi present, so these sums are indeed equal.
So it is all self-consistent. The key part of the computation is:
for my $hyp (values %abhyp) {
if ($conf) {
$hyp->{wt} *= $hyp->{ppos}[$evi];
} else {
$hyp->{wt} *= (1. - $hyp->{pneg}[$evi]);
}
}
And the matching part of the table building is:
foreach my $c (@case) {
my $hyp = $c->{hyp}[0];
# this code really handles only the TC values of 0 and 1,
# for the arbitrary values it would have to do an interpolation
if ($c->{tc}[$i] >= 0.5) {
$c->{wt} /= $abhyp{$hyp}->{ppos}[$i];
} else {
$c->{wt} /= (1. - $abhyp{$hyp}->{pneg}[$i]);
}
}
The training undoes the weight change that will be done in the computation.
Now let's try some examples. Here is the example that I used in the whitepaper:
$ perl ex24_01run.pl -n tab24_01.txt in24_01_01.txt Original training cases: ! , ,E1 ,E2 ,E3 , hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,1.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00, AdaBoostian table: ! , ,E1 ,E2 ,E3 , hyp1 ,3.00000,0.66667^0.66667,0.50000^0.50000,0.40000^0.33333, hyp2 ,3.00000,0.33333^0.33333,0.50000^0.50000,0.60000^0.66667, --- Applying event E1, c=1.000000 hyp1 w=2.00000 p=0.66667 hyp2 w=1.00000 p=0.33333 --- Applying event E2, c=1.000000 hyp1 w=1.00000 p=0.66667 hyp2 w=0.50000 p=0.33333 --- Applying event E3, c=1.000000 hyp1 w=0.40000 p=0.57143 hyp2 w=0.30000 p=0.42857
Here the option "-n" means "don't normalize the weights" (or when normalized to the sum of 1 they will be the same as probabilities). The two values printed in the AdaBoostian table separated by a "^" are the P(H|E) and P(~H|~E).
As you can see, the result is not correct either (because of the XOR problem) but it's better than with the plain Bayes version that gave hyp1 the probability 0.667. And since E1 and E2 are the same, E2 ended up with the values of 0.5 in the table, and applying it didn't change the weight.
If we change the order of events, E2 gains some use back:
$ perl ex24_01run.pl -n tab24_02.txt in24_01_01.txt Original training cases: ! , ,E1 ,E3 ,E2 , hyp1 ,1.00000,1.00000/1.00,0.00000/1.00,1.00000/1.00, hyp1 ,1.00000,1.00000/1.00,0.00000/1.00,1.00000/1.00, hyp1 ,1.00000,0.00000/1.00,1.00000/1.00,0.00000/1.00, hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,1.00000/1.00,0.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00, AdaBoostian table: ! , ,E1 ,E3 ,E2 , hyp1 ,3.00000,0.66667^0.66667,0.40000^0.33333,0.47368^0.48276, hyp2 ,3.00000,0.33333^0.33333,0.60000^0.66667,0.52632^0.51724, --- Applying event E1, c=1.000000 hyp1 w=2.00000 p=0.66667 hyp2 w=1.00000 p=0.33333 --- Applying event E3, c=1.000000 hyp1 w=0.80000 p=0.57143 hyp2 w=0.60000 p=0.42857 --- Applying event E2, c=1.000000 hyp1 w=0.37895 p=0.54545 hyp2 w=0.31579 p=0.45455
Rather surprisingly, the result ended up more correct. Or maybe it's not that surprising: after all, AdaBoost is designed to gain more information from available data.
Yet another interesting result get produced from repeating the same pair of events multiple times:
$ perl ex24_01run.pl -n tab24_03.txt in24_03_01.txt Original training cases: ! , ,E01 ,E02 ,E11 ,E12 ,E21 ,E22 ,E31 ,E32 ,E41 ,E42 ,E51 ,E52 ,E61 ,E62 ,E71 ,E72 ,E81 ,E82 ,E91 ,E92 , hyp1 ,1.00000,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00, hyp1 ,1.00000,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00,0.00000/1.00,1.00000/1.00, hyp2 ,1.00000,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00,0.00000/1.00, AdaBoostian table: ! , ,E01 ,E02 ,E11 ,E12 ,E21 ,E22 ,E31 ,E32 ,E41 ,E42 ,E51 ,E52 ,E61 ,E62 ,E71 ,E72 ,E81 ,E82 ,E91 ,E92 , hyp1 ,3.00000,0.66667^0.66667,0.40000^0.33333,0.47368^0.48276,0.49694^0.49526,0.49916^0.49946,0.49990^0.49985,0.49997^0.49998,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000, hyp2 ,3.00000,0.33333^0.33333,0.60000^0.66667,0.52632^0.51724,0.50306^0.50474,0.50084^0.50054,0.50010^0.50015,0.50003^0.50002,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000,0.50000^0.50000, --- Applying event E01, c=1.000000 hyp1 w=2.00000 p=0.66667 hyp2 w=1.00000 p=0.33333 --- Applying event E02, c=1.000000 hyp1 w=0.80000 p=0.57143 hyp2 w=0.60000 p=0.42857 --- Applying event E11, c=1.000000 hyp1 w=0.37895 p=0.54545 hyp2 w=0.31579 p=0.45455 --- Applying event E12, c=1.000000 hyp1 w=0.18831 p=0.54242 hyp2 w=0.15886 p=0.45758 --- Applying event E21, c=1.000000 hyp1 w=0.09400 p=0.54159 hyp2 w=0.07956 p=0.45841 --- Applying event E22, c=1.000000 hyp1 w=0.04699 p=0.54149 hyp2 w=0.03979 p=0.45851 --- Applying event E31, c=1.000000 hyp1 w=0.02349 p=0.54147 hyp2 w=0.01990 p=0.45853 --- Applying event E32, c=1.000000 hyp1 w=0.01175 p=0.54146 hyp2 w=0.00995 p=0.45854 ... --- Applying event E92, c=1.000000 hyp1 w=0.00000 p=0.54146 hyp2 w=0.00000 p=0.45854
AdaBoost converges pretty quickly to the weights that make both events get the probability 0.5 and stop the further changes.
This seems to work, although it needs more testing. One more limitation of this implementation is that it works only with the events that have the value of either 0 or 1, not anything in between. I'll talk more about this in the next post.
Wednesday, February 22, 2017
a better explanation of Bayes-AdaBoost connection
After some re-reading, my previous posts on the Bayesian
interpretation of AdaBoost have been kind of cryptic. It's no wonder
because I've been writing them as I was understanding things, so they
came out as more of a personal reminder rather than the general
explanation. But I've got around and wrote another version as a
whitepaper, that goes all the way from scratch and hopefully is much
more understandable:
https://sourceforge.net/p/exbayes/code/HEAD/tree/whitepapers/AdaboostBayes.pdf?format=raw
https://sourceforge.net/p/exbayes/code/HEAD/tree/whitepapers/AdaboostBayes.pdf?format=raw
Friday, January 6, 2017
Bayesian networks & neural networks
I've been recently reading about the neural networks. By the way, here are some introductory links:
I can most highly recommend this document that explains in a very clear and simple way how the training of the neural networks through the backpropagation works:
http://www.numericinsight.com/uploads/A_Gentle_Introduction_to_Backpropagation.pdf
A simple introductory series of 6 (and maybe growing to more) articles starting with this one:
https://medium.com/@ageitgey/machine-learning-is-fun-80ea3ec3c471#.hxsoanuo2
Some other links:
http://karpathy.github.io/2015/05/21/rnn-effectiveness/
http://colah.github.io/posts/2015-08-Understanding-LSTMs/
https://colah.github.io/posts/2015-01-Visualizing-Representations/
http://mmlind.github.io/Deep_Neural_Network_for_MNIST_Handwriting_Recognition/
Also, the apparently the father of the deep neural networks is G.E. Hinton, and you may also want to search for the articles by Harry Shum. Hinton's home page is:
https://www.cs.toronto.edu/~hinton/
that seems to have a bunch of the links to his courses but I haven't looked at them yet.
As you can see from the introductory reading, each neuron in a neural network is a pretty simple machine: it takes some input values, multiples them by some coefficients, adds the results up, and then passes the result through a nonlinear (usually some kind of a sigmoid) function. The whole thing can be written as an expression:
result = nonlinear( sum [for inputs i] (inputi * Ci) )
The nonlinear part is pretty much what we do at the end of the Bayesian computations: if the probability of a hypothesis is above some level, we accept it as true, i.e. in other words pull it up to 1, if it's below some equal or lower level we reject it, i.e. pull it down to 0, and if these levels are not the same and the probability is in the middle then we leave it as some value in the middle, probably modified in some way from the original value.
The sum part is pretty much the same as the sum done in AdaBoost. AdaBoost does the sum of logarithms. And I've shown in the previous posts that this sum can be converted to a logarithm of a product, and then the product can be seen as a Bayesian computation expressed as chances, and the logarithm being a part of the decision-making process that converts the resulting chance value to a positive-or-negative value. So we can apply the same approach to the sum in the neuron, say that the values it sums up are logarithms, convert it to the logarithm of a product, make the logarithm a part of the final nonlinear function, and then the remaining product can be seen as a Bayesian computation on chances.
This pretty much means that a neuron can be seen as a Bayesian machine.
And guess what, apparently there is also such a thing as a Bayesian network. There people take multiple Bayesian machines, and connect the results of one set of machines as the input events to the Bayesian machines of the next level. For all I can tell, the major benefit of the handling of the problem when some hypotheses are indicated by a XOR of the input events, similarly to the splitting of the hypotheses into two and then merging them afterwards like I've shown before but instead of the external arithmetics the logic being folded into the Bayesian computation of the second level.
But if a neuron can be seen as a Bayesian machine then the neural networks can also be seen as the Bayesian networks! The only difference being that in the Bayesian networks the first-level (and in general intermediate-level) hypotheses are hand-picked while the neural networks find these intermediate hypotheses on their own during the training.
I wonder if this is something widely known, or not known, or known to be wrong?
I can most highly recommend this document that explains in a very clear and simple way how the training of the neural networks through the backpropagation works:
http://www.numericinsight.com/uploads/A_Gentle_Introduction_to_Backpropagation.pdf
A simple introductory series of 6 (and maybe growing to more) articles starting with this one:
https://medium.com/@ageitgey/machine-learning-is-fun-80ea3ec3c471#.hxsoanuo2
Some other links:
http://karpathy.github.io/2015/05/21/rnn-effectiveness/
http://colah.github.io/posts/2015-08-Understanding-LSTMs/
https://colah.github.io/posts/2015-01-Visualizing-Representations/
http://mmlind.github.io/Deep_Neural_Network_for_MNIST_Handwriting_Recognition/
Also, the apparently the father of the deep neural networks is G.E. Hinton, and you may also want to search for the articles by Harry Shum. Hinton's home page is:
https://www.cs.toronto.edu/~hinton/
that seems to have a bunch of the links to his courses but I haven't looked at them yet.
As you can see from the introductory reading, each neuron in a neural network is a pretty simple machine: it takes some input values, multiples them by some coefficients, adds the results up, and then passes the result through a nonlinear (usually some kind of a sigmoid) function. The whole thing can be written as an expression:
result = nonlinear( sum [for inputs i] (inputi * Ci) )
The nonlinear part is pretty much what we do at the end of the Bayesian computations: if the probability of a hypothesis is above some level, we accept it as true, i.e. in other words pull it up to 1, if it's below some equal or lower level we reject it, i.e. pull it down to 0, and if these levels are not the same and the probability is in the middle then we leave it as some value in the middle, probably modified in some way from the original value.
The sum part is pretty much the same as the sum done in AdaBoost. AdaBoost does the sum of logarithms. And I've shown in the previous posts that this sum can be converted to a logarithm of a product, and then the product can be seen as a Bayesian computation expressed as chances, and the logarithm being a part of the decision-making process that converts the resulting chance value to a positive-or-negative value. So we can apply the same approach to the sum in the neuron, say that the values it sums up are logarithms, convert it to the logarithm of a product, make the logarithm a part of the final nonlinear function, and then the remaining product can be seen as a Bayesian computation on chances.
This pretty much means that a neuron can be seen as a Bayesian machine.
And guess what, apparently there is also such a thing as a Bayesian network. There people take multiple Bayesian machines, and connect the results of one set of machines as the input events to the Bayesian machines of the next level. For all I can tell, the major benefit of the handling of the problem when some hypotheses are indicated by a XOR of the input events, similarly to the splitting of the hypotheses into two and then merging them afterwards like I've shown before but instead of the external arithmetics the logic being folded into the Bayesian computation of the second level.
But if a neuron can be seen as a Bayesian machine then the neural networks can also be seen as the Bayesian networks! The only difference being that in the Bayesian networks the first-level (and in general intermediate-level) hypotheses are hand-picked while the neural networks find these intermediate hypotheses on their own during the training.
I wonder if this is something widely known, or not known, or known to be wrong?
Saturday, August 27, 2016
AdaBoost 9: Boost by majority afterthought
After some time I've realized that all this monkeying with the conditional probabilities in the Bayesian table is not necessary. You can just throw away a whole training case or a part of it and continue like nothing happened, the probabilities should stay consistent anyway. After all, the point of adjusting the weights after each round opposite to how the run-time weights would be changed is to give each training case an equal chance. But if we don't want to give some training case an equal chance then there is no point in treating it equally, an ignored training case can be simply ignored.
Another thought is that it looks like the two-pass approach can be used to find what training cases to throw away in a dynamic way. We can do it by splitting the set of available cases randomly in half. Then use one half for the first pass of training of N rounds and remember the weights throughout it. Then test the effectiveness of this training on the second half of the cases. But not just run the N rounds in the test. Instead, keep the test results for using only 1 round, 2 rounds, 3 rounds, and so on all the way to the N rounds. Then see the number of rounds on which the test did best, say K rounds. Going back to the training weights, we can find, what training cases were not getting guessed well at K rounds. We can mark them as outliers. Then repeat the same thing swapping the two halves, and find the outliers in the second half. Then throw away the outliers and do the second pass of training on the rest of the cases.
Another thought is that it looks like the two-pass approach can be used to find what training cases to throw away in a dynamic way. We can do it by splitting the set of available cases randomly in half. Then use one half for the first pass of training of N rounds and remember the weights throughout it. Then test the effectiveness of this training on the second half of the cases. But not just run the N rounds in the test. Instead, keep the test results for using only 1 round, 2 rounds, 3 rounds, and so on all the way to the N rounds. Then see the number of rounds on which the test did best, say K rounds. Going back to the training weights, we can find, what training cases were not getting guessed well at K rounds. We can mark them as outliers. Then repeat the same thing swapping the two halves, and find the outliers in the second half. Then throw away the outliers and do the second pass of training on the rest of the cases.
Saturday, August 20, 2016
AdaBoost 8: Boost by majority
When I wrote before
The premise of boosting is that we're able to find a number of methods (what they call "hypotheses" in AdaBoost) to predict the correct outcomes of the training cases, each method correctly predicting more than 50% of the training cases. Then if we collect a large-ish number of these methods, we can predict the correct outcomes of all the training cases simply by averaging the predictions of these methods. And the other cases will follow the training cases (unless an overfitting happens). Since more than 50% of the cases are correctly predicted by each method, after the averaging more than 50% of the votes for each training case will be correct, and thus the result will be correct too. Of course this depends on the correct predictions being distributed pretty evenly among the cases. If we have a thousand methods that predict correctly the same cases and incorrectly the other cases, obviously after averaging these other cases will still be predicted incorrectly. So the selection of methods must somehow shuffle the preference for the cases, so that the next picked method will predict well the cases that have been predicted poorly by the previous picked methods. That's it, that's the whole basic idea. It's a bit of an oversimplification but it's easy to understand.
I really did mean it as an oversimplification, since AdaBoost uses the Bayesian decisions to do much better than the simple majority counting. Little did I know that there actually is the method of Boost By Majority (BBM) that does just the counting. It has some other differences but more about that later.
The simple averaging can be simulated through the Bayesian means too. Just use the same confidence for each event. Incidentally, that's what the NonAdaBoost algorithm, also known as epsilon-Boost does: it looks for the weak hypotheses that have at least a fixed "edge" gamma (i.e. the probability of the right guess being at least 0.5+gamma) and then always sets the confidence C=0.5+gamma, and uses the same value to adjust the weights of the training cases.
The NonAdaBoost is essentially a version of AdaBoost with a fixed confidence, and suffering from this defect. But Boost By Majority has another big difference: the way it adjusts the weight of the training cases. The formula it uses is pretty complicated, so I won't even try to reproduce it here. But here is the gist: it keeps track of how many rounds are left to the end of the boosting and what is the balance of the votes collected by each training case. If the modulo of the balance is higher than the number of rounds left, it means that the fate of this case can't be changed any more: it's either guaranteed to be guessed right if the balance is positive or guaranteed to be guessed wrong if the balance is negative, so the algorithm gives up on these cases. It gives the most weight to the most undecided cases, and spreads the rest of the weights in the bell shape of the binomial distribution. The result is that unlike AdaBoost and NonAdaBoost, BBM doesn't concentrate on the hardest cases that are likely to be the noise in the data anyway, and thus reduces the overfitting.
The last chapter of the book is about a combination of AdaBoost and BBM called BrownBoost (from the Brownian motion), or also "boosting in continuous time". It starts with the idea that if the returned partial hypothesis has a higher edge than minimally needed, it might still have enough edge after the re-weighting the training cases, then it can be directly reused on the next round too without searching for a new one, and so on until its edge wears off. This gets developed into an algorithm that uses a real number in the range [0,1) instead of the round count, with the actual rounds moving the current point on it by the varying amounts. The speed of the movement is determined by the pre-set desired training error. This training error gets reached when the end of the range is reached. If the target error is set to 0, the algorithm behaves in the same way as AdaBoost.
The downside is that the algorithm is complex, there isn't even a formula for determining the confidence values for each partial hypothesis. Instead you get a system of two equations that connect this confidence value and advancement through the range to be solved numerically. In the great scheme of things it's not a big deal, after all, compared to the finding of the partial hypotheses this shouldn't be such a big overhead. But it's not easy to think of. And the proof of the validity of this algorithm is quite complicated.
I can't help thinking of a couple of simpler ideas.
The first idea, or should I say guess, is that when we do AdaBoost, it fits into a Bayesian model. So if we keep this Bayesian model consistent, the boosting should still be valid. Obviously, I have no proper proof of that but it looks like a reasonable assumption. There is an easy way to take some training case (or a part of its weight) out of rotation and still keep the Bayesian model consistent.
Remember, previously I've described that we start with a Bayesian table that contains each individual training case
Which then gets conflated into a two-line table, all the cases with the true outcome combined into one line, and the false ones into another line. The conditional probabilities in the table get averaged during conflation but since it's an averaging of all ones (or all zeroes), the result is still one (or zero).
To take a training case out of rotation, we just change its conditional probability in all the following events (that match the AdaBoost's partial hypotheses) to 0.5. This says that no future events will affect it. And accordingly we set the AdaBoost weight of it to 0. Such decisions can be made according to any algorithm, matching any desired curve.
For example, suppose that we decide to take a case out of rotation when its weight relative to the sum of all weights reaches 0.1 (this is probably not a very good rule, since it allows at most 10 cases to be excluded, but simple for the sake of demonstration). Suppose that its a case with the true ("1") outcome. And suppose that all the weights of all the true cases are totaling to the same value as of all the false cases, each of them having the relative weight of 0.5 (not very likely in reality but just as good a number as any other).
After the disablement, the conditional probability of the true cases will become ((0.5*0.1) + (1 * 0.4))/0.5 = 0.9.
Once a training case gets disabled, it stays disabled for all the future rounds, and the AdaBoost keeps acting only on the weights of those training cases that still have 1 or 0 for the conditional probability. Obviously, the more you disable, the less will be the effect of the following rounds when the Bayesian computation runs.
Interestingly though the edges of the partial hypotheses will be higher. Remember, the training cases that get thrown away get it for being difficult to predict. So suppose the partial hypothesis EvN would have returned the confidence of 0.8 if that case wasn't thrown away and had guessed that case wrong. When we throw away the stubborn case, that would become 0.8 out of former 0.9, so the confidence becomes 0.8/0.9 = 0.89, an improvement!
However all this throwing-away has no effect on the previous rounds, these are already set in stone. Which begs an easy solution which is my second idea: why not do two passes of AdaBoost? After the first pass look at the final weights of the training cases to determine the most stubborn ones. Throw them away and do the second pass from scratch. After all, BrownBoost requires an adjustment of the target training error which gets done by running it multiple times with the different values and then selecting the best one. Doing two passes of AdaBoost isn't any worse than that.
The premise of boosting is that we're able to find a number of methods (what they call "hypotheses" in AdaBoost) to predict the correct outcomes of the training cases, each method correctly predicting more than 50% of the training cases. Then if we collect a large-ish number of these methods, we can predict the correct outcomes of all the training cases simply by averaging the predictions of these methods. And the other cases will follow the training cases (unless an overfitting happens). Since more than 50% of the cases are correctly predicted by each method, after the averaging more than 50% of the votes for each training case will be correct, and thus the result will be correct too. Of course this depends on the correct predictions being distributed pretty evenly among the cases. If we have a thousand methods that predict correctly the same cases and incorrectly the other cases, obviously after averaging these other cases will still be predicted incorrectly. So the selection of methods must somehow shuffle the preference for the cases, so that the next picked method will predict well the cases that have been predicted poorly by the previous picked methods. That's it, that's the whole basic idea. It's a bit of an oversimplification but it's easy to understand.
I really did mean it as an oversimplification, since AdaBoost uses the Bayesian decisions to do much better than the simple majority counting. Little did I know that there actually is the method of Boost By Majority (BBM) that does just the counting. It has some other differences but more about that later.
The simple averaging can be simulated through the Bayesian means too. Just use the same confidence for each event. Incidentally, that's what the NonAdaBoost algorithm, also known as epsilon-Boost does: it looks for the weak hypotheses that have at least a fixed "edge" gamma (i.e. the probability of the right guess being at least 0.5+gamma) and then always sets the confidence C=0.5+gamma, and uses the same value to adjust the weights of the training cases.
The NonAdaBoost is essentially a version of AdaBoost with a fixed confidence, and suffering from this defect. But Boost By Majority has another big difference: the way it adjusts the weight of the training cases. The formula it uses is pretty complicated, so I won't even try to reproduce it here. But here is the gist: it keeps track of how many rounds are left to the end of the boosting and what is the balance of the votes collected by each training case. If the modulo of the balance is higher than the number of rounds left, it means that the fate of this case can't be changed any more: it's either guaranteed to be guessed right if the balance is positive or guaranteed to be guessed wrong if the balance is negative, so the algorithm gives up on these cases. It gives the most weight to the most undecided cases, and spreads the rest of the weights in the bell shape of the binomial distribution. The result is that unlike AdaBoost and NonAdaBoost, BBM doesn't concentrate on the hardest cases that are likely to be the noise in the data anyway, and thus reduces the overfitting.
The last chapter of the book is about a combination of AdaBoost and BBM called BrownBoost (from the Brownian motion), or also "boosting in continuous time". It starts with the idea that if the returned partial hypothesis has a higher edge than minimally needed, it might still have enough edge after the re-weighting the training cases, then it can be directly reused on the next round too without searching for a new one, and so on until its edge wears off. This gets developed into an algorithm that uses a real number in the range [0,1) instead of the round count, with the actual rounds moving the current point on it by the varying amounts. The speed of the movement is determined by the pre-set desired training error. This training error gets reached when the end of the range is reached. If the target error is set to 0, the algorithm behaves in the same way as AdaBoost.
The downside is that the algorithm is complex, there isn't even a formula for determining the confidence values for each partial hypothesis. Instead you get a system of two equations that connect this confidence value and advancement through the range to be solved numerically. In the great scheme of things it's not a big deal, after all, compared to the finding of the partial hypotheses this shouldn't be such a big overhead. But it's not easy to think of. And the proof of the validity of this algorithm is quite complicated.
I can't help thinking of a couple of simpler ideas.
The first idea, or should I say guess, is that when we do AdaBoost, it fits into a Bayesian model. So if we keep this Bayesian model consistent, the boosting should still be valid. Obviously, I have no proper proof of that but it looks like a reasonable assumption. There is an easy way to take some training case (or a part of its weight) out of rotation and still keep the Bayesian model consistent.
Remember, previously I've described that we start with a Bayesian table that contains each individual training case
CaseId Weight Outcome Ev1 ... EvT 1 1 * true 1 ... 1 ... M 1 * false 0 ... 0
Which then gets conflated into a two-line table, all the cases with the true outcome combined into one line, and the false ones into another line. The conditional probabilities in the table get averaged during conflation but since it's an averaging of all ones (or all zeroes), the result is still one (or zero).
Weight Outcome Ev1 ... EvT 1 * true 1 ... 1 1 * false 0 ... 0
To take a training case out of rotation, we just change its conditional probability in all the following events (that match the AdaBoost's partial hypotheses) to 0.5. This says that no future events will affect it. And accordingly we set the AdaBoost weight of it to 0. Such decisions can be made according to any algorithm, matching any desired curve.
For example, suppose that we decide to take a case out of rotation when its weight relative to the sum of all weights reaches 0.1 (this is probably not a very good rule, since it allows at most 10 cases to be excluded, but simple for the sake of demonstration). Suppose that its a case with the true ("1") outcome. And suppose that all the weights of all the true cases are totaling to the same value as of all the false cases, each of them having the relative weight of 0.5 (not very likely in reality but just as good a number as any other).
After the disablement, the conditional probability of the true cases will become ((0.5*0.1) + (1 * 0.4))/0.5 = 0.9.
Weight Outcome Ev1 ... EvN-1 EvN ... 1 * true 1 ... 1 0.9 ... 1 * false 0 ... 0 0 ...
Once a training case gets disabled, it stays disabled for all the future rounds, and the AdaBoost keeps acting only on the weights of those training cases that still have 1 or 0 for the conditional probability. Obviously, the more you disable, the less will be the effect of the following rounds when the Bayesian computation runs.
Interestingly though the edges of the partial hypotheses will be higher. Remember, the training cases that get thrown away get it for being difficult to predict. So suppose the partial hypothesis EvN would have returned the confidence of 0.8 if that case wasn't thrown away and had guessed that case wrong. When we throw away the stubborn case, that would become 0.8 out of former 0.9, so the confidence becomes 0.8/0.9 = 0.89, an improvement!
However all this throwing-away has no effect on the previous rounds, these are already set in stone. Which begs an easy solution which is my second idea: why not do two passes of AdaBoost? After the first pass look at the final weights of the training cases to determine the most stubborn ones. Throw them away and do the second pass from scratch. After all, BrownBoost requires an adjustment of the target training error which gets done by running it multiple times with the different values and then selecting the best one. Doing two passes of AdaBoost isn't any worse than that.
Saturday, August 6, 2016
AdaBoost 7: multi-class & unseen combinations
The basic idea behind the multi-class (and also multi-label, i.e. where each case may have more than one outcome) AdaBoost can be described as boosting the recognition of all the outcomes in parallel. It takes the "yes or no" dichotomies for all the outcomes, and on each round it tries to find such a partial hypothesis where the sum of Z for all of them is minimal. This is very similar to what was described in the part 6, where multiple ranges were added, each with its own confidence. The difference is in the formula for the final computation: in the multi-class version there is a separate formula for each class that uses only the confidence values that all the training rounds computed for this particular class.
There is also a possible optimization for the situation where there may be only one outcome per case (i.e. single-label), saying that the mapping between the dichotomies used in the logic above and the outcomes doesn't have to be one-to-one. Instead each outcomes can be mapped to a unique combination (or multiple combinations) of the dichotomies. The dichotomies can be selected on some smart way, say if we're trying to recognize the handwritten digits, they can be "pointy vs roundy", "a loop on the bottom vs no loop at the bottom" etc. Or just by just dividing the outcomes in half in some blind way, like "0,1,2,3,4 vs 5,6,7,8,9", "0,2,4,6,8 vs 1,3,5,7,9" etc.
Returning to the multi-label situation, one of the problems I've experienced with it is the ability to recognize the combinations of outcomes that weren't present in the training data. That is, the outcomes were present but none of the training cases had exactly this combination. For the basic diagnostics, this can be discounted by saying "but what's the percentage of such cases" but when you start pushing the quality of diagnosis around 95%, it turns out that great many of the remaining misdiagnosed cases fall into this category.
AdaBoost doesn't have any built-in solution for this problem. The solution it produces is only as good as the underlying algorithm. There is nothing in AdaBoost that puts the pressure on the underlying algorithm to recognize the combinations that aren't present in the training data. If the underlying algorithm can do it anyway (and perhaps despite the pressure from AdaBoost), the resulting combined formula will be able to do it too. If it can't then the combined formula won't either. The simple algorithms like the decision stumps can't.
But maybe some multi-pass schemes can be devised. Run the boosting once, get a set of the candidate symptoms (i.e. partial hypotheses). Use these symptoms on the training cases to try to differentiate, which symptom is related to which outcome. Then run the boosting the second time from scratch, only this time with the relevance knowledge mixed in: whenever a symptom that is close to an irrelevant one is tested on a training case, make it return "I don't know", i.e. the confidence 0.5. This will shift the choice of symptoms. Obviously, if using the resulting formula, the same pruning of irrelevance has to be applied there in the same way. The symptoms from the second pass can be re-tested for relevance, and if any change is found, the third pass can be made, and so on.
Or even better, perhaps this logic can be merged directly into each round of the underlying algorithm in one pass of AdaBoost: when a candidate partial hypothesis (i.e. symptom) is found, measure its relevance right there and change its Z-value accordingly. Pick the candidate that has the lowest Z-value even after it has been corrected for the relevance. Include the relevance information into the partial hypothesis.
There is also a possible optimization for the situation where there may be only one outcome per case (i.e. single-label), saying that the mapping between the dichotomies used in the logic above and the outcomes doesn't have to be one-to-one. Instead each outcomes can be mapped to a unique combination (or multiple combinations) of the dichotomies. The dichotomies can be selected on some smart way, say if we're trying to recognize the handwritten digits, they can be "pointy vs roundy", "a loop on the bottom vs no loop at the bottom" etc. Or just by just dividing the outcomes in half in some blind way, like "0,1,2,3,4 vs 5,6,7,8,9", "0,2,4,6,8 vs 1,3,5,7,9" etc.
Returning to the multi-label situation, one of the problems I've experienced with it is the ability to recognize the combinations of outcomes that weren't present in the training data. That is, the outcomes were present but none of the training cases had exactly this combination. For the basic diagnostics, this can be discounted by saying "but what's the percentage of such cases" but when you start pushing the quality of diagnosis around 95%, it turns out that great many of the remaining misdiagnosed cases fall into this category.
AdaBoost doesn't have any built-in solution for this problem. The solution it produces is only as good as the underlying algorithm. There is nothing in AdaBoost that puts the pressure on the underlying algorithm to recognize the combinations that aren't present in the training data. If the underlying algorithm can do it anyway (and perhaps despite the pressure from AdaBoost), the resulting combined formula will be able to do it too. If it can't then the combined formula won't either. The simple algorithms like the decision stumps can't.
But maybe some multi-pass schemes can be devised. Run the boosting once, get a set of the candidate symptoms (i.e. partial hypotheses). Use these symptoms on the training cases to try to differentiate, which symptom is related to which outcome. Then run the boosting the second time from scratch, only this time with the relevance knowledge mixed in: whenever a symptom that is close to an irrelevant one is tested on a training case, make it return "I don't know", i.e. the confidence 0.5. This will shift the choice of symptoms. Obviously, if using the resulting formula, the same pruning of irrelevance has to be applied there in the same way. The symptoms from the second pass can be re-tested for relevance, and if any change is found, the third pass can be made, and so on.
Or even better, perhaps this logic can be merged directly into each round of the underlying algorithm in one pass of AdaBoost: when a candidate partial hypothesis (i.e. symptom) is found, measure its relevance right there and change its Z-value accordingly. Pick the candidate that has the lowest Z-value even after it has been corrected for the relevance. Include the relevance information into the partial hypothesis.
Saturday, July 2, 2016
AdaBoost 6: multiple confidence ranges & other thoughts
One of the chapters I quickly read through was on using a better estimation of probability of the success of the partial hypotheses (in the AdaBoost sense), with the following example:
Suppose, the underlying algorithm found a decision stump, and finds that it can classify the cases having a value above some limit pretty well (say, 90% of them are "+1") while the cases with the values under this limit are undifferentiated (say, 49% of them are "+1"). In this case if we allow the underlying algorithm to return the values not only +1 and -1 but also 0 for when it can't differentiate well, the boosting goes much better.
Since the part 3 I've been wondering if the algorithm can be improved in an obvious way by using the separate confidence values for the situations when the underlying algorithm returns +1 or -1 (or in equivalent Bayesian terms, 1 or 0), and maybe even do better than that by forming multiple "bands" of training cases by some rule and assigning a separate confidence values to each band, and maybe even further by computing an individual confidence value for each case. The idea above shows that it can, and the book then goes on to the exact same idea of multiple bands, each with its own confidence value, and on to the partial hypotheses returning the individual confidence values for each training case. So that idea really was obvious, and there is not much point in writing more about it. The only tricky part is the minimalization criteria, but that becomes straightforward from the description in the part 4.
One more idea would be to make the decision stumps not discrete ("1" on this side of this value, "0" on the other side) but graduated, with the confidence being 0.5 at the value and growing towards 1 on one side and towards 0 on the other side. Possibly saturating at some distance from the center point value.
An easy example of saturation would be this: If we're classifying a set of points in a 2-dimensional space with the decision stumps based on the coordinate values, this means that on each step we find some value of a coordinate (X or Y) and say that the points on one side have mostly the value "1" and on the other side they have mostly the value "0". Then the classic AdaBoost approach (without the square root in the confidence) takes the confidence C as the fraction of the points whose values got guessed right. Or, translating from the pair (value, confidence) to the just the confidence, the pair (1, C) becomes C, and the pair (0, C) becomes (1-C). But the breaking point is usually not one point, it's a range between the coordinate values closest to this break. The classic approach is to pick the centerpoint of this range as the breaking point. But we could say that the confidence changes linearly between these two coordinate values and beyond this range saturates to C and (1-C). This smooth transition could help with the training on the data with errors in it. The book contains an example of training on the data that contained 20% of errors which led to overfitting over many rounds of boosting. The smooth transitions could provide the averaging that would counteract this overfitting. Maybe.
Another thought that occurred to me is what if we're boosting while we're boosting? Or in other words, what if the partial algorithm runs a few rounds of boosting on its own? How can it be equivalently represented as a single round of boosting?
This looks like a good example where an individual value of the confidence for each training case would be handy. As we go through the execution stage, the weight of each example would be multiplied on each round of "nested boosting" in the same way as if would be on each round of normal boosting. I.e. if a round of boosting had the confidence C, and guessed this particular training case right, the weight of this training case will be multiplied by C, and if it guessed this training case wrong, the weight would be multiplied by (1-C).
So if we define the effective confidence Ce as:
(if the round guessed right, its Ce=C, otherwise its Ce=1-C)
the we can see that the multiplier will be:
product for rounds t(Cet)
Except that it's not properly scaled to be in the range [0..1]. To adjust the scaling, it has to become
product for rounds t(Cet) / (product for rounds t(Cet) + product for rounds t(1-Cet))
There won't be a single confidence value for all the training cases of such a composite round, each training case will have its own confidence value, with the probability of pointing towards 0 or 1 built into it.
One more interesting thing I've read is that after some number of rounds AdaBoost tends to start going in a circle through the same set of distributions (or sometimes not quite the same but very close). To me this looks like an indication that it's time to stop. Boosting the margins by going through this loop repeatedly looks like cheating, because if we look at its Bayesian meaning, this meaning implies that the events that get examined must be essentially independent of each other. But if we repeatedly examine the same events, they're not independent, they're extra copies of the events that have already been seen. Thus re-applying them repeatedly doesn't seem right. On the other hand, the events in such a loop do form this loop because they represent each event in a balanced way. So maybe the right thing to do is to throw away everything before this loop too, and just leave one iteration of this loop as the only events worth examining. This would be interesting to test if/when I get around to do it.
Suppose, the underlying algorithm found a decision stump, and finds that it can classify the cases having a value above some limit pretty well (say, 90% of them are "+1") while the cases with the values under this limit are undifferentiated (say, 49% of them are "+1"). In this case if we allow the underlying algorithm to return the values not only +1 and -1 but also 0 for when it can't differentiate well, the boosting goes much better.
Since the part 3 I've been wondering if the algorithm can be improved in an obvious way by using the separate confidence values for the situations when the underlying algorithm returns +1 or -1 (or in equivalent Bayesian terms, 1 or 0), and maybe even do better than that by forming multiple "bands" of training cases by some rule and assigning a separate confidence values to each band, and maybe even further by computing an individual confidence value for each case. The idea above shows that it can, and the book then goes on to the exact same idea of multiple bands, each with its own confidence value, and on to the partial hypotheses returning the individual confidence values for each training case. So that idea really was obvious, and there is not much point in writing more about it. The only tricky part is the minimalization criteria, but that becomes straightforward from the description in the part 4.
One more idea would be to make the decision stumps not discrete ("1" on this side of this value, "0" on the other side) but graduated, with the confidence being 0.5 at the value and growing towards 1 on one side and towards 0 on the other side. Possibly saturating at some distance from the center point value.
An easy example of saturation would be this: If we're classifying a set of points in a 2-dimensional space with the decision stumps based on the coordinate values, this means that on each step we find some value of a coordinate (X or Y) and say that the points on one side have mostly the value "1" and on the other side they have mostly the value "0". Then the classic AdaBoost approach (without the square root in the confidence) takes the confidence C as the fraction of the points whose values got guessed right. Or, translating from the pair (value, confidence) to the just the confidence, the pair (1, C) becomes C, and the pair (0, C) becomes (1-C). But the breaking point is usually not one point, it's a range between the coordinate values closest to this break. The classic approach is to pick the centerpoint of this range as the breaking point. But we could say that the confidence changes linearly between these two coordinate values and beyond this range saturates to C and (1-C). This smooth transition could help with the training on the data with errors in it. The book contains an example of training on the data that contained 20% of errors which led to overfitting over many rounds of boosting. The smooth transitions could provide the averaging that would counteract this overfitting. Maybe.
Another thought that occurred to me is what if we're boosting while we're boosting? Or in other words, what if the partial algorithm runs a few rounds of boosting on its own? How can it be equivalently represented as a single round of boosting?
This looks like a good example where an individual value of the confidence for each training case would be handy. As we go through the execution stage, the weight of each example would be multiplied on each round of "nested boosting" in the same way as if would be on each round of normal boosting. I.e. if a round of boosting had the confidence C, and guessed this particular training case right, the weight of this training case will be multiplied by C, and if it guessed this training case wrong, the weight would be multiplied by (1-C).
So if we define the effective confidence Ce as:
(if the round guessed right, its Ce=C, otherwise its Ce=1-C)
the we can see that the multiplier will be:
product for rounds t(Cet)
Except that it's not properly scaled to be in the range [0..1]. To adjust the scaling, it has to become
product for rounds t(Cet) / (product for rounds t(Cet) + product for rounds t(1-Cet))
There won't be a single confidence value for all the training cases of such a composite round, each training case will have its own confidence value, with the probability of pointing towards 0 or 1 built into it.
One more interesting thing I've read is that after some number of rounds AdaBoost tends to start going in a circle through the same set of distributions (or sometimes not quite the same but very close). To me this looks like an indication that it's time to stop. Boosting the margins by going through this loop repeatedly looks like cheating, because if we look at its Bayesian meaning, this meaning implies that the events that get examined must be essentially independent of each other. But if we repeatedly examine the same events, they're not independent, they're extra copies of the events that have already been seen. Thus re-applying them repeatedly doesn't seem right. On the other hand, the events in such a loop do form this loop because they represent each event in a balanced way. So maybe the right thing to do is to throw away everything before this loop too, and just leave one iteration of this loop as the only events worth examining. This would be interesting to test if/when I get around to do it.
Tuesday, June 28, 2016
AdaBoost 5: the square root and the confidence value
The question of what should be used as the confidence value for Bayesian computations is a thorny one. In my previous take on it I've used the value without a square root, while the classic AdaBoost formula uses the one with the square root. Which one is more right?
Both of them produce the same decision for the classification of the cases. The difference is in the absolute value of the chances, or in the AdaBoost terms, the margin (with the classic AdaBoost also applying the logarithm on top).
I still think that using the value without the square root has the more correct "physical meaning". But either can be used with the same result.
Following the classic AdaBoost, the version of the confidence with the square root follows from the expression
Z = sum for all good cases i (Wi / S) + sum for all bad cases j (Wj * S)
Z = sum for all good cases i (Wi * (C-1) / C) + sum for all bad cases j (Wj * C / (C-1))
Just like the last post, W is the weight of a particular training case, same as D(i) in the classic AdaBoost terms, just since I've been using weights rather than a distribution, the letter W comes easier to my mind.
The "physical meaning" here is that the weights of the training cases for the next round of boosting are adjusted opposite to how the chances of these training cases get affected by this round during the final computation. If a training case gets predicted correctly by a partial hypothesis, its weight will get multiplied by C and the weight of the other cases will be multiplied by (1-C), so the changes will get multiplied by C/(1-C), and for the next round of boosting the good cases get divided by that to compensate. For the cases that get predicted incorrectly, the opposite happens.
This translates to
C / (1-C) = S = sqrt((1-e) / e) = sqrt(1-e) / sqrt(e)
The last expression does NOT mean
C = sqrt(1-e)
Instead, it means
C = sqrt(1-e) / (sqrt(1-e) + sqrt(e))
Alternatively, the approach without the square root starts with the premise
Z = sum for all good cases i (Wi / C) + sum for all bad cases j (Wj / (1-C))
The "physical meaning" is as described before, the weights of the training cases for the next round of boosting are adjusted opposite to how the weights of these training cases get affected by this round during the final computation. It seems to me that compensating the weights for the changes in weights is the more correct "physical meaning" than compensating the weights for the changes in chances.
This translates to
C / (1-C) = S2 = sqrt( (1-e) / e )2 = (1-e) / e
and
C = (1-e)
By the way, chasing this version through the derivatives as shown in the previous post was interesting. I've appreciated why the authors of AdaBoost involved the exponents into the formulas: doing the derivatives and integrals with the exponents is much easier than without them. Then I've realized that with the derivatives where S = exp(Alpha) I'm computing dZ/dAlpha, not dZ/dC. And that is the correct approach. So without the exponents I should be computing the dZ/dS, and that gets easy again.
So, the real version of AdaBoost described in the third part is this:
Given: (x1, y1), ..., (xm, ym) where xi belongs to X, yi belongs to {-1, +1}.
Initialize: D1(i) = 1 for i = 1, ..., m.
For t = 1, ..., T:
H(x) {
chance = 1;
for t=1,...,T {
if (ht(x) > 0) {
chance *= Ct/(1-Ct);
} else
chance *= (1-Ct)/Ct;
}
}
return sign(chance - 1)
}
Having this sorted out, I can move on to more creative versions of the algorithm where on a step of boosting the different training cases may get stamped with the different confidence values C.
Both of them produce the same decision for the classification of the cases. The difference is in the absolute value of the chances, or in the AdaBoost terms, the margin (with the classic AdaBoost also applying the logarithm on top).
I still think that using the value without the square root has the more correct "physical meaning". But either can be used with the same result.
Following the classic AdaBoost, the version of the confidence with the square root follows from the expression
Z = sum for all good cases i (Wi / S) + sum for all bad cases j (Wj * S)
Z = sum for all good cases i (Wi * (C-1) / C) + sum for all bad cases j (Wj * C / (C-1))
Just like the last post, W is the weight of a particular training case, same as D(i) in the classic AdaBoost terms, just since I've been using weights rather than a distribution, the letter W comes easier to my mind.
The "physical meaning" here is that the weights of the training cases for the next round of boosting are adjusted opposite to how the chances of these training cases get affected by this round during the final computation. If a training case gets predicted correctly by a partial hypothesis, its weight will get multiplied by C and the weight of the other cases will be multiplied by (1-C), so the changes will get multiplied by C/(1-C), and for the next round of boosting the good cases get divided by that to compensate. For the cases that get predicted incorrectly, the opposite happens.
This translates to
C / (1-C) = S = sqrt((1-e) / e) = sqrt(1-e) / sqrt(e)
The last expression does NOT mean
C = sqrt(1-e)
Instead, it means
C = sqrt(1-e) / (sqrt(1-e) + sqrt(e))
Alternatively, the approach without the square root starts with the premise
Z = sum for all good cases i (Wi / C) + sum for all bad cases j (Wj / (1-C))
The "physical meaning" is as described before, the weights of the training cases for the next round of boosting are adjusted opposite to how the weights of these training cases get affected by this round during the final computation. It seems to me that compensating the weights for the changes in weights is the more correct "physical meaning" than compensating the weights for the changes in chances.
This translates to
C / (1-C) = S2 = sqrt( (1-e) / e )2 = (1-e) / e
and
C = (1-e)
By the way, chasing this version through the derivatives as shown in the previous post was interesting. I've appreciated why the authors of AdaBoost involved the exponents into the formulas: doing the derivatives and integrals with the exponents is much easier than without them. Then I've realized that with the derivatives where S = exp(Alpha) I'm computing dZ/dAlpha, not dZ/dC. And that is the correct approach. So without the exponents I should be computing the dZ/dS, and that gets easy again.
So, the real version of AdaBoost described in the third part is this:
Given: (x1, y1), ..., (xm, ym) where xi belongs to X, yi belongs to {-1, +1}.
Initialize: D1(i) = 1 for i = 1, ..., m.
For t = 1, ..., T:
- Train the basic algorithm using the weights Dt.
- Get weak hypothesis ht: X -> {-1, +1}.
- Aim: select ht to minimalize the boundary on the training error Zt where:
Wgoodt = 0; Wbadt = 0;
for i = 1, ..., m {
if ht(xi) = yi {
Wgoodt += Dt(i)
} else {
Wbadt += Dt(i)
}
}
Ct = Wgoodt / (Wgoodt + Wbadt)
Zt = Wgoodt/Ct + Wbadt/(1-Ct)
which can also be represented symmetrically through St:
Zt = Wgoodt/St + Wbadt*St
St = sqrt(Ct / (1-Ct)) = sqrt(Wgoodt / Wbadt)
and substituting St:
Zt = Wgoodt / sqrt(Wgoodt / Wbadt) + Wbadt * sqrt(Wgoodt / Wbadt)
= 2 * sqrt(Wgoodt * Wbadt)
Which gets minimalized when either of Wgoodt or Wbadt gets minimalized, but to be definitive we prefer to minimalize Wbadt.
- Update,
for i = 1, ..., m {
if ht(xi) != yi; {
Dt+1(i) = Dt(i) / (1-Ct)
} else {
Dt+1(i) = Dt(i) / Ct
}
}
H(x) {
chance = 1;
for t=1,...,T {
if (ht(x) > 0) {
chance *= Ct/(1-Ct);
} else
chance *= (1-Ct)/Ct;
}
}
return sign(chance - 1)
}
Having this sorted out, I can move on to more creative versions of the algorithm where on a step of boosting the different training cases may get stamped with the different confidence values C.
Subscribe to:
Posts (Atom)