CS230 吴恩达深度学习课程

Refernece

• bilibili 吴恩达深度学习
• 网易云课堂deeplearning.ai
• 吴恩达深度学习课程笔记及资源
• CS230
• CS230 Code
• 知识点速查 [Github]

3 多变量线性回归

1.矩阵如何相加？

2.矩阵如何和标量相乘？

3.矩阵的乘法规则？

𝑚 × 𝑛矩阵乘以𝑛 × t矩阵，变成𝑚 × t矩阵。

矩阵的乘法不满足交换律：𝐴 × 𝐵 ≠ 𝐵 × 𝐴
矩阵的乘法满足结合律。即：𝐴 × (𝐵 × 𝐶) = (𝐴 × 𝐵) × C

4.什么是单位矩阵？

在矩阵的乘法中，有一种矩阵起着特殊的作用，如同数的乘法中的 1,我们称 这种矩阵为单位矩阵．它是个方阵，一般用 𝐼 或者 𝐸 表示，本讲义都用 𝐼 代表单位矩阵，从左上角到右下角的对角线（称为主对角线）上的元素均为 1 以外全都为 0。

5.什么是矩阵的逆？

矩阵的逆：如矩阵𝐴是一个𝑚 × 𝑚矩阵（方阵），如果有逆矩阵，则：

6.什么是矩阵的转置？

矩阵的转置：设𝐴为𝑚 × 𝑛阶矩阵（即𝑚行𝑛列），第𝑖行𝑗列的元素是𝑎(𝑖,𝑗)，即：𝐴 = 𝑎(𝑖,𝑗)
定义𝐴的转置为这样一个𝑛 × 𝑚阶矩阵𝐵，满足𝐵 = 𝑎(𝑗, 𝑖)，即 𝑏(𝑖,𝑗) = 𝑎(𝑗, 𝑖)（𝐵的第𝑖行
第𝑗列元素是𝐴的第𝑗行第𝑖列元素），记

4 Parallel Programming Abstractions

Reference

• ISPC [docs]

Brief

• SPMD - single program, multiple data - Programming model
• ISPC - Intel SPMD Program Compiler
• Programming models
• SMP - Symmetric multi-processor
• NUMA - Non-uniform memory access

SPMD & ISPC

• SPMD - single program, multiple data
• ISPC - Intel SPMD Program Compiler
  • 用于编译串行 C code 到 SIMD implementation 程序 - xxx.ispc --> xxx.o
• Program Instance: 同时运行的程序 single program
• gang: 一系列的 Program Instance
  • = N x Program Instance - N 取决于 SIMD width
  • 用于 one core + SIMD
• task: 用于 multi-core
  • 比 thread 更轻量
• ISPC supports parallelism
  • SPMD parallelism: SIMD vector lanes on a single core
  • task parallelism: multiple processor cores

Interleaved assignment	Blocked assignment

Programming models

• Thread Programming model
• ISPC Programming model

System Layers Interface & Implementation
Thread Programming model
ISPC Programming model

• 按照通信方式可以分为三种模型
• 实际使用中会混合使用编程模型 Shared Address Space + Message Passing

Shared Address Space Model

Shared address space
SMP HW Implementation
NUMA HW Implementation

• SMP - Symmetric(shared-memory) multi-processor
• NUMA - Non-uniform memory access
• Interconnect
  • Hyper-transport - AMD
  • QuickPath (QPI) - Intel

Message Passing Model

• MPI - Message Passing Interface
• 通常用于机器集群

Message passing

Data Parallel Model

• 一个函数处理大量的数据
• HW support - Vector Processors - SIMD
• SPMD Programming
• Stream Programming
• Languages - ISPC/OpenCL/CUDA

ISPC-> SPMD/SIMD

Stream Programming

• Streams - Data
• Kernels - 处理函数
• Gather/Scatter

CS229 吴恩达机器学习课程

Lectures

