B****x
发帖数: 17 | 1 STOC 2009 Valiant Workshop
http://www.umiacs.umd.edu/conferences/stoc2009/valiant-program.
Program for the Valiant 60th Birthday Celebration:
Stephen Cook
Pebbles and Branching Programs
Paul Valiant
Leveraging Collusion in Unrestricted Combinatorial Auctions
Michael Rabin
Completely Anonymous, Secure, Verifiable, and Secrecy Preserving
Auctions
Vijay Vazirani
Combinatorial Algorithms for Convex Programs Capturing Market Equilibria
and Nash Bargaining Solutions
Rocco Servedio
A Quarter-Century of Efficient Learnability
Michael Kearns
Computational Learning Theory and Beyond
Vitaly Feldman
On the Learning Power of Evolution
Mike Paterson
Strassen Symmetries
Jin-Yi Cai
Proving Dichotomy Theorems for Counting Problems
Mark Jerrum
The Permanent: Algorithms
Avi Wigderson
Valiant's Permanent Gift to Complexity Theory |
d******e
发帖数: 7844 | 2 没人说他不牛，现在是在和Vapnik比。
不过图灵奖这东西就是个虚名，50年后的Machine Learning教材里，SVM还会是重头戏
，Statistical Learning Theory也将带着Vapnik的名字名垂青史。
你们现在谁能马上完整的说出最近10年的图灵奖获得者？这东西也就是爽一时而已嘛。
永远是挖大坑的人才能被人传诵，只能说PAC这个坑还不够大。
【在 B****x 的大作中提到】
: STOC 2009 Valiant Workshop
: http://www.umiacs.umd.edu/conferences/stoc2009/valiant-program.
: Program for the Valiant 60th Birthday Celebration:
: Stephen Cook
: Pebbles and Branching Programs
: Paul Valiant
: Leveraging Collusion in Unrestricted Combinatorial Auctions
: Michael Rabin
: Completely Anonymous, Secure, Verifiable, and Secrecy Preserving
: Auctions
|
w***g
发帖数: 5958 | 3 我不知道vapnik当初搞SVM是怎么搞出来的。但是我上学时教授教的顺序是先PAC，然后
VC dimension，然后再SVM，所有这些都在PAC的框架上做的。我不是说Vapnik不牛，他
从贡献上来说早就够诺贝尔奖了。但是这个Valiant即使不如Vapnik，差的也不大。
(看了 BudFox的回帖再补充一下，PAC和SVM可能没关系。话说我上的那门课是Robert
Schapire教的，所以SVM就被PAC给统一了。)
再说statistical learning theory。这东西现在这么火主要就是出了个SVM。别的理论
也不是没有，只是因为没有像SVM这么好用的，所以就都被比下去了。这么多learning方
法，SVM胜出了，30%是理论好，30%是时代背景，还有30%是运气。十年前neural
network多火？现在还有多少人用？
再说时代背景。很难说50年后是什么状态，但我比较倾向认为10年后SVM就会让位于K-N
N。什么算法最流行，很大程度上决定于当时的计算机性能和数据规模的。一旦SVM退出
了历史舞台，statistical learning theory也就会慢慢被人淡忘。到时候牛气的就是我
们这些搞K-NN的。但说不定20年以后计算机性能和数据规模的对比又有很大的改变，到
时候SVM换个名字就又出来了（话说这东东50年前叫perceptron,当然从理论上来看完全
就不是一回事）。
【在 d******e 的大作中提到】
: 没人说他不牛，现在是在和Vapnik比。
: 不过图灵奖这东西就是个虚名，50年后的Machine Learning教材里，SVM还会是重头戏
: ，Statistical Learning Theory也将带着Vapnik的名字名垂青史。
: 你们现在谁能马上完整的说出最近10年的图灵奖获得者？这东西也就是爽一时而已嘛。
: 永远是挖大坑的人才能被人传诵，只能说PAC这个坑还不够大。
|
B****x
发帖数: 17 | 4 computational learning theory is just one of Valiant's fields. and PAC
theory had led to practical algorithms too, such as boosting.
Christos Papadimitriou also deserves a Turing Award.
【在 d******e 的大作中提到】
: 没人说他不牛，现在是在和Vapnik比。
: 不过图灵奖这东西就是个虚名，50年后的Machine Learning教材里，SVM还会是重头戏
: ，Statistical Learning Theory也将带着Vapnik的名字名垂青史。
: 你们现在谁能马上完整的说出最近10年的图灵奖获得者？这东西也就是爽一时而已嘛。
: 永远是挖大坑的人才能被人传诵，只能说PAC这个坑还不够大。
|
d******e
发帖数: 7844 | 5 到现在为止，很多实际问题中，人们仍然还只能玩玩small sample size，所谓大规模
数据，只是p大罢了，所以SVM很有市场。
即使是在大规模的n，比如text，SVM依然有用武之地，随着更快的优化算法和并行算法
的出现，SVM老当益壮，参见ICML 09的Best Paper。
learning方
-N
【在 w***g 的大作中提到】
: 我不知道vapnik当初搞SVM是怎么搞出来的。但是我上学时教授教的顺序是先PAC，然后
: VC dimension，然后再SVM，所有这些都在PAC的框架上做的。我不是说Vapnik不牛，他
: 从贡献上来说早就够诺贝尔奖了。但是这个Valiant即使不如Vapnik，差的也不大。
: (看了 BudFox的回帖再补充一下，PAC和SVM可能没关系。话说我上的那门课是Robert
: Schapire教的，所以SVM就被PAC给统一了。)
: 再说statistical learning theory。这东西现在这么火主要就是出了个SVM。别的理论
: 也不是没有，只是因为没有像SVM这么好用的，所以就都被比下去了。这么多learning方
: 法，SVM胜出了，30%是理论好，30%是时代背景，还有30%是运气。十年前neural
: network多火？现在还有多少人用？
: 再说时代背景。很难说50年后是什么状态，但我比较倾向认为10年后SVM就会让位于K-N
|
p*********g
发帖数: 226 | 6 > 50年后的Machine Learning教材里，SVM还会是重头戏
你还真别说，现在哪本教材里 SVM 是重头戏？即使是 Alex Smola 现在在写的教材也
不是（他和 Scholkopf 那本当然不算教材），Robert Schapire, Kevin Murphy 在写
的更不是了。至于 Elements of machine learning, PRML, Tom Mitchel 的就更不提
了。
真的等你写书时，发现 SVM 也就是群星中的一颗。现在火的原因 wdong 讲得差不多了。
【在 d******e 的大作中提到】
: 没人说他不牛，现在是在和Vapnik比。
: 不过图灵奖这东西就是个虚名，50年后的Machine Learning教材里，SVM还会是重头戏
: ，Statistical Learning Theory也将带着Vapnik的名字名垂青史。
: 你们现在谁能马上完整的说出最近10年的图灵奖获得者？这东西也就是爽一时而已嘛。
: 永远是挖大坑的人才能被人传诵，只能说PAC这个坑还不够大。
|
d******e
发帖数: 7844 | 7 所以说还是politics
【在 B****x 的大作中提到】
: computational learning theory is just one of Valiant's fields. and PAC
: theory had led to practical algorithms too, such as boosting.
: Christos Papadimitriou also deserves a Turing Award.
|
p*********g
发帖数: 226 | 8 > 参见ICML 09的Best Paper。
哪一张？
【在 d******e 的大作中提到】
: 到现在为止，很多实际问题中，人们仍然还只能玩玩small sample size，所谓大规模
: 数据，只是p大罢了，所以SVM很有市场。
: 即使是在大规模的n，比如text，SVM依然有用武之地，随着更快的优化算法和并行算法
: 的出现，SVM老当益壮，参见ICML 09的Best Paper。
:
: learning方
: -N
|
B****x
发帖数: 17 | 9 未必。PAC theory is not necessarily Valiant's best work. See the 1986
Nevanlinna Prize citation:
``Valiant has contributed in a decisive way to the growth of almost every
branch of the fast growing young tree of theoretical computer science, his
theory of counting problems being perhaps his most important and mature
work''
【在 d******e 的大作中提到】
: 所以说还是politics
|
d******e
发帖数: 7844 | 10 说“重头戏”是有些过头了，但你看ESL第12章，SVM独立占据了一个章节，PRML的第7
章也算是围着SVM说。
就好比Neural Network，过了几十年了，哪本书里没有再过20年，也还会在教科书里
。你找一个单独有PAC章节的教材来看看？
了。
【在 p*********g 的大作中提到】
: > 参见ICML 09的Best Paper。
: 哪一张？
|
|
|
d******e
发帖数: 7844 | 11 sorry,typo 2008
"SVM Optimization: Inverse Dependence on Training Set Size" Shai Shalev-
Shwartz and Nathan Srebro. ICML 2008
【在 p*********g 的大作中提到】
: > 参见ICML 09的Best Paper。
: 哪一张？
|
p*********g
发帖数: 226 | 12 ESL 共18章，PRML 共14章，SVM 占半章。
> 就好比Neural Network，过了几十年了，哪本书里没有
我想问，哪本书里有？
7
书里
【在 d******e 的大作中提到】
: 说“重头戏”是有些过头了，但你看ESL第12章，SVM独立占据了一个章节，PRML的第7
: 章也算是围着SVM说。
: 就好比Neural Network，过了几十年了，哪本书里没有再过20年，也还会在教科书里
: 。你找一个单独有PAC章节的教材来看看？
:
: 了。
|
p*********g
发帖数: 226 | 13 Shai 这张 paper 实在是个大joke，无非是优化里的 stochastic gradient descent
的一个 verbatim 应用。
【在 d******e 的大作中提到】
: sorry,typo 2008
: "SVM Optimization: Inverse Dependence on Training Set Size" Shai Shalev-
: Shwartz and Nathan Srebro. ICML 2008
|
d******e
发帖数: 7844 | 14 NN PRML第5章ESL第11章
【在 p*********g 的大作中提到】
: ESL 共18章，PRML 共14章，SVM 占半章。
: > 就好比Neural Network，过了几十年了，哪本书里没有
: 我想问，哪本书里有？
:
: 7
: 书里
|
p*********g
发帖数: 226 | 15 thanks, interesting.
Chris Bishop 早年专做NN的，可以理解。
三个 stanford 的牛也讲nn，有点意思。
【在 d******e 的大作中提到】
: NN PRML第5章ESL第11章
|
d******e
发帖数: 7844 | 16 NN虽然过时，但是地位在那里摆着呢。
那个PAC，我实在不知道哪本书里能给他留个地儿。
【在 p*********g 的大作中提到】
: thanks, interesting.
: Chris Bishop 早年专做NN的，可以理解。
: 三个 stanford 的牛也讲nn，有点意思。
|
p*********g
发帖数: 226 | 17 老实说，可能PAC不容易学，而且不讲它也能讲别的方法，实用中也不需要 PAC。
不过要真的搞 ml 研究，PAC 还是要学的。
就像 SLT，基本上所有教材都不提或略过，但其重要性不言而喻。
【在 d******e 的大作中提到】
: NN虽然过时，但是地位在那里摆着呢。
: 那个PAC，我实在不知道哪本书里能给他留个地儿。
|
B****x
发帖数: 17 | 18 there is a monograph:
An Introduction to Computational Learning Theory
Michael J. Kearns and Umesh V. Vazirani, The MIT Press, 1994
【在 p*********g 的大作中提到】
: 老实说，可能PAC不容易学，而且不讲它也能讲别的方法，实用中也不需要 PAC。
: 不过要真的搞 ml 研究，PAC 还是要学的。
: 就像 SLT，基本上所有教材都不提或略过，但其重要性不言而喻。
|
p*********g
发帖数: 226 | 19 这个自然不能作教材，除非专门的 theoretic ml 课
Kearns 的数学文笔确实令人陶醉啊
【在 B****x 的大作中提到】
: there is a monograph:
: An Introduction to Computational Learning Theory
: Michael J. Kearns and Umesh V. Vazirani, The MIT Press, 1994
|
b******x
发帖数: 826 | 20 说句公道话
NN容易上手，到处都是代码
PAC难懂，写成教材了也不是很多人能学的
你们都是学理论的哈
我们这种作应用的人都不会怎么考虑PAC这样的问题
作理论的人永远是少数
【在 d******e 的大作中提到】
: NN虽然过时，但是地位在那里摆着呢。
: 那个PAC，我实在不知道哪本书里能给他留个地儿。
|
|
|
b******x
发帖数: 826 | 21
-NN
KNN means "K-nearest-neighbor"吗？在数据量趋于无穷的时候，KNN无敌
哈哈
【在 w***g 的大作中提到】
: 我不知道vapnik当初搞SVM是怎么搞出来的。但是我上学时教授教的顺序是先PAC，然后
: VC dimension，然后再SVM，所有这些都在PAC的框架上做的。我不是说Vapnik不牛，他
: 从贡献上来说早就够诺贝尔奖了。但是这个Valiant即使不如Vapnik，差的也不大。
: (看了 BudFox的回帖再补充一下，PAC和SVM可能没关系。话说我上的那门课是Robert
: Schapire教的，所以SVM就被PAC给统一了。)
: 再说statistical learning theory。这东西现在这么火主要就是出了个SVM。别的理论
: 也不是没有，只是因为没有像SVM这么好用的，所以就都被比下去了。这么多learning方
: 法，SVM胜出了，30%是理论好，30%是时代背景，还有30%是运气。十年前neural
: network多火？现在还有多少人用？
: 再说时代背景。很难说50年后是什么状态，但我比较倾向认为10年后SVM就会让位于K-N
|
d******e
发帖数: 7844 | 22 Andrew Ng的CS229有讲SLT
【在 p*********g 的大作中提到】
: 老实说，可能PAC不容易学，而且不讲它也能讲别的方法，实用中也不需要 PAC。
: 不过要真的搞 ml 研究，PAC 还是要学的。
: 就像 SLT，基本上所有教材都不提或略过，但其重要性不言而喻。
|
p*********g
发帖数: 226 | 23 好吧，我说教材，你开始扯到 course 了。
这个随意性就大了，Robert Shapire COS 511 还讲 PAC 呢。下学期我也讲讲 PAC 的
一些基本概念，其实都没什么大不了的。这种撩一下皮毛的东西说明不了什么。
【在 d******e 的大作中提到】
: Andrew Ng的CS229有讲SLT
|
p*********g
发帖数: 226 | 24 现在在高维情况下knn发展地怎么样了？
【在 b******x 的大作中提到】
:
: -NN
: KNN means "K-nearest-neighbor"吗？在数据量趋于无穷的时候，KNN无敌
: 哈哈
|
d******e
发帖数: 7844 | 25 n->inf的时候还要考虑p->inf的速度的
【在 b******x 的大作中提到】
:
: -NN
: KNN means "K-nearest-neighbor"吗？在数据量趋于无穷的时候，KNN无敌
: 哈哈
|
d******e
发帖数: 7844 | 26 这就取决于多高维算高维了。
【在 p*********g 的大作中提到】
: 现在在高维情况下knn发展地怎么样了？
|
i*********8
发帖数: 3229 | 27 说说他除了灌水，理论上做了啥杰出贡献？
唯一放的上台面的就是PAC，已经N多人指出PAC跟SVM比就是nothing。
【在 B****x 的大作中提到】
: STOC 2009 Valiant Workshop
: http://www.umiacs.umd.edu/conferences/stoc2009/valiant-program.
: Program for the Valiant 60th Birthday Celebration:
: Stephen Cook
: Pebbles and Branching Programs
: Paul Valiant
: Leveraging Collusion in Unrestricted Combinatorial Auctions
: Michael Rabin
: Completely Anonymous, Secure, Verifiable, and Secrecy Preserving
: Auctions
|
d******e
发帖数: 7844 | 28 讲一点是一点。
再说Andrew Ng把自己的lecture notes整理整理也能出书。
【在 p*********g 的大作中提到】
: 好吧，我说教材，你开始扯到 course 了。
: 这个随意性就大了，Robert Shapire COS 511 还讲 PAC 呢。下学期我也讲讲 PAC 的
: 一些基本概念，其实都没什么大不了的。这种撩一下皮毛的东西说明不了什么。
|
i*********8
发帖数: 3229 | 29 什么乱七八糟连smola也出来了
他那功力写个上台面tutorial都够呛，你大概不知道author和editor的区别吧？
了。
【在 p*********g 的大作中提到】
: 现在在高维情况下knn发展地怎么样了？
|
d******e
发帖数: 7844 | 30 你觉得被引用2000次的Tutorial能上台面么？
【在 i*********8 的大作中提到】
: 什么乱七八糟连smola也出来了
: 他那功力写个上台面tutorial都够呛，你大概不知道author和editor的区别吧？
:
: 了。
|
|
|
i*********8
发帖数: 3229 | 31 他自己写的那个tutorial也是写svr的吧
靠vapnik讨生活的。
【在 d******e 的大作中提到】
: 你觉得被引用2000次的Tutorial能上台面么？
|
p*********g
发帖数: 226 | 32 真希望这样啊。Andrew 天才啊，而且是个会上课的天才。
【在 d******e 的大作中提到】
: 讲一点是一点。
: 再说Andrew Ng把自己的lecture notes整理整理也能出书。
|
i*********8
发帖数: 3229 | 33 你这档次太低了，属于对科普很感兴趣的民科
Elements of ML, PRML那都是写人家的东西，没成系统的原创
这两本书加起来citation才4K还不到VPKNIK一本书的零头。
了。
【在 p*********g 的大作中提到】
: 真希望这样啊。Andrew 天才啊，而且是个会上课的天才。
|
i*********8
发帖数: 3229 | 34 跟vapnik比就是个杰出的工程师而已。
【在 p*********g 的大作中提到】
: 真希望这样啊。Andrew 天才啊，而且是个会上课的天才。
|
p*********g
发帖数: 226 | 35 哈哈，你再下去可以转 joke 版了，改天你上 intro to ml 课，把 Vapnik 的书从头
教到尾试试。
【在 i*********8 的大作中提到】
: 你这档次太低了，属于对科普很感兴趣的民科
: Elements of ML, PRML那都是写人家的东西，没成系统的原创
: 这两本书加起来citation才4K还不到VPKNIK一本书的零头。
:
: 了。
|
d******e
发帖数: 7844 | 36 你先回答能不能上台面
【在 i*********8 的大作中提到】
: 他自己写的那个tutorial也是写svr的吧
: 靠vapnik讨生活的。
|
i*********8
发帖数: 3229 | 37 一般，我读phd的时候写的还有400多次引用呢呢。
【在 d******e 的大作中提到】
: 你先回答能不能上台面
|
d******e
发帖数: 7844 | 38 http://scholar.google.com/scholar?hl=en&q=tutorial&btnG=Search&
Check No.9
【在 i*********8 的大作中提到】
: 一般，我读phd的时候写的还有400多次引用呢呢。
|
i*********8
发帖数: 3229 | 39 你是不是半路出家的文科生？
抛弃内容不讲，你讲话非常缺乏逻辑。
【在 p*********g 的大作中提到】
: 哈哈，你再下去可以转 joke 版了，改天你上 intro to ml 课，把 Vapnik 的书从头
: 教到尾试试。
|
p*********g
发帖数: 226 | 40 哈哈，说你自己吧，就知道google一下、比比citation数字，然后胡搅蛮缠一番。
典型的文科生，还不带半路出嫁的，半路烂校 phd 读不下去quit倒有可能。
这些偷换概念、转换话题、避重就轻、指鹿为马的伎俩，留到你的
chinanews/military 去用吧，不送。
【在 i*********8 的大作中提到】
: 你是不是半路出家的文科生？
: 抛弃内容不讲，你讲话非常缺乏逻辑。
|
|
|
r********3
发帖数: 2998 | 41 为啥老是有是那么崇拜Vapnik和SVM呢？
为啥我看待SVM就是一个quatric programming的优化问题？
【在 d******e 的大作中提到】
: 没人说他不牛，现在是在和Vapnik比。
: 不过图灵奖这东西就是个虚名，50年后的Machine Learning教材里，SVM还会是重头戏
: ，Statistical Learning Theory也将带着Vapnik的名字名垂青史。
: 你们现在谁能马上完整的说出最近10年的图灵奖获得者？这东西也就是爽一时而已嘛。
: 永远是挖大坑的人才能被人传诵，只能说PAC这个坑还不够大。
|
r********3
发帖数: 2998 | 42 我刚也看了一下，这篇文章是有点问题。
它开篇的例子是说，给定1000个数据，就能够达到5%的generation error。那么我有10
倍1000的数据，意味着我有更多的资源，我training的performance不应该比资源少的
时候更差。
你说的stochastic gradient descent在这里是有道理的。数据少的时候，你为什么不
能用stochastic gradient descent？为什么每个数据要反复看，反复纠正你的margin
？你不确定training出来到底好不好，所以必须找尽量的margin，给你尽量大的
classification confidence。
当你数据多的时候，为什么可以用stochastic gradient descent？因为你数据多，即
便每个数据的利用度很低，总共扫完所有数据之后，我一样可以达到一个比较准确的分
界面。
于是，stochastic gradient descent每个数据只扫一遍，当然就比原先反复看，
interoir point反复迭代得快了。
但是，我个人觉得，两者根本不具备比较性。这个跟解决大数据的问题是两码事。如果
这样也算是解决大数据集的问题，那跟sample的方法没多大区别。那么任何一个算法都
可以解决任意大的数据集。因为，只要我都只sample很小的数据集来做training就行了。
【在 p*********g 的大作中提到】
: Shai 这张 paper 实在是个大joke，无非是优化里的 stochastic gradient descent
: 的一个 verbatim 应用。
|
p*********g
发帖数: 226 | 43 呵呵，这当然要分析 rates。不过基本上优化里的人早就把这些研究透了。
10
margin
【在 r********3 的大作中提到】
: 我刚也看了一下，这篇文章是有点问题。
: 它开篇的例子是说，给定1000个数据，就能够达到5%的generation error。那么我有10
: 倍1000的数据，意味着我有更多的资源，我training的performance不应该比资源少的
: 时候更差。
: 你说的stochastic gradient descent在这里是有道理的。数据少的时候，你为什么不
: 能用stochastic gradient descent？为什么每个数据要反复看，反复纠正你的margin
: ？你不确定training出来到底好不好，所以必须找尽量的margin，给你尽量大的
: classification confidence。
: 当你数据多的时候，为什么可以用stochastic gradient descent？因为你数据多，即
: 便每个数据的利用度很低，总共扫完所有数据之后，我一样可以达到一个比较准确的分
|
r********3
发帖数: 2998 | 44 不过，这篇paper的要说明的问题，和处理large scale data是两回事。
前面有人跟帖说看好KNN的，认为KNN是真正解决large scale data的。KNN跟这篇paper
在对待大数据集上有本质的区别。 这个本质区别在于，KNN可以和数据库的存储索引和
查询优化这些结合起来。而这些技术才是解决真正意义上大规模数据集训练的渠道，而
不是一些局部小trick，五十步和百步的区别。
Yahoo Research Lab的director说过。实际大数据集的公司里面，都只能用linear或者
低于linear的算法。
【在 p*********g 的大作中提到】
: 呵呵，这当然要分析 rates。不过基本上优化里的人早就把这些研究透了。
:
: 10
: margin
|
p*********g
发帖数: 226 | 45 抛开算法复杂度不谈，在高维条件下，KNN 的 generalization performance 我不知道
会不会比 SVM 好。example 的数量 n 需要随维度 p 而上升，不知道 knn 中 n 对 p
的 dependence 是否好过 SVM。
而且在 testing 的时候，我有一个 weight vector，做一下内积，无论如何总比 knn
要快吧，不论 knn 做何indexing。
paper
【在 r********3 的大作中提到】
: 不过，这篇paper的要说明的问题，和处理large scale data是两回事。
: 前面有人跟帖说看好KNN的，认为KNN是真正解决large scale data的。KNN跟这篇paper
: 在对待大数据集上有本质的区别。 这个本质区别在于，KNN可以和数据库的存储索引和
: 查询优化这些结合起来。而这些技术才是解决真正意义上大规模数据集训练的渠道，而
: 不是一些局部小trick，五十步和百步的区别。
: Yahoo Research Lab的director说过。实际大数据集的公司里面，都只能用linear或者
: 低于linear的算法。
|
d******e
发帖数: 7844 | 46 p增长，knn是完蛋最快的，无论是regression还是classification
p
knn
【在 p*********g 的大作中提到】
: 抛开算法复杂度不谈，在高维条件下，KNN 的 generalization performance 我不知道
: 会不会比 SVM 好。example 的数量 n 需要随维度 p 而上升，不知道 knn 中 n 对 p
: 的 dependence 是否好过 SVM。
: 而且在 testing 的时候，我有一个 weight vector，做一下内积，无论如何总比 knn
: 要快吧，不论 knn 做何indexing。
:
: paper
|
N**D
发帖数: 10322 | 47 aparrently, you know 0.
learning方
-N
【在 w***g 的大作中提到】
: 我不知道vapnik当初搞SVM是怎么搞出来的。但是我上学时教授教的顺序是先PAC，然后
: VC dimension，然后再SVM，所有这些都在PAC的框架上做的。我不是说Vapnik不牛，他
: 从贡献上来说早就够诺贝尔奖了。但是这个Valiant即使不如Vapnik，差的也不大。
: (看了 BudFox的回帖再补充一下，PAC和SVM可能没关系。话说我上的那门课是Robert
: Schapire教的，所以SVM就被PAC给统一了。)
: 再说statistical learning theory。这东西现在这么火主要就是出了个SVM。别的理论
: 也不是没有，只是因为没有像SVM这么好用的，所以就都被比下去了。这么多learning方
: 法，SVM胜出了，30%是理论好，30%是时代背景，还有30%是运气。十年前neural
: network多火？现在还有多少人用？
: 再说时代背景。很难说50年后是什么状态，但我比较倾向认为10年后SVM就会让位于K-N
|
N**D
发帖数: 10322 | 48 PAC is for zero error, i.e., linearly separable case
SLT is general enough for non-zero erro case.
【在 B****x 的大作中提到】
: computational learning theory is just one of Valiant's fields. and PAC
: theory had led to practical algorithms too, such as boosting.
: Christos Papadimitriou also deserves a Turing Award.
|
N**D
发帖数: 10322 | 49 Alex 的large margin, 本质就是SVM,
kevin murphy, 是谁？
Elements of machine learning, 错误百出
PRML重点是graph model, Bayes method, 根本是和SLT对着干的，当然不会说SVM好了
了。
【在 p*********g 的大作中提到】
: 抛开算法复杂度不谈，在高维条件下，KNN 的 generalization performance 我不知道
: 会不会比 SVM 好。example 的数量 n 需要随维度 p 而上升，不知道 knn 中 n 对 p
: 的 dependence 是否好过 SVM。
: 而且在 testing 的时候，我有一个 weight vector，做一下内积，无论如何总比 knn
: 要快吧，不论 knn 做何indexing。
:
: paper
|
f*****x
发帖数: 2748 | 50
2010年5月份的时候，你就是这个论调，有人给你指正了，
你怎么没有长进呢？
【在 r********3 的大作中提到】
: 为啥老是有是那么崇拜Vapnik和SVM呢？
: 为啥我看待SVM就是一个quatric programming的优化问题？
|
|
|
N**D
发帖数: 10322 | 51 PAC没有算法，咋讲？
【在 p*********g 的大作中提到】
: 老实说，可能PAC不容易学，而且不讲它也能讲别的方法，实用中也不需要 PAC。
: 不过要真的搞 ml 研究，PAC 还是要学的。
: 就像 SLT，基本上所有教材都不提或略过，但其重要性不言而喻。
|
N**D
发帖数: 10322 | 52 但是intro都会讲SVM
【在 p*********g 的大作中提到】
: 哈哈，你再下去可以转 joke 版了，改天你上 intro to ml 课，把 Vapnik 的书从头
: 教到尾试试。
|
N**D
发帖数: 10322 | 53 再接着看，
【在 r********3 的大作中提到】
: 为啥老是有是那么崇拜Vapnik和SVM呢？
: 为啥我看待SVM就是一个quatric programming的优化问题？
|
f*****x
发帖数: 2748 | 54 老实说吧，数据库存储索引这些技术相对于前台处理技术
才是小TRICK呢。
处理超大规模数据时用线性或是SUB-LINEAR技术是那个
领域的共识。
paper
【在 r********3 的大作中提到】
: 不过，这篇paper的要说明的问题，和处理large scale data是两回事。
: 前面有人跟帖说看好KNN的，认为KNN是真正解决large scale data的。KNN跟这篇paper
: 在对待大数据集上有本质的区别。 这个本质区别在于，KNN可以和数据库的存储索引和
: 查询优化这些结合起来。而这些技术才是解决真正意义上大规模数据集训练的渠道，而
: 不是一些局部小trick，五十步和百步的区别。
: Yahoo Research Lab的director说过。实际大数据集的公司里面，都只能用linear或者
: 低于linear的算法。
|
N**D
发帖数: 10322 | 55 超大数据拼的是硬盘读写速度，没别的
【在 f*****x 的大作中提到】
: 老实说吧，数据库存储索引这些技术相对于前台处理技术
: 才是小TRICK呢。
: 处理超大规模数据时用线性或是SUB-LINEAR技术是那个
: 领域的共识。
:
: paper
|
f*****x
发帖数: 2748 | 56 当p一大时，普通的距离函数就不可靠了，
几乎任何两点之间的距离都差不多，这时kNN得到的结果
已经很不可靠了。
p
knn
【在 p*********g 的大作中提到】
: 抛开算法复杂度不谈，在高维条件下，KNN 的 generalization performance 我不知道
: 会不会比 SVM 好。example 的数量 n 需要随维度 p 而上升，不知道 knn 中 n 对 p
: 的 dependence 是否好过 SVM。
: 而且在 testing 的时候，我有一个 weight vector，做一下内积，无论如何总比 knn
: 要快吧，不论 knn 做何indexing。
:
: paper
|
i**p
发帖数: 940 | 57 还有一个共识是：更好更多的数据比算法上的改进往往更重要。事实上，svm比起别的
算法强多少？
【在 f*****x 的大作中提到】
: 老实说吧，数据库存储索引这些技术相对于前台处理技术
: 才是小TRICK呢。
: 处理超大规模数据时用线性或是SUB-LINEAR技术是那个
: 领域的共识。
:
: paper
|
f*****x
发帖数: 2748 | 58 你这个说法老夫没记错的话，几年前google的Norvig就
高声唱过，但是很快他就哑了。
不少时候数据的增加量根不上数据本身复杂度的增加，
对于有些数据即使把全人类的所有的数据都凑一块也跟不上。
【在 i**p 的大作中提到】
: 还有一个共识是：更好更多的数据比算法上的改进往往更重要。事实上，svm比起别的
: 算法强多少？
|
p*********g
发帖数: 226 | 59 en, 所以说即使大数据集，要考虑的也并非只有计算复杂度。
【在 f*****x 的大作中提到】
: 当p一大时，普通的距离函数就不可靠了，
: 几乎任何两点之间的距离都差不多，这时kNN得到的结果
: 已经很不可靠了。
:
: p
: knn
|
i**p
发帖数: 940 | 60 这个基本上工业界算是共识。www上海量数据让很多以前不可想象的东西变成现实，包
括搞出好用的
search engine。这靠小数据＋nb算法是没戏的。
再比如，netflix prize里，凡是给了众多rating的user都容易预测，反之则难，算法
根本没法
bridge the gap。
再比如，前些时候bing搞clickstream data，你让他们专心搞nb算法去？
不存在Norvig哑不哑。他能怎么唱？data不是想有就有的，学术界更不太可能搞到data。
【在 f*****x 的大作中提到】
: 你这个说法老夫没记错的话，几年前google的Norvig就
: 高声唱过，但是很快他就哑了。
: 不少时候数据的增加量根不上数据本身复杂度的增加，
: 对于有些数据即使把全人类的所有的数据都凑一块也跟不上。
|
|
|
B****x
发帖数: 17 | 61 Is it a joke?
【在 N**D 的大作中提到】
: PAC is for zero error, i.e., linearly separable case
: SLT is general enough for non-zero erro case.
|
f*****x
发帖数: 2748 | 62 他的高调是基于google当时搞的一个NLP算法(充分利用了
google当时已有的海量数据)暂时领先于别人而说的。
data。
【在 i**p 的大作中提到】
: 这个基本上工业界算是共识。www上海量数据让很多以前不可想象的东西变成现实，包
: 括搞出好用的
: search engine。这靠小数据＋nb算法是没戏的。
: 再比如，netflix prize里，凡是给了众多rating的user都容易预测，反之则难，算法
: 根本没法
: bridge the gap。
: 再比如，前些时候bing搞clickstream data，你让他们专心搞nb算法去？
: 不存在Norvig哑不哑。他能怎么唱？data不是想有就有的，学术界更不太可能搞到data。
|
r********3
发帖数: 2998 | 63 你的意思是说，研究了几十年的数据库技术都是小trick了？ 在计算机领域里面，除了
最老的OS，System那个派系外，还没其他哪个派系刚这样说database领域。
超大规模数据处理的时候，即便是linear和sub-linear都不行的。KNN是可以直接做到
log级别的。话说回来，即便同样是linear，数据访问的顺序不同，也会造成几倍的差
别。你要是了解现在计算体系结构就明白了。
【在 f*****x 的大作中提到】
: 老实说吧，数据库存储索引这些技术相对于前台处理技术
: 才是小TRICK呢。
: 处理超大规模数据时用线性或是SUB-LINEAR技术是那个
: 领域的共识。
:
: paper
|
r********3
发帖数: 2998 | 64 最开始，看山便是山。多看一会，发现看山不是山。但是你再多看一会，你会发现，看
山还是山。
你不要想太复杂了，本来就是那么回事，你以为多高深啊？
【在 f*****x 的大作中提到】
: 他的高调是基于google当时搞的一个NLP算法(充分利用了
: google当时已有的海量数据)暂时领先于别人而说的。
:
: data。
|
f*****x
发帖数: 2748 | 65 您能不能给老夫说说你看山不是山的时候都看到了什么。
【在 r********3 的大作中提到】
: 最开始，看山便是山。多看一会，发现看山不是山。但是你再多看一会，你会发现，看
: 山还是山。
: 你不要想太复杂了，本来就是那么回事，你以为多高深啊？
|
r********3
发帖数: 2998 | 66 看来你不是很了解indexing技术。建议你去看看现代计算机体系结构。
p
knn
【在 p*********g 的大作中提到】
: 抛开算法复杂度不谈，在高维条件下，KNN 的 generalization performance 我不知道
: 会不会比 SVM 好。example 的数量 n 需要随维度 p 而上升，不知道 knn 中 n 对 p
: 的 dependence 是否好过 SVM。
: 而且在 testing 的时候，我有一个 weight vector，做一下内积，无论如何总比 knn
: 要快吧，不论 knn 做何indexing。
:
: paper
|
r********3
发帖数: 2998 | 67 呵呵，跟你看玩笑的。你还当真啊。。。
你说说看，它本质除了利用quadatric programming外来求maximum margin外，还有其
他啥东西？
【在 f*****x 的大作中提到】
: 您能不能给老夫说说你看山不是山的时候都看到了什么。
|
f*****x
发帖数: 2748 | 68 与其回答，老夫给你提两个问题。
1) svm为什么可以转化为quad programming问题？
2) svm的performance guarantee哪里来？
【在 r********3 的大作中提到】
: 呵呵，跟你看玩笑的。你还当真啊。。。
: 你说说看，它本质除了利用quadatric programming外来求maximum margin外，还有其
: 他啥东西？
|
p*********g
发帖数: 226 | 69 你倒是说说看啊，卖关子只能证明你心虚。
向CS本科、但不major 现代计算机体系结构的人介绍一下这个技术，也是你
应该具备的素质。
基于向量运算的机器，做 SVM 内积不更合适？
当然不是谈 training。
【在 r********3 的大作中提到】
: 看来你不是很了解indexing技术。建议你去看看现代计算机体系结构。
:
: p
: knn
|
r********3
发帖数: 2998 | 70 原来你说的是这个啊。我觉得这2点其实很直观的。1)的转化，就是来源于maximum
margin。 2）因为是maximum margin，所以分界面的confidence最大，对看不见的test
sample有最大的兼容度，尽量避免overfitting。
不过，这两点，为啥我觉得是很直观的。
【在 f*****x 的大作中提到】
: 与其回答，老夫给你提两个问题。
: 1) svm为什么可以转化为quad programming问题？
: 2) svm的performance guarantee哪里来？
|
|
|
r********3
发帖数: 2998 | 71 好吧，我承认，我心虚。。。
我没有说过不SVM做内积不合适。而是，你没有明白别人回帖里面说看好KNN的原因。
【在 p*********g 的大作中提到】
: 你倒是说说看啊，卖关子只能证明你心虚。
: 向CS本科、但不major 现代计算机体系结构的人介绍一下这个技术，也是你
: 应该具备的素质。
: 基于向量运算的机器，做 SVM 内积不更合适？
: 当然不是谈 training。
|
p*********g
发帖数: 226 | 72 kNN 的好处是显然的。
每个方法都有 advantage 和 disadvantage。我问一下 disadvantage，不代表我不承
认它的 advantage。
【在 r********3 的大作中提到】
: 好吧，我承认，我心虚。。。
: 我没有说过不SVM做内积不合适。而是，你没有明白别人回帖里面说看好KNN的原因。
|
p*********g
发帖数: 226 | 73 直观的东西，严格地写下来就不容易了。VC-dim 牛就牛在抓住了问题的关键，而不是
看有几个参数之类。
再到后来 Rademacher 就更牛了，当然啦，是站在 VC-dim 的肩膀上。
test
【在 r********3 的大作中提到】
: 原来你说的是这个啊。我觉得这2点其实很直观的。1)的转化，就是来源于maximum
: margin。 2）因为是maximum margin，所以分界面的confidence最大，对看不见的test
: sample有最大的兼容度，尽量避免overfitting。
: 不过，这两点，为啥我觉得是很直观的。
|
d******e
发帖数: 7844 | 74 因为是maximum margin，所以分界面的confidence最大。
这句话说简单可简单，说复杂可复杂。
test
【在 r********3 的大作中提到】
: 原来你说的是这个啊。我觉得这2点其实很直观的。1)的转化，就是来源于maximum
: margin。 2）因为是maximum margin，所以分界面的confidence最大，对看不见的test
: sample有最大的兼容度，尽量避免overfitting。
: 不过，这两点，为啥我觉得是很直观的。
|
f*****x
发帖数: 2748 | 75 你对自己的回答满意吗？
老夫白跟你浪费时间了。
test
【在 r********3 的大作中提到】
: 原来你说的是这个啊。我觉得这2点其实很直观的。1)的转化，就是来源于maximum
: margin。 2）因为是maximum margin，所以分界面的confidence最大，对看不见的test
: sample有最大的兼容度，尽量避免overfitting。
: 不过，这两点，为啥我觉得是很直观的。
|
N**D
发帖数: 10322 | 76 svm还是很厉害的， 那个digit recognition, 那个new york 的哥们搞了20几年的ANN,
结果和SVM不相上下。
【在 i**p 的大作中提到】
: 还有一个共识是：更好更多的数据比算法上的改进往往更重要。事实上，svm比起别的
: 算法强多少？
|
R*******V
发帖数: 57 | 77 鼓掌，这个把我笑翻了。
【在 f*****x 的大作中提到】
: 你对自己的回答满意吗？
: 老夫白跟你浪费时间了。
:
: test
|
R*******V
发帖数: 57 | 78 提示一个typo.
那个叫CNN。
你说的这个消息比较surprising.
我一直觉得Lecun的数字识别做得最好了。
哪篇文章说结果不相上下？
说一下链接好么？
ANN,
【在 N**D 的大作中提到】
: svm还是很厉害的， 那个digit recognition, 那个new york 的哥们搞了20几年的ANN,
: 结果和SVM不相上下。
|
R*******V
发帖数: 57 | 79 是啊，curse of dimensionality不是说着玩的。
有个几个milinon的training data，就觉得数据解决一切问题确实显得很幼稚。
这就跟IBM曾经用疯狂的机械速度提高卡片计算机的速度一样。
【在 f*****x 的大作中提到】
: 你这个说法老夫没记错的话，几年前google的Norvig就
: 高声唱过，但是很快他就哑了。
: 不少时候数据的增加量根不上数据本身复杂度的增加，
: 对于有些数据即使把全人类的所有的数据都凑一块也跟不上。
|
R*******V
发帖数: 57 | 80 他陷在QP里面了。
其实SVM的精髓就是那个maximum margin.
怎么解是另外一回事。他口口声声QP说明对SVM的理解还不够。
这里好几个人告诉他了。。。。。。。
【在 f*****x 的大作中提到】
: 与其回答，老夫给你提两个问题。
: 1) svm为什么可以转化为quad programming问题？
: 2) svm的performance guarantee哪里来？
|
|
|
p*********g
发帖数: 226 | 81 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1038
See Table 3.
【在 R*******V 的大作中提到】
: 提示一个typo.
: 那个叫CNN。
: 你说的这个消息比较surprising.
: 我一直觉得Lecun的数字识别做得最好了。
: 哪篇文章说结果不相上下？
: 说一下链接好么？
:
: ANN,
|
R*******V
发帖数: 57 | |
s***y
发帖数: 198 | 83 大规模商用的，是集总学习，所以Valiant 和Vapnik都比周差太多。
paper
【在 r********3 的大作中提到】
: 不过，这篇paper的要说明的问题，和处理large scale data是两回事。
: 前面有人跟帖说看好KNN的，认为KNN是真正解决large scale data的。KNN跟这篇paper
: 在对待大数据集上有本质的区别。 这个本质区别在于，KNN可以和数据库的存储索引和
: 查询优化这些结合起来。而这些技术才是解决真正意义上大规模数据集训练的渠道，而
: 不是一些局部小trick，五十步和百步的区别。
: Yahoo Research Lab的director说过。实际大数据集的公司里面，都只能用linear或者
: 低于linear的算法。
|
