专栏名称: 算法与数学之美
从生活中挖掘数学之美,在实践中体验算法之奇,魅力旅程,从此开始!
目录
相关文章推荐
九章算法  ·  前端岗位面试该如何建立护城河? ·  昨天  
九章算法  ·  今日开播!FAANG工程师给北美码农划202 ... ·  2 天前  
九章算法  ·  一招通关Meta面试!system ... ·  4 天前  
九章算法  ·  湾区宝妈们,“杀入”新赛道 ·  4 天前  
51好读  ›  专栏  ›  算法与数学之美

数学家破解婚恋网站配对程序 90天找到灵魂伴侣

算法与数学之美  · 公众号  · 算法  · 2017-09-10 21:11

正文

找个合适或者善良的另一半比什么都强,谁说搞技术的情商低?他们可以靠高超的技能来弥补,照样能找到优秀的灵魂伴侣!


凌晨三点,在加州大学洛杉矶分校(UCLA)数学系大楼五楼的一个拥挤小隔间里,只有一只灯泡和一台计算机的屏幕发出光亮。克里斯·麦金利(Chris McKinlay)正在为他的博士论文《大规模数据处理和并行数值方法》跑程序。计算机发出嘎嚓声,他点击打开第二个窗口,检查了一下他在交友网站 OkCupid 的收件箱。


约有 4000 万美国人使用 Match.com、J-Date 和 e-Harmony 等交友网站寻找浪漫恋情,35 岁的麦金利就是其中之一。他身材瘦高,头发凌乱,自从九个月前跟前女友分手之后,他就一直都在寻找新恋情,但迄今为止都是徒劳无果。

男主角麦金利


OkCupid 号称可以用算法找到跟你匹配的约会对象,麦金利已经向数十位匹配度不低的女性发送了私信,但大多石沉大海。只有 6 个人跟他见过面。



OkCupid 的运作方式


2012 年 6 月的那个清晨,当麦金利的编译器在一个窗口中显示机器代码,他的交友账号在另一个窗口中默默发呆时,他突然意识到自己做错了一件事:他之前就像其他普通用户一样使用网上交友服务。这时他觉得,自己应该像一个真正的数学专家那样去寻找约会对象。


OkCupid 是哈佛大学数学专业的学生在 2004 年创建的,它最初吸引用户的地方是可以使用算法来匹配会员。会员需要做大量的多项选择题,这些问题涵盖了包括政治、宗教、家庭、爱、性、智能手机在内的方方面面。比如:


「以下哪项最有可能吸引你去看一部电影?」

「宗教或神对你的生命有多重要?」


问题总共有数千个之多。平均而言,一个用户会挑选其中 350 个问题来回答。此外用户还可以指定只接受潜在伴侣的何种回答,并用打分的方式说明这个问题对自己有多么重要:0 代表「不重要」,5 代表「必不可少」。


然后 OkCupid 的匹配引擎就会使用这些数据来计算两个人的匹配度。百分比越接近 100% 就越匹配。100% 表示你们是灵魂伴侣。



麦金利的问题


麦金利跟洛杉矶女性的匹配度简直糟糕透顶。因为 OkCupid 算法所使用的问卷问题,仅仅是双方都选择回答了的问题,而麦金利在选择回答哪些问题时比较随性。事实证明,他选择回答的这些问题很多人都不会选。


洛杉矶大约拥有 200 万女性,其中约有 8 万人使用 OkCupid 交友服务。但是查看一下麦金利的匹配列表,只有不到 100 名女性跟他的匹配度达到 90 % 以上。在交友网站上,匹配度就相当于可见度,麦金利的可见度如此之低,跟鬼魂也差不多少。


麦金利意识到,他必须增加跟他匹配度在 90 % 以上的女性人数。如果可以用统计抽样来确定哪些问题对他喜欢的那类女性来说很重要,他就可以修改自己的个人账户资料,老老实实地回答这些问题,不再去操心其他问题了。这样一来,可能适合他的每个同城女性都会出现在匹配列表里,而不适合他的女性一个都不会出现。

从中文系到数学系


对于一名数学专家来说,麦金利的经历有些不同寻常。他在波士顿市郊长大,2001 年从明德学院毕业,获得了中文学位。当年八月,他在纽约做兼职,帮助世贸中心北楼第 91 层的一家公司把中文翻译成英文。五周后 9.11 事件发生了,第一架飞机在上午 8:46 撞上世贸中心北楼。幸而麦金利那个时候不当班,正在家睡觉。


