【大数据】机器学习----------计算机学习理论
1. PAC (Probably Approximately Correct) 学习
1.1 基本概念
- PAC 学习旨在找到一个假设 (h)，使得在高概率下，该假设的错误率低于一个可接受的阈值。
1.2 公式
- 对于一个学习算法 (A) 和假设空间 (H)，对于任意的 (\epsilon) 和 (\delta)，存在 (m) 个样本，使得对于任何分布 (D) 上的目标概念 (c)，以至少 (1 - \delta) 的概率，学习算法 (A) 输出的假设 (h) 满足：
，其中 (err_D(h)) 是假设 (h) 在分布 (D) 上的错误率，(S) 是大小为 (m) 的样本集。
2. 有限假设空间
2.1 基本概念
- 当假设空间 (H) 是有限的时，我们可以使用简单的概率分析来界定学习所需的样本数量。
2.2 公式
- 样本复杂度上界在这里插入图片描述
表示为了保证以至少 (1 - \delta) 的概率找到错误率小于 (\epsilon) 的假设，所需的样本数量。
3. VC (Vapnik-Chervonenkis) 维
3.1 基本概念
- VC 维衡量了假设空间 (H) 的复杂度，它是可以被 (H) 打散的最大样本集的大小。
3.2 公式
- 对于一个假设空间 (H)，其 VC 维 (d_{VC}(H)) 是满足以下条件的最大的 (d)：存在一个大小为 (d) 的样本集 (S)，使得 (H) 可以实现 (S) 的所有可能的标记（(2^d) 种）。
4. [Rademacher 复杂度]
4.1 基本概念
- Rademacher 复杂度衡量了函数类 (F) 拟合随机噪声的能力，是学习理论中的一个重要工具。
4.2 公式
- 对于一个函数类 (F) 和样本集
，经验 Rademacher 复杂度定义为：
，其中 (\sigma_i) 是独立同分布的 Rademacher 随机变量
5. 稳定性
5.1 基本概念
- 稳定性关注学习算法在数据的小扰动下的性能变化，分为均匀稳定性和假设稳定性等。
5.2 公式
- 对于一个学习算法 (A)，均匀稳定性定义为：
，其中 (S) 是样本集，(z) 和 (z’) 是不同的数据点，(S_{(z)}) 是将 (z) 替换为 (z’) 后的样本集，(L) 是损失函数。
6. 代码示例
6.1 计算有限假设空间的样本复杂度
import math
def sample_complexity(H_size, epsilon, delta):
"""
计算有限假设空间的样本复杂度
:param H_size: 假设空间的大小 |H|
:param epsilon: 错误率阈值
:param delta: 概率阈值
:return: 所需的样本数量 m
"""
m = math.ceil((1 / epsilon) * (math.log(H_size) + math.log(1 / delta)))
return m
# 示例
H_size = 100
epsilon = 0.1
delta = 0.05
print("Sample complexity:", sample_complexity(H_size, epsilon, delta))
6.2 计算 VC 维的示例（简单示例，假设已知可以打散的样本集大小）
def vc_dimension(can_shatter_size):
"""
计算 VC 维
:param can_shatter_size: 可以打散的最大样本集大小
:return: VC 维
"""
return can_shatter_size
# 示例
can_shatter_size = 5
print("VC dimension:", vc_dimension(can_shatter_size))
6.3 计算 Rademacher 复杂度的经验估计（简单示例）
import numpy as np
def empirical_rademacher_complexity(F, X):
"""
计算经验 Rademacher 复杂度
:param F: 函数类
:param X: 样本集
:return: 经验 Rademacher 复杂度
"""
m = len(X)
rademacher_sum = 0
num_iterations = 1000 # 为了估计期望，多次采样
for _ in range(num_iterations):
sigma = np.random.choice([-1, 1], size=m)
max_val = -float('inf')
for f in F:
val = np.mean(sigma * np.array([f(x) for x in X]))
max_val = max(max_val, val)
rademacher_sum += max_val
return rademacher_sum / num_iterations
# 示例函数类和样本集
def f1(x):
return x
def f2(x):
return 2 * x
F = [f1, f2]
X = np.array([1, 2, 3, 4, 5])
print("Empirical Rademacher complexity:", empirical_rademacher_complexity(F, X))
6.4 稳定性的简单示例（使用均方误差损失）
import numpy as np
def uniform_stability(A, S, z, z_prime, L):
"""
计算均匀稳定性
:param A: 学习算法
:param S: 样本集
:param z: 数据点
:param z_prime: 另一个数据点
:param L: 损失函数
:return: 均匀稳定性
"""
S_z = np.copy(S)
index = np.random.randint(len(S))
S_z[index] = z_prime
loss_diff = np.abs(L(A(S), z) - L(A(S_z), z_prime))
return loss_diff
def mean_squared_error(y_true, y_pred):
"""
均方误差损失函数
:param y_true: 真实值
:param y_pred: 预测值
:return: 均方误差
"""
return np.mean((y_true - y_pred) ** 2)
# 示例学习算法（简单线性回归）
def linear_regression(S):
X = S[:, :-1]
y = S[:, -1]
w = np.linalg.inv(X.T @ X) @ X.T @ y
return w
# 示例样本集和数据点
S = np.random.rand(100, 2)
z = np.random.rand(2)
z_prime = np.random.rand(2)
print("Uniform stability:", uniform_stability(linear_regression, S, z, z_prime, mean_squared_error))
代码解释
有限假设空间代码解释：
sample_complexity函数根据公式 (m \geq \frac{1}{\epsilon}(\ln |H| + \ln \frac{1}{\delta})) 计算所需的样本数量。
VC 维代码解释：
vc_dimension函数根据可以打散的最大样本集大小计算 VC 维，这里假设已知可以打散的样本集大小。
Rademacher 复杂度代码解释：
empirical_rademacher_complexity函数通过多次采样 Rademacher 随机变量，计算函数类 (F) 对样本集 (X) 的经验 Rademacher 复杂度。
稳定性代码解释：
uniform_stability函数计算学习算法 (A) 的均匀稳定性，使用均方误差损失函数作为损失函数。linear_regression函数是一个简单的线性回归学习算法示例。
原文地址：https://blog.csdn.net/yuanbenshidiaos/article/details/145276275
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！