“大数据与机器智能”版本间的差异

来自iCenter Wiki
跳转至： 导航、 搜索
（→‎问答QA）
（→‎问答QA）
第412行： 第412行：
 
*在“学习“栏加入一条wiki百科的网址。例如“https://en.wikipedia.org/wiki/University_of_Michigan”
 
*在“学习“栏加入一条wiki百科的网址。例如“https://en.wikipedia.org/wiki/University_of_Michigan”
 
*转到“推断“栏，询问与添加百科信息有关的问题。例如“密歇根大学位于哪里？”
 
*转到“推断“栏，询问与添加百科信息有关的问题。例如“密歇根大学位于哪里？”
 +
<gallery>
 +
文件:Infer2.png
 +
</gallery>
 +
(3)数据库信息类
 +
例：
 +
谁是中国的最后一位皇帝?
 +
谁发现了南极点?
 +
谁发明了电话?
 +
哪位希腊数学发发展了几何学？
 +
慕尼黑协定在何时签订?
 +
泰森在何时夺冠
 +
尼罗河位于什么地方？
 +
 +
2.依赖项介绍
 +
（1）OpenEphyra：OpenEphyra 是一个使用 Java 开发的模块化、可扩展的开源问答系统。它从网络和其他资源检索自然语言问题的答案。开发者能基于这项项目开发新的问答系统，而不用关心端到端系统。
 +
 +
（2）Indri：提供目前最先进的文本搜索，支持多种结构的询问语言。可在一台机器上实现对五千万个文档的文本收集；分配搜索后，量级能再增加一倍。支持linux，solaris，windows和mac os等多个系统。
 +
（3）MongoDB：可以应用于各种规模的企业、各个行业以及各类应用程序的开源数据库。它为开发人员 提供了传统数据库的功能：二级索引，完整的查询系统以及严格一致性等等。
 +
（4）Apache Thrift：提供标量化跨语言开发服务。由一个软件栈和代码生成引擎组成，提供在C++, Java, Python, PHP, Ruby等多种语言间无缝高效转换的服务。
  
 
====手写数字识别DIG====
 
====手写数字识别DIG====

2016年10月25日 (二) 19:19的版本

版权申明

CC BY-NC-SA

教学团队

互联网+实验室 iNetLab

陈震 马晓东 章屹松 王蓓蓓 高英

助教：郑文勋 李辰星

协同开发

iCenter-cloud iCenter-cloud

Gitlab GitLab

教学目标

以完成一种以大数据为基础的智能系统的原型开发为目标，在实践中运用大数据智能理论与技术。团队成员学习大数据系统与机器智能的理论知识和专业技能，完成项目团队结构设计和原型开发的实践环节，全面提高学生的技术实践能力。

课程内容

技术浅论

技术本质

  • 多维多角度：工具论/人文关怀/社会抱负/技术社会
  • 客观上（大众）
    • “受害与受益” （两面性）
金融理财便捷
金融电信诈骗
    • 受益方
技术改变的领导者（“quick money”）
受惠的人群（便捷性）
    • 受害方
技术改变被动接受的人
被技术改变淘汰的人
  • 主观上（单个人）
取决于个人立场、价值观、经历等等

技术泡沫

  • 市场宣传和预期炒作，以及一些传媒的洗脑性的报道等的原因，导致概念混乱。
  • 需要找到技术的本质（涉及认识论）
  • 科学思维就是防止被洗脑，无脑思考。
  • 研究思路：规范模式和实证模式
    • 事实陈述的时候，一定要找到论点以及论据，以及判断论点是否统帅论据，论据是否支持论点。
    • 实践与操作获得体验，而非感觉与愿望。

大数据索引

索引是加快查找的数据结构(data structure)，主要有树Tree，哈希表和倒排索引。

Readings:

  1. Thomas H. Cormen, introduction to algorithms, third edition, MIT press, 2009.
  2. Tardos, Eva, and Jon Kleinberg. "Algorithm Design." (2006).

Hash Table

布隆过滤器（BloomFilter）

BloomFilter

java-bloomfilter

Bloofi


