5 ms·

The body of literature you are looking for is called statistical learning theory. If you are interested, you can start with Vapnik's two books, but that is what

by srean 13y ago

The body of literature you are looking for is called statistical learning theory. If you are interested, you can start with Vapnik's two books, but that is what I said, a start. The theory of Learning has shifted quite a bit, but the fundamentals remain the same. Once you are up to speed with Vapnik you can start reading proceedings of COLT and ALT (computational learning theory and algorithmic learning theory respectively). You will find the following 3 types of guarantees i) Strong assumptions on the knowledge of the stochastic process generating the data to back guarantees on the algorithm ii) No assumptions on the on the data generating process except that it is governed by some unknown independent stochastic process. Prove guarantees on the output of the algorithm iii) Don't even assume that the data generation process is stochastic yet provide guarantees on the output. What exactly is guaranteed will of course differ. Little advice, smugness as demonstrated with ...I figured it out 16 years ago yo bitches, will not help your cause whatever that might be. BTW are you H. A. Dye, 'cause Dye figured out group structures on measure preserving transformations in 1959 a little bit earlier than 16 years ago...just saying.

graycat 13y ago
I was commenting on the OP. I started reading it but found just 'algorithms' with no indication of anything like any guarantees or qualities for them. Your i) sounds good. E.g., in stochastic dynamic programming with assumptions reasonably expected, e.g., essentially a Markov assumption, we can easily prove that the number crunching yields the decisions with the least possible expected cost from any 'measurable' means of manipulating the data. And once when I argued this, I also included a proof that additional data independent of what we already wouldn't help either. This result is, of course, 'obvious' although obvious is not a proof. The proof turned out to be just a light tap with Fubini's theorem. So, good: Some people actually argue that some of the algorithms actually have some desirable qualities. So, the world is not totally coming apart at the seams or being turned over to naive hackers who only know to watch the code run and then conclude qualitative that it seems 'nice'. On your ii), "some unknown independent stochastic process", that's not so clear. So, for some index set I and random variables X(i) for i in I, the set { X(i) | i in I } is independent? That's something of an unusual and, in practice, not very interesting stochastic process. Maybe some EEs would call that 'white noise'. On your iii), sorry, but essentially everything is 'stochastic'. Even a 'deterministic' process is stochastic, in practice usually is also Markov (past and future conditionally independent given the present). Thanks for the reference to H. A. Dye. I went on to show how such a group leads easily to statistical hypothesis tests. That is, in particular I was making sense out of 'resampling' and 'bootstrap' plans. In part I got the idea of considering 'measure preserving', of course, from ergodic theory where measure preserving transformations are central, but the transformations I used, and needed for the statistics, are the ones that ergodic theory throws out. No, I'm not Dye. That's the first I heard of Dye's paper. Thanks. At one point long after publishing I saw remark in one of the volumes of Dunford and Schwartz, as I recall, attributed to Norbert Wiener, that maybe something could be done with the 'periodic' case where, thus, there is a finite group. Never heard of Vapnik. Thanks for the reference. From a simple Google, found at http://vserver1.cscs.lsa.umich.edu/~crshalizi/reviews/vapnik-nature/ http://vserver1.cscs.lsa.umich.edu/~crshalizi/reviews/vapnik... a review The Bactra Review: Occasional and eclectic book reviews by Cosma Shalizi The Nature of Statistical Learning Theory by V. N. Vapnik Okay, Vapnik is trying to do some mathematics to show some desirable mathematical properties of some of statistical learning theory, maybe in particular some of the algorithms. Good. The review is a bit tough on Vapnik's writings from when he was writing in Russia. That's sad: The famous Russian texts on probability and stochastic processes, usually from Springer, were exemplary and with beautifully done translations to English, e.g., E. Dynkin, R. Lipster, etc. I can'f find where I said "yo bitches". But I do believe that a proposed algorithm should do something, that what it does should be clear, good, and demonstrated, hopefully with some theorems and proofs. Knuth's TACP was big on 'analysis' of algorithms, but from the OP and, say, Prof Ng's course on machine learning it appears that the analysis part is being omitted. Broadly, it looks like (1) statistics, optimization, stochastic processes are old fields and no longer very popular, at least in the US where they might be in departments of mathematics which, however, in the US, mostly don't like those fields; (2) computing is a new field and has lots of grant money, interest, and students; (3) for an actual application, those old fields need computing to do the specified data manipulations; (4) computing wants to take on some of the problems the old fields worked on and, then, is at risk of putting poor versions of good old wine in new bottles with new labels. This is a form of 'academic theft'? Well, if not, if the new wine is poor, then it's a form of academic dilution. Not good.
- srean 13y ago
  Well its a HN comment not a scientific communication. Scenario (i) is mostly considered uninteresting and "solved" because it assumes that the particular stochastic process generating the data is known (this was the pre-Vapnik model). In most practical cases, however, one does not know the corresponding measure from which the data was generated (and will be generated in future). The old school thinking was that one should estimate the generating distribution, and then solve for the optimal decision, based on the estimate. Vapnik showed that it is far better to do it directly without bothering to estimate the distribution which in itself is a non-trivial problem. So (ii) is the more interesting case that machine learners care to handle and Vapnik's was one of the first breakthrough fundamental result in this formalism. It applies to all algorithms that does something called structural risk minimization, not just one specific algorithm. His bound applies to all generating distributions, all samples, and all structural risk minimization algorithms ! However in this set up we still need to assume independence. Some form of independence, even in some weak form needs to be present. But it is quite remarkable that you can give guarantees on performance regardless of what actual distribution generated the data. I should also mention Leslie Valiant. Lookup PAC learning you will understand the basic premise of this style. One genuine criticism is that it is overly conservative (and it has to be, because it is giving guarantees that applies for the worst distribution, worst training sample, worst algorithm...). (iii) Removes the need for independent draws. If you want to read up on these, search for "regret minimization." In this setup the guarantees hold for all sequence of data, even if adversarially generated by someone who knows the algorithm you will employ. Some geometric assumptions are necessary on the domain and some function analytic ones on the function that you are trying to minimize (typically convex. Non-differentiable functions are allowed). -- Shalizi's Review -- Shalizi writes good stuff but this review of Vapnik's book is surprisingly mean spirited. The field of course has progressed after Vapnik and there are legitimate criticisms that one can raise, but the review exhibits bad form, I think. Prior to Vapnik there were very few results that one could state outside of the statistical physics community (that worked with strong assumptions, typically Gaussian noise etc) -- Aside -- No you did not say the word "yo bitches" but that was the attitude you demonstrated. Before casting judgments as you did at least make an effort to familiarize yourself with the background. And that is exactly what it is, background. A machine learner will not even mention these things because you are expected to know these things if you are in this field. -- Re: Analysis being omitted -- Think of it this way, one doesn't really need to know precise chemistry of hydrocarbon combustion to drive a car, conversely, knowledge of such chemistry alone is useless unless it is teamed up with good engineering and in this case algorithm. There is a huge difference between showing that minimizing a particular function has nice properties and actually coming up with a piece of code to efficiently minimize such a function, not just in theory where constants can be conveniently swept under the rug, but also in practice. So dont be too quick to dismiss the "naive coders". Most importantly, practice, almost always precedes explanation and analysis in engineering. Usually practitioners find the algorithms in their hacky ways. The analyst/theorist smoothens the kinks and explains why the method works so well after it has been demonstrated to work so well-- not always, but almost always.

