Month: 6 月 2012

读完了数学之美

正如上一篇日志中提到的, 最近买了吴军博士数学之美并利用晚上的时间在看. 粗粗的过了一遍, 把以前很多没明白的东西给理顺了下, 具体的一些数学推导没来得及去验证. 书的后半部分感觉比较凌乱和随意, 不过还是值得购买去支持的, 如果大家都不买书, 那以后也会越来越难读到经典之作.

读的过程中用手机简单记了些简单的笔记, 现在回头想想, 再过一下:

方法论

1. 做事要简洁高效: 简单粗暴的方法, 只要是对的那就应该这么做, 与其花非常大的代价弄一个貌似完美的系统, 最后还不一定能保证结果, 还不如花很短的时间去做一个能达到 90% 性能的可用系统, 并用若干个 90% 性能的系统组合起来达到完美效果. 这一点也是我非常认可和坚持的, 在团队里也需要贯彻下去.

2. 凡事都需要可解释: 做策略做算法, 一定要对每个 case 给出合理的解释, 这样才能知道怎么去改进. 吴军在书里举的例子是说搜索, 一开始要用简单高效的系统和特征来保证鲁棒性和可调试性, 其实在计算广告和推荐系统里也是一样, 只是我们现在总会一上来就弄很多复杂的上去, 导致很难调试和追查, 最后就一把烂账怎么也算不清. 这点上自己一直做的不好, 要好好注意.

3. 真理应该拥有简单漂亮的描述: 自然真理的本质描述往往是很简单的很漂亮的, 如果搞的太复杂, 就不太对头, 多半是方向都错了. 书里的例子是说描述太阳系的行星运动, 地心说的模型需要用 40 层圆周修正, 日心说则可以降低到 8-10 个圆周修正, 但最后的真理却是一个椭圆方程就完美解释.

具体案例

1. 新闻/文本分类中的加权. 在做余弦相似度计算时, 需要考虑位置加权, 词性加权等影响. 对于位置加权, 一般的思路都是对树形结构做加权, 比如普通文章的标题/摘要等, 网页则一般是 HTML 语法树的加权, 实际上 Google 在很早之前就开始模拟网页渲染, 做物理位置的加权, 而这一套网页渲染的技术, 用来开发 Chrome 不是正好? 而且随着 Chrome 的市场占有率上升, 也可以逼迫高质量网站的网页代码会更标准, 至少是可以兼容 Chrome 的标准, 这样 Google 可以获得更准确的页面渲染效果并用于权重计算, 现在很多别的公司也开始关注浏览器, 但是不知道有没有想到这一层用法. 词性加权这又回到 NLP 的基础建设上, 果然做互联网, 要做精做深, NLP 是个绕不开的大坑, 就算数学模型如此优雅和有用, 但还是需要有基础数据才能去计算.

2. Logistic Regression 在工业界的广泛应用. 自己好像在生产环境中就用过这一种模型, 接触过线性回归和 Naive Bayes, 但是都没能去深入理解, 其他 boosting 和 SVM 等方法, 每次都是听了个大概, 一直没空去试. 根据自己的经验, 以及吴军的说法, LR 最大的优点是线性叠加, 皮实耐操以及水平扩展性好, 这几个都挺符合方法论的. 不过在点击率非常低的环境下, 要用好 LR 确实很难, 吴军说的是特征权重在 [-6, +6] 区间才有意义, 按 Sigmod 变换函数 1/(1+exp(-z)) 计算, -6 对应的也不过是 0.247%, 这个点击率在搜索广告以外的很多地方还是挺难达到的, 加上位置, beta0 等修正后可以让值很接近, 但是精度又受很大影响, 之前想过把某个小区间做放大处理, 但是一直没想清楚到底要怎么扩, 怎么能维持相对关系并可以还原, 求指点.

随笔杂记

有一些比较糙的想法, 没有成型, 随便记录下

大公司病和用户基因

主要内容来自新浪微博 @纯银V 的博文 腾讯抄你怎么办. 里面有挺多非常值得参考的观点, 吐槽大公司的各种弊端让人看的非常爽, 强烈推荐.

