上海 T 沙龙 AI 与算法专场 活动总结
技术编辑：冬瓜 & Eyrefree
运营编辑：千叶知风
作为 2018 年的开箱活动，我们为大家带来了 AI 与算法专场。过去的一年里 AI 有多火热，想必大家都非常清楚，所以虽然是 Swift 沙龙，但我们仍然特意为大家准备了这么一场以 AI 为主题的分享活动。
下面是我们沙龙技术编辑童鞋对这三个 Topic 的一些总结：
自适应学习 - 机器学习在开心词场中的应用
分享嘉宾 - 王新义
王新义是沪江网数据挖掘总监，主要负责数据挖掘和机器学习技术在互联网教育中的应用，包括用户画像、推荐系统、知识图谱、自适应学习系统等。加入沪江前积累了 6 年以大数据和数据挖掘为核心的行业数据应用经验、流程及知识。熟悉 Hadoop 架构，对数据挖掘、机器学习/深度学习和大数据方向应用有较丰富的应用经验和技术积累。
教育是最传统和复杂的社会活动，如何使用 AI（机器学习）技术改造和促进人类自身学习（提高学习效率和学习效果），是互联网教育大数据及挖掘的基本问题；简单介绍 AI 技术应用沪江各个产品线（核心包括辅助学生“个性化”学习和辅助教师教学工作）的情况，重点分享：使用 DM、ML 技术结合 RM(Retention Model)、IRT(Item Response Theory)、DKT(Deep Knowledge Tracing) 等模型在开心词场中应用实践和认识。
王新义带来的一套“自适应学习”的方案。首先向我们展示了机器学习在沪江的业务各个层级中的运用情况，并用以下结构图进行总概。
自适应词汇量测试
为了照顾在场多数的前端（iOS）工程师，王老师具体介绍了一个场景，即 自适应词汇量测试。首先先分析了现在市面上的背单词软件的词汇量分析功能，其原理一般分为两种：
- 静态试卷：特点：1. 每个学生所做的题目相同；2. 在会做的容易题和不会做的难题上浪费较多时间，影响用户体验。
- 动态交互式测试：特点：1. 每个学生所做的题目不相同；2. 下一道题目根据历史做题反馈动态改变；3. 算法可以聚焦于算法不确定的题目请学生回答，而避免在肯定会做和肯定不会做的题目浪费太多时间。
显然，其动态交互式测试法师优于原始的静态试卷法，于是我们引入一种评估流程：算法 → 单词 → 用户作答。这里需要套用一种算法，根据用户的做题记录评估其能力后反馈出一个新的单词让用户来作答，然后根据作答情况，继续通过算法来评估能力，并持续这个循环。再一定量的循环后，我们并可以预估用户的词汇量。这个词汇量的关键是用户的能力情况，而这个值也是与单词难度可比。
Item Response Theory - IRT 教学模型
为了评估用户的能力情况并使其量化，我们引入了 IRT 模型，来解决问题。IRT 是用来分析考试成绩或问卷调查数据的数学模型，这些模型的目标是来确定其潜在特征(Latent Trait)是否可以通过测试题反映出来，以及测试题和被测者之间的互动关系，下面给出其数学模型。wikipedia
$$
\begin{aligned}
P(\theta)=c+(1-c)\int_{-\infty}{a(\theta-b)}\frac{e{-t2}}{2}\sqrt{2\pi}dt
\end{aligned}
$$
这个熟悉社模型称为 3PN。为了计算方便，可以用 3PL 模型来替代，运用在数值处理：
$$
\begin{aligned}
P(\theta)=c+\frac{1-c}{1+e{-Da(\theta-b)}}
\end{aligned}
$$
其中，D 为常数 1.7。a 叫做区分度参数(Item Discrimination)，a / 4 的值是该曲线拐点处的斜率，即斜率最大值。b 叫做难度参数(Item Difficulty)，也是在图像上最陡处所对应的 $\theta$ 值。当 b 增加时，曲线会向右移动，即使此时 $\theta$ 保持不变，但是答题的正确率下降，说明题目的难度增加，反之降低。c 一般称作猜测参数(Guessing Parameter)，当用户的能力值很低时，但他做对题目的概率 c ，即为猜测的能力。
当前场景下，我们套用 IRT 模型即可转化表达：
$$
\begin{aligned}
P(A|b, c)=\frac{1}{1+e{-1.4 * (c - b)}}
\end{aligned}
$$
其中 A 为答对题目事件，B 和 C 分别表示单词难度和人的能力量化值。为了评估人的能力，我们引入极大似然估计。
知识追踪 DKT
自适应学习是现在教育科技领域谈得比较多的一个概念，它的核心问题可以用一句话概括，即通过个性化的学习路径规划，提高学生的学习效率。为了对学习序列建模，并评估学生各个时刻的能力，沪江引入了 Deep Knowledge Tracing（DKT）模型，这个模型是由 Stanford 大学的 Piech Chris 等人在 NIPS 2015发表的，其本质是一个 Seq2Seq 的 RNN 模型。
以下是该模型的结构图：
x 代表问题是否作对的编码，y 代表对于所有问题做对的概率，h 代表学生隐含的知识水平。再来看该模型的层次结构：
假设题库中总共有 4 道题，则输出层的数量为 4，对应各题回答正确的概率。另外我们已知这些题目的结果数目，所以输入层的节点数就可以用 $x{n}=y{n}\times a_{n}$ 来求得。进而，我们将输入层全部链接到 RNN 的隐层，接着建立隐层到输出层的全连接，最后使用 Sigmoid 函数作为激活函数，就完成了基础的 DKT 模型。在 PPT 中展示了很多训练集的训练结果，这里是[连接]()。
简单了解机器学习思想
王老师在讲述完机器学习在沪江业务中的运用后，又简明地介绍了什么是机器学习的思想。他在现场出了这么一个题目
求出满足这个式子的所有可能性：xxx * x - xxxx = 0。并且其中每个 x 代表一位数，切满足这八位数分别是 1 ~ 8。例如有这么一组满足的算式 453 * 6 - 2718 = 0。
用传统的计算机算法思维来解决这个问题，我们直接使用全排列对每一种情况进行枚举即可实现，全排列算法复杂度为 O(n!)。
# 全排列解法 1：使用多层嵌套遍历实现
for i in range(1,9):
for j in range(1,9):
for k in range(1,9):
for m in range(1,9):
ss=str(i)+str(j)+str(k)+str(m)+str((i*100+j*10+k)*m)
if len(ss)==8 and len(set(list(ss)))==8 and '0' not in ss and '9' not in ss :
print(ss[0:3]+'*'+ss[3]+'='+ss[4:])
# 全排列解法 2：itertools 包中已经有 permutations 全排列方法
from itertools import permutations
print([''.join(x[:3])+'*'+''.join(x[3])+'='+''.join(x[4:]) for x in list(permutations('12345678', 8)) if int(''.join(x[:3]))*int(x[3])==int(''.join(x[4:]))])
for x in list(permutations('12345678',8)):
if int(''.join(x[:3]))*int(x[3])==int(''.join(x[4:])):
print(x)
print(''.join(x[:3])+'*'+''.join(x[3])+'-'+''.join(x[4:])+'='+str(int(''.join(x[:3]))*int(x[3])-int(''.join(x[4:]))))
如果我们从机器学习的角度来考虑整个问题，首先需要定义一个损失函数，用来评估模型的预测值和真实值的不一致程度，它是一个非负实值函数，如果损失函数越小，则模型的鲁棒性越好。这里我们的损失函数直接用 xxx * x - xxxx 的绝对值即可描述。
第二，梯度下降函数。由于没有一个可靠的下降方式，所以这里我们采用 SGD 随机梯度下降方式，在取值范围内做随机取值来实现梯度下降。
x=[1,2,3,4,5,6,7,8]
ss=train(x)
ss
x
#%%
import random
def lose(x): # 损失函数
return abs((int(x[0])*100+int(x[1])*10+int(x[2]))*int(x[3])-(int(x[4])*1000+int(x[5])*100+int(x[6])*10+int(x[7])))
def swap(x,i,j): #
xx=x.copy()
tmp=xx[i]
xx[i]=xx[j]
xx[j]=tmp
return xx
def sgd(x): # 梯度下降
data_dict={}
for i in range(0,7):
for j in range(i+1,8):
x_tmp=swap(x,i,j)
lose_v_tmp=lose(x_tmp)
data_dict[''.join(x_tmp)]=lose_v_tmp
dd=sorted(data_dict.items(),key=lambda item:item[1])
#print(dd[1][0])
return list(dd[random.randint(0, 10)][0])
def train(x):
while lose(x)>0 :
x=sgd(x)
print(x,'lose value:',lose(x))
return x
x=['1','2','3','4','5','6','7','8']
ss=train(x)
print()
print(ss)
在随机梯度中输出的损失值，会发现会有抖动，不会按照正确的方向持续下降，这个波动特点会使得优化的方向从当前具备极小值点跳跃到另一个更好的局部极小值点，对于非凸函数，最终收敛域一个较好的局部极值点，甚至是全局极值点。
在 SGD 中，由于波动，因此迭代次数很多，收敛速度慢。不过最终会和全量梯度下降算法一样，具有相同的收敛性，即凸函数收敛于全局极值点，非凸损失函数收敛于局部极值点。
为了优化其收敛性，王老师还提供了一种差分进化算法(Differential Evolution)方案，详细代码转至 Github 进行学习，这里不做赘述。
初探地图类 App 后端那些事：空间索引算法
分享嘉宾 - 冰霜
冰霜，了解 iOS 开发，略懂 JavaScript, Go, C, C++。GitHub：@halfrost，微博：@halfrost。
霜神主要讲解 2 个常用的空间索引算法，Redis 中的 geohash 和 mongodb 中的 Google S2。涉及到四叉树和空间填充曲线相关的知识。这是一场物理知识和数学知识融汇贯通的分享。
机器学习介绍
分享嘉宾 - 梅元刚
梅元刚是中科院硕士，擅长图像处理和机器学习，三星 Gear 360 全景视频作者，金山云美颜作者，金山云 AI 画质增强核心作者。由于之前种种原因接触了 Swift 并接触了 iOS 开发，本场沙龙，他以移动开发者的角度，带着我们简单了解了机器学习。
首先他跟我们看了三个总结：
机器学习的基本分类
监督学习就是标明一些数据是对的，另一些数据是错的，然后让程序预测，新的数据是对的还是错的。所以说，有监督学习，必须是有标签的。
无监督学习，顾名思义，就是不对数据进行标明，让机器自动去判断，哪些数据比较像，归到一类等等。
强化学习或者叫做加强学习，是指什么呢？在前边的监督学习中，机器每次做出预测，都会知道结果对不对，但是在这里却不行，每次做出预测不会得到对或者不对的结果，只会收到看似没有半毛钱关系的反馈。所以强化学习不是依赖数据的标签进行学习，而是依赖自己积累的反馈。强化学习适合学习交互过程，比如下围棋（AlphaGo的成功就是强化学习的力量）。
卷积神经网络
如下图所示，展示了一个33的卷积核在55的图像上做卷积的过程。每个卷积都是一种特征提取方式，就像一个筛子，将图像中符合条件（激活值越大越符合条件）的部分筛选出来。不同的卷积核能够提取到图像中的不同特征，这里有 在线 demo
深度学习图像应用
我在此不是要说明作者是怎么做到这些的，而是让大家看一些令人难以置信的结果。
艺术类
TYLE2PAINTS：强大的为线稿上色的 AI
推荐理由：新一代的强大线稿上色 AI，可根据用户上传的自定义色彩给线稿进行上色。项目提供了在线使用网站，十分方便使用。
CycleGAN：[生成对抗网络图像处理工具](hhttps://github.com/junyanz/pytorch-CycleGAN-and-pix2pix)
这个工具功能十分强大，不仅可将绘画作品“还原”成照片（可理解为是一个 “反滤镜”），还能将夏天转换成冬天，或将普通的马转化成斑马。
make ASCII Art by Deep Learning
识别类
maskrcnn
使用迁移学习做动物脸部识别
牛其实不愿意看到人类的，他们会视人类为捕食者，因此养牛场的工作人员会给牛群带来紧张情绪。那么我们就把农场的管理交给人工智能吧。
人工智能通过农场的摄像装置获得牛脸以及身体状况的照片，进而通过深度学习对牛的情绪和健康状况进行分析，然后帮助农场主判断出那些牛生病了，生了什么病，那些牛没有吃饱，甚至那些牛到了发情期。除了摄像装置对牛进行“牛脸”识别，还可以配合上可穿戴的智能设备，这会让农场主更好的管理农场。这些数据上传到云服务器上，用自己开发的算法通过机器学习让这些海量的原始数据变成直观的图表和信息发送到客户那里。这些信息包括奶牛的健康分析、发情期探测和预测、喂养状况、位置服务等。
图像增强类
DeblurGAN
图像超分辨率
RAISR 这项技术能利用机器学习，把低分辨率图片转为高分辨率图片。它的效果能达到甚至超过现在的超分辨率解决方案，同时速度提升大约 10 至 100 倍，且能够在普通的移动设备上运行。
Face2Face：扮演特朗普
斯坦福大学的一个小组做了一款名为Face2Face的应用，这套系统能够利用人脸捕捉，让你在视频里实时扮演另一个人，简单来讲，就是可以把你的面部表情实时移植到视频里正在发表演讲的美国总统身上。
增强学习
MIT最新课程 ——九小时速成深度学习&自动驾驶汽车
a minitaur duck
OpenAI，所训练的一款人工智能算法在著名的电子竞技游戏Dota2国际邀请赛The International中，参与了1V1比赛环节，并压倒性的击败了顶级电子竞技选手Dendi。
反复攻破和修补自己的防火墙
Google大脑的研究团队创建了两个深度学习网络用于安全工具开发，他们让其中一个不断创造自己的加密算法，然后让另一个网络去尽力攻破它。在两套系统的反复缠斗后，第一个系统已经能生成非常优秀的安全加密算法。
AI可以自己编程
DeepCoder使用了一种叫做程序合成(program synthesis)的技术，其运行原理与程序员所做的事情差不多，就是从存在的软件中获取已知的代码段，并将它们拼接到一起执行新的程序。只要赋予DeepCoder中每个片段对应的输入和输出，程序就可以“学习”到哪些代码是我们所需要的。
iOS实现
在WWDC 2017上，苹果首次公布了机器学习方面的动作。iOS系统早已支持Machine Learning 和 Computer Vision ，但这次苹果提供了更合理，容易上手的API，让那些对基础理论知识一窍不通的门外汉也能玩转高大上的前沿科技。
此后，苹果公司宣布了可以在设备上应用机器学习的两种新技术：Core ML和MPS graph API（Core ML 构建于MPS之上，MPS更底层）。
注意：运行demo需要使用 Xcode 9 和运行 iOS 11 的设备
iOS10的MPS框架已实现支持GPU的快速CNN计算
支持在iOS设备上运行卷积神经网络（CNN）的API已经加入到了 iOS 10 的 MPS （MetalPerformanceShaders）框架中。我们现在可以利用GPU实现快速的CNN计算，换句话说，最先进的深度学习技术已经可以在单机上离线独立运行。
需要传入 MPSCNNConvolutionDataSource 对象。该对象负责加载权重。
我们开始写数据输入类。由于我们的层都非常相似，所以我们DataSource将为所有层使用相同的类 - 但是每个层都有自己的实例。代码如下所示：
class DataSourceCNN: NSObject, MPSCNNConvolutionDataSource {
let wName: String
let bName: String
let kernelWidth: Int
let kernelHeight: Int
let inputFeatureChannels: Int
let outputFeatureChannels: Int
let useLeaky: Bool
let stride:Int
let paramA:Float
var wData: Data?
var bData: Data?
init(_ wName: String, _ bName: String, _ kernelWidth: Int, _ kernelHeight: Int,
_ inputFeatureChannels: Int, _ outputFeatureChannels: Int,
useLeaky: Bool = true, stride: Int = 1,paramA:Float=0.0) {
self.wName = wName
self.bName = bName
self.kernelWidth = kernelWidth
self.kernelHeight = kernelHeight
self.inputFeatureChannels = inputFeatureChannels
self.outputFeatureChannels = outputFeatureChannels
self.useLeaky = useLeaky
self.stride=stride
self.paramA=paramA
}
func descriptor() -> MPSCNNConvolutionDescriptor {
let desc = MPSCNNConvolutionDescriptor(kernelWidth: kernelWidth,
kernelHeight: kernelHeight,
inputFeatureChannels: inputFeatureChannels,
outputFeatureChannels: outputFeatureChannels)
if useLeaky {
desc.setNeuronType(.reLU, parameterA: 0.0, parameterB: 0.0)
} else {
desc.setNeuronType(.none, parameterA: 0.0, parameterB: 0.0)
}
desc.strideInPixelsX=stride
desc.strideInPixelsY=stride
return desc
}
func weights() -> UnsafeMutableRawPointer {
let ptr=UnsafeMutableRawPointer(mutating: (wData! as NSData).bytes)
return ptr
}
func biasTerms() -> UnsafeMutablePointer<Float>? {
return nil
}
func load() -> Bool {
if let url = Bundle.main.url(forResource: name, withExtension: "bin") {
do {
data = try Data(contentsOf: url)
return true
} catch {
print("Error: could not load \(url): \(error)")
}
}
return false
}
func purge() {
wData = nil
bData=nil
}
func label() -> String? {
return wName
}
func dataType() -> MPSDataType {
return .float32
}
}
该 MPSCNNConvolutionDataSource 需要具有 load() 和 purge() 函数。在这里，我们只需将上一步导出的二进制文件（例如，conv1.bin）加载到Data对象中即可。
要获取此层的权重，该 weights() 函数将返回一个指向此 Data 对象的第一个元素的指针。假设我们的层没有偏置，所以 biasTerms() 可以返回 nil.
现在，数据源被整理出来，我们可以开始构建图：
let inputImage = MPSNNImageNode(handle: nil)
let scale = MPSNNLanczosScaleNode(source: inputImage,
outputSize: MTLSize(width: 416, height: 416, depth: 3))
let conv1 = MPSCNNConvolutionNode(source: scale.resultImage,
weights: DataSource("conv1", 3, 3, 3, 16))
let pool1 = MPSCNNPoolingMaxNode(source: conv1.resultImage, filterSize: 2)
let conv2 = MPSCNNConvolutionNode(source: pool1.resultImage,
weights: DataSource("conv2", 3, 3, 16, 32))
let pool2 = MPSCNNPoolingMaxNode(source: conv2.resultImage, filterSize: 2)
// ... and so on ...
guard let graph = MPSNNGraph(device: device,
resultImage: conv9.resultImage) else {
fatalError("Error: could not initialize graph")
}
我们首先为输入图像声明一个节点，并将一个将该输入图像缩放到 416×416。接下来每个层都使用 source 参数连接到前一个层。所以 scale 节点连接到 inputImage，conv1 被连接到 scale.resultImage，等等。graph 本身是一个 MPSNNGraph 对象，并连接到网络中最后一层的输出 conv9。
总结
Core ML 大大降低了开发者在苹果设备上使用机器学习技术的门槛。苹果制定了自己的模型格式，这样当前主流机器学习模型通过转换工具都能运用到 APP 当中。如果你是移动开发者，又看好机器学习，为什么不试一试呢？如果说前几年是智能机时代，有可能未来几年就是智能应用时代了。
深度学习局限性
如果问题不能纯粹地转化为一个映射问题时，深度学习的执行力就存在局限性。(由于深度学习更专注于一些基于数据驱动的映射问题，而事实上无论在视觉领域还是在人工智能领域，很多问题并不是映射问题。)
比如，深度学习解决问题时，是通过构建神经网络架构实现的，这一过程过度依赖样本。同时，我们又不清楚深度学习具体如何解决问题、如何解释解决问题的过程。因此，深度学习有一些和统计学习方法相同的顽疾：容易被一些方法陷害，比如灌入脏数据。从而使得深度学习做得不好。
例如，做一个巡逻机器人放在小区里。开始时，业主和物业觉得这个巡逻机器人有趣，但后来觉得它没用，不能解决他们的问题。他们就想这东西能干什么，然后提出了一个痛点需求:小区里面猫屎、狗屎，如果没有被及时清理，影响环境且容易被踩到。机器人能不能通过巡逻，找到狗屎，反馈给物业，让保洁快速清理掉？
以这样一个问题为例，如果我们用传统的非深度学习的方法去做的话，可能要搜集几百、几千张狗屎的照片，然后人工地去搜集它的颜色、形状、以及纹理特征，然后去调节分类器。我们过去做人脸检测、行人检测，车辆检测都是这么做的，可能需要十几年的时间才调出来一个还不错的模型。但是深度学习模型一两个月就可以解决这个问题：我们先用平台去收集上万张狗屎的照片，也许我们再花上一两个星期的时间，调调模型然后交给机器去训练就好了，大概一两个月也许就可以部署这样一个系统。
对于大数据来说这够了，但和人相比还是不够。如果一个小孩踩了一次狗屎，基本上就不会踩第二次，也就意味着他基本上用一个样本，几秒钟的时间就学完了狗屎检测的问题。
深度学习缺乏常识
比如说杯子不会悬在空中，它一定是在桌面上；狗屎一般不会在墙上，因为狗一般不会跑到墙上去拉屎，这些“常识”使得人在不需要很多样本的情况下，很精准的解决问题。比如行人检测，人不会去树上做检测，那很奇怪。因为人知道，行人一般不会在树上。比如汽车检测，人不会在天上做汽车检测。因为人知道，天上不会飞汽车。人其实都有“常识”，它使得人并不需要很多样本，就可以做很准确的判断。
深度学习需要大量数据
自动驾驶其实大家知道，真正测试一个自动驾驶系统的行为，不是靠这些 normal traffic（常规交通），而是靠什么呢？靠很多边界的case，靠很多不正常的 traffic data，比如小孩子突然走到马路，你可能一辈子很难碰到几个，但是你就是要拿这些情况去测试。但是你不可能用真实的数据，你不可能让小孩真的去横闯马路，然后去测试你这个自动驾驶的系统，所以一定是用仿真的系统，去产生的很多的这种配制，然后去训练去测试。这个是自动驾驶必须要走的路，那这个里面实际上就是用大量的数据，但是这个数据是举一反三虚拟想象出来的。所以未来的话，有可能想象的数据会填补我们对数据的缺失所带来的掣肘，然后使你实际上effectively（有效的）是用小数据，但是你从 generate 很多大量的数据，使得你这个系统能够不断的进化，去变得越来越聪明。
强化学习反馈时延很久
Alphago zero，你会发现它其实一定意义上来讲没有数据，因为它是完全从零的状态开始博弈，它完全是左右博弈，去虚拟下无数盘棋。整个这个程序是用的深度学习加强化学习，在不断的从虚拟的对决里面去学习很多的经验，最后达到一个很强大的能力，会接近棋盘真理。 zero data learning ，它是没有用任何人类历史的棋盘对决的数据，但是它又是大数据，为什么呢？因为它用很多虚拟的数据来学习，所以就是说，你就发现想象力使你在 zero data learning 和 data learning 之间好像有个虫洞效应。实际上它们两个之间距离是非常短的，不是我们想象的差别那么大。
总结
当然我们也提供了 Slides 和录屏，感兴趣的同学可以通过下面的链接获取：
这次的沙龙可以说是非常干货的了，想了解 AI 和算法的小伙伴相信能从三位嘉宾的分享中收获不少哦。
T 沙龙是一个非盈利的线下沙龙组织，我们会定期举办 iOS 开发相关的线下沙龙活动，目的是促进 iOS 开发技术人员的线下面对面交流。沙龙通过采用闭门邀请制的方式，使参加者的技术水平和学习兴趣尽可能地接近，促进大家进行真正的交流。
最后感谢本次沙龙的场地提供 皑沐(上海)文化传媒。