彭老师是肥科计院为数不多的偏数学的老师，这门课是计院为数不多的偏数学的老师，要好好珍惜呀🤭~~

助教也很给力的，作业都有工整的答案，第一次体验到讲义区提供卷子的服务，体验非常好

前半个学期的一点总结

1. SVD的几何意义、2种表示(\(UDV^T/\sum_{i=1}^r \sigma_i u_i v_i^T\)+||A-A_k||的含义

PS1:\(VV^T=\sum v_iv_i^T\)；

PS2:\(||A||_2=\underset{||v||_2=1}{max}||Av||\)(用来证||A-Ak||_2 minimal)

PS3:变换I=VV^T=UU^T，可以利用A=UDV^T与U,V的关系

\(\begin{align*} &v_1=\underset{|v_1|=1}{max} ||Av_1||_2^2=\underset{|v_1|=1}{min}||A-Av_1||_2^2=\underset{|v_1|=1}{min}\sum_{i=1}^n|a_i-a_iv_1|^2\\ &v_2=\underset{|v_2|=1,v2\perp v_1}{min}\sum_{i=1}^n|a_j-a_iv_2|^2\\ &...\\ &{v1,...,vk}=\underset{v_1,...,v_k}{min}\sum_{j=1}^k\sum_{i=1}^n|a_i-a_iv_jv_j^T|^2\\ &=\underset{v_1,...,v_k}{min}\sum_{i=1}^n\sum_{j=1}^k|a_i-a_iv_jv_j^T|^2\\ &=\underset{v_1,...,v_k}{min}\sum_{i=1}^n dist(a_i,V_k)^2\\ &\therefore A_k=\sum_{i=1}^k \sigma_iu_iv_i^T=\sum_{i=1}^kAv_iv_i^T\\ &=A\sum_{i=1}^k v_iv_i^T=\sum_{j=1}^n a_j\sum_{i=1}^k v_iv_i^T \end{align*}\\\)

2. JL引理用ajU实现降维，同时保持大部分特征

3. mean方法用来线性放缩，median用来指数放缩；

4. 先算出E[X],Var[X]，再用markov,chebyshev,chernoff bound放缩→指示变量法证明中位数的性质

5. Matrix Sketches中的Abel变换

PS:均值的另一种表示(展开成二重积分交换次序)，\(E[Y]=\int_{-\inf}^{\inf} P(Y\geq \lambda)d\lambda\)

期中的教训

1. 考试的时候要求判断Matrix Sketch算法是否存在在i到来时，存在全为0的行，

因为想到\(||Ax||^2-||Bx||^2=\sum_{i=1}^n[||a_ix||^2+||B^{i-1}x|| ^2-||B^ix||^2]=\sum_{i=1}^n[||C^ix||^2-||B^ix||^2]\),如果存在一个时刻没有全为0的行，C^i=|B^{i-1}|，Bi为SVD再删除<=σ(k/2)的行，那么这个ai行就被扔掉了，于推导不符，因此选了不存在没有时刻全为0的行，(即使有也先作SVD再插入ai)，一开始以为错了，反转~

2.LSH是说，将n个值a1,...,anhash到L个2^k容器的容器中，

1)在L个2^k的容器中，E[Y]\le L，由markov不等式，P(Y>=4L)<1/4

2)如果有一个a*满足d(a*,x)<=r，那么它在L个容器中的投影和x的hash值都不等的概率<1/7，

那么查询4L个满足h(x)=h(a)的a，计算d(x,a)是否\leqcr，
以0.6的P，其中至少一个a有d(x,a)\leq cr(超过4L个y,d(y,x)\leq cr且h(y)=h(x)已被排除，至少有一个h(x)=h(a*)的a*，d(x,a)\leq cr)，
如果没有这样的d(x,a)\leqcr，返回FAIL(卒)，

PS:后来发现判断题和选择题出得挺好的，可以检验菜鸡有没有理解~~

3.\(P(Y-td>\sqrt d \epsilon)\leq e^{-\frac {\epsilon^2} {5}}\)(怀疑是不是\(e^{-\frac \epsilon 5}\))，群里有说log的用了得到E[Y]>=td(写反了)，转成\(P(Y-E[Y]>\sqrt d \epsilon)\)，用chernoff到\(e^{-2\epsilon^2}\)，以为记不清的Gaussian Annulus可以，卒，

4. 最后一问，是不能同理的，大于和小于的情况并不完全一样，被我跳过去了，卒，好吧，我果然菜鸡，

我是小丑，菜鸡读书一定要静下心来呀，对我这样的fw，果然没有什么所谓的速度，只有一点点积累

给分：

• 出勤率（10%，无点名白给）+ 3次作业（3 * 10%）+ 期中考试（30%）+ 期末考试（30%）
• 调分给满优秀率

课程内容：

1. Singular Value Decomposition and Principal Component Analysis
2. Johonson-Linenstrauss Lemma. Nearest Neighbor Search
3. Locality Sensitive Hashing
4. Probabilistic Counting, Reservoir Sampling
5. Estimating the Number of Distinct Elements
6. Frequent Items: Misra-Gries Algorithm, Count-Min Sketch, Count Sketch
7. Matrix Sketches
8. VC-dimension, PAC learning
9. The Perceptron Algorithm
10. Support Vector Machine
11. k-means/median/center
12. Coreset for Clustering
13. Hierarchical Clustering

参考教材（和丁虎老师的参考教材差不多）：

• Foundations of Data Science
• Mathematical Foundations for Data Analysis
• Sketching Algorithms

作业：

• 6次作业，只有3次需要提交；
• 需要提交的3次中，第一次难度一般，后两次难度较大；

期中/期末考试：

• 不难，比平时作业还要简单一些；
• 题量正常；
• 题型包含选择、判断和若干大题，大题分值10分或20分；

教学：

• 老师提供详细的手写讲义，可读性很好（注：指内容的可读性很好，字儿还是算了吧doge），和上课板书完全一致，与丁虎老师之前的讲义相比，感觉彭攀老师的课程广度和深度要大一些；
• 大部分内容提供完整数学推导的课堂演示；
• 讲课清晰明了，内容循序渐进，听课十分享受，收获很多；
• 提供Classin直播，早课可以寝室在线听课（是好事！）；

总结：

上课舒适有收获，作业加深课程内容，考试大放水送福利，这样的课程哪里找！

另外，彭攀老师的学术水平也比较高，在SODA、COLT、STOC上都发表过文章，大家不要都去找陈雪老师呀，你看看我呀！你看看我呀！