by srean 13y ago

graycat 13y ago

I was commenting on the OP. I started reading it but found just 'algorithms' with no indication of anything like any guarantees or qualities for them. Your i) sounds good. E.g., in stochastic dynamic programming with assumptions reasonably expected, e.g., essentially a Markov assumption, we can easily prove that the number crunching yields the decisions with the least possible expected cost from any 'measurable' means of manipulating the data. And once when I argued this, I also included a proof that additional data independent of what we already wouldn't help either. This result is, of course, 'obvious' although obvious is not a proof. The proof turned out to be just a light tap with Fubini's theorem. So, good: Some people actually argue that some of the algorithms actually have some desirable qualities. So, the world is not totally coming apart at the seams or being turned over to naive hackers who only know to watch the code run and then conclude qualitative that it seems 'nice'. On your ii), "some unknown independent stochastic process", that's not so clear. So, for some index set I and random variables X(i) for i in I, the set { X(i) | i in I } is independent? That's something of an unusual and, in practice, not very interesting stochastic process. Maybe some EEs would call that 'white noise'. On your iii), sorry, but essentially everything is 'stochastic'. Even a 'deterministic' process is stochastic, in practice usually is also Markov (past and future conditionally independent given the present). Thanks for the reference to H. A. Dye. I went on to show how such a group leads easily to statistical hypothesis tests. That is, in particular I was making sense out of 'resampling' and 'bootstrap' plans. In part I got the idea of considering 'measure preserving', of course, from ergodic theory where measure preserving transformations are central, but the transformations I used, and needed for the statistics, are the ones that ergodic theory throws out. No, I'm not Dye. That's the first I heard of Dye's paper. Thanks. At one point long after publishing I saw remark in one of the volumes of Dunford and Schwartz, as I recall, attributed to Norbert Wiener, that maybe something could be done with the 'periodic' case where, thus, there is a finite group. Never heard of Vapnik. Thanks for the reference. From a simple Google, found at http://vserver1.cscs.lsa.umich.edu/~crshalizi/reviews/vapnik-nature/ http://vserver1.cscs.lsa.umich.edu/~crshalizi/reviews/vapnik... a review The Bactra Review: Occasional and eclectic book reviews by Cosma Shalizi The Nature of Statistical Learning Theory by V. N. Vapnik Okay, Vapnik is trying to do some mathematics to show some desirable mathematical properties of some of statistical learning theory, maybe in particular some of the algorithms. Good. The review is a bit tough on Vapnik's writings from when he was writing in Russia. That's sad: The famous Russian texts on probability and stochastic processes, usually from Springer, were exemplary and with beautifully done translations to English, e.g., E. Dynkin, R. Lipster, etc. I can'f find where I said "yo bitches". But I do believe that a proposed algorithm should do something, that what it does should be clear, good, and demonstrated, hopefully with some theorems and proofs. Knuth's TACP was big on 'analysis' of algorithms, but from the OP and, say, Prof Ng's course on machine learning it appears that the analysis part is being omitted. Broadly, it looks like (1) statistics, optimization, stochastic processes are old fields and no longer very popular, at least in the US where they might be in departments of mathematics which, however, in the US, mostly don't like those fields; (2) computing is a new field and has lots of grant money, interest, and students; (3) for an actual application, those old fields need computing to do the specified data manipulations; (4) computing wants to take on some of the problems the old fields worked on and, then, is at risk of putting poor versions of good old wine in new bottles with new labels. This is a form of 'academic theft'? Well, if not, if the new wine is poor, then it's a form of academic dilution. Not good.

