Learning deep Architectures for AI ftml_book Page

文对 Learning Deep Architectures for AI 的书评发表时间：2013-09-25 23:09:52

具体内容：
More precisely ,functions that can be compactly represented by a depth k architecture might require an exponential number of computational elements to be represented by a depth k-1 architecture.

这句意思是k-1层架构可以表示的函数需要的计算元素可能是k层架构的指数倍，字面上应该是这个意思吧，但是我还是比较难理解，谁能帮忙提点下下，能举个例子最好啦。

有用 0 无用 1

您对该书评有什么想说的？

对“Learning deep Architectures for AI ftml_book Page ”的回应

文 2014-01-14 17:26:36

这篇文章直切主题，应该有比较完整的证明。有些问题总想追根问源，我得看看。

回应他

Bayesian 2014-01-14 11:48:16

这个结果来自1994年Godel prize的论文：Johan Håstad, "Almost optimal lower bounds for small depth circuits," Advances in Computing Research 5 (1989), 143-170.
是理论计算机领域的证明，方法据说很精巧，抱歉我没读过。

回应他

文 2013-10-08 00:48:44

我也是这么想的，感谢你的指教，本以为豆瓣上没人会理会的，你的回答让我觉得这个社区还是挺活跃的，而且你也很耐心认真地讨论，这种素养难能可贵，咱们社会需要更多你这样的人材，活跃求知求真的气氛。跟你交流很愉快，Thank u very much!

回应他

观宇 2013-10-08 00:22:42

我不保证我举的例子就是对的，但是我的看法是，在我们不知道这个逻辑运算具体表达式（比如 A and B or C）的时候，我们确实是要通过枚举去“表示”（注意是表示，或者叫唯一确定一个函数f(A, B, C)）而不是“计算”；而用两层结构表示的话，就是俩逻辑运算符号。可能我之前的说法有些问题，一个讲了计算一个讲了表示。
可能另一个从“计算次数”来讲比较合适的例子是秦九韶算法？不过从层数来增加了不少……

回应他

文 2013-10-07 18:05:15

如果你把规模用运算的次数来衡量的话，两种表示方式都做3次运算（判断3个变量的真值）即可，就枚举来说，只要三个值确定，对应的结果也就确定了。断不出熟优熟劣！

回应他

观宇 2013-10-07 15:15:25

1. (A and B) or C, 括号内是第一层，括号外是第二层，从这个角度，你只需要判断C是否为真，以及C为假时A和B是否都为真，理论上至多只要3次运算；
2. 一层表示，例如枚举的话，你需要枚举出(A, B, C)的所有真值组合（共8个），然后对应给输出，例子：
(T, T, T) -> T; (T, F, F) -> F; (T, F, T) -> T

回应他

文 2013-10-07 05:16:21

对这个论点的理解，文章后面还是有不少解析的，也有不少例子，例如逻辑表达式，多项式的表示。但是对你举的这个例子：你说的逻辑运算是指如何表示结果，还是指其他的？ A and B or C，用两层架构表示，怎样表示？用枚举怎么表示？可能是我的更解方向上跟你的意思有偏差，还请不吝赐教。

回应他

观宇 2013-10-01 05:39:41

你可以考虑一下逻辑运算，比如 A and B or C，它可以用一个两层架构表示，但是如果要用一层表示，比如枚举，要得到所有结果需要枚举8次。

回应他