「自那之后,我问自己,我真正想做的事情是什么。」他说。一位朋友将他招进了著名的「麻省理工 21 点小组」的一个分组,在接下来的几年中,他在纽约和拉斯维加斯之间飞来飞去,靠算牌赚到了 6 万美元的年收入。


「麻省理工 21 点小组」由麻省理工学院和哈佛学生于 1979 年组建,曾多次打败拉斯维加斯和大西洋城的众多赌场。Blackjack 又称 21 点,是各地赌场最热门的牌桌项目之一。这在很大程度是因为 21 点并不完全是碰运气,而要求玩家拥有对数字的敏锐反应、娴熟的算牌技术和沉着冷静的心理。


这段经历激发了他对应用数学的兴趣,他开始攻读数学硕士学位,然后又继续读博。「数学系的学生在很多情况下都可以用到自己的专业,」麦金利说。「比如玩一些新游戏,『三张牌牌九』之类的,然后回家写一些代码,找出一个策略来打败它。」现在,他要为了爱情做同样的事情。


用假账户搜集数据


首先,麦金利需要数据。就在那天凌晨,他的论文任务继续在另一个窗口里跑的同时,他设置了 12 个 OkCupid 假账户,并编写了一个 Python 脚本来管理它们。这个脚本会搜索麦金利的目标人群(25 至 45 岁之间的异性恋和双性恋女性),访问她们的网页,并在她们的个人资料里搜集所有可用信息:种族、身高、是否吸烟、星座,所有一切。


为了获取问卷数据,他必须做更多的侦查活动。在 OkCupid 上,只有当你自己回答过某个问题时,你才可以看到别人对这个问题的回答。于是麦金利编写了 bot 机器人来随机回答每一个问题(假账户的目的不是用来吸引约会对象,所以它们是怎么回答问题的并不重要),然后把目标人群的回答搜集到自己数据库中。


麦金利满意地看着机器人忙忙碌碌。但是,在搜集了约 1000 份个人资料之后,他遇到了第一个障碍。OkCupid 采用了一个系统来防止这种数据收集活动:它可以轻而易举地发现这种连续、快速的活动。麦金利的机器人一个接一个地被禁了。

Chris McKinlay 用 Python 脚本分析 OkCupid 的调查问题,并且把女性分成七大类,比如:「Diverse」and「Mindful,」,每类都各具特点。



克服第一个障碍


他必须训练这些机器人,让它们的活动显得有人味。


麦金利找到了他的朋友山姆·托里西(Sam Torrisi)。托里西是个神经学家,最近跟麦金利进行了「技能交换」:他教麦金利音乐理论,麦金利教他高等数学。


托里西也是 OkCupid 的用户,他同意让麦金利在自己的计算机上安装间谍软件,跟踪自己使用这个网站的方式。有了这种数据,麦金利就可以模仿托里西的点击和打字速度给机器人编程了。


麦金利从家里搬来了第二台计算机,把它接到数学系的宽带上,让机器人每天 24 小时不间断地运行。三周后他就从全美各地 2 万名女性用户那里搜集了 600 万条问题和回答。


麦金利现在一头扎进了这些数据,完全把博士论文当成了副业。本来他就已经常常在小隔间里过夜,现在他几乎不回公寓了,完全搬进了这个小隔间。到了睡觉的时候,只要在办公桌上铺上薄薄的床垫,就可以躺上去了。



女性用户的七种类型


麦金利的计划要想奏效,就必须找出问卷数据中的规律——根据数据的相似性,把女性分为大致几个类型。


贝尔实验室(Bell Labs)有个名叫 K-Modes 的算法,最早是在 1998 年投入使用,用来分析病变的大豆作物,它可以把具有相似性的数据凝结在一起。麦金利对它做了一些微调,以便调整结果的粘度。然后他用这个修改后的算法来处理搜集到的问卷数据。


他调整刻度盘,发现了一个点,可以根据 2 万名女性的问题和答案,把她们分成七个在统计学上具有明显区别的类型。「当时我欣喜若狂。」他说。


他给机器人重新分派了任务,以便搜集另一个样本: 5000 名在过去一个月内登陆过 OkCupid 的洛杉矶和旧金山女性。然后他再用修改过的 K-Modes 算法处理她们的问卷数据。结果这些女性用户也以同样的方式被划分成七个类型,证实他的统计抽样方法确实有效。



