https://www.nituchao.com/ 计算机是人造科学，数学是神造科学！ https://www.nituchao.com/optimize/92.html 2024-04-07T10:57:33+08:00 CEM（Cross-Entropy Method）是一种优化算法，通常用于解决连续优化问题。它的基本思想是通过迭代地生成随机样本，并根据样本在目标函数上的表现来更新参数，以找到最优解。下面是一个具体的例子，展示如何使用CEM算法来解决一个简单的连续优化问题。实例假设我们要最小化函数 f(x) = x^2 + 2x + 1，其中 x 是实数。我们想找到使函数 f(x) 取得最小值的 x 值。import numpy as np # 定义目标函数 def f(x): return x**2 + 2*x + 1 # 定义CEM算法的参数 num_samples = 100 # 每次迭代生成的样本数量 elite_frac = 0.2 # 每次迭代保留下来的精英个数的比例前20% learning_rate = 0.1 # 每次迭代的学习率 # 定义初始解集 mean = 0.0 std = 1.0 solutions = np.random.normal(mean, std, num_samples) # 接下来，我们执行CEM算法的迭代过程。在每次迭代中，我们生成样本， # 计算他们在目标函数上的表现，选择表现最好的一部分样本，并使用他 # 们来更新解集的均值和标准差 num_iterations = 10 # 迭代次数 for i in range(num_iterations): # 生成样本 samples = np.random.normal(mean, std, num_samples) # 计算样本在目标函数上的表现 scores = f(samples) # 选择表现最好的一部分样本 elite_size = int(num_samples * elite_frac) elite_indices = np.argsort(scores)[:elite_size] elite_samples = samples[elite_indices] # 更新解集的均值和标准差 mean = np.mean(elite_samples) std = np.std(elite_samples) # 打印当前的均值和标准差 print(f"Iteration {i+1}: Mean = {mean:.4f}, Std = {std:.4f}") # 输出迭代结果 best_sample = elite_samples[0] best_score = f(best_sample) print(f"Best sample after iteration {i+1}: x = {best_sample:.4f}, f(x) = {best_score:.4f}") # print(elite_samples)运行结果：Iteration 1: Mean = -1.0185, Std = 0.1761 Best sample after iteration 1: x = -1.0124, f(x) = 0.0002 Iteration 2: Mean = -0.9993, Std = 0.0225 Best sample after iteration 2: x = -1.0004, f(x) = 0.0000 Iteration 3: Mean = -0.9999, Std = 0.0044 Best sample after iteration 3: x = -0.9999, f(x) = 0.0000 Iteration 4: Mean = -1.0000, Std = 0.0011 Best sample after iteration 4: x = -1.0000, f(x) = 0.0000 Iteration 5: Mean = -1.0000, Std = 0.0001 Best sample after iteration 5: x = -1.0000, f(x) = 0.0000 Iteration 6: Mean = -1.0000, Std = 0.0000 Best sample after iteration 6: x = -1.0000, f(x) = 0.0000 Iteration 7: Mean = -1.0000, Std = 0.0000 Best sample after iteration 7: x = -1.0000, f(x) = 0.0000 Iteration 8: Mean = -1.0000, Std = 0.0000 Best sample after iteration 8: x = -1.0000, f(x) = 0.0000 Iteration 9: Mean = -1.0000, Std = 0.0000 Best sample after iteration 9: x = -1.0000, f(x) = 0.0000 Iteration 10: Mean = -1.0000, Std = 0.0000 Best sample after iteration 10: x = -1.0000, f(x) = 0.0000即：当取x=-1.0000时，f(x) = x^2 + 2x + 1有最小值0.0000 https://www.nituchao.com/optimize/91.html 2024-04-07T10:49:00+08:00 坐标随机梯度下降法（Coordinate Stochastic Gradient Descent，简称CSGD）是一种优化算法，用于求解目标函数的最小化问题。与传统的梯度下降法不同，CSGD每次迭代仅更新一个坐标（参数），而不是同时更新所有参数。CSGD的基本思想是，在每次迭代中，选择一个随机的坐标（参数），然后计算该坐标上的梯度，并更新该坐标的取值。这样，通过在不同的坐标上进行迭代更新，最终可以达到目标函数的最小值。下面是CSGD的基本步骤：初始化参数：给定一个初始的参数向量。随机选择一个坐标：从参数向量中随机选择一个坐标。计算梯度：计算选择的坐标上的梯度。更新坐标：使用梯度信息更新选择的坐标的取值。重复步骤2-4，直到满足停止条件（例如达到最大迭代次数或梯度的变化很小）。CSGD的优点是每次迭代的计算成本相对较低，因为只需计算一个坐标上的梯度。这在处理大规模数据集或高维参数空间时特别有用。然而，CSGD也存在一些挑战，例如可能收敛速度较慢，因为每次迭代只更新一个坐标。需要注意的是，CSGD是一种随机算法，每次迭代选择的坐标都是随机的。因此，它不能保证在每次迭代中都朝着全局最小值的方向前进。然而，通过合理的学习率调度和随机坐标选择策略，可以使CSGD在实践中表现良好。实例假设我们有一个简单的线性回归问题，目标是通过最小化均方误差来拟合一个线性模型。我们的模型参数是一个二维向量 (w0, w1)，其中 w0 是截距，w1 是斜率。我们的训练数据集包含多个样本点 (x, y)，其中 x 是输入特征，y 是对应的目标值。我们使用坐标随机梯度下降法来优化模型参数。下面是一个简化的示例代码，演示如何使用坐标随机梯度下降法来拟合线性回归模型：import numpy as np # 训练数据集 X = np.array([1, 2, 3, 4, 5]) # 输入特征 y = np.array([2, 3, 4, 5, 6]) # 目标值 # 初始化参数 w0 = 0.0 # 初始截距 w1 = 0.0 # 初始斜率 # 定义学习率和迭代次数 learning_rate = 0.01 num_iterations = 100 # 坐标随机梯度下降法 for _ in range(num_iterations): # 随机选择一个坐标 index = np.random.randint(len(X)) # 计算选择坐标的梯度 gradient_w0 = -2 * (y[index] - w0 - w1 * X[index]) gradient_w1 = -2 * X[index] * (y[index] - w0 - w1 * X[index]) # 更新选择坐标的参数 w0 -= learning_rate * gradient_w0 w1 -= learning_rate * gradient_w1 # 打印最终的模型参数 print("w0: ", w0) print("w1: ", w1) 在上述代码中，我们使用 NumPy 库来进行向量化计算。每次迭代时，随机选择一个训练样本，计算选择坐标的梯度，并更新对应的参数。重复这个过程一定次数后，得到最终的模型参数 w0 和 w1。需要注意的是，这只是一个简化的示例，实际应用中可能需要进行更多的数据预处理、参数调优等步骤。希望这个示例能帮助你理解坐标随机梯度下降法在线性回归问题中的应用。如有任何进一步的问题，请随时提问。 https://www.nituchao.com/golang-core/golang-go-modue.html 2021-07-04T14:24:00+08:00 现在哪个新编程语言不都是提供库版本工具呢？Java、Python、NodeJS，Rust都有一套自己的库管理方法和库注册中心，不管他们的叫法如何。Go最初推出来的时候并没有一个库管理反射，而是采用GOPATH的方式，所有的项目都必须放在GOPATH下，不止一次有从其他语言比如Java转过来的同学问我："为什么我在我的一个文件夹下建的项目没法编译呢？"，那是因为他的文件夹没有建在GOPATH下，而等他想在GOPATH下建项目的时候，package path 他又不知道该怎么写。所以，GO使用的GOPATH的方式确实对新手来说是一件非常令人困惑的事。而随着Go生态圈的快速壮大，另一个经典的库管理的问题也出现了。就是我们项目中的依赖库经常出现API Broken的情况，因为依赖的库相关接口改变了，导致我们的项目更新了依赖库后编译不过，我们不得不需要修改自己的代码以便适应依赖库的最新版本。更困难的是，如果多个依赖库分别依赖第三方依赖库的第三个版本，版本冲突就出现了。依赖库冲突几乎每个编程语言都有这样的问题，甚至操作系统也有DDL地狱问题，所以各种编程语言都尝试使用自己的方式解决依赖库版本的问题。前面说了，Go最初是没有官方版本的方式的，都是靠第三方的工具实现，比如godep、glide、dep等，从2012年各种工具分别出现，大海淘沙，浮浮沉沉，最后也就有几个常用的工具大家在使用，dep是2017出现的一个版本，让人眼前一亮，而且也得到了Go官方的支持，项目也放在Golang组织之下golang/dep。但是蜜月期没有多久，2018年Russ Cox经过深思熟虑以及一些早期的试验，决定Go库版本的方式需要从头再来，深度集成go的各种工具（go get、go list等），实现精巧的最小化版本选择算法，解决broken API共存等问题，所以ddep就被废弃了，这件事还导致dep的作者相当的失望和数次争辩。但是不管怎样，Go官方的库管理方式还是在2018年go 1.11中实验性的推出了，通过设置一个环境变量GO111MODULE=on就可以启用，并且期望go 1.12正式推出，而环境变量GO111MODULE=on就可以去掉了。可是没有想到的是，go module推出后问题多多，现在每一个Go的版本中都有对go module的修改，导致这个特性一直没有最终完成，这也是我吐槽它的地方：都快三年了，一个feature都开发那么久，而且未来的go 1.17、go 1.18还有一些改变，同学们，还学的动吗？go官方库管理方式叫做go module。先前，我们的库都是以package来组织的，package以一个文件或者多个文件实现单一的功能，一个项目包含一个package或者多个package。Go module就是一组统一打版发布的package的集合，在根文件下有go.mod文件定义module path和依赖库的版本，package以子文件夹的形式存在module中，对package path就是module path + "/" + package name的形式。一般我们项目都是单module的形式，项目主文件夹下包含go.mod，子文件夹定义package，或者主文件夹也是一个package。但是一个项目也可以包含多个module，只不过这种方式不常用而已。go.modgo module最重要的是go.mod文件的定义，它用来标记一个module和它的依赖库以及依赖库的版本。会放在module的主文件夹下，一般以go.mod命名。一个go.mod内容类似下面的格式：module github.com/panicthis/modfile go 1.16 require ( github.com/cenk/backoff v2.2.1+incompatible github.com/coreos/bbolt v1.3.3 github.com/edwingeng/doublejump v0.0.0-20200330080233-e4ea8bd1cbed github.com/stretchr/objx v0.3.0 // indirect github.com/stretchr/testify v1.7.0 go.etcd.io/bbolt v1.3.6 // indirect go.etcd.io/etcd/client/v2 v2.305.0-rc.1 go.etcd.io/etcd/client/v3 v3.5.0-rc.1 golang.org/x/net v0.0.0-20210610132358-84b48f89b13b // indirect golang.org/x/sys v0.0.0-20210611083646-a4fc73990273 // indirect ) exclude ( go.etcd.io/etcd/client/v2 v2.305.0-rc.0 go.etcd.io/etcd/client/v3 v3.5.0-rc.0 ) retract ( v1.0.0 // 废弃的版本，请使用v1.1.0 )虽然是一个简单的文件，但是里面的乾坤不少，让我们依次介绍他们。1. 语义化版本2.0.0Go module遵循语义化版本规范2.0.0。语义化版本规范2.0.0规定了版本号的格式，每个字段的意义以及版本号比较的规则等等。语义化版本 2.0.0Major.minor.patch-beta+metadata版本格式：主版本号.次版本号.修订号，版本号递增规则如下：主版本号：当你做了不兼容的API修改次版本号：当你做了向下兼容的功能新增修订号：当你做了向下兼容的问题修正先行版本号及版本编译信息可以加到"主版本号.次版本号.修订版本号"的后面，作为延伸。如果你想为你的项目发版，你可以设置tag为上面的格式，比如：v1.3.0、v2.0.0-rc.1等等。metadata中在Go版本比较时是不参与运算的，只是一个辅助信息。2. module pathgo.mod的第一行是module path，一般采用仓库 + module name的方式定义。这样我们获取一个module的时候，就可以的到它的仓库中去查询，或者让go proxy到仓库中去查询。module github.com/panicthis/modfile如果你的版本已经大于等于2.0.0，按照Go的规范，你应该加上major的后缀，module path改成下面的方式：module github.com/panicthis/modfile/v2module github.com/panicthis/modfile/v3而且引用代码的时候，也要加上v2、v3、vx后缀，以便和其他major版本进行区分。这是一个很奇怪大的约定，带来的好处是你一个项目中可以使用依赖库的不同major版本，它们可以共存。3. go directive第二行是go directive。格式是go 1.xx，它并不是指你当前使用的Go版本，而是指你的代码所需要的Go的最低版本。go 1.16因为Go的标准库也有变化，一些新的API也被增加进来，如果你的代码用到了这些新的API，你可能需要指明它依赖的go版本。这一行不是必须的，你可以不写。4. requirerequire段中列出了项目所需要的各个依赖库以及它们的版本，除了正规的v1.3.0这样的版本外，还有一些奇奇怪怪的版本和注释，那么它们又是什么意思呢？正式的版本号我们就不需要介绍了，大家都懂：github.com/cores/bbolt v1.3.34.1 伪版本号github.com/edwingeng/doublejump v0.0.0-2020033008023上面这个库中的版本号就是一个伪版本号v0.0.0-20200330080233-e4ea8bd1cbed，这是go module为它生成的一个类似符合语义化版本2.0.0版本，实际这个库并没有发布这个版本。正是因为这个依赖库没有发布版本，而go module需要指定这个库的一个确定的版本，所以才创建的这样一个伪版本号。go module的目的就是在go.mod中标记出这个项目所有的依赖以及它们确定的某个版本。这里的20200330080233是这次提交的时间，格式是yyyyMMddhhmmss，而e4ea8bd1cbed就是这个版本的commit id，通过这个字段，就可以确定这个库的特定版本。而前面的v0.0.0可能有多种生成方式，主要看你这个commit的base version:vX.0.0-yyyymmddhhmmss-abcdefabcdef: 如果没有base version，那么就是vX.0.0的形式。vX.Y.Z-pre.0.yyyymmddhhmmss-abcdefabcdef：如果base version是一个预发布的版本，比如vX.Y.Z-pre，那么它就用vX.Y.Z-pre.0的形式。vX.Y.(Z+1)-0.yyyymmddhhmmss-abcdefabcdef：如果base version是一个正式发布的版本，那么它就path号加1，如vX.Y.(Z+1)-05. indirect注释go.etcd.io/bbolt v1.3.6 // indirect golang.org/x/net v0.0.0-20210610132385-84b48f89b13b golang.org/x/sys v0.0.0-20210611083646-a4fc73990273有些库后面加了indirect后缀，这又是什么意思的。如果用一句话总结，间接的使用过了这个库，但是又没有被列到某个go.mod中，当然这句话也不算太准确，更精确的说法是下面的情况之一就会对这个库加indirect后缀：当前项目依赖A，但是A的go.mod遗漏了B，那么就会在当前项目的go.mod中补充B，加indirect注释当前项目依赖A，但是A没有go.mod，同样就会在当前项目的go.mod中补充B，加indirect注释++ 当前项目依赖A，A又依赖B，当对A降级的时候，降级的A不再依赖B，这个时候B就标记indirect注释。++6. incompatible有些库后面加了incompatible后缀，但是你如果看这些项目，它们只是发布了v2.2.1的tag，并没有+incompatible后缀。github.com/cenk/backoff v2.2.1+incompatible这些库采用了go.mod的管理，但是不幸的是，虽然这些库的major版本已经大于等于2了，但是他们的module path中依然没有添加v2、v3这样的后缀。所以go module把他们标记为incompatible的，虽然可以引用，但是实际上它们是不符合规范的。7. exclude如果你想在你的项目中跳过某个依赖大的某个版本，你就可以使用这个段。exclude ( go.etcd.io/etcd/client/v2 v2.305.0-rc.0 go.etcd.io/etcd/client/v3 v3.5.0-rc.0 )这样，Go在版本选择的时候，就会主动跳过这些版本，比如你使用go get -u ...或者go get github.com/xxx/xxx@latest等命令时，会执行version query的动作，这些版本不在考虑的范围之内。8. replacereplace也是常用的一个手段，用来解决一些错误的依赖库的引用或者调试依赖库。replace github.com/cores/bbolt => go.etcd.io/bbolt v1.3.3 replace github.com/panicthis/A v1.1.0 => github.com/panicthis/R v1.8.0 replace github.com/coreos/bbolt => ../R比如etcd v3.3.x的版本中错误的使用了github.com/coreos/bbolt作为bbolt的module path，其实这库在它自己的go.mod中声明的module path是go.etcd.io/bbolt，又比如etcd使用的grpc版本有问题，你也可以通过replace替换成所需要的grpc版本。甚至你觉得某个依赖库有问题，自己fork到本地做修改，想调试一下，你也可以替换成本地的文件夹。replace可以替换某个库的所有版本到另一个库的特定版本，也可以替换某个库的特定个版本到另一个库的特定版本。9. retractretract是go 1.16中新增加的内容，借用学术期刊撤稿的术语，宣布撤回库的某个版本。如果你误发布了某个版本，或者事后发现某个版本不成熟，那么你可以推一个新的版本，在新的版本中，声明前面的某个版本被撤回，提示大家都不要用了。撤回的版本tag依然还存在，go proxy也存在这个版本，所以你如果强制使用，还是可以使用的，否则这些版本就会被跳过。和exclude的区别是retract是这个库的owner定义的，而exclude是库的使用者在自己的go.mod中定义的。 https://www.nituchao.com/os-linux/87.html 2020-06-14T16:44:48+08:00 参考Docker的官方网站上的安装指南，注意我们安装的是docker-ce社区版，使用上倒是没什么区别。1，卸载老版本$ sudo yum remove docker \ docker-client \ docker-client-latest \ docker-common \ docker-latest \ docker-latest-logrotate \ docker-logrotate \ docker-engine2，安装依赖工具$ sudo yum install -y yum-utils \ device-mapper-persistent-data \ lvm23，导入Docker仓库$ sudo yum-config-manager \ --add-repo \ https://download.docker.com/linux/centos/docker-ce.repo4，安装Dockersudo yum install docker-ce docker-ce-cli containerd.io5，安装Composedocer-compose的官方github仓库上选择最新版本$ curl -L https://github.com/docker/compose/releases/download/1.25.4/docker-compose-`uname -s`-`uname -m` -o /usr/local/bin/docker-compose chmod +x /usr/local/bin/docker-compose6，开机启动Dockersystemctl start docker systemctl enable docker7，更换Docker源更换国内的Docker镜像源，可以提升image下载速度。a) 执行下面命令，生成service文件$ sudo systemctl enable docker Created symlink from /etc/systemd/system/multi-user.target.wants/docker.service to /usr/lib/systemd/system/docker.service.b）编辑daemon.json编辑/etc/docker/daemon.json文件，添加新的镜像源。{ "registry-mirrors": [ "https://dockerhub.azk8s.cn", "https://reg-mirror.qiniu.com" ] }c）重启Docker服务重启docker服务，使新的镜像源生效。sudo systemctl daemon-reload sudo systemctl restart docker8，测试dockersudo docker run hello-world参考资源https://www.jianshu.com/p/7d9ff93bc89eGet Docker Engine - Community for CentOS https://www.nituchao.com/ml-tf/ubuntu1804-install-tensorflow-1x-gpu.html 2020-03-04T10:56:00+08:00 Ubuntu 18.04安装TensorFlow 1.x GPU版本概述带GPU支持的TensorFlow需要依赖一些驱动和库，主要是NVIDIA显卡驱动和CUDA。另外，推荐使用Anaconda来管理Python环境，并且使用Python 3.6.x版本，以避免不必要的麻烦。本机环境操作系统：Ubuntu 18.04.3 LTSAnaconda：conda 5.2Python: Python 3.6.9 :: Anaconda, Inc.Compiler: gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0必要组件NVIDIA GPU drivers - CUDA 10.0要求410.x及以上。CUDA: TensorFlow支持CUDA 10.0（TensorFlow >= 1.13.0）CUPTI: CUDA性能分析接口组件cuDNN: The NVIDIA CUDA Deeep Neural library(cuDNN)，提供了一组经过优化的深度学习操作组件，包括前向卷积，反向卷积，池化，正则化，激活层等。TensorRT: version 5.0，可选，改善某些模型的推理的延迟和吞吐量。TensorFlow: 1.15note:TensorFlow所需要的软件依赖请查看:Software requirementsTensorFlow对Python,GCC,cuDNN,CUDA等版本要求，请查看Tested build configurationsUbuntu系统安装Ubuntu选择安装界面，在按e键进入编辑界面。找到"Boot Options ed boot=… initrd=/casper/initrd.lz quiet splash —"修改红色部分（删去“—”并添加“nomodeset”）如下“Boot Options ed boot=… initrd=/casper/initrd.lz nomodeset quiet splash”接着按 '‘F10’'启动系统》安装NVIDIA显卡驱动1，使用命令ubuntu-drivers devices 查看当前提供的驱动列表：== /sys/devices/pci0000:00/0000:00:01.0/0000:01:00.0 == modalias : pci:v000010DEd00001C03sv00001043sd000085BFbc03sc00i00 vendor : NVIDIA Corporation model : GP106 [GeForce GTX 1060 6GB] driver : nvidia-driver-390 - distro non-free driver : nvidia-driver-430 - distro non-free driver : nvidia-driver-435 - distro non-free recommended driver : xserver-xorg-video-nouveau - distro free builtin == /sys/devices/pci0000:00/0000:00:1c.6/0000:04:00.0 == modalias : pci:v000014E4d000043B1sv00001A3Bsd00002123bc02sc80i00 vendor : Broadcom Limited model : BCM4352 802.11ac Wireless Network Adapter driver : bcmwl-kernel-source - distro non-free2，推荐安装最新版本的显卡驱动使用命令sudo apt install nvidia-driver-435安装显卡驱动，安装成功后重启系统。3，查看当前显卡信息使用命令nvidia-smi查看当前先看的驱动版本，内心及处理器信息。Tue Dec 31 11:18:01 2019 +-----------------------------------------------------------------------------+ | NVIDIA-SMI 435.21 Driver Version: 435.21 CUDA Version: 10.1 | |-------------------------------|----------------------|----------------------+ | GPU Name Persistence-M| Bus-Id Disp.A | Volatile Uncorr. ECC | | Fan Temp Perf Pwr:Usage/Cap| Memory-Usage | GPU-Util Compute M. | |===============================+======================+======================| | 0 GeForce GTX 106... Off | 00000000:01:00.0 On | N/A | | 29% 23C P8 8W / 120W | 603MiB / 6075MiB | 0% Default | +-------------------------------|----------------------|----------------------+ +-----------------------------------------------------------------------------+ | Processes: GPU Memory | | GPU PID Type Process name Usage | |=============================================================================| | 0 1228 G /usr/lib/xorg/Xorg 40MiB | | 0 1274 G /usr/bin/gnome-shell 49MiB | | 0 2081 G /usr/lib/xorg/Xorg 300MiB | | 0 2212 G /usr/bin/gnome-shell 210MiB | +-----------------------------------------------------------------------------+安装CUDA在NVIDIA官网的CUDA下载界面，按照操作系统类型选择合适的安装包，我这里选择Ubuntu 18.04 deb[local]。然后使用下面的命令，来安装：wget https://developer.download.nvidia.com/compute/cuda/repos/ubuntu1804/x86_64/cuda-ubuntu1804.pin sudo mv cuda-ubuntu1804.pin /etc/apt/preferences.d/cuda-repository-pin-600 wget http://developer.download.nvidia.com/compute/cuda/10.1/Prod/local_installers/cuda-repo-ubuntu1804-10-1-local-10.1.243-418.87.00_1.0-1_amd64.deb sudo dpkg -i cuda-repo-ubuntu1804-10-1-local-10.1.243-418.87.00_1.0-1_amd64.deb sudo apt-key add /var/cuda-repo-10-1-local-10.1.243-418.87.00/7fa2af80.pub sudo apt-get update sudo apt-get -y install cuda安装CUPTICUPTI组件包含在CUDA中，无需单独安装。CUPTI采用懒加载的方式进行初始化，当你第一次调用CUPTI函数时，会触发该初始化操作。CUPTI提供了包括Activity API，Callback API，Event API，Metric API和Profiler API。安装cuDNN现在cuDNN安装包在cuDNN的官网，按照要求勾选一些选项后，进入下载界面，按照操作系统类型选择合适的安装包，我这里选择"Download cuDNN v7.6.5 (November 5th, 2019), for CUDA 10.1"下的运行时库和文档库：cuDNN Runtime Library for Ubuntu18.04 (Deb)cuDNN Developer Library for Ubuntu18.04 (Deb)cuDNN Code Samples and User Guide for Ubuntu18.04 (Deb)安装cuDNN载完成后后，使用下面的命令来依次安装：sudo dpkg -i ./libcudnn7_7.6.5.32-1+cuda10.1_amd64.deb sudo dpkg -i ./libcudnn7-dev_7.6.5.32-1+cuda10.1_amd64.deb sudo dpkg -i ./libcudnn7-doc_7.6.5.32-1+cuda10.1_amd64.debnote: cuDNN的runtime, dev, doc三个包要按顺序依次安装。验证cuDNN安装完cuDNN的三个组件后，使用如下命令nvidia-smi查看本机NVIDIA驱动程序，如果显然如下错误，则需要重启系统。Failed to initialize NVML: Driver/library version mismatch依次执行如下命令，如果结果输出Test passed!，则表示cuDNN安装成功。cp -r /usr/src/cudnn_samples_v7/ ~/Downloads/cudnn_samples_v7/ cd ~/Downloads/cudnn_samples_v7/mnistCUDNN make clean && make ./mnistCUDNN安装TensorFlow本机在Anaconda环境下安装TensorFlow 2.0.0，Python版本是3.6.9，$ pip install tensorflow-gpu==2.0.0note：1，建议Python版本使用3.6.x，而不是3.7.x。测试TensorFlow GPU使用如下代码，如果安装正确，则会输出True。tf.test.is_gpu_availablelibcudart.so.10.0解决如果测试TensorFlow过程中，会出现下面的错误：2020-01-09 13:44:35.195765: W tensorflow/stream_executor/platform/default/dso_loader.cc:55] Could not load dynamic library 'libcudart.so.10.0'; dlerror: libcudart.so.10.0: cannot open shared object file: No such file or directory 2020-01-09 13:44:35.195853: W tensorflow/stream_executor/platform/default/dso_loader.cc:55] Could not load dynamic library 'libcublas.so.10.0'; dlerror: libcublas.so.10.0: cannot open shared object file: No such file or directory 2020-01-09 13:44:35.195919: W tensorflow/stream_executor/platform/default/dso_loader.cc:55] Could not load dynamic library 'libcufft.so.10.0'; dlerror: libcufft.so.10.0: cannot open shared object file: No such file or directory原因：TensorFlow2.0现在支持CUDA10.0，还不支持CUDA10.1，而我的Ubuntu上安装的是CUDA10.1（也正确安装了cuDNN）。现在只需要安装一个CUDA10.1就行。可以仿照安装pytorch时就自动安装cudatoolkit 10.1.243，无需再下载CUDA10.0的包，在Ubuntu上重新安装CUDA10.0，而是直接用conda安装cudatoolkit。conda install cudatoolkit=10.0Other Problem安装TensorFlow问题 解决Cannot uninstall 'wrapt'. It is a distutils installed project https://www.nituchao.com/bigdata-spark/spark-create-multi-data-type-dataframe.html 2019-12-25T14:28:00+08:00 假如我们要通过RDD[Row]创建一个包含多个列的DataFrame，重点是列的数据类型可能会包含多个，这时候需要有一点技巧。uiduser_nameageincome1111nituchao21123.0这个DataFrame里包含多个数据类型：uid: Longuser_name: Stringage: Intincome: Double我们可以使用下面的方式来构建：import org.apache.spark.sql.Row import org.apache.spark.sql.types.{DoubleType, IntegerType, LongType, StringType, StructField, StructType} val uidSeq = Seq(1111L) val nameSeq = Seq("nituchao") val ageSeq = Seq(21) val incomeSeq = Seq(123.0) val rowRDD = spark.sparkContext.parallelize(Seq(Row.fromSeq(uidSeq ++ userNameSeq ++ ageSeq ++ incomeSeq))) val schema = StructType(Seq(StructField("uid", LongType, nullable = true), StructField("name", StringType, nullable = true), StructField("age", IntegerType, nullable = true), StructField("sex", DoubleType, nullable = true))) val df = spark.sqlContext.createDataFrame(rowRDD, schema) df.printSchema() df.show()输出：root |-- uid: long (nullable = true) |-- name: string (nullable = true) |-- age: integer (nullable = true) |-- sex: double (nullable = true) +----+---------+---+-----+ | uid|name |age| sex| +----+---------+---+-----+ |1111| nituchao| 21|123.0| +----+---------+---+-----+上面的技巧在于，使用Row.fromSeq()时，不同类型的数据，要用Seq()分别包起来然后++拼接后传进去。因为Seq中的元素必须是同类型的，如直接构造成一个Seq则会自动进行类型转换，多种类型数据不能混用。问题不大，却造成很大困扰。 https://www.nituchao.com/nituchao/photos.html 2019-12-05T14:47:00+08:00 20191216-故宫大雪端门 ISO 250, 焦距 52mm, 光圈 f/4, 快门 1/200s 午门 ISO 400, 焦距 48mm, 光圈 f/4, 快门 1/320s 角楼 ISO 400, 焦距 35mm, 光圈 f/4, 快门 1/400s 长廊角楼 ISO 320, 焦距 48mm, 光圈 f/4, 快门 1/400s 大红墙 ISO 1000, 焦距 66mm, 光圈 f/4, 快门 1/200s 中山公园 ISO 400, 焦距 86mm, 光圈 f/4, 快门 1/200s 阙右门远景 ISO 200, 焦距 58mm, 光圈 f/4, 快门 1/200 东安门侧影 ISO 400, 焦距 58mm, 光圈 f/4, 快门 1/200s 20191204-故宫行广院 ISO 100, 焦距 24mm, 光圈 f/4, 快门 1/2000s 飞鸽 ISO 100, 焦距 70mm, 光圈 f/4, 快门 1/1000s 月影 ISO 100, 焦距 120mm, 光圈 f/4, 快门 1/640s 龙生九子 ISO 100, 焦距 120mm, 光圈 f/4, 快门 1/640s 一树柿子 ISO 100, 焦距 120mm, 光圈 f/4, 快门 1/640s 一只柿子 ISO 100, 焦距 120mm, 光圈 f/4, 快门 1/640s 山楂 ISO 100, 焦距 120mm, 光圈 f/6.3, 快门 1/320s 20191130-景山行神武门城墙 ISO 100, 焦距 48mm, 光圈 f/22, 快门 1/13s 故宫烟火气 ISO 400, 焦距 70mm, 光圈 f/22, 快门 1/80s 故宫角楼 ISO 100, 焦距 82mm, 光圈 f/22, 快门 1/15s 故宫小雪人 ISO 100, 焦距 50mm, 光圈 f/22, 快门 1/13s 20191129-故宫初雪四季民福 ISO 1600, 焦距 24mm, 光圈 f/4, 快门 1/4s 故宫路灯 ISO 12800, 焦距 24mm, 光圈 f/7.1, 快门 1/320s 故宫剪影 ISO 1600, 焦距 24mm, 光圈 f/4, 快门 1/13s 阙左门城楼 ISO 51200, 焦距 24mm, 光圈 f/4, 快门 1/200s 故宫午门前 ISO 51200, 焦距 24mm, 光圈 f/4, 快门 1/160s https://www.nituchao.com/algorithm-ml/ml-stats-em.html 2019-10-29T20:56:00+08:00 EM算法是一种迭代算法，1977年由Dempster等人总结提出，用于含有隐变量(hidden variable)的概率模型参数的极大似然估计，或极大后验概率估计。EM算法的每次迭代由两步组成：E步：求期望(expectation)；M步：求极大(maximization)；所以这一算法称为期望极大算法(expectation maximization algorithm)，简称EM算法。EM算法概率模型有时即含有观测变量(observable variable)，又含有隐变量或潜在变量(latent variable)。如果概率模型的变量都是观测变量，那么给定数据，可以直接用极大似然估计法，或贝叶斯估计法估计模型参数。但是，当模型含有隐变量时，就不能简单地使用这些估计方法。EM算法就是含有隐变量的概率模型参数的极大似然估计法，或极大后验概率估计法。首先介绍一个使用EM算法的例子 ---- 三硬币模型假设有3枚硬币，分别记作A，B，C。这些硬币正面出现的概率分别是$\pi, p$和$q$。进行如下抛硬币实验：先抛硬币A，根据其结果选出硬币B或硬币C，正面选硬币B，反面选硬币C；然后抛选出的硬币，抛硬币的结果，出现正面记作1，出现反面记作0；独立地重复n次实验(这里，n=10)，观测结果如下：$$1,1,0,1,0,0,1,0,1,1$$假设只能观测到抛硬币的结果，不能观测到抛硬币的过程。问如何估计三硬币正面出现的概率，即三硬币模型的参数：解 三硬币偶像可以写作：$$P(y|\theta)=\sum_zP(y,z|\theta)=\sum_zP(z|\theta)P(y|z,\theta) \\ = \pi p^y(1-p)^(1-y) + (1-\pi)q^y(1-q)^)(1-y)$$ https://www.nituchao.com/algorithm-ml/boosting_adaboost.html 2019-10-28T20:51:00+08:00 提升方法提升(boosting)方法是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。提升方法的基本思路提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是"三个臭皮匠顶个诸葛亮"的道理。历史上，Kearns和Valiant首先提出了"强可学习(strongly learnable)"和"弱可学习(weakly learnable)"的概念。指出：在概率近似正确(probably approximately correct, PAC)学习的框架中，一个概念（一个类），如果存在一个多项式学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测好，那么就称这个概念是弱可学习的。Schapire后来证明强可学习与弱可学习是等价的。也就是说，在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。由于，发现弱学习算法通常要比发现强学习算法容易得多。通过将已经发现的"弱学习算法"提升(boost)为"强学习算法"，就是我们所说的提升方法。对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据集的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。这样，对提升方法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。关于第1个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器"分而治之"。至于第2个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减少分类误差率大的弱分类器的权值，使其在表决中起较小的作用。AdaBoost算法假设给定一个二分类的训练数据集：$$T=\{(x_1, y_1),(x_2, y_2),...,(x_N,y_N)\}$$其中，每个样本点由实例与标记组成。实例$x_i \in X \subset R^n$，标记$y_i \in Y = \{-1,1\}$ ,$X$是实例空间，$Y$是标记集合。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基分类器，并将这些弱分类器线性组合成为一个强分类器。输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ,其中$x_i \in X \subset R^n, y_i \in Y={-1,+1}$;弱学习算法。输出：最终分类器$G(x)$(1) 初始化训练数据的权值分布$$D_1 = \{w_{11},...,w_{1i},...w_{1N}\}, w_{1i}=\frac{1}{N}, i=1,2,...,N$$(2) 对m=1,2,...,M​ (a) 使用具有权值分布$D_m$的训练数据集学习，得到基本分类器：$$G_m(x): X -> {-1,+1}$$(b) 计算$G_m(x)$在训练数据集上的分类误差率：$$e_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^{N}w_{mi}I(G_m(x_i) \neq y_i)$$(c) 计算$G_m(x)$的系数$$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$$这里的对数是自然对数。(d) 更新训练数据集的权值分布$$D_{m+1}=(w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})$$$$w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)), i=1,2,...,N$$这里，$Z_m$是规范化因子：$$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$$它使$D_m+1$成为一个概率分布。(3) 构建基本分类器的线性组合：$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$得到最终分类器：$$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$$对AdaBoost算法作如下说明：步骤(1) 假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第1步能够在原始数据上学习基本分类器$G_1(x)$。步骤(2) AdaBoost反复学习基本分类器，在每一轮$m=1,2,...,M$顺次地执行下列操作：(a) 使用当前分布$D_m$加权的训练数据集，学习基本分类器$G_m(x)$。(b) 计算基本分类器$G_m(x)$在加权训练数据集上的分类误差率：$$e_m=P(G_m(x_i) \neq y_i)=\sum_{G_m(x_i) \neq y_i}w_{mi}$$这里，$w_mi$表示第m轮中第i个实例的权值，$\sum_{i=1}^Nw_{mi}=1$。这表明，$G_m(x)$在加权的训练数据集上的分类误差率是被$G_m(x)$误分类样本的权值之和，由此可以看出数据权值分布$D_m$与基本分类器$G_m(x)$的分类误差率的关系。(c) 计算基本分类器$G_m(x)$的系数$\alpha_m·\alpha_m$表示$G_m(x)$在最终分类器中的重要性。由式$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$可知，当$e_m \leq \frac{1}{2}$时，$\alpha_m \geq 0$，并且$\alpha_m$随着$e_m$的减小而增大 ，所以分类误差率越小的基本分类器在最终的分类器中的作用越大。(d) 更新训练数据的权值分布作为下一轮作准备。$$w_{m_1,i} = \begin{cases} \frac{w_{mi}}{Z_m}e^{-\alpha_m}& G_m(x_i)=y_i\\ \frac{w_{mi}}{Z_m}e^{\alpha_m}& G_m(x_i) \neq y_i \end{cases}$$由此可知，被基本分类器$G_m(x)$误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。两相比较，误分类样本的权值被放大$e^{2\alpha_m} = \frac{e_m}{1-e_m}$倍。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点。步骤(3) 线性组合$f(x)$实现M个基本分类器的加权表决。系数$\alpha_m$表示了基本分类器$G_m(x)$的重要性，这里，所有$\alpha_m$之和并不为1。$f(x)$的符号决定实例x的类，$f(x)$的绝对值表示分类的确信度。利用基本分类器b的线性组合构建最终分类器是AdaBoost的另一特点。AdaBoost实例给定如下表所示训练数据。假设弱分类器由$x<v$或$x>v$产生，其阈值v使该分类器在训练数据集上分类误差率最低。试用AdaBoost算法学习一个强分类器。$$AdaBoost实例 训练数据表$$序号12345678910x0123456789y111-1-1-1111-1解 初始化数据权值分布：$$D_1 = (w_{11},w_{12},...,w_{110})$$$$w_{1i}=0.1, i=1,2,...,10$$对$m=1$(a) 在权值分布为$D_1$的训练数据上，阈值v取2.5时分类误差率最低，故基本分类器为:$$G_1(x) = \begin{cases} 1,& x<2.5\\ -1,& x>2.5 \end{cases}$$(b) $G_1(x)$在训练数据集上的误差率$e_1=P(G_1(x_i) \neq y_i) = 0.3$(c) 计算$G_1(x)$的系数：$\alpha_1=\frac{1}{2}log\frac{1-e_1}{e_1}=0.4236$(d) 更新训练数据的权值分布：$$D_2=(w_{21},...,w_{2i},...,w_{210})$$$$w_{2i}=\frac{w_{1i}}{Z_1}exp(-\alpha_1y_iG_1(x_i)), i=1,2,...10$$$$D_2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)$$$$f_1(x)=0.4236G_1(x)$$分类器$sign[f_1(x)]$在训练数据集上有3个误分类点。对$m=2$，(a) 在权值分布为$D_2$的训练数据集上，阈值v是8.5时分类误差率最低，基本分类器为:$$G_1(x) = \begin{cases} 1,& x<8.5\\ -1,& x>8.5 \end{cases}$$(b) $G_2(x)$在训练数据集上的误差率$e_2=0.2143$。(c) 计算$\alpha_2=0.6496$。(d) 更新训练数据权值分布:$$D_3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)$$$$f_2(x)=0.4236G_1(x) + 0.6496G_2(x)$$分类器$sign[f_2(x)]$在训练数据集上有3个误分类点。对m=3，(a) 在权值分布为$D_3$的训练数据上，阈值v是5.5时分类误差率最低，基本分类器为：$$G_1(x) = \begin{cases} 1,& x>5.5\\ -1,& x<5.5 \end{cases}$$(b) $G_3(x)$在训练样本集上的误差率$e_3=0.1820$。(c) 计算$\alpha_3=0.7514$。(d) 更新训练数据的权值分布:$$D_4=(0.125,0.125,0.125,0.102,0.102,0.065,0.065,0.065,0.125)$$于是得到：$$f_3(x)=0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)$$AdaBoost算法的训练误差分析AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。关于这个问题有下面的定理：AdaBoost的训练误差界 AdaBoost算法最终分类器的训练误差界为：$$\frac{1}{N}\sum_{i=1}^NI(G(x_i) \neq y_i) \leq \frac{1}{N}\sum_iexp(-y_if(x_i))=\prod_mZ_m$$$$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$$$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$$$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$$证明 当$G(x_i) \neq y_i$时，$y_if(x_i) < 0$，因而$exp(-y_if(x_i)) \geq 1$。由此直接推导出前半部分。后半部分的推导要用到$Z_m$的定义式及变形：$$w_{mi}exp(-\alpha_my_iG_m(x_i))=Z_mw_{m+1,i}$$现推导如下：$$\frac{1}{N}\sum_iexp(-y_if(x_i)) \\ = \frac{1}{N}\sum_iexp(-\sum_{m=1}^M)\alpha_my_iG_m(x_i) \\ = \sum_iw_{1i}\prod_{m=1}^Mexp(-\alpha_my_iG_m(x_i)) \\ = Z_1\sum_iw_{2i}\prod_{m=2}^Mexp(-\alpha_my_iG_m(x_i)) \\ = Z_1Z_2\sum_iw_{3i}\prod_{m=3}^Mexp(-\alpha_my_iG_m(x_i)) \\ = ... \\ = Z_1Z_2...Z_{M-1}\sum_iw_{Mi}exp(-\alpha_My_iG_M(x_i)) \\ = \prod_{m=1}^MZ_m$$这一定理说明，可以在每一轮选取适当的$G_m$使得$Z_m$最小，从而使训练误差下降最快。对二分类问题，有如下结果：二分类问题 AdaBoost的训练误差界$$\prod_{m=1}^MZ_m = \prod_{m=1}^M[2\sqrt{e_m(1-e_m)}] = \prod_{m=1}^M\sqrt{1-4\gamma_m^2} \leq exp(-2\sum_{m=1}^M\gamma_m^2)$$这里，$\gamma_m = \frac{1}{2} - e_m$。证明 由Z_m的定义式得：$$Z_m = \sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i)) \\ = \sum_{yi=G_m(x_i)}w_{mi}e^{-\alpha_m} + \sum_{y_i \neq G_m(x_i)}w_{mi}e^{\alpha_m} \\ = (1-e_m)e^{-\alpha_m} + e_me^{\alpha_m} \\ = 2\sqrt{e_m(1-e_m)} = \sqrt{1-4\gamma_m^2}$$至于不等式：$$\prod_{m=1}^M\sqrt{1-4\gamma_m^2} \leq exp(-2\sum_{m=1}^M\gamma_m^2)$$则可先由$e^x$和$\sqrt{1-x}$在点x=0的泰勒展开式推出不等式$\sqrt{1-4\gamma_m^2} \leq exp(-2\gamma_m^2)$，进而得到。推论 如果存在$\gamma > 0$，对所有m有$\gamma_m \geq \gamma$，则：$$\frac{1}{N}\sum_{i=1}{N}I(G(x_i) \neq y_i) \leq exp(-2M\gamma^2)$$这表明在此条件下AdaBoost的训练误差是以指数速率下降的。这一性质当然是很有吸引力的。注意，AdaBoost算法不需要知道下界$\gamma$。这正是Freund与Schapire设计AdaBoost时所考虑的。与一些早期的提升方法不同，AdaBoost具有适应性，即它能适应弱分类器各自的训练误差率。这也是它的名称(适应的提升)的由来，Ada是Adaptive的简写。AdaBoost算法的解释AdaBoost算法还有另一个解释，即可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二分类学习方法。前向分布算法考虑加法模型(additive model)：$$f(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)$$其中，$b(x;\gamma_m)$为基函数，$\gamma_m$为基函数的参数，$\beta_m$为基函数的系数。在给定训练数据及损失函数$L(x,f(x))$的条件下，学习加法模型$f(x)$成为经验风险最小化即损失函数极小化问题：$$min_{\beta_m,\gamma_m}\sum_{i=1}^NL(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m))$$通常这是一个复杂的优化问题。前向分布算法(forward stagewise algorithm)求解这一优化问题的想法是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：$$min_{\beta,\gamma}\sum_{i=1}^NL(y_i,\beta b(x_i;\gamma))$$给定训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}, x_i \in X \subset R^n, y_i \in Y = \{-1,+1\}$。损失函数L(y, f(x))和基函数的集合$\{b(x;\gamma\}$，学习加法模型f(x)的前向分布算法如下：前向分布算法输入：训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$；损失函数$L(y,f(x))$;基函数集$\{b(x;\gamma)\}$;输出：加法模型$f(x)$。(1) 初始化$f_0(x)=0$(2) 对$m=1,2,...,M$(a) 极小化损失函数$$(\beta_m,\gamma_m)=argmin_{\beta,\gamma}\sum_{i=1}^NL(y_i,f_{m-1}(x_i) + \beta b(x_i;\gamma))$$得到参数$\beta_m,\gamma_m$(b) 更新$$f_m(x)=f_{m-1}(x) + \beta_mb(x;\gamma_m)$$(3) 得到加法模型$$f(x)=f_M(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)$$这样，前向分布算法将同时求解从m=1到M所有参数$\beta_m,\gamma_m$的优化问题简化为逐次求解各个$\beta_m,\gamma_m$的优化问题。前向分布算法与AdaBoost由前向分布算法可以推导出AdaBoost，用定理叙述这一关系。定理 AdaBoost算法是前向分布加法算法的特例，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器：$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$由基本分类器$G_m(x)$及其系数$\alpha_m$组成，$m=1,2,...,M$。前向分布算法逐一学习基函数，这一过程与AdaBoost算法逐一学习基本分类器的过程一致。下面证明前向分布算法的损失函数是指数损失函数(exponential loss function)$$L(y, f(x))=exp[-yf(x)]$$时，其学习的具体操作等价于AdaBoost算法学习的具体操作。假设经过m-1轮迭代前向分布算法已经得到$f_{m-1}(x)$：$$f_{m-1}(x) = f_{m-2}(x)+\alpha_{m-1}G_{m-1}(x) \\ = \alpha_1G_1(x) + ... + \alpha_{m-1}G_{m-1}(x)$$在第m轮迭代得到$\alpha_m, G_m(x)$和$f_m(x)$。$$f_m(x)=f_{m-1}(x) + \alpha_mG_m(x)$$目标是使前向分布算法得到的$\alpha_m$和$G_m(x)$使$f_m(x)$在训练数据集T上的指数损失最小，即：$$(\alpha_m,G_m(x))=argmin_{\alpha,G}\sum_{i=1}^Nexp[-y_i(f_{m-1}(x_i) + \alpha G(x_i))]$$也即：$$目标式：(\alpha_m,G_m(x))=argmin_{\alpha,G}\sum_{i=1}^Nw_{mi}exp[-y_i\alpha G(x_i)]$$其中，$w_{mi}=exp[-y_if_{m-1}(x_i)]$。因为$w_{mi}$既不依赖$\alpha$也不依赖$G$，所以与最小化无关。但$w_{mi}$依赖于$f_{m-1}(x)$，随着每一轮迭代而发生改变。现证使上式达到最小的$\alpha_m^*$和$G_m^*(x)$就是AdaBoost算法所得到的的$\alpha_m$和$G_m(x)$。求解可分为两步：首先，求$G_m^*(x)$。对任意$\alpha > 0$，使目标式最小的G(x)由下式得到：$$G_m^*(x)=argmin_G\sum_{i=1}^Nw_{mi}I(y_i \neq G(x_i))$$其中，$w_{mi}=exp[-y_if_{m-1}(x_i)]$。此分类器$G_m^*(x)$即为AdaBoost算法的基本分类器$G_m(x)$，因为它是使第m轮加权训练数据分类误差率最小的基本分类器。之后，求$\alpha_m^*$。目标式中：$$\sum_{i=1}^Nw_{mi}exp[-y_i\alpha G(x_i)] \\ = \sum_{y_i=G_m(x_i)}w_{mi}e^{-\alpha} + \sum_{y_i \neq G_m(x_i)}w_{mi}e^{\alpha} \\ = (e^{\alpha} - e^{-\alpha})\sum_{i=1}^Nw_{mi}I(y_i \neq G(x_i)) + e^{-\alpha}\sum_{i=1}^Nw_{mi}$$将以求得的$G_m^*(x)$带入上式，对$\alpha$求导并使导数为0，即得到使目标式最小的$\alpha$。$$\alpha_m^*=\frac{1}{2}log\frac{1-e_m}{e_m}$$其中，$e_m$是分类误差率：$$e_m=\frac{\sum_{i=1}^Nw_{mi}I(y_i \neq G_m(x_i))}{\sum_{i=1}^Nw_{mi}}=\sum_{i=1}^Nw_{miI(y_i \neq G_m(x_i))}$$这里的$\alpha_m^*$与AdaBoost算法第2(c)步的$\alpha_m$完全一致。最后看来每一轮样本权值的更新。由$$f_m(x)=f_{m-1}(x) + \alpha_mG_m(x)$$以及$w_{mi}=exp[-y_if_{m-1}(x_i)]$，可得$$w_{m+1,i}=w_{m,i}exp[-y_i\alpha_mG_m(x)]$$这与AdaBoost算法第2(d)步的样本权值的更新，只相差规范化因子，因而等价。 https://www.nituchao.com/algorithm-ml/ml-gbdt.html 2019-09-30T09:41:00+08:00 提升树是以分类树或回归树为基础分类器的提升方法，提升树被认为是统计学习中性能最好的方法之一。当损失函数是平方损失和指数损失函数时是普通提升树，当利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树时称为梯度提升决策树(GBDT)。提升树模型提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。如果我们取一个基本分类器if (x > 30) 1 else 0，这可以看做是由一个根节点直接连接两个叶结点的简单决策树，即所谓的决策树桩(decision stump)。提升树模型可以表示为决策树的加法模型。$$ f_M(x) = \sum_{m=0}^{M}{\alpha}_{m}G_{m}(x) $$其中，$T(x;{\theta}_m)$表示决策树；${\theta}_m$为决策树的参数；M为树的个数。提升树算法提升树算法采用前向分布算法。首先确定初始提升树$f_0(x) = 0$，第m步的模型是$$ f_m(x) = f_{m-1}(x) + T(x;{\theta}_m) $$其中，f_{m-1}(x)为当前模型，通过经验风险极小化确定下一棵决策树的参数 $ {\theta}_m$，$$ {\theta}_m = argmin_{{\theta}_m}\sum_{i=1}^{N}L(y_i, f_{m-1}(x_i) + T(x_i;{\theta}_m)) $由于树的线性组合可以很好的拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。当提升树使用平方误差损失函数时可解决回归问题，当使用指数损失函数时可解决分类问题。回归问题的提升树算法输入：训练数据集$ T={(x_1, y_1), (x_2, y_2), ... (x_N, y_N)}, x_i \in X \subset R^n, y_i \in y \subset R; $输出：提升树$ f_M(x) $(1) 初始化 $ f_0(x) = 0$(2) 对m=1,2,...,M(a) 按式$r=y-f_{m-1}(x)$计算残差$$ r_{mi} = y_i - f_{m-1}(x_i), i = 1,2,...,N $$(b) 拟合残差$ r_{mi} $学习一个回归树，得到$T(x;{\theta}_m)$(c) 更新$ f_m(x) = f_{m-1}(x) + T(x;{\theta}_m) $(3) 得到回归问题提升树$$ f_M(x) = \sum_{m=1}^{M}T(x;{\theta}_m) $$提升树实例已知如表8.2所示的训练数据，x的取值范围为区间[0.5, 10.5]，y的取值范围为区间[5.0, 10.0]，学习这个回归问题的提升树模型，考虑只用树桩作为基函数。$$ 提升树实例，训练数据表 $$$x_i$12345678910$y_i$5.565.705.916.406.807.058.908.709.009.05解 按照提升树算法，第1步求$f_i(x)$ 即回归树$T_i(x)$。首先通过以下优化问题：$$ min_s [min_{c_1}\sum_{x_i \in R_i } (y_i - c_i)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2] $$求解训练数据的切分点s:$$ R_1 = {x|x<= s}, R_2 = {x|x>s} $$容易求得在$ R_1, R_2 $内部使平方损失误差达到最小值的$c_1,c_2$为$$ c_1 = \frac{1}{N} \sum_{x_i \in R_i}y_i, c_2 = \frac{1}{N} \sum_{x_i \in R_2}y_i $$这里$N_1, N_2$是$R_1, R_2$的样本点数。求训练数据的切分点。根据所给数据，考虑如下切分点：$$ 1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5 $$对各切分点，不难求出相应的$R_1, R_2, c_1, c_2$及$$ m(s) = min_{c_1} \sum_{x_i \in R_1}(y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2 $$例如，当s=1.5时，$$R_1 = {1}, R_2 = {2, 3, ...10}, c_1 = 5.56, c_2 = 7.50$$$$m(s) = min_{c_1} \sum_{x_i \in R_1}(y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2}(y_i - c_2)^2 = 0 + 15.72 = 15.72 $$现将s及m(s)的计算结果列表如下：$$提升树算法，计算数据表$$s1.52.53.54.55.56.57.58.59.5$m(s)$15.7212.078.365.783.911.938.0111.7315.74由上表可知，当s=6.5时m(s)达到最小值，此时$R_1={1,2,...,6}, R_2={7,8,9,10}, c_1=6.24, c_2 = 8.91,$所以回归树$T_1(x)$为：$$T_1(x) = \begin{cases} 6.24& \text{x<6.5}\\ 8.91& \text{x >= 6.5} \end{cases}$$$$f_i(x)=T_i(x)$$用$f_i(x)$拟合训练数据的残差见下表，表中$r_2i=y_i - f_i(x_i), i=1,2,...,10.$$$提升树算法，残差表$$$x_i$12345678910$r_{2i}$-0.68-0.54-0.330.160.560.81-0.01-0.210.090.14用$f_1(x)$拟合训练数据的平方损失差：$$L(y, f_i(x)) = \sum_{i=1}^{10}(y_i - f_1(x_i))^2 = 1.93 $$第2步求$T_2(x)$。方法与求$T_1(x)$一样，只是拟合的数据是上表的残差。可以得到：$$T_1(x) = \begin{cases} -0.52,& \text{x<3.5}\\ 0.22& \text{x <= 3.5} \end{cases}$$$$f_2(x) = f_1(x) + T_2(x) = \begin{cases} 0.57,& \text{x<3.5}\\ 6.46,& \text{3.5 <= x <= 6.5}\\ 9.13,& \text{x >= 6.5} \end{cases}$$用$f_2(x)$拟合训练数据的平方损失误差是：$$L(y,f_2(x)) = \sum_{i=1}^{10}(y_i - f_2(x_i))^2 = 0.79$$继续求得：$$T_3(x) = \begin{cases} 0.15,& \text{x<6.5}\\ -0.22& \text{x >= 6.5} \end{cases} L(y,f_3(x))=0.47,$$$$T_4(x) = \begin{cases} -0.16,& \text{x<4.5}\\ 0.11& \text{x >= 4.5} \end{cases} L(y,f_4(x))=0.30,$$$$T_5(x) = \begin{cases} 0.07,& \text{x<6.5}\\ -0.11& \text{x >= 6.5} \end{cases} L(y,f_5(x))=0.23,$$$$T_6(x) = \begin{cases} -0.15,& \text{x<2.5}\\ 0.04& \text{x >= 2.5} \end{cases} $$$$f_6(x) = f_5(x) + T_6(x) = T_1(x) + ... + T_5(x) + T_6(x) \\ = \begin{cases} 5.63,& \text{x<2.5}\\ 5.82,& \text{2.5 >= x < 3.5} \\ 6.56,& \text{3.5 >= x < 4.5} \\ 6.83,& \text{4.5 >= x < 6.5} \\ 8.95,& \text{x >= 6.5} \end{cases} $$用$f_6(x)$拟合训练数据的平方损失误差是：$$L(y,f_6(x)) = \sum_{i=1}^{10}(y_i - f_6(x_i))^2=0.17$$假设此时已满足误差要求，那么$f(x) = f_6(x)$即为所求提升树。梯度提升算法提升树利用加法模型与前向分步算法实现学习的优化过程，当损失函数是平方损失和指数损失函数时，每一步优化是很简单的。但对一般损失函数而言，往往每一步优化并不是那么容易。针对这一问题，Freidman提出了梯度提升(gradient boosting)算法。这是利用最速下降法的近似方法，器其关键是利用损失函数的负梯度在当前模型的值：$$ -\left[ \partial{L(y, f(x_i))} / \partial{f(x_i)} \right] $$作为回归问题提升树算法中的残差的近似值，拟合一个回归树。梯度提升算法:输入：训练数据集$ T={(x_1, y_1), (x_2, y_2),... (x_N, y_N)}, x_i \in X \subset R^n, y_i \in y \subset R; $ 损失函数L(y, f(x));输出：回归树f(x).(1) 初始化$$ f_0(x) = argmin_c{\sum_{i=1}^NL(y_i, c)} $$(2) 对m=1,2,...,M(a) 对i=1,2,...,N,计算$$ r_{mi} = -\left[ \partial{L(y, f(x_i))} / \partial{f(x_i)} \right] $$(b) 对$ r_{mi} $拟合一个回归树，得到第m棵树的叶节点区域$R_{mj}, j=1,2,...,J$(c) 对$ j=1,2,...J, $计算$$ c_{mj} = argmin_c {\sum_{x_i \in R_{mj}}L(y_i, f_{m-1}(x_i) + c)} $$(d) 更新 $ f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J}c_{mj}I(x \in $_{mj}) $(3) 得到回归树$$ \hat{f(x)} = f_M(x) = \sum_{m=1}^{M}\sum_{j=1}^Jc_{mj}I(x \in R_{mj}) $$算法第1步初始化，估计使损失函数极小化的常数值，它只是一个根结点的树。第2(a)步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。对于平方损失函数，它就是通常所说的残差；对于一般损失函数，它就是残差的近似值。第2(b)步估计回归树叶结点区域，以拟合残差的近似值。第2(c)步利用线性搜索估计叶结点区域的值，使损失函数极小化。第2(d)步更新回归树。第2步得到输出的最终模型$ \hat{f(x)} $