其中有一段在说 “用户基因”, 大意是在网易里想做一个摄影社区, 为了利用好网易庞大的已有用户量, 任意往里倒资源, 就会让用户群鱼龙混杂, 最后完全做不下去, 还不如一直走兴趣相投的精英版路线. 这样的例子比比皆是, 比如百度知道和知乎, 就是完全不一样的定位和用户群, 哪怕一开始都想定位于精品问答, 而知道绝对还是会发展成大众化问答且质量参次不齐. 其实这应该也是百度一直比较难做出什么精品产品而非大众产品的原因, 偏偏百度做大众产品成功运气的成分更大点 (比如知道和贴吧), 很多时候是想做精品产品而因为用户基因的关系而悲剧掉 (比如百科绝对没法像维基那样精品化, 只能是不那么严谨的大众科普加一些好玩搞笑). 从这个结论出发, 如果是在有很多用户基础的公司内做新产品, 路就两条, 一是做小众精品, 尽量不要用公司资源, 免得导入大量低质用户, 二是老老实实做平民产品, 利用已有用户资源且应对各种坑爹的奇葩. 是不是突然觉得有哪里不对? 如果走第一条路, 那为什么还在个大公司里做呢? 还不如直接出去创业, 反正做事都一样, 还免得大公司各种条条框框限制, 比如风车. 除非这个公司的已有用户也都是高质量用户, 如豆瓣的很多新产品.

回归模型和在线学习

一开始还是一个微博上的问题, 说幼儿园的题目大人不会解, 找了个样例是

967621 = 3
797321 = 1
378581 = 4
422151 = 0
535951 = 1
335771 = 0
565441 = ?

一般都是列方程求解, 但其实这也是个挺好的回归模型应用例子, 打算下次写机器学习手记的时候就写这个. 我人人上的好友写了一篇 幼儿园的题目和机器学习的关系, 我分享的链接后还跟别人讨论了下在线算法和离线算法的差异. 其中提到一些很有意思的观点, 就是 online 的更新算法会因为只在继续拟合新样本而不管原来样本的拟合, 会导致结果的抖动很大, 这是其在跟 batch 方法比较时的缺陷, 但换个角度看, 正因为 online 的方法没有受到历史数据的约束, 反倒可以更快的响应新数据的变化. 最后那个响应的问题, 也许可以在现在的工作中用起来, 最近就一直被新数据响应和数据短期内剧烈变化所困扰.

数学之美

吴军博士浪潮之巅后的又一部经典之作, 把以前谷歌黑板报上的系列文章重新整理加补完, 前几天在京东上买了这本, 正在看, 强烈推荐.

希望读完后能有一些笔记性的东西出来, 这里先记一下. 第三章 2.2 节讲到对低频样本出现的潜在观测误差的处理, 用平滑或做折算的方式降低抖动可能, 这个想法也非常赞, 在最近的工作中应该也可以用起来, 实际上之前做过的某事情已经就在用类似的方法, 只不过思想和折算方法不太一样罢了.

电脑修的好

昨天去给灰太狼同学修了一把 ThinkPad T500, 各种诡异, 记录娱乐下.

灰狼早几天在群里说自己笔记本开不了机, 直接通不了电, 之前还开过一次机报 BIOS 时间错误, 于是帮查了下看有说静电因素的, 有说 BIOS 电池没电的, 看他按各种土法比如按住电源键十秒钟来放电什么的搞了几天都没弄好, 昨天带上两把螺丝刀过去蹭饭兼修电脑.

先听灰狼吐槽了把说这机器才过保修期就坑爹了, 果然欧美产品都这德行么, 问说是 09 年 4 月那批大陆学生机的 T500, 印象中 09 年的两批学生机都很赞, 如果自己留意下还可以注册 3+3 的意外保, 不过到现在怎么算也都过期了, 还是拆机搞吧. 先去看了下官方的维护手册, 感觉跟 T60 是完全一样的拆法, 直接上螺丝刀搞开看 BIOS 电池.