• 1 绪论：初识机器学习
• 2 单变量线性回归
• 3 线性代数回顾
• Matlab&Octave Install&Config
• 4 多变量线性回归
• Octave/Matlab 教程
• Logistic 回归
• 正则化
• 神经网络学习
• 神经网络参数的反向传播算法
• 应用机器学习的建议
• 机器学习系统设计
• 支持向量机
• 无监督学习
• 降维
• 异常检测
• 推荐系统
• 大规模机器学习
• 应用举例：照片OCR

Reference

• 网易云课堂版
• 斯坦福大学2014（吴恩达）机器学习教程中文笔记 [Github]
• 机器学习 - coursera
• CS229
• 精炼知识点 [Github]
• CS229 资源
• 南瓜书PumpkinBook - Github [Page]

CS231n 计算机视觉 李飞飞

• 章节1深度学习与计算机视觉
• 课时1课件下载方法
• 课时2计算机视觉历史回顾与介绍（上）27:29
• 课时3计算机视觉历史回顾与介绍（中）21:28
• 课时4计算机视觉历史回顾与介绍（下）25:46
• 课时5数据驱动的图像分类方式：K最近邻与线性分类器（上）29:35
• 课时6数据驱动的图像分类方式：K最近邻与线性分类器（下）28:57
• 课时7 线性分类器损失函数与最优化（上）36:30
• 课时8线性分类器损失函数与最优化（下）35:50
• 课时9反向传播与神经网络初步（上）40:59
• 课时10反向传播与神经网络初步（下）40:42
• 课时11神经网络训练细节part1（上）40:29
• 课时12神经网络训练细节part1（下）40:06
• 课时13神经网络训练细节part2（上）35:42
• 课时14神经网络训练细节part2（下）34:58
• 课时15卷积神经网络详解（上）40:12
• 课时16卷积神经网络详解（下）39:48
• 课时17迁移学习之物体定位与检测（上）37:05
• 课时18迁移学习之物体定位与检测（下）28:58
• 课时19卷积神经网络的可视化与进一步理解（上）39:48
• 课时20卷积神经网络的可视化与进一步理解（下）39:41
• 课时21循环神经网络（上）30:45
• 课时22循环神经网络（下）40:05
• 课时23卷积神经网络工程实践技巧与注意点（上）36:48
• 课时24卷积神经网络工程实践技巧与注意点（下）39:07
• 课时25深度学习开源库使用介绍（上）42:40
• 课时26深度学习开源库使用介绍（下）39:44
• 课时27图像分割与注意力模型（上）33:56
• 课时28图像分割与注意力模型（下）38:08
• 课时29视频检测与无监督学习（上）36:40
• 课时30视频检测与无监督学习（下）43:19
• 课时31来自谷歌大脑负责人Jeff Dean的受邀讲座（上）36:57
• 课时32来自谷歌大脑负责人Jeff Dean的受邀讲座（下）39:03
• 章节2配套作业与答案（中文版）
• 课时33Asignment 1-Q1 k-Nearest Neighbor (kNN) exercise
• 课时34Assignment 1-Q2 Multiclass Support Vector Machine
• 课时35Assignment 1-Q3 Softmax exercise
• 课时36Assignment 1-Q4 Two-Layer Neural Network
• 课时37Assignment 1-Q5 Image features exercises
• 课时38Assignment 2 Q1-Q3一段关于神经网络的故事
• 课时39Assignment 2 Q4 - ConvNet on CIFAR-10
• 课时40Assignment 2 Q5 - TensorFlow
• 课时41Assignment 3 Q1 - Q2
• 课时42Assignment 3 Q3
• 课时43Assignment 3 Q4
• 课时44Assignment 3 Q5

Reference

• 斯坦福CS231n李飞飞计算机视觉
• CS231n: Convolutional Neural Networks for Visual Recognition
• 2017CS231n 斯坦福李飞飞视觉识别
• Schedule and Syllabus

• PCAP15418
  • 1
  • 2
  • 3
  • 4
• CS229
  • 1
  • 2
  • 3
  • 4

5 Parallel Programming Basics

