对 ML 中 Normal Equation 的理解

机器学习中的回归问题,类似于以往各种工程上的优化问题。定义一个 Cost Function:

(1)   \begin{equation*}  J(\theta) = \frac{1}{2m}\sum_{i=1}^m(h_\theta(x^i)-y^i)^2 \end{equation*}

对这个函数求解最优化问题。

由于J是一个关于\theta的函数,所以目标是求一组最优的\theta,来使J取得最小值。

一个符合直觉的做法是Gradient Descent。也就是迭代地用 J\theta 求导,顺着梯度最大的方向移动,直到收敛于最低点。

另一个方法则是Normal Equation,对我来说这是一个非常强的公式,可以把Gradient Descent花了那么多次迭代才解决的事用一次运算就搞定:

(2)   \begin{equation*}  best \theta = (\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top \overrightarrow{y} \end{equation*}

这里面的\mathbf{X}是一个矩阵,\overrightarrow{y}是列向量,\theta其实也是列向量。
\mathbf{X}的每一行是一个样本,第i行其实就是 x_i^1, x_i^2, x_i^3, \dots 这样的一组特征(feature),其中的每个值都可以视作特征空间里的一个维度。
对于第i个样本,它对应的(标准)结果就是 y_i,总共m个样本结果组成了向量\overrightarrow{y}
(回顾一下Cost Function:损失函数其实是定义了我们的Hypothesis h_\theta(\mathbf{X})与真实结果\overrightarrow{y}之间的距离。以此衡量训练结果。)
再补充Hypothesis:

(3)   \begin{equation*}  h_\theta(x) = \theta^\top \overrightarrow{x} = \theta_1 x_1 + \theta_2 x_2 + \dots + \theta_n x_n \end{equation*}

Normal Equation 的思路类似于中学数学里求极值:对某个方程求导,然后让式子等于 0,等于 0 的点即为极值点。
但为什么上述思路能被(2)这样一个式子实现呢。


这个问题是我去年初遇到的。当时就想把阳哥哥给我的解答记录下来。拖了这么久,终于给Wordpress装了LaTeX插件,所以来记录一下:

(2)的推导方法有两种,第一种是 cost function J (1)对 \theta 这个向量的每一个分量求偏导

    \[ \begin{cases} \frac{\partial J}{\partial \theta_1} = \frac{1}{m} (h_\theta(x^1)-y^1) x_1\\ \frac{\partial J}{\partial \theta_2} = \frac{1}{m} (h_\theta(x^2)-y^2) x_2\\ \dots \\ \frac{\partial J}{\partial \theta_n} = \frac{1}{m} (h_\theta(x^n)-y^n) x_n \end{cases} \]

假设 \theta 是个n维向量,就得到了n个式子,令这n个式子都等于0,我们就得到了一个线性方程组:

    \[ \begin{cases} \frac{1}{m} (h_\theta(x^1)-y^1) x_1 = 0\\ \frac{1}{m} (h_\theta(x^2)-y^2) x_2 = 0\\ \dots \\ \frac{1}{m} (h_\theta(x^n)-y^n) x_n = 0 \end{cases} \]

这个线性方程组可以写成矩阵相乘的形式,即

(4)   \begin{equation*}  \mathbf{X}^\top\mathbf{X}\theta = \mathbf{X}^\top \overrightarrow{y} \end{equation*}

(4)这个式子就是所谓的Normal Equation。它跟式(2)是等价的。


第二种方法要稍微高级一点儿,写出来会简洁得多。就是直接把cost function写成矩阵的形式,即

    \[ J = (\overrightarrow{y} - \mathbf{X}\theta)^\top (\overrightarrow{y} - \mathbf{X}\theta) \]

然后直接以这个式子对向量 \theta 求导,也会直接得出normal equation。
至于如何直接对向量求导,你可以参考wikipedia的matrix calculus。其实本质上对向量求导就是一种记号,和对向量的每个分量求导没的本质区别。


再回头看一次这个好用的Normal Equation:

    \[ best \theta = (\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top \overrightarrow{y} \]

对于有 n 个特征维度的 \mathbf{X} 来说,用 Normal Equation 求 \theta 的复杂度是 O(n^3),而 Gradient Descent 的复杂度为 O(kn^2)
所以,当特征维度不多时,都可以用 Normal Equation 快速求解。当 features n > 10000 时,才开始考虑使用 Gradient Descent 。

但是,这个公式显然也不是能够无条件使用的。你可以看到其中有 (\mathbf{X}^\top\mathbf{X})^{-1} ,意味着括号内的矩阵必须是可逆的。
真的是这样吗?——老师说,此处的矩阵并不必须是可逆的。在代码中,对这个矩阵的求逆直接用pinv()函数来做(也就是求伪逆、广义逆)。阳哥哥说,使用广义逆来算 \theta(\mathbf{X}^\top\mathbf{X}) 不可逆时的一种传统的处理方式,可以用的原因是广义逆得出的 \theta 符合一些良好的统计性质。(具体参考:高惠璇的《统计计算》)
不过, (\mathbf{X}^\top\mathbf{X}) 不可逆往往意味着数据模型有问题(Features数量比样本数量还大,或是非常强的collinearity),遇到不可逆的情况还是返回去检查模型比较好。

Python 可视化图形界面简单实践

最近工作上常用的一个操作需要进行二进制数bit翻转。由于不知道windows系统计算器就有这个功能,自己用python写了一个。简单记录下实践过程。

Python进行GUI编程,可用的库并不多。功能也不算强大,这篇文章简单列举了几个库的特点。
我呢,没有被它们任何一个吸引。所以直截了当地选择了Python标准库自带的Tkinter
( Python Tkinter 官方文档:https://docs.python.org/2/library/tkinter.html

完成品大致是这样的:

基本框架是:

from Tkinter import *
top = Tk()
top.title("Listen's Option Checker")
# Your code here
top.mainloop()

在这个基础的窗口里,用Frame控件分割空间(类似于html和CSS那种方式)实现布局。
然后在各个分区的frame里,根据与用户的交互方式,选择对应的控件:Button、Entry、Label……

控件由类似这样的句子生成:

Confirm_Button = Button(frm2Sub1,text="确认",command=hex2bin)
Confirm_Button.pack(side=LEFT)

第一句创建了一个Button实例,这个按钮的父容器是frm2Sub1,按钮上文字为「确认」,当用户按下这个按钮时,就会立即触发一个名为hex2bin的函数,来对用户的操作进行响应。
现在命名空间内的Confirm_Button指向了这个Button实例。用.pack()方法来完成对它的部署。参数side=LEFT是要让它在所属Frame容器内靠左放置,若不指定位置,每个新的控件都会被部署在前一个控件下方。

当然,包括Frame在内的所有控件都需要通过.pack()来呈现。如果漏了这一句,程序界面内就看不到对应控件。

去查一下Tkinter支持控件列表,再配合以上基本信息,已经足以制作一些功能极其简单的可视化程序界面。其实网络上大多数介绍文章也没有讲的更多。
但还有一些值得注意的地方。

 

Command传参

Button控件的command参数,是不允许传参的
我理解此处的command参数就类似于一个函数指针,指向目标函数。
网上比较常见的传参方法是用lambda函数

Button(frm, textvariable=strvar31, command = lambda : FlipBit(31,strvar31))

它其实是定义了一个匿名函数,在Button被按下时执行的是lambda,再由lambda将参数交给你的执行函数。类似这样的用法,在只有一两个同类控件的时候是可行的。也很方便。

但对我这个程序来说,需要32个按钮充当32位二进制bit,不可能手动复制32个button的创建过程。
这里的Lambda函数,如果用在for循环创建的button内,就会导致它传进去的参数固定为for循环的控制变量i(的最大值,也就是最后一次循环的值)。
原因也很简单,lambda函数在未被执行时并不会被解释(编译成固定的函数)。它只有被真正执行时才生效。而真正执行时是Button按下时,不是For循环当初loop经过它时。所以i始终为定值(终值)。

最终的办法是用一个Event Handler。定义如下两个function:

def handler(bit):
num[bit] = num[bit] ^ 1
strvarlist[bit].set(str(num[bit]))
binary = "".join(map(str,num))
decimal = int(binary,2)
var16.set(hex(decimal))

def handlerAdaptor(fun,v):
return lambda event, fun=fun, v=v: fun(v)

由handlerAdaptor作中介,将参数传进去。方法是将handler与鼠标点击event绑定。
绑定鼠标事件的Button写法如下:

ButtonList.append(Button(SubSubFrameList[i], textvariable=strvarlist[i]))
ButtonList[i].bind('', handlerAdaptor(handler, i))
ButtonList[i].pack()

这里跟前面创建控件的方式不同,有一个小变化:
为了使我们这32个bit的控件(包括button和其上的textvariable)可以被方便地遍历,我不再是给它们赋予一个固定的命名,而是将每个实例直接.append()到它们各自的list里
这样我在另外的函数里处理它们时,可以直接用下标来控制和选择。——包括这里创建完成后的.bind()和.pack(),也都是用list加下标来做选择。


一些参考资料:
tkinter官方文档学习笔记
Tkinter 控件简单计算器示例
Python Tkinter参考资料之(通用控件属性)
tkinter模块常用参数(python3)
Python Tkinter GUI(三)显示图片
Python GUI进阶(ttk)—让界面变得更美


打包exe程序


上表来自《Python程序打包成exe可执行文件》,文章很有用。我此前用过的py2exe不好用,这次选择pyinstaller,简单打包方法:

pyinstaller -F -w main.py

生成文件在dist目录。build仅为中间文件。

-F 是打包成一个单独的exe文件,不加则会生成一整个目录的文件。(加了该参数会导致程序调用外部image失败,在spec配置内添加DATA也没用)

-w 不需要查看命令行时,用这个参数隐藏cmd画面。

亲测-F之后程序启动速度慢了几十倍不止。所以我不建议-F

更复杂的配置,需要使用脚本相同目录下,由pyinstaller生成的一个.spec文件。我没有深入研究,需要时可以在网上查。(参考:pyinstaller打包工具的使用说明将自己的python程序打包成.exe/.app)
Continue reading “Python 可视化图形界面简单实践”

Mac操作系统上的ss客户端:ShadowsocksX-NG

一直以来我使用的ss客户端都是ShadowsocksX,设置比较简单,功能也很稳定。没有想过要换。
但是GFW砌墙技术日新月异,ss的开发者们想必也没有闲着,ShadowsocksX却很久很久都没有更新过了,这让我很没有安全感。

后来在GitHub上一找,才发现原作者@clowwindy停止更新ShadowsocksX之后,其他开发者用Swift重写了一版ShadowsocksX-NG,之后都在NG版本进行更新。
但是我下载X-NG之后,经过简单的配置,却无法像X那样开始使用。于是开始(瞎jb)排查问题。


以下这些操作我在单独执行每一步的时候都没有作用。直到我把它们全都做过一遍之后,我的X-NG才开始正常工作。
所以把它们记录下来,希望有人能用得上。


首先需要知道,这版X-NG会把自己的log文件:ss-local.log
保存在路径:~/Library/Logs
所以这个log文件的地址为:~/Library/Logs/ss-local.log

通过log文件的error记录,可以看到一些错误提示

例如上图中,我的error是:address已被占用。

查看了一下端口监听状况,问题在于,我在偏好设置中,把本地的「Socks5监听端口」和「HTTP代理监听端口」设置成了同一端口。导致http代理先启动而占用了端口,Socks代理就启动失败了。

⬆️随便把它们改成不同的值即可解决问题。

 

另外一种常见问题是,ss-local服务启动失败
(log里的记录为:ShadowsocksX-NG Start ss-local failed.
这可能是ss-local没有执行权限导致的。

GitHub上有一种说法是删除软件重新安装可以解决。但是……???重装这种操作真的是程序员解决问题的思路吗…………………………

我参考了另外的做法,
cd /Applications/ShadowsocksX-NG.app/Contents/Resources

ss-local赋予执行权限:
chmod +x ss-local
然后,重启电脑。
(我还发现另外有个地方也有ss-local文件:/Users/godlike/Library/Application Support/ShadowsocksX-NG/ss-local-3.0.5   不知道影不影响)

 

我还看到有人的做法是把这个文件的读写权限赋给所有用户⬇️,我也照做了。虽然我感觉这项并不影响它的运行。

如果你曾经安装过另外的ss客户端,前往文件夹:
~/Library/Application Support/
删除其他的SS文件夹 ,只留一个
因为可能是ss-local冲突(虽然我觉得这种说法很没有道理)

 

最后,可以用这个命令来检查一下端口监听状况:
lsof -iTCP -sTCP:LISTEN -n -P
我这里,正常运行的ShadowsocksX-NG会有图示的4个进程:

其中,privoxy监听了我设置的HTTP代理端口,ss-local监听了我设置的Socks5代理端口。而两个Shadowsoc如果没跑起来,你就翻不了墙。

下面的命令可以用来验证Socks代理是否成功转发你的流量
curl --socks5 127.0.0.1:1086 http://cip.cc


我的服务器在日本,所以可以看到这个网站返回的我的IP是东京的地址。
当然,其实你用浏览器开个google就知道代理是否运行成功了。


PS. 如果你像我一样,之前对别的软件做过代理设置(例如Dropbox的「网络」-「代理服务器」,我之前设置了本机的Socks5代理)
你需要根据新的Socks5监听端口对它们进行修改。
因为老版本的ShadowsocksX默认监听在1080端口,而ShadowsocksX-NG则默认监听1086端口。


附赠:《科学上网漫游指南》
我觉得上面的信息挺有用的

深入理解GFW:内部结构

用python控制鼠标键盘帮我做测试

写了一个脚本实现自动化测试过程。

最近公司在做一些测试,属于简单重复劳动,一套做下来费神费力,又学不到什么东西,几乎没有收获。
因此写了一个python脚本自动去控制整个流程。


测试的流程是在一个Terminal软件里执行一系列命令(有一定规律性),然后对输出的结果做文字处理(提取关键信息,做数据统计、分析)。
文字处理用python好做,但是数据处理过程中其实是用一个前辈写的脚本软件实现的,所以有一丢丢麻烦的地方。

最后我写了三个程序来组成这个自动化脚本。

主程序会使用PyAutoGUI库来实现对鼠标和键盘的控制。
A子程序是一个命令生成器,在它里面定义一些规律性的东西,然后生成出一个cmd_list传回主程序。调试的时候直接运行子程序就能看到是否生成了预期的系列指令。
B子程序是中间信息处理。将主程序写在input文件里的内容提取出目标数据,存入另一个文档,用os库调用前辈的.exe档来执行中间处理。

具体来说,我的PyAutoGUI在程序开始运行时会要求用户进行两次移动鼠标的操作(坐标采集)。
采集到的坐标分别对应了Terminal软件和txt文档的编辑器。
正式开始运行之后,程序调用A的生成器获取命令列表,移动鼠标到Terminal去,选中这个Terminal,然后用键盘对它输入指令(整个命令列表)。
这里存在一个判断,如果当前输入的这条指令是一个很耗时的操作,那就time.sleep(5)这样等待一段时间。否则Terminal那边执行到一半,键盘就会开始下指令。相应地,输出的log信息也就会被打乱。

完成一套测试指令之后,PyAutoGUI会执行CTRL+C,去txt编辑器那边CTRL+V,然后保存这个log文件,交给B去做数据处理。

B完成处理的分析结果我是直接print到了console里。这样我对每轮的输出可以进行检查,然后手动写入excel文档里。
不过应该用csv库直接导出到csv更好。给代码增加一点健壮性,遇到log异常的时候直接重新进行测试就好了。


用到的第三方库:

  • os
  • time
  • pyautogui

经验性的总结:

PyAutoGUI很好用,它还有官方中文说明文档:Doc PyAutoGUI

应该将程序模块化实现。对每个子程序都可以用

if __name__ == "__main__":

单独调试,很赞。

如果程序的功能相对固定,不需要经常修改的话,可以封装成exe,这样也方便同事使用(比如前辈给我的那个exe档)。例如可以参考:如何将python程序封装成exe可执行文件

后续如果要加csv输出的功能,参考:
13.1. csv — CSV File Reading and Writing
总结python对csv文件的操作

目前还存在另一个问题就是PyAutoGUI库还没支持多屏。双屏时它对相同坐标位于哪个屏幕可能会有些困扰。所以我跑脚本时都得把外接显示器拔掉。
这个问题只能等新版本的PyAutoGUI解决了。

导出Ello上的个人数据

Ello是我常用的一个社交自言自语平台。
我不想打扰朋友圈的时候就发在ello里。它的优势是文字内容不限长度,支持基础的排版(加粗、链接、tag、划去),允许发布后再次编辑,还支持图文混排。
以前它还有个优势是发图是不会被压缩,但现在也要压图了,而且没有针对长图优化(超长图片大概是起源于微博的中国特色?),所以有点烦。

ello另一个「卖点」是尊重个人信息的所有权。有比较丰富的隐私设置,号称绝不把用户数据出卖给广告商,还能方便地「带走」或者删除自己在这个平台上的数据。

我已经在ello上面产生了太多的内容(612 Posts),开始对这些信息的管理有所担忧。
所以今天试了下「带走」数据。


点击右上角头像,进入settings。往下翻,翻到Your Data标签,点开之后有Export Data选项,点申请。
然后ello就会把你的数据打包,下载链接发送到你的邮箱,24小时有效。

我跑到邮箱里一看,蒙蔽了,是个.json文件。
打开之后的体验如下:

好在我会python,对吧。

然后我就写了一个小的辅助程序。
它把json文件读入python,然后略去不重要的信息,只把post的内容和发布时间提取出来:

这对我来说就已经够用了。提取结果以文本形式输出到一个txt文件里方便以后查看。

图片以网址的方式给出。如果需要存图的话,随便写个小爬虫就能存下来了。

保存的post是按照最后编辑时间逆序(因为ello给的json里就是按这个顺序)。编辑顺序往往跟发布顺序不同。
发布时间已经从json里提取出来了,如有需要可以按发布时间再做一次排序。对我来说影响不大,我就没有加。

代码已放到GitHub:https://github.com/MamaShip/ElloExporter