插一句, ThinkPad 有个好处是官方的维修手册非常详细而且可以很容易弄到, 在 Google 上直接搜 “hardware maintenance manual t500” 就有, 每个模块怎么拆, 螺丝型号都标的一清二楚. 其他型号也可以类似的搜到, 换下型号名就可以了.

把 BIOS 电池拔掉后直接插外接电源, 机器自动开机, 提示 BIOS 时间不对, 重设后自动重启, 一切正常. 心说这也没多大个事嘛, 就是缺把螺丝刀, 哼哧呼哧把键盘和掌托装回去, 插电池插电源, 开机, 开机, 好像开不了机… 还是一样的问题. 这时候正好饭点, 一群吃货表示应该先吃饭, 于是把本子搁一边先胡吃海喝了一通.

吃完继续折腾, 拔 BIOS 电池, 把整个 BIOS 都重设了一把, 插电能点亮进系统, 但是只能是在 BIOS 电池不在的情况下直接插外接电源才能开机, 键盘其他键工作正常, 但是开机键无法启动. 这时候抱个 iPad 搜了半天, 问题一般都还赖在 BIOS 电池上, 仔细瞅了下不就是块 CR2032 么, 以前文曲星都用这个, 随便个表店或小超市都有, 出门买一块回来换上就行了.

和灰狼出门去他家旁边的家乐福买电池和电工胶带, 悲剧开始. 先是绕了一圈到家乐福里, 在卖电池那看了半天也没看到有 CR2032, 于是问旁边的工作人员, 人直接说没有, 对面哪家有, 汗, 有这么做生意的么… 再次 BS 家乐福坑爹的路线设计, 绕到三楼出来下去, 走到二楼的时候我说看看这有没卖表或修表的, 多半有, 果然走到一楼看到一个修表铺, 一问真有, 掏钱买之. 想了下既然还没出家乐福这个楼, 直接回去再买电工胶带就可以回去了, 回到卖电工设备那, 找半天继续没找到电工胶带, 问工作人员, 说他们没有, 楼下百安居有, 这… 你们家到底在卖什么啊, 还是说这种垂直领域都放弃了? 绕一大圈到一楼百安居, 按工作人员提示到地下一层找到电工胶带, 回到一楼准备出去, 发现进来那个大门方面赫然写着 “收银台在地下一层”, 这你妹的, 出门不看黄历, 一定是不宜出行. 下楼, 付钱, 再上楼原地出去, 好像也没人查, 要当时直接出来了估计也没人管?

回去把原装电池的胶皮弄掉, 两根引线两头的接触片居然分别用两个焊点焊在了电池上, 我了个大擦, 找出把水果刀俩人一起搞了半天才搞掉. 把引线缠新电池上, 胶带封好让正负极分离, 跟外面也绝缘, 插回去, 这活做的还是挺不赖的, 但是… 他瞄的症状还是一样的, 这情何以堪啊.

仔细想了很久, 说会不会是这个电源键坏了… 虽然键盘上其他键都是好的, 但是好像这个电源键真的不太对路. 用不插 BIOS 电池直接插外接电源的方式开机, 点亮后把 BIOS 电池插回去, 进系统后按电源键, 依然没有反应. 看了下 TP 键盘的排线接口, 好像跟以前我的 T60 是一样一样的, 跟灰狼出馊主意说要不背上本去我那, 我把我的 X200 键盘拆了接你机器上看能不能用. 反正也没啥别的好想法, 灰狼就背着他死沉的加了九芯电池的 T500 一起回我这, 顺带在我家吃火锅.

继续搜 HMM X200 搜到怎么拆解 X200, 用 iPad 打开放旁边, 忍不住插嘴赞一句 retina 屏的 new iPad 显示细腻度拿来放这种带图说明手册太爽了, 当时拼 LEGO 的时候这么拿着比看说明书估计还爽, 就是缩放比例要维持对 (LEGO 的说明书上经常有 1:1 的零件图示供你比划, 让注意别找错东西了). X200 的拆机顺序跟之前拆过的 T60/T61/T500 都不一样, 是直接先下键盘再下掌托, 而且键盘螺丝有四枚, 分布的还非常诡异, 不过图还是给的很清楚的, 螺丝刀下去键盘起来, 干净利落. 把 X200 键盘接 T500 上的时候发现, 虽然排线接口是一样的, 但是排线走的方向不一样, 而 T500 的那个口刚好很接近防滚架, 纠结了半天才让排线扭到防滚架和主板中间的缝隙并让插头插到位. 第一次方向弄反了, 还是点不亮, 换个方向成功点亮, 进系统后也能正常起作用. 同情的看着灰狼说这种人品事件真的没办法, 换个键盘吧, 估计就两百大洋, 灰狼同学执行力果然一流, 当场就在旁边抱着自己的 iPad 上淘宝买了个, 不过两个人还是纳闷了半天这个电源键怎么可能坏…

