Foundations of data science

หน้านี้สำหรับเก็บเอกสารและการบ้านรายวิชา 01204515 Foundations of Data Science ปีการศึกษา 2564 ภาคต้น

รายวิชานี้จะใช้หนังสือ Foundations of Data Science (Blum, A., Hopcroft, J., & Kannan, R. (2020). Foundations of Data Science. Cambridge: Cambridge University Press. doi:10.1017/9781108755528) เป็นหนังสือหลัก (ดาวน์โหลดจากโฮมเพจของ Hopcroft)

การบ้าน

อ้างอิงจากหนังสือ ฉบับวันที่ 2 March 2019

• Homework 1 (due 2 Sep.): 12.6, 12.15, 2.1(1), 2.5, 2.9, 2.27 (Programming), 2.32 (Programming), 2.14 (optional), 2.23 (optional)
  • Hint: 2.9 พิจารณา 1 มิติก่อน (d=1) นิยามของ variance คืออะไร, จากนั้นค่อยพิจารณา d มิติ

• Homework 2 (due 4 Oct): 3.1, 3.6, 3.14, 3.15 (คำนวณค่า), 3.24, 3.23 (optional)
  • Hint: 3.1 least squares vertical error
  • Hint: 3.6 จากการที่แถวเป็น orthonormal ให้แสดงว่า (1) $AA^{T}=I$ หรือ (2) $A^{-1}=A^{T}$ (ข้อใดข้อหนึ่ง หรือจะแสดงทั้งคู่ก็ได้) จากนั้นให้ใช้คุณสมบัติดังกล่าวประกอบกับการตีความ $A^{T}A$

• Homework 3 (due 11 Oct): 5.3, 5.4, 5.7, 5.10, 5.12
  • Hint: 5.3 ให้ลอง fix disjunction ก่อน จากนั้นพิจารณาว่า w ควรเป็นอะไร (ลองพิจารณาจากกรณีที่ใช้ perceptron ในการหาเวกเตอร์ก็ได้)
  • Hint: 5.4 พิสูจน์ by contradiction ให้สร้างเงื่อนไขที่ตอบถูกบางกรณีก่อน จากนั้นนำมารวมกันเพื่อสร้างข้อขัดแย้ง

• Homework 4 (due 8 nov)
  • บังคับทำ 5.26 (boosting)
  • ให้เลือก 2 ข้อจากด้านล่าง
    • 5.21 (programming), 5.22 (programming)
    • 5.19 (linear cnn), 5.23 (perceptron & sgd)
    • 5.24 (online perceptron)
  • โบนัส 5.20 (programming)

เนื้อหา