• 统计学习方法-李航
• CS231n 计算机视觉-李飞飞
• 吴恩达机器学习课程
• 吴恩达深度学习课程
• CMU 15-418 并行计算机架构及编程
  • 1 Why parallelism?
  • 2 Instruction-Level Parallelism
  • 3 A Modern Multicore Processor
  • 4 Parallel Programming Abstractions
• CS329P Practical Machine Learning
• 北邮计算机视觉

4 多变量线性回归

1.多变量线性回归的假设

即

2.多变量线性回归的代价函数

3.多变量线性回归的批量梯度下降算法

即：

求导数后得到：

更新参数：



……
……

4.特征缩放

面对多维特征问题的时候，我们要保证这些特征都具有相近的尺度，这将帮助梯度下降算法更快地收敛。

当两个特征有较大的数量级差异时，绘制代价函数的等高线图能，看出图像会显得很扁，梯度下降算法需要非常多次的迭代才能收敛。
解决的方法是尝试将所有特征的尺度都尽量缩放到-1到1之间。

5.学习率

• 如果学习率过小，则达到收敛所需的迭代次数会非常高；
• 如果学习率过大，每次迭代可能不会减小代价函数，可能会越过局部最小值导致无法收敛。

6.特征和多项式回归

线性回归并不适用于所有数据，有时我们需要曲线来适应我们的数据，比如二次方模型或者三次方模型：

多项式回归模型，在运行梯度下降算法前，特征缩放非常有必要。

7.正规方程

对代价函数求导

对于那些不可逆的矩阵（通常是因为特征之间不独立，如同时包含英尺为单位的尺寸和米为单位的尺寸两个特征，也有可能是特征数量大于训练集的数量），正规方程方法是不能用的。

8.梯度下降与正规方程的比较

梯度下降	正规方程
需要选择学习率a	不需要
需要多次迭代	一次运算得出
当特征数量n大时也能较好适用	需要计算 如果特征数量n较大则运算代价大，因为矩阵逆的计算时间复杂度为，通常来说当n小于10000 时还是可以接受的
适用于各种类型的模型	只适用于线性模型，不适合逻辑回归模型等其他模型

1 Why parallelism?

• 并行计算发展史: 多处理器的计算机 --> 云计算
• 处理器性能发展史
  • 4/8/16/32 --> 64 bit
  • 3.5 CPI --> 1.1 CPI
  • 10Mhz/200Mhz --> 3GHz
  • ILP: Superscalar & OoO
  • ...
• CPU 瓶颈 - Power Density Wall
  • 单处理器的性能到达瓶颈, 提升很慢

Term

• CPI : Cycles Per Instruction
• ILP: instruction-level parallelism - 指令并行
• OoO: Out of order

History of Parallel Computing

• 1970s 用于超级计算机进行科学计算
• 1990s 用于数据库/Web服务/交易
• 2004 CPU 频率升级到达技术瓶颈
• 2019 用于云计算

Microprocessor Trend Data

SuperComputer VS Cloud System(Data Center)

并行编程 4 个方向

• SIMD and multi-core parallelism
• CUDA programming on NVIDIA GPUs
• Parallel Programming via a Shared-Address Space Model
• Parallel Programming via a Message Passing Model

Metrics

• Performance - 性能
  • 2004 年之前
  • speedup = 执行时间(1 Processor) / 执行时间(N Processors)
  • 影响 speedup 的因素 - 通信(数据同步)/imbalance(CPU 任务分配不均)
• Efficiency - 效率
  • 2004 年之后
  • 芯片面积方面 - 最大化 Performance per area
  • 功率消耗方面 - 最大化 Performance per Watt

Reference

• Microprocessor Trend Data

Le vent se lève, ‌‍‍‌‍​‌‌‍​‍‌‌‌‌​‌‌‍‍‍​‌‍‍‍‍​‌‍‍‍‍​‌‍‍‌‍​‌‌‍​‍‍‌‌‌​‌‌‍‍‍​‌‌‌‍‍​‌‍‍‍‍​‌‍‍‌‍​‌‌‍​‌‌‌‌‍​‌‌‍‌​‍‌‌‌‌​‍‍‍‍‍​‍‍‍​‍‌​‌​‌‌‌​‌‌‌‌​‌‌‍il faut tenter de vivre.