把两台本装回去的时候顺带给 X200 清了下灰, 风扇里好多絮状灰尘, 没有皮吹没有能吹冷风的电吹风, 其实就是用嘴狠狠吹了几把, 不过好像散热是好了那么点, 至少风扇嚎起来的时候声音没那么大了.

最后自吐一把, IT support 你好, IT support 再见.

New iPad 越狱记

New iPad 入手两三周, 一直就安分守己的用, 也没觉得有啥不爽. 期间充值 50RMB 用于购买 随手记专业版 (12RMB) 和 鳄鱼小顽皮爱洗澡 (6RMB), 做的好的 App 确实值得付费, 随手记我认证后在手机上也可以通过 Android 版同步. 用盗版还是心存愧疚, 一是现在自己也不差这么点钱, 二是作为 IT 从业者, 自己都不支持这个行业, 那怎么指望行业能好起来.

因为 iOS 系统自带中文输入法确实不够好用, 打算越狱装百度输入法, 另外如果想用 GoAgent 之类的东西在 iPad 上翻墙, 也都需要越狱, 所以 pod2g 大神的 Absinthe 2.0 放出来后就一直惦念快把自己手上这个 5.1.1 的 new iPad 给 JB 了, 但一直懒得搞, 看教程也都说如果已经装了很多应用, 越狱要比较久, 所以拖到今天才完成. 记录一下过程, 中间有个诡异问题, 如果有同样遇到此问题的, 希望能帮到你.

整体越狱过程按 91 上的 http://ipad.91.com/content/2012-05-25/20120525055537524_1.shtml 进行, 需要下载的工具 91 上也直接有提供.

iPad 一到手就将其升级 5.1.1, 所以只需要用 iTunes 备份数据, 以及备份自己的 SHSH. iTunes 备份也还比较快, 把一堆 iPad 上装的东西同步到本地后, 没到一分钟就完成了备份. 在备份 SHSH 的时候遇到了麻烦, 按 http://iphone.91.com/content/2010-06-28/20100628000014805,1.shtml 上的方法进行备份时, TinyUmbrella 一直无法启动, 同文件夹下 .log 文件内报如下错误