Week	Topics	Book chapter	Clips	Notes
1	Review of probability theory. Law of large numbers. Markov's Inequality. Chebyshev's Inequality	2	01-1: แนะนำ Law of large numbers, ทบทวนทฤษฎีความน่าจะเป็น (1) 01-2: ทบทวนความน่าจะเป็น - Random variable และ expectation 01-3: ทบทวนความน่าจะเป็น - Indicator random variable และ variance (แก้ไขแล้ว) 01-4: Markov's Inequality, Chebyshev's Inequality, และบทพิสูจน์ Law of large numbers	notes-01-1 notes-01-2
2	More review of probability theory: binomial, Poisson, and Gaussian random variables. High dimensional unit balls.	2	02-1: ทบทวนความน่าจะเป็น - ตัวแปรสุ่มแบบ binomial และ Poisson 02-2: ทบทวนความน่าจะเป็น - ตัวแปรสุ่มแบบ Gaussian 02-3: High dimensional unit balls - Volume ใกล้ surface 02-4: การสุ่มจุดจาก unit ball 02-5: คุณสมบัติของเซตของจุดที่สุ่มจาก unit ball 02-6: High dimensional unit balls - Volume ใกล้ equator	notes-02-1 notes-02-2
3	Gaussians in high dimensions. Random projection and the Johnson-Lindenstrauss Lemma. Separating Gaussians. Introduction to SVD and review of linear algebra.	2, 3	03-1: ตัวอย่าง Dimension reduction และ random projection กับ Johnson-Lindenstrauss lemma 03-2: ตัวอย่างการแยก Gaussian ใน high dimension และการใช้ SVD 03-3: ตัวอย่าง SVD ในการหา low-rank approximation กับรูปภาพ 03-4: Random projection และ Johnson-Lindenstrauss Lemma 03-5: การแยก Gaussian ใน high dimension 03-6: แนะนำ Singular value decomposition และทบทวนเนื้อหาพีชคณิตเชิงเส้น Series แนะนำ: Essence of linear algebra จาก 3Blue1Brown	notes-03-1 notes-03-2
4	Singular Value Decomposition	3	04-1: ทบทวนนิยาม SVD แนะนำ eigenvalue decomposition และแนะนำความสัมพันธ์กับ SVD 04-2: ตัวอย่าง eigenvectors และการคำนวณ การหา singular vector ด้วย iterative method 04-3: นิยาม best-fit subspace สองแบบ, นิยาม singular vectors และแนวทางการคำนวณแบบ greedy 04-4: นิยาม left singular vector และพิสูจน์ว่าผลลัพธ์เป็น decomposition 04-5: คุณสมบัติของ left singular vectors 04-6: Rank-k approximation ที่ดีที่สุด 04-7: การคำนวณหา SVD	notes-04-1
5	Applications of SVD. Machine learning (intro). Perceptrons. Kernel functions.	3, 5	คลิป: 05-1: การประยุกต์ใช้งาน SVD 05-2: แนะนำเนื้อหาส่วน machine learning, Perceptron algorithm และบทพิสูจน์ 05-3: Kernel functions	notes-05-1 notes-05-2 notes-05-3
6	ตัวอย่าง Perceptron และ kernelized Perceptron, Uniform convergence (finite hypothesis classes)	5	คลิป: 06-1: ตัวอย่าง perceptron และการใช้ kernel 06-2: นิยามโมเดลในการวิเคราะห์ generalization 06-3: Generalization กรณี finite hypothesis class และ consistent hypothesis, แนะนำ uniform convergence 06-4: พิสูจน์ uniform convergence กรณี finite hypothesis class ด้วย Hoeffding bounds 06-5: Occam's Razor และ Regularization 06-6: แนะนำ VC dimension	notes-06-1
7	VC dimension	5	คลิป: 07-1: ทบทวนแนวคิดเกี่ยวกับ uniform convergence 07-2: นิยาม VC dimension 07-3: Shatter function 07-4: ทฤษฎีบทจาก VC dimension และแนวคิดในการพิสูจน์	notes-07-1
8	Deep learning	5	คลิป: 08-1: Optimization กับ machine learning 08-2: Logistic regression 08-3: แนะนำ deep neural network 08-4: หัวข้อเกี่ยวข้องกับ DL: Adversarial attack และ Generative Adversarial Network 08-5: Gradient descent	notes-08-1
9	Online learning, learning from expert advice, boosting	5	คลิป: 09-1: แนะนำ online learning, learning disjunctions, และ halving algorithm 09-2: Perceptron algorithm แบบออนไลน์ และการวิเคราะห์กรณี inseparable data ด้วย hinge loss 09-3: การแปลง online learning algorithm ไปใช้กับ batch learning 09-4: การทำนายโดยใช้ Expert advice 09-5: Boosting	notes-09-1 notes-09-2 notes-09-3
10	Streaming algorithms (1)	6	คลิป: 10-1: แนะนำ streaming model, ปัญหาการสุ่มข้อมูล 10-2: Approximate counter, นิยาม frequency moments 10-3: จำนวนข้อมูลที่แตกต่างกัน (part 1) 10-4: จำนวนข้อมูลที่แตกต่างกัน (part 2): 2-universal hashing	notes-10-1
11	Streaming algorithms (2) - majority และ second frequency moment	6	คลิป: 11-1: Majority และ frequent elements 11-2: การประมาณ Second Frequency Moment (Part 1) - อัลกอริทึม 11-3: การประมาณ Second Frequency Moment (Part 2) - 4-way independent random vectors 11-4: Demo - second moment	notes-11-1 notes-11-2
12	Streaming algorithms (3) - approximate matrix multiplication & matrix sketches	6	คลิป: 12-1: การประมาณการคูณเมตริกซ์ (Part 1) - sampling 12-2: การประมาณการคูณเมตริกซ์ (Part 2) - พิสูจน์ขอบเขตความผิดพลาด 12-3: การประมาณการคูณเมตริกซ์ (Part 3) - เปรียบเทียบ 12-4: Matrix Sketches (Part 1) - ภาพรวม 12-5: Matrix Sketches (Part 2) - บทพิสูจน์	notes-12-1 notes-12-2