P与NPP能在多项式时间能找到解NP能在多项式时间内验证候选解的对错。NP 难所有 NP 问题都能在多项式时间内归约到它即它至少和 NP 类问题一样难。不要求多项式时间可验证。NP 完全NP ∩ NP 难机器学习的很多问题是 NP 难甚至更难的问题。但学习算法必须在多项式时间内找到解。如果可以彻底避免过拟合那就可以通过优化经验误差得到最优解构造性证明了 “P NP”。因此如果我们相信 “P ≠ NP”过拟合就不可避免。留出法使用注意事项1分层抽样。训练集、测试集中样本类别比例需和原数据集保持一致2train ratio。如果训练样本过小结果偏差大。如果测试样本过小结果方差大。代码Logistic Regression数学原理为什么需要 Logistic Regression? 答Logistic Regression 本质上是解决分类问题。如果使用单位阶跃函数输出标签再用 MSE 均方误差进行拟合由于单位阶跃函数不可导从数学上讲极难优化。Logistic Regression 做了什么去完成分类答使用 sgmoid 函数讲线性模型的输出值由离散标签变成了连续的概率值即模型输出为正例的概率构造负似然对数求解分类正确的最优参数sgmoid 函数引入了非线性没有闭式解可以直接通过数学公式等方法计算出的解可通过牛顿法求最优解。负似然对数及牛顿法求解似然函数likelihood∑i1mp0y0p1y1似然函数likelihood \sum_{i1}^{m}p_{0}^{y_{0}}p_{1}^{y_{1}}似然函数likelihood∑i1m​p0y0​​p1y1​​负对数似然negative_log_likelihood−∑i1m(y0logp0y1logp1)∑i1mlog(1ezi)−yizi负对数似然negative\_ log\_likelihood -\sum_{i1}^{m}(y_{0}logp_{0}y_{1}logp_{1}) \sum_{i1}^{m}log(1e^{z_{i}})-y_{i}z_{i}负对数似然negative_log_likelihood−∑i1m​(y0​logp0​y1​logp1​)∑i1m​log(1ezi​)−yi​zi​牛顿法coefficientst1coefficientst−H−1grad牛顿法coefficients_{t1} coefficients_{t}-H^{-1}grad牛顿法coefficientst1​coefficientst​−H−1grad二阶导HHjk∑i1mpi(1−pi)xijxikj/k是参数编号Hjk是矩阵里的一个元素H_{jk} \sum_{i1}^{m} p_i(1-p_i)x_{ij}x_{ik}j/k是参数编号 H_{j}{k}是矩阵里的一个元素Hjk​∑i1m​pi​(1−pi​)xij​xik​j/k是参数编号Hj​k是矩阵里的一个元素梯度grad)∑i1m(pi−yi)xi梯度grad) \sum_{i1}^{m}(p_{i}-y_{i})x_{i}梯度grad)∑i1m​(pi​−yi​)xi​代码dataclass# 快速定义只设置数据的类比如 initclassTrainingResult:coefficients:list[float]loss:floatiterations:intconverged:bool# 是否收敛classLogisticRegression:def__init__(self,max_iter:int100,tolerance:float1e-8,l2:float0.01)-None:# l2 0.01ifmax_iter0:raiseValueError(max_iter must be positive.)iftolerance0:raiseValueError(tolerance must be positive.)ifl20:raiseValueError(l2 must be non-negative.)self.max_itermax_iter self.tolerancetolerance self.l2l2 self.coefficients:list[float][]deffit(self,features:list[list[float]],labels:list[int])-TrainingResult:ifnotfeatures:raiseValueError(No training data was provided.)# 特征值非空iflen(features)!len(labels):raiseValueError(Feature rows and labels must have the same length.)# 特征值和标签一一对应ifset(labels)-{0,1}:# 对二分类而言只有 01raiseValueError(Labels must be encoded as 0 or 1.)feature_countlen(features[0])# 取出特征值的属性个数ifany(len(row)!feature_countforrowinfeatures):# 每个特征的属性个数必须一样不多不少raiseValueError(All feature rows must have the same length.)design_matrix[[1.0]rowforrowinfeatures]# 增加截距项parameter_countfeature_count1# 参数值1coefficients[0.0]*parameter_count# 初始化参数列表convergedFalse# 未收敛foriterationinrange(1,self.max_iter1):# 最多迭代 max_iter 次probabilities[sigmoid(dot(coefficients,row))forrowindesign_matrix]# 预测概率值列表gradient[0.0]*parameter_count# 梯度初始化hessian[[0.0]*parameter_countfor_inrange(parameter_count)]# 二阶导hessian矩阵forrow,probability,labelinzip(design_matrix,probabilities,labels):# 对于每一组数据residualprobability-label weightprobability*(1.0-probability)forcol_indexinrange(parameter_count):gradient[col_index]residual*row[col_index]# 按照公式不断累加梯度forinner_indexinrange(parameter_count):hessian[col_index][inner_index]weight*row[col_index]*row[inner_index]# 累加 hessian 矩阵中的每个元素forindexinrange(1,parameter_count):# 在截距以外的其他参数加正则化项下面是求一阶导 二阶导之后的内容gradient[index]self.l2*coefficients[index]hessian[index][index]self.l2# m 个样本之后才更新stepsolve_linear_system(hessian,gradient)coefficients[coefficient-deltaforcoefficient,deltainzip(coefficients,step)]ifvector_norm(step)self.tolerance:convergedTruebreakself.coefficientscoefficientsreturnTrainingResult(coefficients,self.loss(features,labels),iteration,converged)defpredict_proba_one(self,feature_row:list[float])-float:ifnotself.coefficients:raiseValueError(Model has not been fitted yet.)returnsigmoid(self.coefficients[0]dot(self.coefficients[1:],feature_row))defpredict_one(self,feature_row:list[float],threshold:float0.5)-int:returnint(self.predict_proba_one(feature_row)threshold)defloss(self,features:list[list[float]],labels:list[int])-float:design_matrix[[1.0]rowforrowinfeatures]negative_log_likelihood0.0forrow,labelinzip(design_matrix,labels):scoredot(self.coefficients,row)negative_log_likelihoodsoftplus(score)-label*score regularization0.5*self.l2*sum(coefficient*coefficientforcoefficientinself.coefficients[1:])returnnegative_log_likelihoodregularization读写文件csv/txt/json/mdimportcsv# 读取和写入 CSV 文件frompathlibimportPath# 更方便、安全地处理文件路径pathPath(data.txt)DEFAULT_DATA_PATHPath(__file__).with_name(watermelon_3a.csv)# _file_: 当前 Python 文件的路径字符串with_name: 要找的文件名前者是相对于当前工作目录读取名为data.txt的文件返回的是一个 Path 对象后者是相对于当前 .py 脚本读取名为 watermelon_3a.csv 的文件返回的是一个 Path 对象。列表推导式的三种形式列表推导式就是一种快速生成列表的写法。missing_columns[columnforcolumnin(*feature_columns,label_column)ifcolumnnotinreader.fieldnames]# 检查特征列和标签列是否存在ifmissing_columns:raiseValueError(fMissing columns in CSV:{, .join(missing_columns)})[表达式for变量in可迭代对象][表达式for变量in可迭代对象if条件][值1if条件else值2for变量in可迭代对象]# if{值1}else{值2}*后面加元组、列表、字符串、range、集合、字典表示解包。默认情况下解包字典的key。如果需要解包值/键值对 *dict.values()/ *dict.items()遍历特征列和标签列如果有不在表头的就记录在列表 missing_columns。分隔符.join(字符串列表在每两个元素之间放一个分隔符用来把一堆字符串拼成一个字符串。比如parts[2026,08,13]print(-.join(parts))# 2026-08-13python里的条件表达式三元表达式比如Aif条件elseB1ifrow[label_column].strip()positive_labelelse0with···as···用法如下with表达式as变量:代码块# Python 的上下文管理器语法# 最常见用途是打开文件后自动关闭文件withpath.open(r,encodingutf-8)asf:textf.read()withpath.open(r,encodingutf-8-sig,newline)ascsv_file:把文件打开把打开的文件对象命名为 csv_file在 with 代码块里使用它代码块结束后自动关闭文件newline“”它控制 Python 打开文本文件时怎么处理换行符。CSV 模块自己会处理换行。如果你不写 newline“”Python 可能先自动转换一遍换行csv 模块又处理一遍尤其在 Windows 上写 CSV 时可能出现多余空行。“utf-8-sig”用 UTF-8 读取同时兼容文件开头可能存在的 BOM。withpath.open(r,encodingutf-8-sig,newline)ascsv_file:# new_linereadercsv.DictReader(csv_file)# 一个读取器。这个读取器有自己的读取规则ifreader.fieldnamesisNone:# 读取器相当于是一个类.fieldnames表示取出表头其实也就是字典的键列表raiseValueError(CSV file has no header row.)创建了一个对象DictReader可迭代、内部有自己的读取规则它的规则读取第一行作为表头 fieldnames后面每一行数据value都和表头key配对每次迭代返回一个字典 row。也可以这么理解csv.DictReader 是一个类csv.DictReader(csv_file) 创建一个 DictReader 实例对象。row_ids:list[str][]# 保存样本编号features:list[list[float]][]# 保存样本特征矩阵labels:list[int][]# 保存标签正类为 1负类为 0forline_number,rowinenumerate(reader,start2):# reader是一个可迭代对象enumerate是给它加编号从1开始但是这里规定从2开始。enumerate 返回的对象是什么编号加在最前面row_ids.append(row.get(编号,str(line_number-1)))# 是从可迭代对象中读出的字典.dict.get(key,default如果dict[key]存在那么就用它否则就用行编号减1features.append([float(row[column])forcolumninfeature_columns])# 添加的元素添加的是一个列表。列表中的元素就是字典从键当中取的值labels.append(1ifrow[label_column].strip()positive_labelelse0)# python中的三元推导式enumerate() 返回的是一个可迭代对象它每次迭代会返回一个二元组(编号, 原来的元素)指定起始编号start2默认从0开始。enumerate() 不是把编号真的“加进”原列表或原字典里它只是遍历时临时配一个编号。returnrow_ids,list(feature_columns),features,labels注意有逗号才是元组括号只是分组或者提高可读性。当然类型打印的时候括号也是用来区分类别的一个标志。但自己写的时候有括号声明的就是元组。比如这个 return 返回的就是一个元组。