Readings:

  1. B. H. Bloom,Space/time trade-offs in hash coding with allowable errors, Commun. ACM, Volume 13 Issue 7, Pages 422-426, July 1970.
  2. Crainiceanu, Adina, and Daniel Lemire. "Bloofi: Multidimensional Bloom Filters." Information Systems 54 (2015): 311-324.

Tree Index

B-tree B-tree

K-D tree kd-tree

R-tree R-tree

R+ tree R+ tree


Readings:

  1. Guttman, Antonin. R-trees: a dynamic index structure for spatial searching. Vol. 14, no. 2. ACM, 1984.
  2. Sellis, Timos, Nick Roussopoulos, and Christos Faloutsos. "The R+-Tree: A Dynamic Index for Multi-Dimensional Objects." VLDB, 1987.

Inverted Index

倒排索引 (Inverted Index)是搜索引擎使用的数据结构。 倒排索引将关键字(keyword)映射到文档(document)，在信息检索（Information Retrieval）中发挥重要作用。

在倒排索引中，每个关键词对应一个倒排链表（inverted list），记录了该关键词出现的所有文档的编号。

  1. 倒排索引上的最重要的运算是集合交（Conjunction），并（Disjunction）和非（Negation）。
  2. 倒排索引在实际实现中，可以采用位图（bitmap）与整数链表（integer list）两种结构形式。
  3. 倒排索引上的交，并和非运算，对应的整数链表操作是Intersection/Unions操作，对应位图是比特AND, OR, NOT操作。

倒排索引实现： Lucene

Bitmap Index

Roarin Bitmap Java-Roaring CRoaring

BAH

Readings:

  1. Chambi, Samy, Daniel Lemire, Owen Kaser, and Robert Godin. "Better bitmap performance with Roaring bitmaps." Software: practice and experience, 2015.
  2. Vallentin, Matthias, Vern Paxson, and Robin Sommer. "VAST: a unified platform for interactive network forensics." 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), 2016.
  3. Vallentin, Matthias. Scalable Network Forensics. Diss. University of California, Berkeley, 2016.
  4. Chenxing Li et al., BAH: A Bitmap Index Compression Algorithm for Fast Data Retrieval, LCN 2016.
Integer List

Data Structures for Inverted Indexes (ds2i) ds2i

partitioned_elias_fano FastPFor

Readings:

  1. Culpepper, J. Shane, and Alistair Moffat. "Efficient set intersection for inverted indexing." ACM Transactions on Information Systems (TOIS), 2010.
  2. Schlegel, Benjamin, Thomas Willhalm, and Wolfgang Lehner. Fast Sorted-Set Intersection using SIMD Instructions, ADMS 2011.
  3. Inoue, Hiroshi, Moriyoshi Ohara, and Kenjiro Taura, Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions, VLDB 2014.
  4. Kane, Andrew, and Frank Wm Tompa, Skewed Partial Bitvectors for List Intersection, SIGIR 2014.
  5. Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini, Optimal Space-Time Tradeoffs for Inverted Indexes, ACM WSDM 2015.
  6. Lakshminarasimhan, Sriram, et al. "Scalable in situ scientific data encoding for analytical query processing." Proceedings of the 22nd international symposium on High-performance parallel and distributed computing. ACM, 2013.

混合结构

融合几种独立结构的混合结构

  1. Athanassoulis, Manos, and Anastasia Ailamaki. "BF-tree: approximate tree indexing." Proceedings of the VLDB Endowment 7, no. 14 (2014): 1881-1892.

其它结构

Succinct Data Structure

Succinct Data Structure Library

Implemented_SDS

  1. Bitvectors supporting Rank and Select
  2. Integer Vectors
  3. Wavelet Trees
  4. Compressed Suffix Arrays (CSA)
  5. Balanced Parentheses Representations
  6. Longest Common Prefix (LCP) Arrays
  7. Compressed Suffix Trees (CST)
  8. Range Minimum/Maximum Query (RMQ) Structures

Readings:

  1. Navarro, Gonzalo, and Eliana Providel. 2012. “Fast, Small, Simple Rank/Select on Bitmaps.” In Proceedings of the 11th International Symposium on Experimental Algorithms (SEA 2013), 295–306.

大数据算法