Exception in thread "AWT-EventQueue-0" java.lang.NoClassDefFoundError: com/sun/jna/Platform
    at com.semaphore.os.UIHandlerManager.getSystemUIHandler(UIHandlerManager.java:22)
    at com.semaphore.TinyUmbrella.(TinyUmbrella.java:131)
    at java.lang.Class.forName0(Native Method)
    at java.lang.Class.forName(Unknown Source)
    at com.semaphore.TinyLoader.loadTiny(TinyLoader.java:248)
    at com.semaphore.TinyLoader.access$000(TinyLoader.java:29)
    at com.semaphore.TinyLoader$1.run(TinyLoader.java:42)
    at java.awt.event.InvocationEvent.dispatch(Unknown Source)
    at java.awt.EventQueue.dispatchEventImpl(Unknown Source)
    at java.awt.EventQueue.access$000(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.awt.EventQueue$3.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.security.ProtectionDomain$1.doIntersectionPrivilege(Unknown Source)
    at java.awt.EventQueue.dispatchEvent(Unknown Source)
    at java.awt.EventDispatchThread.pumpOneEventForFilters(Unknown Source)
    at java.awt.EventDispatchThread.pumpEventsForFilter(Unknown Source)
    at java.awt.EventDispatchThread.pumpEventsForHierarchy(Unknown Source)
    at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
    at java.awt.EventDispatchThread.pumpEvents(Unknown Source)
    at java.awt.EventDispatchThread.run(Unknown Source)
Caused by: java.lang.ClassNotFoundException: com.sun.jna.Platform
    at java.net.URLClassLoader$1.run(Unknown Source)
    at java.net.URLClassLoader$1.run(Unknown Source)
    at java.security.AccessController.doPrivileged(Native Method)
    at java.net.URLClassLoader.findClass(Unknown Source)
    at java.lang.ClassLoader.loadClass(Unknown Source)
    at sun.misc.Launcher$AppClassLoader.loadClass(Unknown Source)
    at java.lang.ClassLoader.loadClass(Unknown Source)
    ... 21 more

一开始一直以为是自己的 Java 版本有问题, 看提示这几个包应该都是 Java 的基础包才对, 怎么可能找不到, 网络上找到的很多说法也是如此. 重装了几次 JRE 7u4, 整个卸载重装都弄过后还是一样的错误, 抓狂了. 找了半天终于在威锋上找到 http://bbs.weiphone.com/read-htm-tid-4677881.html 这么一帖, 楼主在 4 楼自己搞定问题, 就是缺这几个包, 下载下来解压到同目录后搞定.

剩下的就完全是按部就班的操作, 整个过程比我想的快很多, 不到 20 分钟就完成了所有的事情, 本来还以为 16G 的 iPad 装了 7G+ 的东西后会耗时很久, 实际看来也没用多久嘛, 被吓到了.

越狱后先装了一个百度输入法, 按照官网上 http://shouji.baidu.com/input/ihelp.html 里的流程来, 很快搞定. 中文输入体验确实要比自带的好很多, 不过还是有几个小问题:
1. 还没有针对 retina 屏的版本, 导致整个皮肤看起来非常糙
2. 不同输入模式的切换是在键盘上大幅度左右划拉, 这个切换没有提示非常不方便, 且一开始划拉距离短了就变成是按下滑动输入

然后就是翻墙啦, 去 GoAgent 的 Google Code Wiki 上找到官方文档 http://code.google.com/p/goagent/wiki/GoAgent_IOS, 按提示来:
1. 把身份改为开发者, 在 Cydia 里的 “软件源” Tab 左上角的 “设置” 里改
2. 装 SBSettings, Cydia 首页右上的推荐里就有
3. 添加新源 http://goagent-app.googlecode.com/svn/trunk/cydia/ 进 Cydia 软件源, 在这个源里安装 Python 和 goagent-local
4. 在 Cydia 里装一个 iFile 用于修改 GoAgent 的 proxy.ini 文件. 在 /User/goagent-local/proxy.ini (其实也就是 /var/mobile/goagent-local/proxy.ini) 里找 appid 并将值修改为自己的 GAE 名
5. 用 iPad 上的 Safari 打开 https://goagent.googlecode.com/files/CA.crt, 按提示安装证书
6. 回到 Cydia 的 goagent 源, 安装 goagent-toggle. 打开 SBSettings 面板 (我的是从屏幕右上角往屏幕中间滑, 不知道是不是默认的设置), 把 GoAgent 打开 (图标变绿)
7. 在 设置 -> Wi-Fi -> 现在连着的这个 Wifi 名 里, 将 HTTP 代理修改为 自动, 并把 url 修改为 file://localhost/var/stash/Applications/MobileSafari.app/8087.pac (官方说的第一个地址 file://localhost/var/mobile/goagent-local/8087.pac 在我这无效)
8. 打开 Facebook.com 测试, 翻墙成功, 玩去 :)

目测常用应用 Facebook, Twitter, YouTube, WikiPedia 等都可以正常使用, oh yeah
其中 Twitter 直接打开网页会提示 403 错误, 用客户端时将 api 的地址从 https://api.twitter.com 改成 http://api.twitter.com 后搞定

机器学习手记系列 2: 离线效果评估

上一次说到选特征的一个简单方法, 但是如果真的要评估一个方法或者一类特征的效果, 简单的相似度计算是不够的, 在上线实验之前, 还是需要有一些别的方式来做验证.