This is a Course Notes. Supported By the Template Wiki

Index

Reference

• 官网

Brief

程序性能优化理论与方法

• 1 程序性能优化的意义
• 2 程序性能的度量指标及优化流程
• 3 程序性能的分析和测量
• 4 系统配置优化
• 5 编译与运行优化
• 6 程序编写优化
• 7 并行
• 7.1 指令级并行
• 7.2 数据级并行
• 8 访存优化
• 9 OpenMP
• 9.1 并行区重构
• 9.2 向量化
• 9.3 避免伪共享
• 9.4 负载均衡优化
• 9.5 避免隐式同步
• 9.6 流水并行优化
• 10 CUDA 程序优化
• 11 MPI
• 11.1 数据划分优化

Practical Machine Learning

• 1 Data I Logistics, course introduction, data acquisition
• 2 Data II Web scraping, data labeling, exploratory data analysis
• 3 Data III Data cleaning, data transformation, feature engineering, data summary
• 4 ML model recap I ML overview, tree methods, linear methods
• 5 ML model recap II Neural networks
• 6 Model Validation Evaluation metrics, underfitting and overfitting, model validation
• 7 Model Combination Bias and variance, bagging, boosting, stacking
• 8 Covariate Shift Generalization performance recap, covariate shift
• 9 Covariate Shift II Covariate shift with more math, adversarial data and invariants
• 10 Label Shift Two sample test, label shift
• 11 Data beyond IID Independence tests, sequence models , graphs
• 12 Model Tuning Model tuning, HPO algorithms, NAS algorithms
• 13 Deep Network Tuning Batch and layer norms, residual connections, attention
• 14 Transfer Learning Fine-tuning for CV, fine tuning for NLP, prompt-based learning
• 15 Model Compression Pruning and quantization, knowledge distillation
• 16 Multimodal data Multimodal data
• 17 Fairness Examples, law, risk distributions, criterias , in practice
• 18 Explainability Explainability, strategies , conditioning and backdoors, axiomatic approaches, heuristics

Reference

• Practical Machine Learning - Stanford-CS329P

3 A Modern Multicore Processor

• Multi-Core
• SIMD
• Hyperthreading
• Memory

Multi-Core

• Thread-level
• 每个 core 执行不同的指令

SIMD

• SIMD Precessing(Vector Program/Computing)
• SIMD 并行化在编译时确定
• Instruction-level/Data-Parallel
• 每个 core->ALUs 执行 相同的指令
• AVX intrinsics
  • SSE -> AVX -> AVX512
• 32 -->256(=32*8) ==> 同时处理 8x data

SIMD Conditional execution

• 当执行代码段存在条件判断时，不同的分支执行不同的指令, 会有一部分时间浪费掉
• 不好的 code 会严重影响 SIMD 效率
  • Instruction stream coherence - 指令流的连续性影响 SIMD 的效率
  • Divergent/Divergence - 发散执行, 指缺乏连续性

Hyperthreading & Interleaved multi-threading

• Simultaneous Multi-Threading - Hyperthreading - 超线程
  • Single core does the work of multiple cores
• in-order 部分独立, Out-of-Order 部分共享
• 对单线程性能无提升，多线程性能有可能提升

Interleaved multi-threading

prefetching, multi-threading is a latency hiding, not a latency reducing technique ？？

Memory

• Latency(cycles/nsec) - 读取延迟
• Bandwidth (GB/s) - 读取最大速度
• Stalls: 运行下条指令时因为依赖不能运行
  • 内存访问是主要 Stalls
  • Caches reduces stalls 可以降低 memory access latency
  • Prefetching reduces stalls: Prefetching data into caches(prefetching 错误的话也会导致 performance 下降)
  • Multi-Threading reduces stalls
• 解决方案
  • L1/2/3 Cache --> DRAM: Cache 有效减少了 内存访问时间
  • Prefetching data 动态分析程序, 预测将要使用的 data(也会存在对performance坏的影响: 占用带宽/污染缓存)
  • Multi-threading 当一个线程 stall,其他线程可以继续执行

