本年度的主要数据科学会议之一今天在伦敦开始。我将尽力迅速谈谈有趣的事情。
最初的结果很紧张：同一天早上，耶和华见证人在同一个中心举行了一次群众大会，所以要找到交警登记处并不容易，当我终于找到它时，电话线长150-200米。 然而，经过约20分钟的等待，他获得了梦badge以求的徽章并上了大师班。
数据分析的隐私
第一个研讨会致力于维护数据分析的隐私。 刚开始的时候，我来晚了，但显然，我并没有损失太多，他们谈论了隐私的重要性，以及攻击者如何滥用所披露的私人信息。 顺便说一句，来自Google，LinkedIn和Apple的相当受人尊敬的人告诉我们。 由于大师班给人们留下了非常积极的印象，幻灯片都可以
在此处找到 。
事实证明，“
差异隐私”的概念已经存在了很长时间，其思想是添加噪音，使建立真正的个人价值变得困难，但保留了恢复公共分布的能力。 实际上，有两个参数：
e披露数据有多困难，
d答案有多失真。
最初的概念表明，分析人员与数据之间存在某种中间联系，即“策展人”，由他来处理所有请求并生成响应，从而使噪声掩盖了私有数据。 实际上，通常使用“本地差异隐私”模型，其中用户数据保留在用户设备（例如，移动电话或PC）上，但是，当响应开发人员请求时，应用程序会从个人设备发送数据包，而该数据包不允许查明确切的内容。该特定用户回答。 虽然，当组合来自大量用户的响应时，您可以高精度地恢复整体图像。
一个很好的例子是“您流产了”吗？ 如果您“在额头上”进行调查，那么没人会说实话。 但是，如果您按以下方式组织调查：“扔硬币，如果有鹰，然后再次扔给鹰，对鹰说”是”，对尾巴说“否”，否则请回答真相”，在维护个人隐私的同时，很容易恢复真实分布。 这个想法的发展是收集敏感数据
Google RAPPOR （随机化隐私保护顺序报告）的机制，该数据用于收集有关Chrome及其分支的使用情况的数据。
开源Chrome浏览器发布后，立即出现了相当多的人，他们想要使用覆盖了首页，搜索引擎，自己的广告骰子的浏览器来制作自己的浏览器。 自然，用户和Google对此并不热心。 人们通常可以理解采取进一步的措施：找出最常见的替代品并进行行政管理，但出人意料的是... Chrome的隐私权政策不允许Google收集和收集有关设置用户主页和搜索引擎的信息：(
为了克服此限制并创建了RAPPOR，其工作原理如下：
- 主页上的数据记录在一个约128位的小布隆过滤器中。
- 永久白噪声被添加到该布隆过滤器。 永久=与此用户相同，在不节省噪音的情况下，多个请求可能会泄露用户数据。
- 除了恒定的噪声之外，还会叠加为每个请求生成的各个噪声。
- 产生的位向量被发送到Google，在此处开始对整体图片进行解密。
- 首先，通过统计方法，我们从整体图像中减去噪声的影响。
- 接下来，我们构建候选位向量（原则上最受欢迎的网站/搜索引擎）。
- 使用获得的向量作为基础，我们构建了线性回归以重建图片。
- 将线性回归与LASSO结合以抑制无关的候选对象。
从原理上讲，过滤器的结构如下所示：
事实证明，实施RAPPOR的经验非常积极，在其帮助下收集的私人统计数据的数量正在迅速增长。 在主要的成功因素中，作者确定：
- 模型的简洁性和清晰度。
- 公开性和代码文档。
- 最终图形上存在误差边界。
但是，这种方法有一个很大的局限性：必须具有用于解密的候选答案列表（这就是O-Ordinal的原因）。 当苹果公司开始收集有关短信中使用的单词和表情符号的统计信息时，很明显，这种方法不是很好。 结果，在WDC-2016大会上，iOS宣布的最重要的新功能之一就是增加了差异隐私。 草图结构与增加的噪声的组合也被用作基础，但是，必须解决许多技术问题：
- 客户端（电话）应该能够在合理的时间内建立并存储此答案。
- 此外，此响应应打包在大小有限的网络消息中。
- 在苹果方面，所有这些都应该在合理的时间内被整合。
结果，我们提出了一种使用
count-min-sketch编码单词的方案，然后我们随机选择了一个哈希函数的响应（但固定了用户/单词对的选择），使用
Hadamard变换转换了向量并将其仅发送到服务器所选哈希函数的一个有效“位”。
为了在服务器上恢复结果，还必须检查候选假设。 但是，事实证明，字典的大小很大，即使对于集群也太复杂了。 必须以某种方式启发性地选择最有希望的搜索领域。 使用双字母组作为起点，然后可以从中组装镶嵌图的实验是失败的-所有双字母组都同样受欢迎。 双字+单词哈希方法解决了该问题，但导致隐私受到侵犯。 结果，我们选择了前缀树：先收集单词的初始部分，然后再收集整个单词的统计信息。
但是，研究界对Apple使用的隐私算法的分析表明，仍然
可以通过长期统计
来损害隐私。
LinkedIn在研究用户薪资分配方面处于更加困难的境地。 事实是，当我们进行大量测量时，差分隐私效果很好，否则无法可靠地减去噪声。 在薪水调查中，报告数量有限，LinkedIn决定采取不同的方法：将技术密码学和网络安全工具与
k-匿名性概念相结合：如果将用户数据提交到包含k个具有相同输入属性的答案的数据包中，则用户数据将被充分掩盖（例如，位置和职业）仅在目标变量（工资）上有所不同。
结果，构建了一个复杂的传送带，其中，不同的服务将彼此之间的数据片段相互传输，并不断进行加密，因此一台机器无法完全打开它们。 结果，将用户按属性划分为同类群组，并且当同类群组达到最小大小时，其统计信息将进入HDFS进行分析。
时间戳值得特别注意：它也需要匿名，否则您可以找出谁的答案是通话记录。 但是我不想完全浪费时间，因为跟随动态变化很有趣。 结果，我们决定为构建同类群组的属性添加时间戳，并在其中平均其值。
结果是一个有趣的高级功能和一些有趣的开放式问题：
GDPR建议，应要求，我们应该能够删除所有用户数据，但是我们试图将其隐藏，以便现在无法找到它的数据。 拥有大量不同切片/同类群组上的数据，您可以隔离匹配并扩展开放属性列表
此方法适用于大数据，但不适用于连续数据。 实践表明，简单地采样数据不是一个好主意，但是Microsoft在NIPS2017上
提出了有关如何使用它
的解决方案。 不幸的是，细节没有时间透露。
大图分析
关于大图分析的第二次研讨会于下午开始。 尽管事实上他也是Google领导的领导者，并且对他寄予了更多期望，但他却不那么喜欢他-他们谈论了自己的封闭技术，然后陷入了平庸主义和通俗哲学，然后陷入了琐碎的细节中，甚至没有时间来制定任务。 尽管如此，我还是能够抓住一些有趣的方面。 幻灯片可以在
这里找到。
首先，我喜欢称为“
自我网络聚类”的方案，我认为有可能在其基础上构建有趣的解决方案。 这个想法很简单：
- 我们从特定用户BUT减去他本人的角度考虑本地图。
- 我们对该图进行聚类。
- 接下来，我们“克隆”用户的顶部，将实例添加到每个集群中，并且不通过边缘将它们彼此连接。
在类似的变换图中，可以更轻松地解决许多问题，并且排名算法的工作更简洁。 例如，以平衡的方式对这样的图进行划分要容易得多，并且在朋友的推荐中排名时，桥节点的噪点要少得多。 为此，ENC的朋友们的建议得到了考虑/推广。
但总的来说，ENC只是一个例子，在Google，整个部门都致力于开发图形算法，并将其作为库提供给其他部门。 该库的声明功能令人印象深刻：SNA的理想库，但所有内容均已关闭。 在最佳情况下，可以尝试用文章来复制单个块。 据称，该库在Google内部具有数百种实现，包括在具有超过一万亿条边的图形上。
然后大约有20分钟的MapReduce模型的促销，好像我们不知道它有多酷。 之后，他们证明了使用随机可组合核心集模型可以（大约）解决许多复杂问题。 主要思想是将有关边缘的数据随机分散到N个节点中，然后将它们拉到内存中，并在本地解决问题，然后将解决方案的结果传输到中央机器并进行汇总。 有人认为，通过这种方法，您可以廉价地获得许多问题的良好近似值：连接组件，最小生成林，最大匹配，最大覆盖范围等。 在某些情况下，mapper和reduce可以同时解决相同的问题，但它们可能略有不同。 一个很好的例子，说明如何巧妙地命名一个简单的解决方案，以使人们相信它。
然后有一个关于我要在这里做什么的对话：平衡图分区。 即 如何将图切成N个部分，以使这些部分的大小大致相等，并且该部分内部的键数明显大于外部键的数。 如果您能够很好地解决此类问题，那么许多算法将变得更容易，甚至A / B测试也可以更有效地运行，并补偿病毒效应。 但是这个故事有点令人失望，一切看起来都像个“侏儒计画”：根据层次的仿射聚类分配数字，移动，增加不平衡。 没有详细信息。 关于KDD的相关信息，稍后将有一份单独的报告，我将尝试解决。 另外还有一篇
博客文章 。
尽管如此，他们还是与一些竞争对手进行了比较，其中一些竞争对手是开放的：
Spinner ，FB的
UB13 ，Microsoft的
Fennel ，
Metis 。 您也可以查看它们。
然后我们讨论了一些技术细节。 他们使用几种范例来处理图形：
- 在Flume顶部的MapReduce。 我不知道这是有可能的-Flume在互联网上写的不是用来收集数据的，而不是用来分析数据的。 我认为这是Google内部的变态。 UPD：我发现这确实是Google的内部产品，与Apache Flume无关，云中有一些名为dataflow的eratz
- MapReduce +分布式哈希表。 他们说，这有助于显着减少MP轮回合的次数，但是在Internet上，关于这种技术的文章很少，例如， 此处
- 普雷格尔-他们说他很快就会死。
- 异步消息传递是最酷，最快和最有前途的。
ASYMP的概念与Pregel非常相似：
- 节点是分布式的，保持其状态并可以向邻居发送消息；
- 在具有优先级，发送内容的机器上建立队列（顺序可能与添加顺序不同）；
- 收到消息后，节点可能会更改状态，也可能不会更改状态；更改时，我们会向邻居发送消息；
- 当所有队列为空时完成。
例如，当搜索连接的分量时，我们使用随机权重U [0,1]初始化所有顶点，此后我们开始至少彼此发送邻居。 因此，在从邻居那里收到最低要求之后，我们正在为他们寻找最低要求等，直到最低要求稳定为止。 他们指出了优化的重要点：折叠来自一个节点的消息（这是转弯），只剩下最后一个。 他们还谈到在保持节点状态的同时从故障中恢复是多么容易。
他们说他们建立了非常快速的算法而没有问题，这似乎是事实-这个概念简单而合理。 有
出版物 。
作为结果，得出的结论出现了：走在关于封闭技术的悲惨故事，但一些有用的位开窍。