我遇到过的大部分机器学习问题, 最终都转成了二分类问题 (概率问题). 最直白的比如 A 是否属于集合 S (某照片中的人脸是否是人物 Z), 排序问题也可以转换为二分类问题, 比如广告点击率或推荐的相关度, 把候选集分为点击/不点击或接受推荐/不接受推荐的二分类概率. 那在上线之前, 可以用过一些分类器性能评估的方法来做离线评估.

分类器的正确率和召回率

前几天在无觅上看到有人分享了一篇 数据不平衡时分类器性能评价之ROC曲线分析, 把这个问题已经讲差不多了, 我这复述一下.

先说混淆矩阵 (confusion matrix). 混淆矩阵是评估分类器可信度的一个基本工具, 设实际的所有正样本为 P (real-Positive), 负样本为 N (real-Negative), 分类器分到的正样本标为 pre-Positive’, 负样本标为 pre-Negetive’, 则可以用下面的混淆矩阵表示所有情况:

              | real-positive       | real-negative
pre-positive' | TP (true positive)  | FP (false positive)
pre-negative' | FN (false negative) | TN (true negative)

通过这个矩阵, 可以得到很多评估指标:

FP rate = FP / N
TP rate = TP / P
Accuracy = (TP + TN) / (P + N)    # 一般称之为准确性或正确性
Precision = TP / (TP + FP)        # 另一些领域的准确性或正确性, 经常需要看上下文来判断
Recall = TP / P                   # 一般称之为召回率
F-score = Precision * Recall

在我接触过的大部分工作中, 大家都在关注 Precision 和 Recall. 同引用原文中提到的, 这样的分类评估性能只在数据比较平衡时比较好用 (正负例比例接近), 在很多特定情况下正负例是明显有偏的 (比如万分之几点击率的显示广告), 那就只能作为一定的参考指标.

分类器的排序能力评估

很多情况下我们除了希望分类器按某个阈值将正负样本完全分开, 同时还想知道候选集中不同条目的序关系. 比如广告和推荐, 首先需要一个基础阈值来保证召回的内容都满足基本相关度, 比如我一大老爷们去搜笔记本维修代理你给我出一少女睫毛膏的广告或推荐关注, 我绝对飙一句你大爷的然后开 AdBlock 屏蔽之. 在保证了基础相关性 (即分类器的正负例分开) 后, 则需要比较同样是正例的集合里, 哪些更正点 (其实说白了就是怎样才收益最大化). 一般来说, 如果分类器的输出是一个正例概率, 则直接按这个概率来排序就行了. 如果最终收益还要通过评估函数转换, 比如广告的 eCPM = CTR*Price, 或推荐里 rev = f(CTR), (f(x) 是一个不同条目的获益权重函数), 那么为了评估序是否好, 一般会再引入 ROC 曲线和 AUC 面积两个指标.

ROC 曲线全称是 Receiver Operating Characteristic (ROC curve), 详细的解释可以见维基百科上的英文词条 Receiver_operating_characteristic 或中文词条 ROC曲线. 我对 ROC 曲线的理解是, 对某个样本集, 当前分类器对其分类结果的 FPR 在 x 时, TPR 能到 y. 如果分类器完全准确, 则在 x = 0 时 y 就能到 1, 如果分类器完全不靠谱, 则在 x = 1 时 y 还是为 0, 如果 x = y, 那说明这个分类器在随机分类. 因为两个都是 Rate, 是 [0, 1] 之间的取值, 所以按此方法描的点都在一个 (0, 0), (1, 1) 的矩形内, 拉一条直线从 (0, 0) 到 (1, 1), 如果描点在这条直线上, 说明分类器对当前样本就是随机分的 (做分类最悲催的事), 如果描点在左上方, 说明当前分类器对此样本分类效果好过随机, 如果在右下方, 那说明分类器在做比随机还坑爹的反向分类. 引用维基百科上的一个图来说明:

ROC 曲线示例

其中 C’ 好于 A (都是正向的), B 是随机, C 是一个反效果 (跟 C’ 沿红线轴对称, 就是说把 C 的结果反过来就得到 C’).