srean 13y ago
Well its a HN comment not a scientific communication. Scenario (i) is mostly considered uninteresting and "solved" because it assumes that the particular stochastic process generating the data is known (this was the pre-Vapnik model). In most practical cases, however, one does not know the corresponding measure from which the data was generated (and will be generated in future). The old school thinking was that one should estimate the generating distribution, and then solve for the optimal decision, based on the estimate. Vapnik showed that it is far better to do it directly without bothering to estimate the distribution which in itself is a non-trivial problem. So (ii) is the more interesting case that machine learners care to handle and Vapnik's was one of the first breakthrough fundamental result in this formalism. It applies to all algorithms that does something called structural risk minimization, not just one specific algorithm. His bound applies to all generating distributions, all samples, and all structural risk minimization algorithms ! However in this set up we still need to assume independence. Some form of independence, even in some weak form needs to be present. But it is quite remarkable that you can give guarantees on performance regardless of what actual distribution generated the data. I should also mention Leslie Valiant. Lookup PAC learning you will understand the basic premise of this style. One genuine criticism is that it is overly conservative (and it has to be, because it is giving guarantees that applies for the worst distribution, worst training sample, worst algorithm...). (iii) Removes the need for independent draws. If you want to read up on these, search for "regret minimization." In this setup the guarantees hold for all sequence of data, even if adversarially generated by someone who knows the algorithm you will employ. Some geometric assumptions are necessary on the domain and some function analytic ones on the function that you are trying to minimize (typically convex. Non-differentiable functions are allowed). -- Shalizi's Review -- Shalizi writes good stuff but this review of Vapnik's book is surprisingly mean spirited. The field of course has progressed after Vapnik and there are legitimate criticisms that one can raise, but the review exhibits bad form, I think. Prior to Vapnik there were very few results that one could state outside of the statistical physics community (that worked with strong assumptions, typically Gaussian noise etc) -- Aside -- No you did not say the word "yo bitches" but that was the attitude you demonstrated. Before casting judgments as you did at least make an effort to familiarize yourself with the background. And that is exactly what it is, background. A machine learner will not even mention these things because you are expected to know these things if you are in this field. -- Re: Analysis being omitted -- Think of it this way, one doesn't really need to know precise chemistry of hydrocarbon combustion to drive a car, conversely, knowledge of such chemistry alone is useless unless it is teamed up with good engineering and in this case algorithm. There is a huge difference between showing that minimizing a particular function has nice properties and actually coming up with a piece of code to efficiently minimize such a function, not just in theory where constants can be conveniently swept under the rug, but also in practice. So dont be too quick to dismiss the "naive coders". Most importantly, practice, almost always precedes explanation and analysis in engineering. Usually practitioners find the algorithms in their hacky ways. The analyst/theorist smoothens the kinks and explains why the method works so well after it has been demonstrated to work so well-- not always, but almost always.