数据解析

数据解析（Data Analytic），是指对数据集的属性值进行SUM，TopN，Rank操作。一般要求实时响应。

Readings:

  1. Navarro, Gonzalo, and Eliana Providel. "Fast, small, simple rank/select on bitmaps." In International Symposium on Experimental Algorithms, pp. 295-306. Springer Berlin Heidelberg, 2012.


Broadword Implementation of Rank

Broadword

  1. Vigna, Sebastiano. "Broadword implementation of rank/select queries." In International Workshop on Experimental and Efficient Algorithms, pp. 154-168. Springer Berlin Heidelberg, 2008.

大数据解析平台

Apache Kylin Kylin

Druid Druid

基数估计

基数估计（Cardinality Estimation），评估一下一个集合中不同数目的个数。比如，访问一个网站的独立IP个数。

Cardinality Estimation Algorithm

  1. Flajolet, Philippe, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm." DMTCS Proceedings 1 (2008).
  2. Heule, Stefan, Marc Nunkesser, and Alexander Hall. "HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm." In Proceedings of the 16th International Conference on Extending Database Technology, pp. 683-692. ACM, 2013.

大数据系统

Hadoop

Hadoop

  1. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. "The Google file system." ACM SIGOPS operating systems review. Vol. 37. No. 5. ACM, 2003.
  2. Jeffrey Dean and Sanjay Ghemawat. "MapReduce: simplified data processing on large clusters." Communications of the ACM 51.1 (2008): 107-113.

Spark

Spark

  1. Zaharia, Matei, et al. "Spark: cluster computing with working sets.“ Proceedings of the 2nd USENIX conference on Hot topics in cloud computing. Vol. 10. 2010.

机器智能

机器学习

Machine Learning scikit-learn

深度神经网络

Google TensorFlow Tensorflow

TensorFlow: A System for Large-Scale Machine Learning, OSDI 2016.OSDI-2016

计算机围棋

Better Computer Go Player with Neural Network and Long-term Prediction

Pachi: State of the art open source Go program

Training Deep Convolutional Neural Networks to Play Go

论文报告撰写

Madoko

项目分组

第一组

组长： 姚沛然

组员： 王逸伦 张正彦

第二组

组长：王亦凡

组员：刘梦旸、邱昱田

第三组

组长：李子豪

组员：娄晨耀 张若天 邹逍遥

第四组

组长：石冠亚

组员：宣程 汤鹏 段了了

第五组

组长：杨文聪

组员：梅杰 计昊哲 杨应人

第六组

组长：赵宇璋

组员：孙炜岳 吴一凡

第八组

组长：熊铮

组员：范承泽，秦梓鑫

论文研读

要求：提交研读论文的PPT（正文部分不超过10页）。

时间：10月14日中午12点之前。

10月19日下午安排每组做一个小报告，每组时间不超过10分钟。

第一组

RUBIK: Efficient Threshold Queries on Massive Time Series, SSDBM 2015.

第二组

SciCSM: Novel Contrast Set Mining over Scientific Datasets Using Bitmap Indices, SSDBM 2015.

第三组

ALACRITY: Analytics-Driven Lossless Data Compression for Rapid In-Situ Indexing, Storing, and Querying, TLDKS X, 2013.

第四组

VSEncoding: Efficient Coding and Fast Decoding of Integer Lists via Dynamic Programming, CIKM 2010.

第五组

Super-Scalar RAM-CPU Cache Compression, ICDE 2006.

第六组

Partitioned Elias-Fano Indexes, SIGIR 2014.

第八组

Optimal Space-time Tradeoffs for Inverted Indexes, WSDM 2015.

课程实践

学生准备

携带笔记本，智能手机 (Bring your own laptop computers and camera-ready smart phones)

Azure云平台使用

Azure

Flask Web服务器搭建

准备virtualenv 安装方法下面两条命令可能会适用mac和linux: 
$ sudo easy_install virtualenv
或者更好的: 
$ sudo pip install virtualenv

如果你使用 Ubuntu ，请尝试: 

$ sudo apt-get install python-virtualenv

Centos，请尝试： 