如果我们有足够多的样本, 则对一个分类器可以在 ROC 曲线图上画出若干个点, 把这些点和 (0, 0), (1, 1) 连起来求凸包, 就得到了 AUC 面积 (Area Under Curve, 曲线下面积). 非常明显, 这个凸包的最小下面积是 0.5 (从 (0, 0) 到 (1, 1) 的这条线), 最大是 1.0 (整个矩形面积), AUC 值越大, 说明分类效果越好.

用 ROC 曲线定义的方式来描点计算面积会很麻烦, 不过还好前人给了我们一个近似公式, 我找到的最原始出处是 Hand, Till 在 Machine Learning 2001 上的一篇文章给出 [文章链接]. 中间的推导过程比较繁琐, 直接说我对这个计算方法的理解: 将所有样本按预估概率从小到大排序, 然后从 (0, 0) 点开始描点, 每个新的点是在前一个点的基础上, 横坐标加上当前样本的正例在总正例数中的占比, 纵坐标加上当前样本的负例在总负例数中的占比, 最终的终点一定是 (1, 1), 对这个曲线求面积, 即得到 AUC. 其物理意义也非常直观, 如果我们把负例都排在正例前面, 则曲线一定是先往上再往右, 得到的面积大于 0.5, 说明分类器效果比随机好, 最极端的情况就是所有负例都在正例前, 则曲线就是 (0, 0) -> (0, 1) -> (1, 1) 这样的形状, 面积为 1.0.

同样给一份 C 代码实现:

struct SampleNode {
  double predict_value;
  unsigned int pos_num;
  unsigned int neg_num;
};

int cmp(const void *a, const void *b)
{
   SampleNode *aa = (SampleNode *)a;
   SampleNode *bb = (SampleNode *)b;
   return(((aa->predict_value)-(bb->predict_value)>0)?1:-1);
}

double calcAuc(SampleNode samples[], int sample_num) {
  qsort(samples, sample_num, sizeof(SampleNode), cmp);

  // init all counters
  double sum_pos = 0;
  double sum_neg = 0;
  double new_neg = 0;
  double rp = 0;
  for (int i = 0; i < sample_num; ++i) {
    if (samples[i].neg_num >= 0) {
      new_neg += samples[i].neg_num;
    }

    if (samples[i].pos_num >= 0) {
      // calc as trapezium, not rectangle
      rp += samples[i].pos_num * (sum_neg + new_neg)/2;
      sum_pos += samples[i].pos_num;
    }
    sum_neg = new_neg;
  }

  return rp/(sum_pos*sum_neg);
}

分类器的一致性

如果分类器的概率结果就是最终结果序, 那 AUC 值基本可以当作最终效果来用. 但是实际应用中分类器的结果都要再做函数转换才是最终序, 则评估的时候需要将转换函数也带上去做 AUC 评估才行. 某些应用中这个转换函数是不确定的, 比如广告的价格随时会变, 推荐条目的重要性或收益可能也是另一个计算模型的结果. 在这种情况下, 如果我们可以保证分类器概率和实际概率一致, 让后续的转换函数拿到一个正确的输入, 那么在实际应用中才能达到最优性能.

为了评估分类器概率和实际概率的一致性, 引入 MAE (Mean Absolute Error, 平均绝对误差) 这个指标, 维基百科对应的词条是 Mean_absolute_error. 最终的计算方法很简单, 对样本 i, fi 是预估概率, yi 是实际概率, 则 i 上绝对误差是 ei, 累加求平均就是 MAE:

MAE 公式

MAE 的值域是 [0, +∞), 值越小说明分类器输出和实际值的一致性越好. 我个人认为如果 MAE 和实际概率一样大, 那这个分类器的波动效果也大到让预估近似随机了.

MAE 看起来和标准差有点像, 类似标准差和方差的关系, MAE 也有一个对应的 MSE (Mean Squared Error, 均方差?), 这个指标更多考虑的是极坏情况的影响, 计算比较麻烦, 一般用的也不多, 有兴趣的可以看维基百科上的词条 Mean_squared_error.

MAE 计算太简单, MSE 计算太纠结, 所以都不在这给出代码实现.