目标锁定两种类型


在这一步,麦金利的任务是选择最适合自己的类型。他从每个类型中抽取了一些个人资料来查看。有一个类型太年轻,有两个类型太年长,还有一个属于基督教徒类型。

有一个类型让他很感兴趣:她们大多二十多岁,看上去特立独行,参与音乐和艺术活动。麦金利希望在这个类型中大海捞针,找到他的真爱。


实际上,还有一个类型看起来也很酷——年龄稍大的女性,是创造性工作专业人士,比如编辑、设计师。他决定两个类型都试试。于是他创建了两份个人资料,分别为两个类型做了优化。


他对这两个类型女用户的文字信息进行了挖掘,以便了解她们对什么东西感兴趣。他发现教学是一个热门话题,于是他写了一篇自我介绍,强调自己是一名数学老师。



精准营销


但是,最重要的是问卷问题。他挑选出在这两种类型中最流行的 500 个问题,诚实地填写了答案——他不想把自己未来的关系建立在计算机生成的谎言上,但是他会让计算机算出应该如何给每个问题的重要性打分。他使用一种名为「自适应提升」(adaptive boosting)的机器学习算法来计算最佳分数。


就这样,他创建了两份个人资料。一份上传了他攀岩的照片,另一份上传了他在一次演出中弹吉他的照片。


「不管未来的计划如何,眼下更吸引你的是什么?是性还是爱情?」这是 500 个流行问题中的一个。回答当然应该是「爱情」。但他按照「自适应提升」的结果,对于较为年轻的 A 组,给该问题打分为「非常重要」,而对于年龄稍大的 B 组,他则给该问题打了 5 分,即「必不可少」。


当回答完最后一个问题并给它打分之后,麦金利在 OkCupid 上进行了搜索,按照跟自己的匹配度来排列洛杉矶女性用户。第一页的女性跟他的匹配度高达 99%。他继续向下滚动页面,直到一万名洛杉矶女性之后,他仍然跟她们有 90% 以上的匹配度。



私信滚滚而来


要引起这些女性的注意,麦金利还需要做另一件事。在 OkCupid 上,每当有人浏览你的个人资料时,你就会收到提醒。所以麦金利写了一个新程序,专门去查看跟他的匹配率最高的女性用户的页面。


这个程序按照年龄顺序进行浏览:周一浏览 1000 名 41 岁女性的页面,周二浏览 1000 名 40 岁女性的页面,以此类推,一直到两个星期后,浏览 1000 名 27 岁女性的页面。在这些用户中,有大约 400 名女性也反过来查看了麦金利的个人资料。结果私信滚滚而来。


「我到现在为止还没有遇到过算牌很厉害的人,我觉得你的个人资料很有意思。」一位女性用户写道。「我想跟你打个招呼。」


「嗨,你的个人资料确实打动了我,我想跟你打个招呼。」另一位写道。「我认为我们之间有相当多的共同点,也许不是数学,但肯定有很多其他方面!」


「你真的能翻译中文吗?」还有一位问道。「我参加过一个中文培训班,但效果并不好。」



前三次约会


到了现在,需要用到数学的部分已经完成,只剩下一件事要做了:麦金利必须离开他的小隔间,去跟她们约会。


6 月 30 日,麦金利在加州大学洛杉矶分校的健身房洗了澡,开着他的破旧日产车,去赴第一个约会。希拉(Sheila)是一位网页设计师,来自 A 组,即较年轻的艺术类型。他们在回音公园的咖啡馆共进午餐。「这真是可怕,」麦金利说。「直到那一刻之前,这件事几乎都是一个学术活动。」


这次约会结束时,状况已经很明显:双个人不来电。第二天,麦金利继续赶赴第二个约会,这次是一个富有魅力的博客编辑,来自 B 组。


麦金利本打算跟她沿着回音公园的湖浪漫地散散步,但却发现挖泥船正在湖里疏浚。她爱读普鲁斯特的作品,对自己的生活感到忧伤。「这个比较负能量。」他说。


第三个约会对象也来自 B 组,名叫艾莉森(Alison)。他们在韩国城的一间酒吧见了面。她是一个学编剧的学生,肩膀上有斐波那契螺旋的纹身。麦金利喝韩国啤酒喝醉了,第二天在小隔间醒来的时候,经历了痛苦的宿醉。他在 OkCupid 上给艾莉森发了一条私信,但她没有回。



成为约会游戏中的强者