L12 VS L123 + Prefetching

CMU 15-418 并行计算机架构及编程

• 1 Why parallelism?
• 2 Instruction-Level Parallelism
• 3 A Modern Multicore Processor
• 4 Parallel Programming Abstractions
• 5 Parallel Programming Basics
• 6 Performance Optimization Part 1: Work Distribution and Scheduling
• 7 GPU Architecture & CUDA Programming
• 8 Performance Optimization Part II: Locality, Communication, and Contention
• 9 Parallel Programming Case Studies
• 10 Workload-Driven Performance Evaluation
• 11 Snooping-Based Cache Coherence
• 12 A Basic Snooping-Based Multi-Processor Implementation
• 13 Directory-Based Cache Coherence
• 14 Memory Consistency
• 15 interconnection Networks
• 16 Implementing Synchronization
• 17 Performance Monitoring Tools
• 18 Fine-grained synchronization & lock-free programming
• 19 Transactional Memory
• 20 Under the Hood, Part 1: Implementing Message Passing
• 21 Heterogeneous Parallelism and Hardware Specialization
• 22 Domain-Specific Programming Systems
• 23 Domain-Specific Programming on Graphs
• 24 Parallel Deep Neural Networks

Reference

• 15-418/15-618: Parallel Computer Architecture and Programming
• 课件

Reference

• notebook code - fengdu78
• Learn-Statistical-Learning-Method, Second Edition

Brief

• 第1章 统计学习方法概论
• 第2章 感知机
• 第3章 k近邻法
• 第4章 朴素贝叶斯
• 第5章 决策树
• 第6章 逻辑斯谛回归
• 第7章 支持向量机
• 第8章 提升方法
• 第9章 EM算法及其推广
• 第10章 隐马尔可夫模型
• 第11章 条件随机场
• 第12章 监督学习方法总结
• 第13章 无监督学习概论
• 第14章 聚类方法
• 第15章 奇异值分解
• 第16章 主成分分析
• 第17章 潜在语义分析
• 第18章 概率潜在语义分析
• 第19章 马尔可夫链蒙特卡洛法
• 第20章 潜在狄利克雷分配
• 第21章 PageRank算法
• 第22章 无监督学习方法总结

2 Instruction-Level Parallelism

• 多样的处理器 CPU/GPU/FPGA/VPU/...
• 不同处理器的并行方法
• ILP
  • Pipelining & Superscalar - 同时执行多条指令
  • Out of order execution - 动态调度执行指令
  • Speculation - 预测下条指令
• in-order/out-of-order

各种处理器

CPU ILP - instruction-level parallelism

Simple CPU Model

• Fetch – get the next instruction from memory
• Decode – figure out what to do & read inputs
• Execute – perform the necessary operations
• Commit – write the results back to registers / memory

Pipelining

• 𝑁-stage pipeline gives up to 𝑁 × speedup(N = 15 是个临界点)
• Fetch/Decode/Execute/Commit - 4X Speedup
• 一些限制 Pipeling 并行的因素
  • Data Hazards
  • Control Hazards

Data Hazards & Forwarding data

• Data hazards:
  • 并行需要是独立的任务, 而许多指令之间并不独立(寄存器读写依赖)
  • 当后一条指令需要用到前一条指令的寄存器时会填充 NOP 指令, 以等到前一条指令 commit
  • example: 前一条指令要写 R3, 后一条指令执行时要读 R3, 后一条指令执行时,前一条指令还没有 commit

• 解决方案: Forwarding data - CPU在一个时钟周期内，把一个单元的输出值内容拷贝到另一个单元的输入值中
  • Forwarding is expensive in deep pipelines

Control Hazards & Speculation

• Control Hazards - 按照 Static instruction sequence 预取指令, 预取到错误指令
  • example: 前一条指令执行完跳转了, 提前 Fetch 的指令是错误的

• 解决方案: Speculation - CPU 猜测下一条要执行的指令 - 如果猜错, rolling back

  • 95% 猜对？？

Out-of-Order