$ sudo yum install python-virtualenv
安装好virtualenv后，可以创建一个项目文件夹，利用virtualenv命令在其下创建 venv 文件夹: 
$ mkdir myproject
$ cd myproject
$ virtualenv venv
New python executable in venv/bin/python
Installing distribute............done.

现在，只要你想要在某个项目上工作，只要激活相应的环境。在 OS X 和 Linux 下，按如下做: 

$ . venv/bin/activate
现在你只需要键入以下的命令来激活你的 virtualenv 中的 Flask: 
$ pip install Flask
几秒后，一切就为你准备就绪。(weiwandaixu)

课程项目

项目1-大数据

描述

任务：基于位图索引的概念和原理，用C++实现一个位图索引数据库。


检验：完成对一段网流数据的索引建立，查询。在虚拟机上运行成功，得到正确结果。

  网流数据：\\166.111.134.110\team-saturn\网流数据

  代码托管：http://gitlab.icenter.tsinghua.edu.cn

  时间：10月7日中午12点之前（特殊情况，推迟一周）

  组织：以组为单位，要求要看到所有同学的贡献。

作业提交

[[Group1]] [[Group2]] [[Group3]] [[Group4]]
[[Group5]] [[Group6]] [[Group7]] [[Group8]]

项目2-Lucida使用

Lucida安装

每个组在清华工业云平台上安装Lucida软件

清华工业云 icenter-cloud

下载地址 Lucida-AI

每组工作

每组熟悉了解Lucida的7种AI服务的实现原理：

日历服务CA

图像匹配IMM

图像分类IMC

问答QA

1.Lucida demo QA使用介绍

（1）用户自定义信息类

  • 在“学习”栏增加至少一段信息。例如“约翰25岁”
  • 转到“推断“栏，询问一个与你所添加信息相关的的问题。例如“约翰多少岁？”
  • Infer.png

（2）网页信息类

  • Infer2.png

(3)数据库信息类 例： 谁是中国的最后一位皇帝? 谁发现了南极点? 谁发明了电话? 哪位希腊数学发发展了几何学？ 慕尼黑协定在何时签订? 泰森在何时夺冠 尼罗河位于什么地方？

2.依赖项介绍 （1）OpenEphyra：OpenEphyra 是一个使用 Java 开发的模块化、可扩展的开源问答系统。它从网络和其他资源检索自然语言问题的答案。开发者能基于这项项目开发新的问答系统，而不用关心端到端系统。

（2）Indri：提供目前最先进的文本搜索，支持多种结构的询问语言。可在一台机器上实现对五千万个文档的文本收集；分配搜索后，量级能再增加一倍。支持linux，solaris，windows和mac os等多个系统。 （3）MongoDB：可以应用于各种规模的企业、各个行业以及各类应用程序的开源数据库。它为开发人员 提供了传统数据库的功能：二级索引，完整的查询系统以及严格一致性等等。 （4）Apache Thrift：提供标量化跨语言开发服务。由一个软件栈和代码生成引擎组成，提供在C++, Java, Python, PHP, Ruby等多种语言间无缝高效转换的服务。

手写数字识别DIG

 手写数字识别DIG这个单元由我们第三组负责。
 由于技术上对图形界面的了解不深，我们组并没能成功模拟出这一个项目，因此，我们主要是对程序代码以及tutorial里面的内容的一些分析，并查阅了相关资料。
 首先，手写数字识别这一个项目，我们可以通过给定一个只包含一个手写数字的jpeg格式照片，那么这一个项目可以识别出这个数字是0到9当中的哪一个。
 然后，这一个项目的代码结构主要分为以下的几个部分：
 1.压缩并存储。在这一步当中，程序通过对给定jpeg文件的输入进行分析，并通过将这个文件压缩到一个固定大小然后存储起来。
 2.黑白二值化。就是通过对原有图片进行一定的修改，使得数字部分和背景部分能更好的区分开来。在这一步当中，应该可以通过采取较优的黑白二值化的方法