被拒绝的感觉不好受,但麦金利仍然每天都能收到 20 条私信。有了计算机算法的支持,他在约会游戏中占据了主动地位。


还记得当初,麦金利主动给别人发私信的时候,每发 3 到 5 条私信才会获得一个约会机会。但现在,别人发给他的私信,只要他看不顺眼,就一概无视。他只回应那些具有幽默感,或个人简介很有意思的女性。而且,他只需要简单地答复「你看起来真的很酷。想见面吗?」基本上就能搞定一个约会。


在去赴第 20 个约会时,他注意到了新的规律:比较年轻的 A 组女性总是有两个或两个以上的纹身,并且住在洛杉矶的东部。在 B 组,养有中型犬的女性人数格外多。


最初几次约会时,他还精心做了准备。但是,随着次数的增加,他把约会形式改成了休闲式的午餐小聚或是喝咖啡,而且常常一天赶赴两场约会。



提高约会效率


麦金利还为这场马拉松式的恋情搜寻行动制定了一套个人规则,比如不要喝酒;时间到了就结束约会,不要拖拖拉拉;不要去听音乐会或看电影。「把注意完全放在对方身上。」他说。「否则效率很低。」


在第一个月,他同时约会 A 组和 B 组女性。一个月后,他不想再约会有纹身、住在洛杉矶东部的女性了,因为不想花太多时间在路上。于是他删除了面向 A 组的个人资料。


这下子他的效率提高了,但结果还是一样。夏季即将结束,他赴约的次数超过了 55 次。每一次约会都被他尽职尽责地记录在了一个实验室笔记本上。只有三个人进行了第二次约会,只有一个人进行了第三次约会。


大多数不成功的交友者都会觉得自尊心受损。对于麦金利来说,情况更是雪上加霜。他对自己的计算思路产生了些许怀疑。



真爱现身


这时,他收到了王婷(Christine Tien Wang,音译)的私信。她 28 岁,是一名艺术系学生,支持废除监狱的活动,希望寻找一位 6 英尺(1.82 米)高,蓝眼睛,住在加州大学洛杉矶分校附近的男伴。她在这所学校攻读美术硕士学位。他们的匹配度是 91%。


两人在学校里的雕塑园见了面,然后从那里步行到了校园里的一间寿司店。他一开始就感觉跟王婷很投缘,两人谈论了书籍、艺术和音乐。


王婷承认,在给麦金利发私信之前,她对自己的个人资料进行了调整,而这时,麦金利就把自己用程序和算法寻找女伴的过程原原本本告诉了王婷。


「我觉得这有点黑暗,有点玩世不恭。」她说,「我喜欢。」


这就是麦金利跟 88 号女士的第一次约会。很快他们又进行了第二次约会,第三次约会。两个星期后,他们各自暂停了 OkCupid 上的帐号。


「我觉得,跟 OkCupid 上其他所有用户做的事情相比,我只不过多用了一点算法,活动规模更大一点,还使用了一些机器学习技术。」麦金利说。每个人都试图创建最佳版本的个人资料——他只不过是拥有一些数据来帮助他做到了这一点。



后续发展和反思


麦金利和王婷的第一次约会已经过去一年多了。现在麦金利已经拿到了数学博士学位,是一名数学老师,目前在读音乐研究生。王婷则获得了卡塔尔为期一年的艺术奖学金。她时不时回到加州探望麦金利。他们一直在 Skype 上保持联系。


在王婷看来,麦金利用 OkCupid 找女友的故事很有趣。但是,对于他们的恋情来说,数学知识和编码技能起到的仅仅是序幕作用。在恋爱关系中,关键的是两人见面之后发生的事。


「真人比个人资料复杂得多。」她说。「所以我们见面的方式可能比较肤浅,但之后发生的一切都不肤浅。那是辛苦培养得来的。」


「并不是说我们匹配度高,就会有良好的关系。」麦金利同意这个看法。「那只是一种让我们走到同一个房间的方式。我可以利用 OkCupid 来找到合适的人。」


王婷说:「你没有找到我。是我找到你了。」麦金利思考了一下,然后承认她说得对。


在一次 Skype 通话中,麦金利掏出一只钻石戒指,把它放在网络摄像头前。她答应了他的求婚。


他们不确定会在何时结婚。要找出最佳的结婚日还需要做一些研究。


最后,2017年9月10日是我国第33个教师节!

祝福所有老师节日快乐!