康奈尔印象
Table of Contents
校园篇
康奈尔的校园坐落于小镇 Ithaca(伊萨卡), 校园绿化率非常高. 由于历史悠久且没有搬过校区, 很多古典风格的建筑得以保存, 相较之下 Gates Hall 这种现代建筑反倒显得突兀.
相比交大而言, 伊萨卡的交通实在是不方便, 高低起伏的地形, 怕是连"共享单车"的生意也难做起来. 比较有趣的是, 康奈尔没有明确的边界, 也没有一个正式的校门, 从 College Town 走上去的话, 大概会以一个峡谷为界:
由于纬度较高, 伊萨卡每天 6 点天亮, 晚上 9 点钟才会天黑, 因此这儿的动植物日照时间充分, 多样性也很丰富: 校园植被繁多, 小松鼠随处可见, 甚至还有鹿.
每周五的下午在钟楼附近的 Arts Quad 都有 Free concert, 经历了五个工作日摧残的人们来到此地放松躯体, 随着灵魂扭动着节拍. 喧嚣过后, 脚下的斜坡注视着余晖下的伊萨卡, 头顶上的钟楼开始接管落日, 守护着夜行者.
Figure 3: 俯瞰 Arts Quad
Figure 4: 标志性建筑钟楼
Figure 5: 校内一隅
Figure 6: 校内的教堂
人文篇
由于很多年前我是王垠的忠实粉丝. 所以先入为主地, 我对 Cornell 的第一印象是: 这是全美自杀率最高的高校之一. 来到 Cornell 之后, 由于大部分本科生已经放暑假, 我失去了接触第一手材料的机会.
暑期一共有好几场 CS PhD 的 lighting talks, 不过限于时间关系(7min/PhD), 实际上能了解的并不多. 可能更多的意义在于与 PhD 的直接交流, 学长学姐们都很热心, 且看起来他们都很热爱自己的科研(对 Alex Zikai Wen 的印象比较深，他正在从事游戏相关的研究, 导师乃Eric Andersen, 主页上挂着 minecraft 的男人). 不过我更希望接触那些"对自己的研究并不满意, 且做出或者希望做出一些转变"的人. 毕竟对于绝大部分人来说, 吾辈所学皆屠龙之技, 我希望能看到他们转变自己心态的过程. 私下里与 SpeechLab 的孙锴学长约了一顿饭, 向我传递的信息更加全面且负面一些, 让我能更清除地意识到读 Ph.D. 的利弊, 学长表示 NLP 领域现在很多短平快的工作, 而他并不愿意做这样的研究, 做帮导师拿经费的项目通常也是无聊且低效的(跨校合作存在很大的沟通不利的问题).
来这边很开心的一件事情是见到了不少大佬: 比如 Jon Kleinberg , Eva Tardos . 在上博弈论课程时就久仰这两位的大名, 这次有幸与 tardos 进行了一段简短的交流, 问了她几个如何寻找问题和科研品味的问题, 她的回答是: 如果能解决一个 open problem, 或者在一个大的目标中完成了一小步, 都是他们欣赏的科研. 如此看来做 theory 的人还是比较单纯, 犯不着整天忧心忡忡"这个新模型有什么用", "这个问题有没有意义". Jon Kleinberg 的讲座主要内容来自于这一篇论文: Human Decisions and Machine Predictions, 一共 76 页, 工作非常扎实.
Robbert Van Renesse 是 system 方向颇有建树的教授, 由于之前我并不是 system 方向, 对他的研究了解不多. 不过他的讲座很精彩, 介绍了 gossip 机制及相关内容, 至少成功地让我听懂了.
课程篇
Cornell 的暑期项目一共有两门课:编程语言与逻辑, 分布式一致性.
Programming Language and Logic
这门课由 David Gries 主讲, 内容主要是证明程序正确性. 由于课时不多, 所以内容偏重于 Hoare Logic 和 Loop Invariant.
David 上课节奏非常非常慢(如果按照国内很多年轻老师的速度, 大概在一周内就能结课), 所以听起来相当轻松. 重新演绎了许多很 trivial 的经典算法, 其中不乏若干闪光点.
对于不想做程序证明相关工作的人来说, 循环不变式的作用在于, 可以逻辑上严格地推导各类递推关系和边界条件; 在 特殊 (课堂上举出的例子都是线性算法, 因此我非常怀疑这套方法的通用性)的情况下, 循环不变式可以直接引导出整个算法.
以下是课程中比较有趣的地方:
二分查找的边界问题
中学写二分时通常会可以忽略边界问题(何时终止?), 不过通过循环不变量可以严格地导出边界条件.
首先需要明确一下, 当存在相同元素时, 返回最右.
# h e t
# ---------------------
# b:| <= | ? | > |
# ---------------------
h, t := -1, n;
do h + 1 < t ->
e := (t + h) / 2;
# {h < e < t}
if b[e] <= x -> h := e;
| b[e] > x -> t := e;
fi
od
return h
其中 \(\{h < e < t\}\) 这个条件始终维护.
\(\log(n)\) 额外空间的快速排序
快速排序的 partition 过程可以用循环不变量导出, 不过方法与上面类似. 比较有趣的是一个小技巧: 普通的快速排序, 在最坏情况下有 \(O(n)\) 的额外时间复杂度. 通过尾递归的技巧, 可以降到 \(O(\log(n))\) .
具体的做法很简单, 就是只在 \(size <= (r - l)/2\) 的分支递归下去,
qsort(b, h, t):
do h + 1 < t ->
e := parition(b, h, t)
if (e - h <= (t - h) / 2) -> qsort(b, h, e); h := e + 1;
| (t - h - 1 <= (t - h) / 2) -> qsort(b, e + 1, t); t := e;
fi
od
这样不改变时间复杂度, 但是 \(e\) 这个变量被复用多次.
Function fasc
源自于 David 的一道作业题:
- \(f(0) = 0, f(1) = 1\)
- \(f(2n) = f(n), n > 0\)
- \(f(2n + 1) = f(n) + f(n + 1), n > 0\)
这道题直接设计一个 \(O(\log n)\) 的算法有一定的难度, 但是用循环不变式硬凑是可以得出的(那么讲道理, 直接规律行不行???当然行)
转化方式非常精巧, 注意到 \(f(2n) = f(n)\) 可以变成 \(f(2n) = f(n) + 0 \cdot f(n+1) = f(n) + 0 \cdot f(n - 1)\) , 因此求值过程遇到的都是同样的 \(n\) 和 \(n+1\) . 这样, 维护循环不变量 \(P: \{f(n) = a\cdot f(k) + b\cdot f(k+1)\}\) 即可:
do k > 0 and even(k) -> k, a := k / 2, a + b; | k > 0 and odd(k) -> k, b := k / 2, a + b; od return b
Distributed Consensus
这门课由密码学大佬 Elaine Shi 主讲, 内容主要是区块链相关, 具体有 Nakamoto consensus, Sleepy consensus, Adversarial Algorithm 和 Byzantine agreement. 实际上内容并不多, 不过授课感觉并没有按照拓扑序, 听起来不是很舒服.
Nakamoto Consensus & Sleep Consensus & Adversarial Algorithm
感觉组里的白皮书(感谢全组的努力, 我衹是在划水)内容已经非常详细: Distributed Consensus Simulator’s White Paper.
Byzantine Consensus
这部分内容我在之前的博文中写过, 不再赘述.
尼亚加拉瀑布之行
这是暑期项目计划的一个部分，已经持续了多年；Niagara Falls 位于中加边界，距离 Cornell 大概有一段几小时的车程（由于我在车上全程睡觉，具体几小时我给忘了）。
Figure 9: 坐在船上感受水雾冲脸
Figure 11: 对面就是枫叶国
逸闻
- David 上课时说, "很多人做 Computational Complexity, 而我做 Computational Simplicity."
海虹餐厅饭后的签语饼:
传授"闷声大发财"的人生经验.
- 在 Cornell 听的所有讲座中没有"纯机器学习"相关的, 与国内 AI 热火朝天的趋势不相径庭. 虽然 Cornell 从来不算 AI 强校, 至少能说明一些问题.
Gates Hall 一楼的墙上贴有 invariants, Big-O, Network, Stochastic, Collaboration, Classification 的标志, 应该可以说明 Cornell 的 CS 学科导向.