（比如说可以与周围一定数量的像素点进行比对）从而同时消除噪点，提高识别的精度。
 3.把修改后的图片作为神经网络的输入。这一步，就是把经过上两步操作后得到的像素矩阵输入到神经网络当中，然后通过引用caffe（卷积神经网络框架）返回权值从而得到与各个数字的一个相关权值；
 4.根据得到的相关权值，返回结果。
 以上就是该项目程序代码结构的主要部分。
 那么，我们可以注意到里面运用到了一个卷积神经网络框架模型。我们通过查阅资料得知，该模型，是通过前期的一些训练准备从而提高对相关图片的识别能力。训练准备的步骤大概分为两步：
 首先，是初始化网络及学习参数，如设置网络初始权矩阵、学习因子等。
 然后，就是提供各种相关图片的训练模式，训练神经网络，不断修正，直到满足要求为止。
 而训练神经网络这一步，分为前向传播过程和后向传播过程。
 前向传播过程就是通过给定的训练模式的输入，计算网络的输出模型，并与期望模式进行比较，如果达到要求，则进行下一个训练模式；如果未达要求，则进行后向传播的过程。 
（与我们的识别图像一步比较相似，只不过我们识别图像的时候是直接返回网络计算出来的输出模型）
 后向传播过程则是可分为三个步骤：
 1. 计算同一层单元的误差；
 2. 修正权值和阈值；
 3. 进行下一个训练模式。
 上面的具体操作则是通过将原本的特征maps与一个可学习的卷积核进行卷积，并通过一个激活函数得到输出特征map。然后再利用计算出来的灵敏度map进行梯度下降方法对原本的特征maps进行修正。
 那么，通过对足够多的训练模式去训练网络，我们就可以得到一个足够优的神经网络去解决手写数字识别问题。

最后是学习过程中参考的资料： 

 1.《Notes on Convolutional Neural Networks》，Jake Bouvrie
 2.《基于神经网络的图像识别方法》，彭淑敏，王军宁
 3.《Deep Learning论文笔记之（四）CNN卷积神经网络推导和实现》，zouxy09

人脸识别FACE

语音识别ASR

时间：10月26日下周三中午12点之前。

项目2-云+端整合

Thrift协议

Thrift

client端

  • 调用摄像头拍照
  • 调用Thrift接口

参考

Android开发入门

cordova

clarity-mobile

server端

  • 接收图片文件
  • 调用服务端程序

项目3-机器智能

描述

完成一个可展示的人工智能系统

  • 步骤1：设置azure虚拟机；
  • 步骤2：架构flask-web服务；
  • 步骤3：建立AI服务（Google Tensorflow）；
  • 步骤4：lucida.ai；
  • 步骤5：智能端开发（移动平台、嵌入式硬件）+thrift协议联调；

参考： Lucida-AI

作业提交

[[Group1]] [[Group2]] [[Group3]] [[Group4]]
[[Group5]] [[Group6]] [[Group7]] [[Group8]]

致谢

本课程获得微软Azure云计算与机器学习捐赠支持。

感谢微软公司 杨滔经理，章艳经理，刘士君工程师，闫伟工程师。

参考文献

基础

  1. Hennessy, John L., and David A. Patterson. Computer architecture: a quantitative approach. Elsevier, 2011.
  2. Matthew, Neil, and Richard Stones. Beginning linux programming. John Wiley & Sons, 2011.
  3. Stroustrup, Bjarne. The C++ programming language. Pearson Education, 2013.
  4. Weiss, Mark Allen. Data structures and algorithm analysis in Java. Addison-Wesley Longman Publishing Co., Inc., 1998.
  5. Flanagan, David. JavaScript: The definitive guide: Activate your web pages. " O'Reilly Media, Inc.", 2011.
  6. Grinberg, Miguel. Flask Web Development: Developing Web Applications with Python. O'Reilly Media, Inc., 2014.

深度学习

  1. Yoshua Bengio, Ian Goodfellow, Aaron Courville, Deep Learning, MIT Press, 2016.
  2. Google brain team, TensorFlow: Large-scale machine learning on heterogeneous systems, whitepaper, 2015.
  3. Vijay Agneeswaran, Real-Time Applications with Storm, Spark, and More Hadoop Alternatives, 2014.
取自“http://wiki.icenter.tsinghua.edu.cn/icenterwiki/index.php?title=大数据与机器智能&oldid=40679”