• Out-Of-Order(OoO): 乱序执行 - 执行已经准备好的指令
• Dataflow: 根据寄存器依赖并行执行
  • True dependence: read-after-write
• Latency Bound - Critical Path - 迭代中最长路径
• Throughput Bound - Execution Unit 数量(并行执行指令的个数)/Structural hazards
• Out-of-Order 比 In-Order 对好代码更少限制

• ldr, mul execute in 2 cycles
• cmp, bne execute in 1 cycle
• mla executes in 3 cycles
• 每个循环执行 3 cycles, 一共 5 条指令
• IPC(Instructions per cycle) = 5/3 =1.66... > 1(perfect pipeling)

Structural hazard

• Structural hazard: 浮点数/整数/Memory 特殊硬件资源有限

Summary

• ILP & Pipeline 扩展性不好/动态调度 & OoO 更复杂/代价更高
• 并行指令是否独立需要 O(w²) 的比较, W= issue width of processor
• Multicore 更 Efficient

1 绪论

1.什么是机器学习?

一个程序被认为能从经验 E 中学习，解决任务 T，达到性能度量值 P
当且仅当，有了经验 E 后，经过 P 评判，程序在处理 T 时的性能有所提升。   
                             ———— Tom Mitchell(卡内基梅隆大学) 

• 分为 监督学习 & 无监督学习

2.机器学习能做些什么事情?

• 搜索引擎
• 垃圾邮件分类
• 身份识别
• 游戏
• 自动驾驶

3.什么是监督学习?

监督学习(Supervised Learning)指的就是我们给学习算法一个数据集。这个数据集由“正确答案”组成。运用学习算法，算出更多的正确答案。

• 分类数据集中的 Label
• 垃圾邮件数据集中 是否为垃圾邮件
• 房价预测问题中的房价
• 一般分为 回归问题 & 分类问题

4.什么是回归问题？

研究一组随机变量(Y1 ，Y2 ，…，Yi)和另一组(X1，X2，…，Xk)变量之间关系的统计分析方法

• 预测值为连续值
• 预测房价/股票走势

5.什么是分类问题？

根据特征使用算法预测类别

• 预测值为离散值
• 图像分类/文本情感识别

6.什么是无监督学习?

无监督学习(Unsupervised Learning)中没有任何的标签或者是有相同的标签或者就是没标签。
无监督学习算法可能会把这些数据分成几个不同的簇。

• 聚类算法

2 单变量线性回归

1.单变量线性回归问题

• 只含有一个特征(输入变量) 的回归问题

房价预测

• 问题: 房价和面积成正比, 建立一个通过面积预测房价的算法

2.什么是代价函数？

代价函数也被称作平方误差函数，有时也被称为平方误差代价函数。

3.代价函数的解法？

4.什么是梯度下降？

梯度下降是一个用来求函数最小值的算法。
开始时我们随机选择一个参数的组合，计算代价函数，然后我们寻找下一个能让代价函数值下降最多的参数组合。我们持续这么做直到找到一个局部最小值（local minimum）。

因为我们并没有尝试完所有的参数组合，所以不能确定我们得到的局部最小值是否便是全局最小值（global minimum），选择不同的初始参数组合，可能会找到不同的局部最小值。

批量梯度下降（batch gradient descent）算法的公式为：

其中α是学习率(learning rate），它决定了我们沿着能让代价函数下降程度最大的方向向下迈出的步子有多大，在批量梯度下降中，我们每一次都同时让所有的参数减去学习速率乘以代价函数的导数。

5.梯度下降的求解方法？

6.什么是批量梯度下降？

在梯度下降的每一步中，我们都用到了所有的训练样本，在梯度下降中，在计算微分求导项时，我们需要进行求和运算，所以，在每一个单独的梯度下降中，我们最终都要计算这样一个东西，这个项需要对所有m个训练样本求和。因此，批量梯度下降法这个名字说明了我们需要考虑所有这一"批"训练样本，而事实上，有时也有其他类型的梯度下降法，不是这种"批量"型的，不考虑整个的训练集，而是每次只关注训练集中的一些小的子集。