精华内容
下载资源
问答
  • Prophet是比较简单易用的,对于非时序预测和机器学习领域专家的是非常容易上手的。其参数大多数都是非常直观的参数。(Prophet的python包大量使用了pandas库,所以使用python做开发的需要首先了解pandas的使用。) ...
    • Prophet是比较简单易用的,对于非时序预测和机器学习领域专家的是非常容易上手的。其参数大多数都是非常直观的参数。(Prophet的python包大量使用了pandas库,所以使用python做开发的需要首先了解pandas的使用。)

    • Prophet也是一种约定优于配置的思想,写代码只需要按照约定的套路定义好pandas中的dataframe就可以轻松进行预测。

    • 下面我们来进行一个官方网站提供的Quick Start来进行学习了解。

    import pandas as pd
    import numpy as np
    from fbprophet import Prophet
    import matplotlib.pyplot as plt
    
    # 数据文件请从github上的Prophet项目下载,并放在代码的对应目录
    df = pd.read_csv('examples/example_wp_peyton_manning.csv')
    df['y'] = np.log(df['y'])
    print df.tail()
    
    # 定义模型
    m = Prophet()
    
    # 训练模型
    m.fit(df)
    
    # 构建预测集
    future = m.make_future_dataframe(periods=365)
    print future.tail()
    
    # 进行预测
    forecast = m.predict(future)
    
    print forecast.tail(10)
    forecast[['ds', 'yhat', 'yhat_lower', 'yhat_upper']].tail(10)
    m.plot(forecast)
    plt.show()

    结果
    上图为最终的作图结果,其中蓝色线为预测结果,黑色点为原数据点。除此之外,由于Prophet使用的是加性模型,也就是把模型分为趋势模型、周期模型、节假日以及随机噪声的叠加。因为我们可以方便对各个成分进行作图观察。我们可以利用m.plot_components(forecast),对各个成分进行作图观察,如下:这里写图片描述
    默认会画出趋势、年周期、星期周期成分(如果在定义模型时给出了holiday参数,还会做出holiday的成分图)

    • 下面干货,从我的学到的经验中设计如何利用Prophet构建有效的预测模型。
      1. 首先我们去除数据中的异常点(outlier),直接赋值为none就可以,因为Prophet的设计中可以通过插值处理缺失值,但是对异常值比较敏感。
      2. 选择趋势模型,默认使用分段线性的趋势,但是如果认为模型的趋势是按照log函数方式增长的,可设置growth='logistic'从而使用分段log的增长方式
      3. 设置趋势转折点(changepoint),如果我们知道时间序列的趋势会在某些位置发现转变,可以进行人工设置,比如某一天有新产品上线会影响我们的走势,我们可以将这个时刻设置为转折点。
      4. 设置周期性,模型默认是带有年和星期以及天的周期性,其他月、小时的周期性需要自己根据数据的特征进行设置,或者设置将年和星期等周期关闭。
      5. 设置节假日特征,如果我们的数据存在节假日的突增或者突降,我们可以设置holiday参数来进行调节,可以设置不同的holiday,例如五一一种,国庆一种,影响大小不一样,时间段也不一样。
      6. 此时可以简单的进行作图观察,然后可以根据经验继续调节上述模型参数,同时根据模型是否过拟合以及对什么成分过拟合,我们可以对应调节seasonality_prior_scale、holidays_prior_scale、changepoint_prior_scale参数。

    相关网站:

    展开全文
  • 转载自:http://blog.csdn.net/kanghua/article/details/44650831Hummer TimeSeries DB (蜂鸟时序数据库)技术...这些时序数据不但数量越积越多、而且频率也越来越快,但传统数据库对于这种数目庞大、更新频繁的时序

    转载自:http://blog.csdn.net/kanghua/article/details/44650831


    Hummer TimeSeries DB (蜂鸟时序数据库)技术介绍

    1. 背景介绍

        不知不觉中我们已经跨入“大数据”时代,而大数据的主要来源是来自于各种“传感器”所产生的时序数据记录。这些时序数据不但数量越积越多、而且频率也越来越快,但传统数据库对于这种数目庞大、更新频繁的时序数据,无论存储或检索都难以应对(“存不下”、“查不出”)。因此工业界当前迫切需要一种面向时序数据特征而专门设计的新型时序数据库 —— 蜂鸟时序数据库正是在此背景下,为存储和检索时序数据而研发的分布式数据库。

    注 : 取名蜂鸟源自于蜂鸟令人惊叹的挥翅速度。蜂鸟每秒翅膀能挥动15-80次不等。想象一下,蜂鸟本身就犹如一个“传感器”,而翅膀挥动就好比不断产生时序数据。

    2. 时序数据带来的新挑战

    2.1. 数据量急剧膨胀

        机器(传感器)产生的时序数据量与人手工录入的传统档案类数据量相比,完全不是一个数量级—— 前者百万、千万记录量已触顶,而后者动暨数十亿、数百亿的记录规模。面对如此大量的时序数据,传统数据库既“存不下”,也“查不出”(原因见 2.2/2.3/2.4)。因此当前业界普遍采用的妥协方案是:或者只存近期数据(无奈的丢弃老数据),或者只存储一些抽样记录(如: 降频down-sampling到只记录整点数据)。显然这些方案都无法避免丢弃宝贵数据。在数据为王的时代,谁拥有的数据更多,谁就拥有更强的竞争力,被迫放弃数据实为可惜!

    2.2. 数据需高速实时导入,且可实时数据获取(ingestin real time)

        大量的传感器数据从四面八方、实时涌来(每分钟成千上万,甚至每秒钟成千上万条记录),若想从中找到瞬息万变的“机会”,就需要数据能高速入库,同时还能允许及时查询刚入库的新鲜数据。但传统数据库在大量随机数据实时写入时,性能欠佳 (入库速度明显不够),更糟的是在入库同时当有并发读操作时,读写性能都将变的更差。因此当前业界普遍采用的妥协办法是: 延迟入库(如,到晚上无查询业务时再入库新数据),或批量入库(如,每天积攒一批数据再批量入库) —— 这些方法实际上都是为了避免或减少读写混合发生。显然上述方案肯定会牺牲数据处理的实时性,因此也必然降低了数据的内在“价值”。

     

    2.3. 按时间断面(区间)高速检索数据

       时序数据最普遍的查询需求是:“在时间断面上,(精确、条件、模糊)检索数据”。其检索特征更偏向于数据扫描(Scan) —— 而不是传统数据库最擅长的数据定位(seek)。对于数据量有限的档案数据,传统数据库只需在时间列上和键(key)上建立索引,就得能应这类检索。但不幸的是当时序数据上量后,索引无法继续驻留在内存;更糟的是不断的更新操作(如无序插入)又带来了索引分片(indexfragment)的麻烦。这两点都使得传统数据库在按时段查询时无法顺序扫描目标数据区(磁头需要跳跃寻址),因此传统数据库的查询性能会随时序数据增加和持续更新变的越来越差,而且是指数性下降。

       除了时序数规模增长和持续更新对传统数据库索引机制造成冲击外,数据乱序入库对传统索引机制更是灾难 —— 乱序入库是指 : 记录入库顺序并非严格按时间有序(试想多地传感器数据从远程输送来,然后再集中入库。经这个“漫长”过程后,几乎可以肯定数据入库顺序已然不等于数据的发生时间顺序了)。传统数据库在时序数据无序写入的情形下,会造成数据在物理存储上也无序分布。所以即便在时间列上建有索引,按时间断面查询还是无法顺序扫描磁盘,而需要不断seek才能定位数据 —— 我们知道在磁盘上只有顺序读写性能才是最佳,随机读写性能要相差百倍以上。

    2.4. 数据分析重要性越发突出

      时序数据存储的目的有两类:第一是“事故反演、场景回放”;第二是“分析统计和预测”。而分析类需求从简单到复杂可再分为三小类:

    n   朴素的统计分析(如多维分析等)


    n   基于移动平均值或者差值的预测分析

    n   基于机器学习等的预测和挖掘分析

        统计分析离不开SQL和各种聚合函数和窗口函数;而对于预测、挖掘则往往需要借助于Hadoop体系的M/R、BSP等计算框架。传统数据库对于统计需求,在数据量不大时还算比较擅长,但若要与Hadoop等NOSQL系统配合,则多有不便 —— 或者接口支持不好、或不能最大发挥硬件能力。

    2.5. 可控的实施成本

        时序数据相关业务才刚刚起步,而且多属于运营支撑性业务。相对于一线盈利业务而言其业务价值和技术本身都存在一定风险;另外业务的数据规模也不一定能一步到位,数据往往是由少到多逐步积累,一开始或相当时间内数据量都很有限。鉴于上述实时,我们建议在项目实施开始阶段应尽量控制成本,降低实施风险。

    成本控制从技术角度讲最好的选择是:

    ü 使用普通PC机器,也可用私有云提供的标准虚拟机。

    ü 先部署有限规模的机器集群(如先满足未来半年数据存储需求)。当业务价值得已证实、数据规模逐步上量后,再对集群进行扩容也不迟(避免初期实施就一步到位,而闲置大量资源)。

    上述需求换而言之就是要求:

    1.  系统在软件层面要做好、做足容错工作(因为普通pc机缺少小型机所具备的硬件容错设备)。传统数据库往往把容错都交给硬件做,不但成本高,而且实际上也不如软件层面更可靠和可控。

    2.  系统必须有良好的横向扩展能力,即补充同类机器机即可实现自动扩容。而传统数据库初期就要购置昂贵的小机,而且扩容时多是采用纵向扩展方式,即需要用户再购买更高配置的小机代替原先的小型机。

     

         综上所述(2.1-2.5),传统数据库由于设计初衷是应对“档案”数据,而非时序数据,所以面对当前大规模时序数据时,传统数据库就显得捉襟见肘,难以应对了。正是如此,原先并不被业界所重视的“时序数据库”得以快速走向前台,并日渐受到重视和推崇。

    3. 时序数据库适用场景

        毫无疑问,存储和检索时序数据肯定是时序数据库的最佳使用场景,但到底有那些场景会产生时序数据呢?我们身边是否有时序数据呢?

        我们首先要认识到最可能产生时序数据的不是人,而是机器,更确切的讲是“传感器”。不过这里所谓的“传感器”更具抽象意义 —— 凡是具备数据采集和上报功能的设备都属于“传感器”。比如刷卡POS机、ATM款机、交通摄像头、手机、PM2.5探头等等都属于传感器。可见我们身边充斥着各种“传感器”,生活中的万千变化都被“传感器”时刻记录着。我们不妨大胆预言——不久的将来,随着数据越来越丰富和准确,基于数据权威的社会发展模式必然会让社会变得更高效、更公平、更廉洁。

      我们不妨归纳一下依赖时序数据的典型行业和其用到的“传感器”数据:

    n  能源行业:智能电表用电量数据。

    n  通讯行业:短信、话单、邮件。

    n  交通行业:监控摄像头(卡口设备)过车记录;监控油轮航运轨迹、耗油等。

    n  金融行业:银行POS机刷卡数据、ATM机取款数据。

    n  环保行业:气象监控数据(温度、风速、降雨等)、环境监控数据(pm2.5等)。

    n  互联网行业:用户访问日志、广告点击日志。

    n  移动互联:近场通讯数据、App应用统计数据。

    n  广电行业:机顶盒操作数据。

    n  物流行业:配送记录数据。

    n  地理信息系统:GPS数据存储和分析。

    n  云计算:服务器性能计数数据。

    n  制造业:监控机器运行指标,优化制造流程。

    n  医疗行业:纪录和监控药品使用情况、纪录和监控病人病理指标。

        另外,公安刑侦、情报分析、物联网、智慧城市等也都是时序数据的消费行业。不夸张的讲:凡是具有公共服务特征的行业就离不开时序数据—— 或产生时序数据、或消费时序数据、或兼而有之(时序数据库的具体实践请见“最佳实践”一章)。

    4. 系统运行环境要求

        蜂鸟不需要高端存储设备和高性能小型机,而是使用配置SATA磁盘的普通PC服务器(组成计算存储一体化集群)。这种通用机型的配置要求其实正是大数据、云计算运行环境发展的主流趋势和必然结果。因为通用机型除了价格低廉和保护企业现有投资的原因外,更重要的原因是:可以使用私有云和公有云所提供的虚拟机部署系统。由此可见,蜂鸟系统可部署在提供虚拟机的“私有云”中,甚至还可被部署在EC2这种“公有云”上。

        当然对于预算宽裕,或想要求最佳性能表现的客户,完全可以给出较高的环境配置 —— 更高的配置必然能带来更高的性能。

        下面简要给出一个大众化的配置要求(可满足大多数要求),供大家参考:

    n  CPU — 4-12 core(主频>2G)  # 如果计算任务颇多,可尝试提升CPU主频档次, 另外核/core数最好比机器磁盘数多才好(如8盘,则12核最佳)

    n  内存 — 16G-512G # 32G属于标配,内存越大缓存越多,处理数据也自然更快,所以有实力的可将内存容量扩充到32G、64G、128G、256G、甚至更高。

    n  磁盘 — 2 - 12个STAT/SAS磁盘 # 一般大容量的SATA磁盘速度就足够了,但数量应尽可能多,因为越多的磁盘数量不仅仅是容量增加,更重要是写入和查询性能的提升(近线性提升),所以多盘是高性能性能的保证之一。

    n  网络 — 千兆网络环境 # 千兆网络已能应对大多数场景了,如在万兆网环境下,则写入和查询性能(尤其是大表Join操作)都将显著提升。

    n  OS — Centos6.5(64bit) # 我们推荐比较稳定的Centos系统,不过实际上Linux各种操作系统都予以支持

    如果要求更高的处理性能和存储能力,则简单补充机器即可达到目的(性能的具体计算公式见章节10.2)

    注:如果需要高可用性,则最少配置三台机器,以保证数据安全;

    5. 体系架构

       蜂鸟系统最重要的架构特点是分层结构 —— 每层各司其职,相互解耦,独立演化。最重要的两层分别是NOSQL数据层和SQL查询层。 而在NOSQL层于SQL层上分别选择了Shared Nothing和MPP两种分布式经典架构。

    层次说明(见图1):


    n  NOSQL数据层 : NOSQL层处于基础层,内部自下而上又分为 “数据存储层” 、“数据同步层”、 “对象检索层”。分别负责数据持久化、多副本数据传播、对象读写控制功能。该层采用NOSQL经典的Shared Nothing架构,具备高扩展性、高并发性、高可用性等优良特性。

    n  SQL查询层 : SQL层依赖于 NOSQL层,内部自下而上又分为“并行SQL执行层” 和“JDBC/ODBC接口层”。该层采用SQL查询领域最成功的MPP架构,具备大吞吐、高并发等优良特性。

    n  离线计算层 : 该层和SQL层一样都是依赖于NOSQL层,但同时也依赖于HADOOP 体系中得M/R组件。简单讲,离线计算原理是利用M/R框架就近(到数据所在机 执行计算任务)操作NOSQL数据层所管理的数据。 从编程接口一节可看到,蜂鸟支持M/R 程序,也支持PIG、Hive等工具,都些无不得益于离线计算层。显然该层继承了HADOOP离线计算框架具有的大吞吐、高容错等优良特性。

     

     图 1

    6. 时序数据存储格式

        近年来,经过在大数据项目中不断探索与实践,使得我们更“懂”时序数据。蜂鸟大胆抛弃了传统数据库的掣肘,针对时序数据设计了专有数据格式和执行计划,以求最佳性能。在展开时序数据存储格式前,重申时序数据处理的主要特征 : 时间断面(区间)上进行精确、模糊、条件检索 —— 例如 : 查找国庆期间查询给定嫌疑人通讯踪迹(精确查询) ; 查春节期间具有“陕A”车牌号字样的进京车辆/总数(模糊前缀查询) ; 查询大年初一北京望京地区用电量最高的电表(地域条件查询);除时间区间上基本检索外,很多场景更需要在时间段面(区间)上进行各种统计分析计算 —— 例如 : 如,总量统计、同比、环比计算等。

        我们针对上述时序数据处理的两大场景 : “区间内个体回放”和“区间内统计分析”(前者是在时间区间上进行给定key的检索;后者是在时间区间上进行分析计算),分别设计了KT和TK两种针对性存储格式。如果应用场景同时有统计分析和个体回放两类需求,则可使用蜂鸟专有的PKT格式兼顾这两类需求 —— PKT格式属于TK格式和KT格式之间的一种“折中”选择。若场景确定时,优先考虑使用KT或TK场格式 —— 比如,侦查员追查嫌疑车辆轨迹,或疑犯的通话记录等场景,属标准的个体回放需求,应优先考虑KT格式;路况车流等指标计算则属于区间内统计分析运算需求,应优先考虑TK格式;但当你既想查看给定车轨迹,又想统计路况信息时,则最好选择PKT格式了。

     

    我们以示例数据做样本,分别按照三种不同存储格式组织时序数据,通过对比展示几种格式之间的区别。

    示例数据:

    时间从2012-06-19 20:30:00到2012-06-21 02:30:00三个小时区间为例,共到来9个时序数据,内容分别如下:

    2012-06-19 20:30:00(1340109000000)  K1,V1(内部包含colume1,colume2,colume3,....)

    2012-06-19 20:40:00(1340109600000)  K3,V2

    2012-06-19 21:10:00(1340111400000)  K2,V3

    2012-06-19 21:35:00(1340112900000)  K1,V4

    2012-06-19 21:45:00(1340113500000)  K3,V5

    2012-06-19 22:15:00(1340115300000)  K1,V6

    2012-06-19 22:45:00(1340117100000)  K3,V7

    2012-06-19 22:55:00(1340117700000)  K2,V8

    2012-06-19 22:58:00(1340117880000)  K1,V9

     

    n   TK 格式(即 TIMESTAMP-KEY 格式) —— 该格式首先按照事件发生时间排序,当时间相同时,则再按照事件ID(key)排序。具体 Layout 见表 6.1:

    Timestamp

    Key

    Colume1

    Colume2

    Colume3

    ....

    1340109000000

    K1

     

     

     

     

    1340109600000

    K3

     

     

     

     

    1340111400000

    K2

     

     

     

     

    1340112900000

    k1

     

     

     

     

    1340113500000

    K3

     

     

     

     

    1340115300000

    K1

     

     

     

     

    1340117100000

    K3

     

     

     

     

    1340117700000

    K2

     

     

     

     

    1340117880000

    K1

     

     

     

     

    ...

    ...

     

     

     

     

     

     表6.1














    n  KT 格式(即 KEY-TIMESTAMP 格式) —— 该格式首先按照key排序。当在key相同时,则再按照事件发生时间再排序。具体 Layout 见表 6.2:

    Key

    Timestamp

    Colume1

    Colume2

    Colume3

    .....

    K1

    1340109000000

     

     

     

     

    K1

    1340112900000

     

     

     

     

    K1

    1340115300000

     

     

     

     

    K1

    1340117880000

     

     

     

     

    K2

    1340111400000

     

     

     

     

    K2

    1340117700000

     

     

     

     

    K3

    1340109600000

     

     

     

     

    K3

    1340113500000

     

     

     

     

    K3

    1340117100000

     

     

     

     

    ...

    ...

     

     

     

     

     表6.2

     














    n   PKT 格式(即 PARTITION-KEY-TIMESTAMP 格式) —— 该格式首先按照时间分区分组排序(其中partition可选择小时、天、月、年等时间单位,其类似传统数据库中的分区概念),在组内首先按照KEY排序,相同KEY再按照事件时间排序。具体 Layout 见表 6.3

    Parttion

    Key

    Timestamp

    Colume1

    Colume2

    Colume3

    Colume4

    13401072

    K1

    1340109000000

     

     

     

     

    13401072

    K3

    1340109600000

     

     

     

     

    13401108

    K1

    1340112900000

     

     

     

     

    13401108

    K2

    1340111400000

     

     

     

     

    13401108

    K3

    1340113500000

     

     

     

     

    13401144

    K1

    1340115300000

     

     

     

     

    13401144

    K1

    1340117880000

     

     

     

     

    13401144

    K2

    1340117700000

     

     

     

     

    13401144

    K3

    1340117100000

     

     

     

     

    ...

    ...

     

     

     

     

     

      分区单位-小时

      表6.3

     













       上述的数据存储格式核心目的都是为了让时序数据在磁盘上“有序存储”,从而按区间扫描时磁头可保证高速顺序移动,并且遍历的数据尽可能少。如果理解了这个准则,那么自然可知上述时序数据格式各自的优缺点了:

    n  TK格式对于区间内无key检索性能最优,而对于给定key查询则有所浪费 —— 因为TK

    格式中未按KEY聚集数据,所以检索给定KEY需要扫描给定时段内全部数据。

    n  KT格式对于给定key检索性能最优,如果区间内无key查询则是麻烦 —— 因为KT格式下要统计给定时段则必须扫描全部数据。

    n  PKT格式对于区间内无key查询效率比TK格式稍差 —— 因为需要扫描完时段所跨分区的全部数据;PKT格式对于给定key检索效率比KT稍差 —— 因为需要在时段所跨越的每个分区内,依次扫描该给定key的对应数据。但PKT格式能兼顾两类查询,且性能损失不大。

       为了能在多种场景下都能提供最佳处理性能,我们对同一数据的不同副本可选择不同数据格式存储,在查询时根据查询条件“智能”选择最佳数据格式所在的分片实施查询,从而确保蜂鸟在各时序场景下都能提供最佳性能(见图2)。


     图2

     

    7. 重要特性和优势

    蜂鸟系统的数据存储格式和体系架构决定了蜂鸟系统的最重要的几个特性:

    n   面向时序检索和分析优化 


    n   分布式存储和计算

    n   高可用性

    n   支持SQL,并扩充时序分析SQL

    上述特性将为用户处理大规模时序数据带来显著好处,具体如下。

    7.1. 读写性能突出

    n  数据导入速度高 :蜂鸟集群中单机单盘能提供40M/s的写入速度,因此不存在数据无法及时入库的烦恼。

    n  数据更新速度高 :蜂鸟实现了列(列族)存储结构,因此很合适需要大规模按列(列族)更新的场景。

    n  数据扫描速度高 :配备8SATA磁盘的PC服务器,能提供约2-4G/s的数据扫描速度,确保时间断面上统计(或者说上钻)性能。

    n  按列计算速度高 :蜂鸟具备列存结构,因此能保证快速在给定列上进行分析计算(无需读取全行)。

    n  时间排序查询速度高 :由于我们时序数据存储遵循时间排序(还有key排序),因此对于按时间排序的检索操作非常高效 —— 比如逆序/正序检索:如,order by timestamp desc/asc limit 100 ;或时间滑动窗口上的计算:如,计算股票MACD等指标。

    7.2. 恒时检索(Constant Query Time)

    恒时体现数据检索速度不随数据总量而变,只与“命中(touched data)”的数据量相关。具体表现在两个方面:

    ü 当给定key检索时,性能只和该key对应的数据多少相关,而与共有多少个key无关(比如,城市车里从100万辆涨到1000万辆后,检索给定车辆的速度不会改变)。

    ü 当无key检索时,性能只和时间段数据量相关,而与总数据量无关(比如,只积累一年数据和积累十年数据情况下,统计某个月数据则响应时间不变)

     

    7.3. 实时数据获取(ingest data in real time)

         蜂鸟支持数据实时流式灌入,无须等待,及刻便能被查询到。这种实时性是在线时序数据处理系统的关键需求。(而使用impala,shark等基于HDFS存储的系统都无法做到数据实时获取)。

    7.4. 支持面向时序的SQL查询

       蜂鸟针对时序数据在插值、时间聚合、Join、递增指标计算等方面对标准SQL进行了扩充,目的是使用户能更直观、方便的对时序数据进行分析处理。

     

    时序SQL扩充项

    语法

    作用

    举例

    时间聚合

    Group by time(number,‘s|m|h|d’

    按照给定时间进行rollup 聚合计算

    监控工厂设备运行状态,需要计算是每5分钟内的某项指标的偏差:

    select deviation(x) from table group by (5,‘m’);

    插值

    Nullpolcation()/prepolcation()

    对于空白时段按照空值或前值进行填充

    为了绘制每5分钟的时间内的数据偏离值,对于采集盲区,需给进行“前值”插值补充:

    select prepolcation(x) from table group by (5,‘m’);

    Join

    time join

    对于多个时序数据进行合并,用于产生新时序(用于分析因果,或计算等)

    观察用电量消耗时序表和天气温度变化时序表之间的因果关系:

    select * from energy time join temperature

     

     

     

    递增指标求增量变化

    Delta()

    对于递增计数指标

    计算用电量费用变化趋势—— 用电量属于单调递增指标。假设电量时序表为table1,电价时序表为table2,两个表的值都按时间变换。

    select table1.timestamp, delta(table1.mount)*table2.price group by table1 time join table2

     

         比如group by语义在蜂鸟中不仅仅作用于给定字段上,而且也可按照任意时间粒度进行聚合 —— select count(type) from events group by time(10m) —— 该功能特别适合于趋势统计(为了方便可视化,蜂鸟还支持对于未有结果的聚集区间进行差值(如填写0/前值等)。 另外蜂鸟也还支持group by count(100)等特有聚合语法。

     

    7.5. 节约空间

        蜂鸟系统存储时序数据相比传统数据库更节约空间。其主要原因如下:

    n  数据压缩存储 :蜂鸟支持面向行和列的压缩,数据压缩比可达到3 – 20 (具体压缩比和数据内容密切相关)

    n  无需额外索引 :蜂鸟避免了像传统数据库那样,在时间列和事件id上建立b树索引,而是将“时间”和“事件ID/Key”撮合为组合KEY,借助LSM树维护有序记录(见数据存储格式一章)。这种“前缀”索引结构以来不但便于时序处理,而且无需额外索引文件,节约了大量存储空间。

        相对于多数传统数据库,蜂鸟至少能节约3-4倍以上的存储空间。比如我们在基准测试一章中提到的120亿、大约600G的气象原始文本数据。如果在关系数据库(如MySQL)中存储,数据本身,再加上索引(需要在key、timestamp、key+timestamp上分别建立索引)大约需要近2*600 = 1.2T存储空间,而在蜂鸟系统中无须额外建索引,且有至少3-4倍的压缩比,所以实际存储空间只需要600/3 = 0.2 T存储空间。

    7.6. 在线离线处理一体化(混合负载支持)

        在传统的大数据处理流程中,在线系统(如OLTP、AD HOC)与离线系统(如报表、OLAP 、数据挖掘)往往被部署成相互独立的的两个集群 —— 在线集群负责数据检索,离线集群负责数据分析。之所以将数据划分到不同集群,是为了避免离线分析对在线数据查询带来负载干扰,妨碍在线系统使用。但如此划分,无疑需要额外的数据搬迁和数据抽取,即ETL过程 —— 数据需要“定期”从在线系统中导入到离线系统。 在工程中运维人员一般会在每天夜间进行ETL操作。但这种传统做法有几个弊端:

    1. 因为离线集群中的数据总要落后于在线集群,所以“新鲜”数据不能及时被分析,从而数据的时效性较差,分析价值也大打折扣。

    2. ETL操作和维护两个集群都需要额外的软件和操作人员,无形增加了软件和人员成本。

    那么理想情况应该将离线集群与在线集群合并,避免不必要的ETL工作,也无需再维护两个集群。为了达到”在线\离线一体化”目的着重需要解决的技术问题是如何避免在线任务和离线任务的负载隔离。具体技术是:

    ü   数据多副本异构同步存储 —— 同一份数据需要存储为多个不同副本,副本之间要求数据同步,副本各自可拥有自己的格式。不同副本将应对不同类型的任务,如列存格式的副本应对分析类任务,排序行存格式应对检索任务。

    ü   任务智能调度,根据任务的不同类型、和集群负载情况,动态选择合适的机器和数据副本执行任务。要求达到最大的资源利用率和性能。

     

       图3

    7.7. 灵活的数据一致性

    根据不同业务需求,用户可选择不同的数据一致性约束。蜂鸟支持如下一致性:

    n  数据“强一致性”:在线检索多使用强一致性

    n  数据“弱一致性”(最终一致性):离线分析时常使用最终一致性。

    n   Session一致性 :

    7.8. 高可用性和高数据安全性

       首先蜂鸟实现了磁盘粒度的故障处理,即当某个磁盘故障时,所在机器其余磁盘负责的数据服务不受影响;另外根据实践统计,存储型机器硬盘年故障率约为3%(网络故障率和机器其他硬件故障率相比磁盘故障要低1-2个数量级别,故下面计算可忽略不计),系统故障切换(Failover)的时间为20秒,系统恢复一块故障硬盘上所存数据最多需要1小时。根据上述条件,我们可计算出“系统可用性”和”数据安全性”这两个衡量系统健壮性的典型指标。

    n  可用性量化计算

        假设一个table只要有一个分片(fragment)不可用,则认为该table不可用。我们只考虑因disk故障(最主要因素)引起的不可用。按含有10台机器的典型集群计算,每台机器8块数据盘,每块数据盘10个副本,分片冗余数为3 —— 即每个分片3 个副本(replica)。一个table在一年内有分片不可用的累计时间是:10*8*3% /20≈0.2小时,有分片有两个副本同时因disk故障丢失的时间为: 10*8*10*2/3*3%*3%/365/24≈0.001826时,因此可得可用性为 1- (0.2 + 0.001826)/365/24≈99.999%。

    n  可靠性量化计算

        一个key-value对成功写入系统后,在一年内丢失的概率为:3%*3%/365/24*3%/365/24≈3.5*10-13,即可靠性为99.99999999996%。 

    7.9. 可扩展性优势

        当数据过多造成容量不足时,或检索分析过程发现性能不足时,蜂鸟只需简单增加硬件即可让系统容量,同时性能也会线性提升—— 增加硬件应优先考虑增加机器中的磁盘,然后才是增加机器。

    7.10. 高并发优势

         蜂鸟设计上重点考虑了多用户并发读写需求,因此相比传统数据库而言,蜂鸟系统在并发性上可以说优势显著 ——SQL接口可支持到数百级别并发读写 ;NOSQL接口单机可支持到数万级别并发读写。

         高并发度的根本原因在于数据负载和查询负载能保持均衡(无数据倾斜和计算倾斜)。因为蜂鸟在时序数据存储时,会将记录按KEY均衡分布到集群中各机器上,在机器内部还会被均分到各磁盘上;而对于分析计算任务,按照数据就近原则,子查询任务将被派发到各段数据所在机器的所在磁盘上并行执行。这种数据分布和计算分布策略对于时序数据处理场景能做做到最大均衡,不存在数据或计算“热点”问题。(Hbase虽然也常用于时序存储,但只能做到数据均衡而无法做到计算均衡)

    7.11. 互联互通性

       除了接口上符合 SQL92 和 M/R 标准外 (见章节8),在互联互通性方面蜂鸟进一步做了两个努力: 


    n 兼容 Mysql协议 :其目的是为了让蜂鸟继承Mysql 客户端的最大优势 ——支持多平台(Linux,Windows,Mac OS)工具访问。但更重要的好处则是:蜂鸟可以借助Mysql协议支持第三方BI软件(因为多数BI软件都支持Mysql)。 


    n 蜂鸟提供了自身与传统关系数据库之间的数据高速迁移工具:可以高效的从传统关系数据库(如 Oracle、Mysql)将数据迁移到蜂鸟时序数据库中,反之亦然。

    7.12.丰富的分析函数

    方便和强大的分析函数是分析型数据库不可或缺的功能—— 既能简化繁琐的SQL表达式,又能提高分析效率。因此蜂鸟系统也努力提供了如下分析函数:

    n  一些列内置的分析函数(兼容Oralce分析函数,如lag,lead,over等窗口函数)

    n  允许用户自定义分析函数

    n  提供特定行业(如交通、电力)的业务分析函数

    7.13. 简单易用的管理界面

        蜂鸟管理中断简单易用,功能完善。支持:一键安装、SQL编辑、结果可视化、故障恢复扩容、缩容等操作。

    7.14. 其它优势                            

    n  支持跨数据中心部署:蜂鸟可应对数据高安全性要求,支持跨机房(地域)部署。

    n  支持数据超期淘汰(OldOut) :蜂鸟支持过期数据自动淘汰,以腾出存储空间用于存储近期数据(如,只存储最近半年的数据)。

    n  支持在线备份:无需停机可在线备份数据(如磁带机)。

    n  支持非时序表:除了时序表外,码表和结果表都是典型非时序表。因此蜂鸟除了重点支持时序表外,同时也支持非时序表的支持。从而予用户使用上的最大方便—— 如,用户可以将时序表和码表进行join,还可以将join结果写入到结果表中。

    n  支持按需动态健表、删表:用户可针对不同场景,在建表语句中指定表类型(时序、非时序)和分布属性(副本数、分布广度等);建表语句可由管理员手动执行,也可在程序中通过API调用;蜂鸟系统可管理数是十到数万张不同类型、不同分布的数据表,完全可以作为数据资源池使用。

    n  支持在线扩容、缩容:蜂鸟支持在不中断在线服务的情况下,进行系统扩容、缩容等运维操作;而且扩容、缩容操作支持以表粒度进行。

    n  支持在线Bug Fix:蜂鸟支持在不中断在线服务的情况下,修复软件Bug。

    n  高速数据恢复:即磁盘或机器永久故障后,系统可将数据损失的副本数据高速(集群环境下 20 - 60分钟)恢复,尽快让副本数重新达到期望值。

    8. 编程和使用接口

          具备方便、易用的用户接口是时序数据库系统能被接受的首要条件,那什么样的接口是最方便、易用呢?从我们多年工程实践经验来看,时序数据库目前最成熟、最受欢迎的用户接口还是SQL(JDBC/ODBC) —— 蜂鸟实现了SQL92标准! 

    n  一是因为SQL接口表现力很强,常见的时序查询和统计需求几乎都可用SQL表达。

    n  二是因为SQL接口容易和第三方或遗留系统对接。JDBC,ODBC是第三方系统访问数据库的业界标准接口,遵循其标准才能与第三方软件实现互联互通。

    鉴于此,我们首推SQL接口;其次我们还提供了其它访问方式:

    ü   NativeJava Api (直接操作NOSQL层)

    ü   ThriftApi(直接操作NOSQL层) —— 可适配各种编程语言(Python、c++、ruby、Java、erlang等)

       除了上述访问接口外,蜂鸟系统同时也兼容Hadoop体系,因此可以直接使用Hive,Pig和M/R程序访问蜂鸟中存放的时序数据。

    9. 竞品分析

          时序数据处理的产品大致分为两类:一类是NOSQL架构的时序数据存储产品(还不能说是数据库);一类是在传统关系数据库内实现时序功能的商业数据库产品。

    前者具有良好的扩展性、可用性和并发性能,但接口一般不支持标准SQL(即便有些产品能模仿SQL接口,但也不能支持聚合运算、嵌套查询、或多表关联等操作);后者能支持标准SQL(甚至支持事务操作),但扩展性和并发性能相比前者要逊色许多。

    蜂鸟系统架构融合了NOSQL和SQL架构的精髓(见体系架构一章)。既具备了NOSQL系统的高扩展性、可用性和高并发特征,同时也具备了SQL系统方便的查询接口和强大的分析功能。

    9.1主要竞品分析

    n   Oralce/Mysql/MS-SQL

    Oracle/Mysql/MS-SQL等传统关系数据库的设计目标是针对“随机访问、随时更新”类档数据,而对于“流式追加、区间检索”类时序数据并未做任何优化处理。事实上传统关系数据库无法应对大规模时序数据处理需求(具体原因见章节2)。

    n   Hbase

    Hbase具备良好的可扩展性,而且也经常被用于存储时序数据。对于时序数据存储又可分为横表存储和纵表存储。横表是指用RowKey存储ID(KEY),而用动态列存储时序事件;纵表则是用RowKey存储ID和事件时间戳的组合键(组合方式多种,如蜂鸟格式中的 PKT,KT,TK等)。但Hbase/Cassandra存在如下问题是:

    1. 未能支持SQL92标准,因此对于聚合运算、嵌套查询、多表join等常用操作都无法简单实现。

    2. 由于存储引擎使用java语言实现,相比C/C++实现的存储引擎,检索性能相对较慢。

    3. Hbase存储按rowKey有序,因此若采用横表方式存储时序数据,则会遇到“热点”问题(具体见7.1章节)。

    n   Cassandra

         Cassandra 相比Hbase而言,对时序数据更友好—— 其避免了hbase的热点问题。但其最终一致性模型对于下推扫描和计算并非最佳选择。

    n   Druid、Geras、InfluxDB、KairosDB、KDB+、OpenTSDB、SiteWhere、TempoDB、TreasureData

    维基百科给出了上述当前比较流行的NOSQL类时序数据库。这些NOSQL架构的时序数据库,其主要服务形态是提供云服务,对外一般提供rest风格的web 接口。它们和Hbase、Cassandra的主要缺陷一样(实际上不少后台的存储就是Hbase或Mysql)—— 不支持SQL92,不支持聚合运算、嵌套查询、多表join等常用查询。

    n   Hive/Impala

    Hive/Impala 实现了SQL92的相关标准,适合数据离线分析(一般使用时间分区的方式将数据存储于HDFS之上)。但对于时序数据处理要求的“实时数据获取”需求无法满足(见7.3),因此不便运用于实时在线系统。

    n   Informix Timeseries

    InformixTimeseries 是当前时序数据库领域里的商业数据库的代表。其有专门“时序数据”类型、也支持SQL92、甚至还支持事务操作。但它扩展性上和并发性比不上NOSQL架构的时序存储系统,也是因为这个原因使得其计算能力受到限制,因此面对计算密集性业务,Informix TimeSeries 比不上蜂鸟。除此以外,InformixTimeSeries 还有两个重要“缺点” —— 成本高、非国产。

    n   Oracle xadata

    Oracle Exadata 数据库是ORACLE应对大规模数据分析的旗舰产品,其已以高性能著称。但Exadata必须使用专有硬件,而且也并非为时序数据优化。另外,和Informix 一样,Exadata扩展性和并发性的局限也使得其计算能力受限(简单计算即可得知:装备20台PC服务器的蜂鸟集群可有大约12*20个CPU CORE 投入计算任务,而Exdata全机架配置也不过128个CPU),而且相比informix其成本更高。

    10. 基准测试

    10.1对比Mysql

       我们使用一组来自NCDC(National Climatic Data Center)的全球气象监控(来自全球分布的气象站)数据作为测试数据,比较蜂鸟和MYSQL对海量气象时序数据处理能力差异。

       测试环境说明:

    ü     物理机器一台: 16G内存、1个容量1T的STATA硬盘、E5-2640(8 core)CPU

    ü     时序数据: 1992-2014年,共约1200个气象监测站,数据记录50字节左右,每分钟产生1条记录。因此原始数据大约120亿条,大小600G左右。

    ü     数据原始格式:93721KBWI(气象站ID) BWI2003090100080508(时间戳) 0.148 N 0.138 N 153(2min均向) 5(2min均速) 151(最高5sec均向) 6(最高5sec均速) 10 60(能见度)

    ü     查询语句: 查询某天平均“能见度” ——  SELECT avg 能见度列 FROM data WHERE id(气象站ID) = ‘93721KBWI’AND timestamp BETWEEN ‘2013-01-01’ AND ‘2014-01-02’—— 大约需要扫描170万(1200*24*60)条记录


     

        图4

       如图(4)可见蜂鸟和MYSQL除了统计速度上存在明显差距外,Mysql 在大约写入4亿条数据之后(这时系统内存不够存放索引),读取性能显著下降,而蜂鸟系统则表现出“恒时查询”特性。

       注:为了便于比较,我们仅是单机单盘条件下对比蜂鸟和Mysql系统。

     

    10.2.性能预测

    由于蜂鸟系统按KEY和时间有序存储数据(类似传统数据库的聚集索引),而且具备线性扩展能力,因此完全可以在给定的硬件环境下,较为准确的预测出检索速度。

    具体的推测方式可按下面的公式简单计算:

    l  机器数量 = M

    l  单机磁盘数量 = N

    l  记录大小 = X

    l  记录数量 = C

    l  实体(KEY)数量 = K

    l  记录时间跨度 = S

    l  压缩比 = Z

    l  磁盘顺序读速度约为60M/s

     

    n  给定时间段D内检索单key耗时T(即在单盘上扫描出该key在该时段的所有记录耗时)

    =  (D/S * C/K  * X ) / Z / (60*1024*1024) 

    n  给定时间段D内统计耗时T(即多盘并发扫描出该时段所有数据耗时)

    =  (D/S * C *X)/ Z / (60*1024*1024) / (M*N)

     

       举例说明:集群机器数量为10,每个机器8个磁盘;记录大小100字节,记录数量100亿,key数量1万,时间跨度1年,压缩比是3,那么可推断出如下结果:

    ü  检索一天内的给定key时间约为 = (1/365 * 10,000,000,000/10,000 * 100) / 3 / (60 * 1024*1024) =0.002秒

    ü  统计一天内的数据时间约为=   1/365 * 10,000,000,000 * 100 / 3 / (60 * 1024*1024) /(10*8) = 0.4秒

     注意,上述查询耗时是扫描数据理论速度,实际在集群环境下执行查询的总耗时必然要高于其。因为除了扫描磁盘外,执行过程还要包含“语法解析”、“任务调度”、“结果返回”、“结果解析”等环节,但是即便如此,以上操作的也能达到亚秒返回(所谓的“秒出”)。

     

    10.3性能优化

     相比传统关系数据库,蜂鸟系统的优化相对简单。从性能预测给出的公式就能看出,优化方向是:

    1. 缩减记录大小;

    2. 提高处理并发度;

    3. 增加磁盘顺序读写速。

        缩减记录大小的最简单办法是将记录中离散度不高的字段进行码表化,进而减少记录大小。比如卡口送出的原始过车记录中含有车品牌、方向等信息(如“大众”、“西向东”)就属于离散度低的字段,完全可以以数字代替,而使用码表来维护数字和实际品牌或方向间的对应关系,查询时将过车时序表和码表做Join即可。提高并发度最简单、经济的办法是增加单机所带磁盘数目,然后是增加机器。增加磁盘顺序读写速度常用办法有:使用前先格式化一次磁盘;采用“轻量”磁盘挂载方法(如ext4格式磁盘采用noatime,data=writeback,barrier=0,nobh,errors=remount-ro方式挂载);使用更对读友好的调度器DeadLine;其它内核参数微调,如增加磁盘队列长度的内核参数(sudo sh -c'echo 1024 > /sys/block/sdx/queue/nr_requests)。

    11. 最佳实践(实例介绍)

    11.1 电力-智能电表相关业务:

    n   用户用电量查询:给定用户单日查询或多日查询等。

    n   低电压异常判断:电压位于 198-205V,则认为该电表低电压异常。

    n   电能量异常判断:当前时间点的电能量值小于前一个时间点电能量值,但中间电表并没有过零的情况发生,则认为该电表电能量异常。

    n   电量/电费计算:计算一段时间内电量的消耗和电费(分时计算)。

    n   线损计算:根据各供电点 ( 电量流入 ) 和受电点 ( 电量流出 ) 的电能量数据的差值为线损。

    n   三相不平衡分析:计算电表24(整点)电流不平很曲线。计算方法三相电中最大电流减去最小电流,再除以最大电流。

    n   分析整箱有功电量曲线中相邻两个整点的跳数。相邻两点之差大鱼该亮点中最大值的%80则为跳跃。

    n   环比增长率计算:本月比上月增长情况。一般环比增长率可使用如下公式计算:(本月电量消耗值– 上月电量消耗值)/ 上月电量消耗值。

    11.2 交通-卡口监控相关业务:

    n   车辆轨迹抽取:按照给定时段检索给定车辆的行车轨迹(经过卡口的记录)。

    n   嫌疑套牌车分析:在选定的行政区划、卡口范围内利用卡口位置信息、路段时段的平均车速信息、以及车辆经过相邻卡口的耗时。当发现耗时明显过小,则可推断出现了相同号牌号码和号牌种类的车辆,即套牌车。

    n   伴随车分析:根据用户输入参数查询出指定车辆(主车)的轨迹,并根据查询出的轨迹结果分析出车辆经过相应卡口时(要求同方向)在伴随时间偏差范围出现的车辆,如果这些车辆的累计出现次数达到用户输入的伴随车轨迹次数,该车列为伴随车。

    n   碰撞车分析:在明确时间和地点,不明确车辆信息的情况下,分析在多个不相关的地点同时出现的车辆信息。

    11.3 刑侦:通讯记录检索相关业务

    n   查询给定时间范围嫌疑号码的呼入呼出记录。

    n   查询给定时间范围嫌疑邮箱的发件和收件记录。

    n   根据嫌疑人的电话、短信、邮件记录,分析嫌疑人的社会关系网。

     

    Hummer TimeSeries DB Dock DEMO 介绍文章和下载见 http://blog.csdn.net/kanghua/article/details/44653149


    展开全文
  • 时序分析:隐马尔可夫模型

    千次阅读 2016-06-06 11:29:18
    接下来我们试图去预言我们所不能观察到的"隐形"的系统状态,在上面的例子中,能被观察到的序列就是海藻的状态吗,隐形的系统就是天气情况 然后我们看一下关于我们这个模型的一些问题,在上面那个例子中,也许我们想...

         在AI综合领域,HMM模型是离散贝叶斯网络,最主要用于非确定性(概率)推理。

           上次的文章被标记为链接,真是有意思。

        

    一:隐马尔科夫模型   


           本人对这篇转载做了修改!

           英文链接http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

           文章链接:http://blog.csdn.net/likelet/article/details/7056068      此文的公式和说明更清晰一些,没有分段总结。

           文章原始链接:http://www.52nlp.cn/hmm-learn-best-practices-one-introduction

           算法杂货铺——分类之贝叶斯网络及应用:http://www.cnblogs.com/leoo2sk/archive/2010/09/18/bayes-network.html


    (一):定义及简介介绍(introduction)


    通常我们总是对寻找某一段时间上的模式感兴趣,这些模式可能出现在很多领域:一个人在使用电脑的时候使用的命令的序列模式;一句话中的单词的序列;口语中的音素序列。总之能产生一系列事件的地方都能产生有用的模式。

    考虑一个最简单的情况:有人(柯南?)试图从一块海藻来推断天气的情况。一些民间的传说认为“soggy”的海藻意味着潮湿(wet)的天气,“dry”的海藻预示着晴朗(sun)。如果海藻处于中间状态“damp”,那就无法确定了。但是,天气的情况不可能严格的按照海藻的状态来变化,所以我们可以说在一定程度上可能是雨天或是晴天。另一个有价值的信息是之前某些天的天气情况,结合昨天的天气和可以观察到的海藻的状态,我们就可以为今天的天气做一个较好的预报。

    这是在我们这个系列的介绍中一个非常典型的系统。

     

    • 首先我们介绍一个可以随时间产生概率性模型的系统,例如天气在晴天或者雨天之间变动。
    • 接下来我们试图去预言我们所不能观察到的"隐形"的系统状态,在上面的例子中,能被观察到的序列就是海藻的状态吗,隐形的系统就是天气情况
    • 然后我们看一下关于我们这个模型的一些问题,在上面那个例子中,也许我们想知道

     

    1. 如果我们观察一个星期每一天的海藻的状态,我们是否能知相应的其天气情况
    2. 如果给出一个海藻状态的序列,我们是否能判断是冬天还是夏天?我们假设,如果海藻干(dry)了一段时间,那就意味着是夏天如果海藻潮湿(soggy)了一段时间,那可能就是冬天。

     


     

    (二):生成模式(Generating Patterns)

     


    • 确定的模式(Deterministic Patterns)

    考虑交通灯的例子,一个序列可能是红-红/橙-绿-橙-红。这个序列可以画成一个状态机,不同的状态按照这个状态机互相交替

    确定的模式

    我们可以注意到,每一个状态都只依赖于此前的状态,如果当前的是绿灯,那么接下来就是橙灯,这就是一个确定型的系统。确定型的系统更容易理解和分析,只要这些状态转移都是已知的。

     

     

    • 不确定的模式(Non-Deterministic Patterns)

    为了让之前那个天气的例子更贴近现实,我们可以添加一个状态-多云。和交通灯的例子不同,我们不能得到一个确定的状态转移系统,但是我们还是希望能得到一个天气的模式。

    一种办法就是假设这个模型的每个状态都只依赖于之前的状态,这个假设被称为马尔科夫假设,这个假设可以大大的简化这个问题。显然,这个假设可能是一个非常糟糕的假设,导致很多重要的信息都丢失了。

    当涉及到天气的时候,马尔科夫假设假设如果我们知道之间一些天的天气的信息,不考虑风力、气压等因素,那么我们就能预言今天的天气。当然,和其他许多例子一样,这个列子也是不合实际的。但是,这样一个简化的系统可以有利于我们的分析,所以我们通常接受这样的假设,因为我们知道这样的系统能让我们获得一些有用的信息,尽管不是十分准确的。

    晴天雨天阴天

    一个马尔科夫过程就是指过程中的每个状态的转移只依赖于之前的n个状态,这个过程被称为1个n阶的模型,其中n是影响转移的状态的数目。最简单的马尔科夫过程就是一阶过程,每一个状态的转移只依赖于其之间的那一个状态。注意这和确定型的系统不一样,因为这种装因是有概率的,而不是确定的。下面这个图展示了天气这个例子中所有可能的一阶转移:

    一阶状态转移

    注意一个含有M个状态的一阶过程有M的平方个状态转移。每一个转移的概率叫做状态转移概率(state transition probability),就是从一个状态转移到另一个状态的概率。这所有的M的平方个概率可以用一个状态转移矩阵来表示。注意这里有一个假设,概率不随时间的变化而变化,这又是一个不现实但很重要的假设。下面就是一个状态转移矩阵的列子:

    状态转移矩阵

    这个矩阵的意思是,如果昨天是晴天,那么今天又50%的可能是晴天,37.5%的概率是阴天,12.5%的概率会下雨,很明显,每一行的和都是1。

    为了初始化这样一个系统,我们需要一个初始的概率向量:

    初始概率向量

    这个向量表示第一天是晴天。

    到这里,我们就为一阶马尔科夫过程定义了以下三个部分:

    • 状态:晴天、阴天和下雨
    • 初始向量:定义系统在时间为0的时候的状态的概率
    • 状态转移矩阵:每种天气转换的概率

    所有的能被这样描述的系统都是一个马尔科夫过程。

     

    • 总结(Summary)

    我们为了找到随时间变化的模式,就试图去建立一个可以产生模式的过程模型。我们使用了具体的时间步骤、状态、并且做了马尔科夫假设。有了这些假设,这个能产生模式系统就是一个马尔科夫过程。一个马尔科夫过程包括一个初始向量和一个状态转移矩阵。关于这个假设需要注意的一点是状态转移概率不随时间变化。


    (三):隐含模式(Hidden Patterns)


           当马尔科夫过程不够强大的时候,我们又该怎么办呢?

     

          在某些情况下马尔科夫过程不足以描述我们希望发现的模式。回到之前那个天气的例子,一个隐居的人可能不能直观的观察到天气的情况,但是有一些海藻。民间的传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合,一个可以观察到的状态集合(海藻的状态)和一个隐藏的状态(天气的状况)。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。

         一个更现实的例子是语音识别,我们听到的声音是声带、喉咙和一起其他的发音器官共同作用的结果。这些因素相互作用,共同决定了每一个单词的声音,而一个语音识别系统检测的声音(可以观察的状态)是人体内部各种物理变化(隐藏的状态、引申一个人真正想表达的意思)产生的。

            某些语音识别设备把内部的发音机制作为一个隐藏的状态序列,把最后的声音看成是一个和隐藏的状态序列十分相似的可以观察到的状态的序列。在这两个例子中,一个非常重要的地方是隐藏状态的数目和可以观察到的状态的数目可能是不一样的。在一个有三种状态的天气系统(sunny、cloudy、rainy)中,也许可以观察到四种潮湿程度的海藻(dry、dryish、damp、soggy)。在语音识别中,一个简单的发言也许只需要80个语素来描述,但是一个内部的发音机制可以产生不到80或者超过80种不同的声音。

           在上面的这些情况下,可以观察到的状态序列和隐藏的状态序列是概率相关的。于是我们可以将这种类型的过程建模为又一个隐藏的马尔科夫过程和一个和这个马尔科夫过程概率相关的并且可以观察到的状态集合。

          下图显示了天气的例子中隐藏的状态和可以观察到的状态之间的关系。我们假设隐藏的状态是一个简单的一阶马尔科夫过程,并且他们两两之间都可以相互转换。

    隐马尔科夫


            下图则明确的表示出模型的演化,其中绿色的圆圈表示隐藏状态,紫色圆圈表示可观察到状态,箭头表示状态之间的依存概率。一个 HMM 可用一个5元组 { N, M, π,A,B }表示,其中 N 表示隐藏状态的数量,我们要么知道确切的值,要么猜测该值,M 表示可观测状态的数量,可以通过训练集获得, π=i}为初始状态概率,A={aij}为隐藏状态的转移矩阵 Pr(xt(i) | xt-1(j)),B={bik} 表示某个时刻因隐藏状态而可观察的状态的概率,即混淆矩阵,Pr(ot(i) | xt(j))。在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的,即当系统演化时,这些矩阵并不随时间改变。对于一个 N 和 M 固的 HMM 来说,用 λ={ π, A, B } 表示 HMM 参数。



            隐藏的状态和可以观察到的状态之间有一种概率上的关系,也就是说某种隐藏状态H被认为是某个可以观察的状态O1是有概率的,假设为P(O1|H)。如果可以可以观察的状态有三种,那么很显然P(O1|H)+ P(O2|H)+ P(O3|H) = 1。这里我和原文的意思不太相同,原文说的意思是P(O1|H1)+ P(O1|H2)+P(O1|H3)= 1,但是这和下面的例子又不同。

           这样,我们也可以得到一个另一个矩阵,称为混淆矩阵。这个矩阵的内容是某个隐藏的状态被分别观察成集中不同的可以观察的状态的概率,在天气的例子中,这个矩阵如下图:

    混淆矩阵

    注意到图中每一行的和为1,但是每一列的和不为1,这里我觉得可能是原文出错了,或者隐藏状态还有其他。

     

    总结

    我们已经看到有一些过程是和一个隐藏的马尔科夫过程概率相关的。在这种情况下,可以观察到的状态和隐藏的状态的数目可能是不一样的。我们可以把这种过程建模为隐马尔科夫模型(HMM)。这个模型包含两个状态集合和三个概率集合。

    • 隐藏的状态:一个隐藏的马尔科夫过程
    • 可以观察到的状态:如名
    • 初始向量:初始状态的隐藏状态的概率
    • 状态转移矩阵:隐藏状态的状态转移概率
    • 混淆矩阵:隐藏状态被观察成各个可以观察到的状态的概率

    我们可以认为隐马尔科夫模型是在一个不可观察的马尔科夫过程上添加了一个可以观察到的状态集合,加上这个过程到这个集合的一些概率关系得到的。


    (四):隐马尔科夫模型(Hidden Markov Models)


    定义隐马尔科夫模型可以用一个三元组(π,A,B)来定义:

    1. π 表示初始状态概率的向量
    2. A =(aij)(隐藏状态的)转移矩阵 P(Xit|Xj(t-1)) t-1时刻是j而t时刻是i的概率
    3. B =(bij)混淆矩阵  P(Yi|Xj)在某个时刻因隐藏状态为Xj而观察状态为Yi的概率

    值得注意的是,在状态转移矩阵中的每个概率都是时间无关的,也就是说我们假设这个概率是固定的,不随时间变化。当然,这是马尔科夫模型最不切合实际的一个假设。

     

    隐马尔科夫模型的使用

    如果一个模型可以被描述成一个隐马尔科夫模型,有三个问题可以得到解决。

    前两个是模式识别的问题:

           1)根据隐马尔科夫模型得到一个可观察状态序列的概率(评价);

            2)找到一个隐藏状态的序列使得这个序列产生一个可观察状态序列的概率最大(解码)。

    第三个问题就是根据一个可以观察到的状态序列产生一个隐马尔科夫模型(学习)。

     

    1. 评价

    假设我们有很多隐马尔科夫模型(也就是说一个三元组的集合)描述不同的系统和一个可观察状态序列集。我们也许想知道哪一个隐马尔科夫模型最可能产生某个可观察状态序列。比如说,我们也许有一个海藻的“Summer”模型和一个“Winter”模型,因为海藻在夏天和冬天的状态应该是不同的,我们希望根据一个可观察状态(海藻的潮湿与否)序列来判断现在是夏天还是冬天。

    我们可以使用前向算法来计算在某个特定的HMM下一个可观察序列的概率,然后据此找到最可能的模型。

    这种类型的应用通常出现在语音设别中,通常我们会使用很多HMM,每一个针对一个特别的单词。一个可观察状态的序列是从一个可以听到的单词向前得到的,然后这个单词就可以通过找到满足这个可观察状态序列的最大概率的HMM来识别。

     

    2. 解码

    根绝可观察状态的序列找到一个最可能的隐藏状态序列。

    和上面一个问题相似的并且更有趣的是根据可观察序列找到隐藏序列。在很多情况下,我们队隐藏状态更有兴趣,因为其包含了一些不能被直接观察到的有价值的信息。比如说在海藻和天气的例子中,一个隐居的人只能看到海藻的状态,但是他想知道天气的状态。这时候我们就可以使用Viterbi算法来根据可观察序列得到最优可能的隐藏状态的序列,当然前提是已经有一个HMM。

    另一个广泛使用Viterbi算法的领域是自然语言处中标引词性。句子中的单词是可以观察到的,词性是隐藏的状态。通过根据语句的上下文找到一句话中的单词序列的最有可能的隐藏状态序列,我们就可以得到一个单词的词性(可能性最大)。这样我们就可以用这种信息来完成其他一些工作。

     

    3.学习

    从一个观察集中得到一个隐马尔科夫模型。

    第三个问题也是最困难的问题,根绝观察到的序列集来找到一个最有可能的HMM,也就是说确定一个最有可能的三元组(π,A,B)。当A,B矩阵都不是直观可测量(通过经验得到)的的时候,可以使用前向后向算法来解决这个问题。

     

    总结:

    尽管做出了一些不太符合实际的假设,但是用三元组描述的HMMs在描述真实系统并进行分析的时候具有很大的价值,并且可以解决下面这些问题:

    1. 用前向算法找到最有可能的隐马尔科夫模型
    2. 用Viterbi算法根据观察序列找到最有可能的隐藏序列
    3. 用前向后向算法决定最有可能产生某个观察集的隐马尔科夫模型的参数


    (五):前向算法(Forward Algorithm)

     

    1如果计算一个可观察序列的概率?  

     

    1.穷举搜索

     加入给定一个HMM,也就是说(P,A,B)这个三元组已知,我们想计算出某个可观察序列的概率。考虑天气的例子,我们知道一个描述天气和海藻状态的HMM,而且我们还有一个海藻状态的序列。假设这个状态中的某三天是(dry,damp,soggy),在这三天中的每一天,天气都可能是晴朗,多云或者下雨,我们可以用下图来描述观察序列和隐藏序列:

    ob

    在这个图中的每一列表示天气的状态可能,并且每个状态都指向相邻的列的每个状态,每个状态装换在状态转移矩阵中都有一个概率。每一列的下面是当天的可观察的海藻的状态,在每种状态下出现这种可观察状态的概率是由混淆矩阵给出的。

    一个可能的计算可观察概率的方法是找到每一个可能的隐藏状态的序列,这里有3^3 = 27种,这个时候的可观察序列的概率就是 Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)。

    很显然,这种计算的效率非常低,尤其是当模型中的状态非常多或者序列很长的时候。事实上,我们可以利用概率不随时间变化这个假设来降低时间的开销。

     

    2.使用递归来降低复杂度

    我们可以考虑给定HMM的情况下,递归的计算一个可观察序列的概率。我们可以首先定义一个部分概率,表示达到某个中间状态的概率。接下来我们将看到这些部分概率是如何在time=1和time = n(n > 1)的时候计算的。

    假设一个T时间段的可观察序列是:

    seq

    2a.部分概率

    下面这张图表示了一个观察序列(dry,damp,soggy)的一阶转移

    tr

    我们可以通过计算到达某个状态的所有路径的概率和来计算到达某个中间状态的概率。比如说,t = 2时刻clody的概率用三条路径的概率之和来表示:

    paths

    我们用at(j)来表示在t时刻是状态j的概率,at ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)。

    最后一个观察状态的部分概率就表示了整个序列最后达到某个状态的所有可能的路径的概率和,比如说在这个例子中,最后一列的部分状态

    是通过下列路径计算得到的:

    final

    因为最后一列的部分概率是所有可能的路径的概率和,所以就是这个观察序列在给定HMM下的概率了。

     

    2b.计算 t = 1时候的部分概率

    计算部分概率的公式是:a t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)

    当t = 1的时候,没有路径到某个状态,所以这里是初始概率, Pr( state | t = 1) = P(state),这样我们就可以计算t=1时候的部分概率为:

    ini

    因为在初始的时候,是状态j的概率不仅和这个状态本身相关,还和观察状态有关,所以这里用到了混淆矩阵的值,k1表示第一个观察状态,bjk1表示隐藏状态是j,但是观察成k1的概率。

     

    2c.计算 t > 1时候的部分概率

    还是看计算部分概率的公式:a t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)

    这个公式的左边是从混淆矩阵中已知的,我只需要计算右边部分,很显然右边是所有路径的和:

    cal

    需要计算的路径数是和观察序列的长度的平方相关的,但是t时刻的部分概率已经计算过了之前的所有路径,所以在t+1时刻只需要根据t时刻的概率来计算就可以了:

    t时刻

    这里简单解释下,bjkt+1 就是在t+1时刻的第j个隐藏状态被认为是当前的观察状态的概率,后面一部分是所有t时刻的隐藏状态到t+1时候的隐藏状态j的转移的概率的和。这样我们每一步的计算都可以利用上一步的结果,节省了很多时间。

     

    2d.降低计算复杂度

    我们可以比较穷举和递归算法的复杂度。假设有一个HMM l  =(P,A,B),其中有n个隐藏状态,我们有一个长度为T的观察序列。

    穷举算法的需要计算所有可能的隐藏序列:

    穷举

    需要计算:

    穷举

    很显然穷举算法的时间开销是和T指数相关的,而如果采用递归算法,由于我们每一步都可以利用上一步的结果,所以是和T线性相关的。(这里认为n是一个常数)

     

    3.总结

    这里我们的目的是在某个给定的HMM下,计算出某个可观察序列的概率。我们通过先计算部分概率的方式递归的计算整个序列的所有路径的概率,大大节省了时间。在t=1的时候,使用了初始概率和混淆矩阵的概率,而在t时刻的概率则可以利用t - 1时刻的结果。

     

    2、前向算法的定义

    我们使用前向算法去计算T长度序列的概率:

    seq

    每一个y就是观察状态。在t=1时刻的中间节点的部分状态可以用下面的公式计算:

    def

    对于t>1的情况,部分概率的计算可以用下面的公式:

    中间

    这里,我觉得是原作者的笔误,后面的应该是bjkt+1

    这样我们就可以用递归的方式来计算所有可能的路径的概率和,最后,所有的部分概率的计算公式为

    all

    使用天气的例子,计算t = 2时刻的cloud状态的概率方法如图:

    例子

    3、总结

    我们使用前向算法在给定的一个HMM下计算某个可观察序列的概率。前向算法主要采用的是递归的思想,利用之前的计算结果。有了这个算法,我们就可以在一堆HMM中,找到一个最满足当前的可观察序列的模型(前向算法计算出来的概率最大)。


    (六):维特比算法(Viterbi Algorithm)

     

    找到可能性最大的隐藏序列

    通常我们都有一个特定的HMM,然后根据一个可观察序列去找到最可能生成这个可观察序列的隐藏序列。

     

    1.穷举搜索

    我们可以在下图中看到每个状态和观察的关系。

    re

    通过计算所有可能的隐藏序列的概率,我们可以找到一个可能性最大的隐藏序列,这个可能性最大的隐藏序列最大化了Pr(observed sequence | hidden state combination)。比如说,对于上图中的可观察序列(dry damp soggy),最可能的隐藏序列就是下面这些概率中最大的:

    Pr(dry,damp,soggy | sunny,sunny,sunny),

    Pr(dry,damp,soggy | sunny,sunny,cloudy),

    Pr(dry,damp,soggy | sunny,sunny,rainy),

    . . . .

    Pr(dry,damp,soggy | rainy,rainy,rainy)

    这个方法是可行的,但是这种计算的代价是昂贵。和前向算法一样,我们可以利用转移概率在时间上的不变性来降低计算的复杂度。

     

    2.使用递归降低复杂度

    在给定了一个可观察序列和HMM的情况下,我们可以考虑递归的来寻找最可能的隐藏序列。我们可以先定义一个部分概率d,既是到达某个中间状态的概率。接下来我们将讨论如果计算t = 1和t = n( n > 1)的部分概率。

    注意这里的部分概率和前向算法中的部分概率是不一样的,这里的部分概率表示的是在t时刻最可能到达某个状态的一条路径的概率,而不是所有概率之和。

     

    2a.部分概率和部分最优路径

    考虑下面这个图以及可观察序列(dry,damp,soggy)的一阶转移

    部分概率

    对于每一个中间状态和终止状态(t = 3)都有一个最可能的路径。比如说,在t=3时刻的三个状态都有一个如下的最可能的路径:

    path

    我们可以称这些路径为部分最优路径。这些部分最优路径都有一个概率,也就是部分概率d。和前向算法中的部分概率不一样,这里的概率只是一个最可能路径的概率,而不是所有路径的概率和。

     我们可以用d (i,t)来表示在t时刻,到状态i的所有可能的序列(路径)中概率最大的序列的概率,部分最优路径就是达到这个最大概率的路径,对于每一个时刻的没一个状态都有这样一个概率和部分最优路径。

    最后,我们通过计算t = T时刻的每一个状态的最大概率和部分最优路径,选择其中概率最大的状态和它的部分最优路径来得到全局的最优路径。

     

    2b.计算t = 1时刻的部分概率

    当t=1时刻的时候,到达某个状态最大可能的路径还不存在,但是我们可以直接使用在t=1时刻某个状态的概率和这个状态到可观察序列k1的转移概率:

    t = 1

    2c.计算t >1 时刻的部分概率

    接下来我们可以根据t - 1时刻的部分概率来求t 时刻的部分概率

    t

    我们可以计算所有到状态X的路径的概率,找到其中最可能的路径,也就是局部最优路径。注意到这里,到达X的路径必然会经过t - 1时刻的A、B和C,所以我们可以利用之前的结果。达到X的最可能的路径就是下面三个之一:

    (sequence of states), . . ., A, X(sequence of states), . . ., B, Xor (sequence of states), . . ., C, X

    我们需要做的就是找到以AX、BX和CX结尾的路径中概率最大的那个。

    根据一阶马尔科夫的假设,一个状态的发生之和之前的一个状态有关系,所以X在某个序列的最后发生的概率只依赖于其之前的一个状态:

    Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)

    有个了这个公式,我们就可以利用t - 1时刻的结果和状态转移矩阵和混淆矩阵的数据:

    alg

    将上面这个表达式推广一下,就可以得到t时刻可观察状态为kt的第i个状态的最大部分概率的计算公式:

    gener

    其中aji表示从状态j转移到状态i的概率,bikt表示状态i被观察成kt的概率。

     

    2d.后向指针

    考虑下图

    back

    在每一个中间状态和结束状态都有一个部分最优概率d (i,t)。但是我们的目的是找到最可能的隐藏状态序列,所以我们需要一个方法去记住部分最优路径的每一个节点。

    考虑到要计算t时刻的部分概率,我们只需要知道t-1时刻的部分概率,所以我们只需要记录那个导致了t时刻最大部分概率的的状态,也就是说,在任意的时刻,系统都必须处在一个能在下一时刻产生最大部分概率的状态。我们可以利用一个后向指针f来记录导致某个状态最大部分概率的上一个状态,形式化的描述为:

    pointer

    这里argmax表示能最大化后面公式的j值,同样可以发现这个公式之和t-1时刻的部分概率和转移概率有关,因为后向指针只是为了找到“我从哪里来”,这个问题和可观察没有关系,所以这里不需要再乘上混淆因子。

     

    2e.优点

    使用viterbi算法对一个可观察状态进行解码有两个重要的优点:

    1. 通过使用递归来减少复杂度,这点和之前的前想算法是一样的
    2. 可以根据可观察序列找到最优的隐藏序列,这个的计算公式是:

    exe

    where

    exet

    这里就是一个从左往右翻译的过程,通过前面的翻译结果得到后面的结果,起始点是初始向量p

     

    2.补充

    但在序列某个地方有噪声干扰的时候,某些方法可能会和正确答案相差的较远。

    但是Viterbi算法会查看整个序列来决定最可能的终止状态,然后通过后向指针来找到之前的状态,这对忽略孤立的噪声非常有用。

     

    3.总结

    Viterbi算法提供了一个根据可观察序列计算隐藏序列的很高效的方法,它利用递归来降低计算复杂度,并且使用之前全部的序列来做判断,可以很好的容忍噪声。

    在计算的过程中,这个算法计算每一个时刻每一个状态的部分概率,并且使用一个后向指针来记录达到当前状态的最大可能的上一个状态。最后,最可能的终止状态就是隐藏序列的最后一个状态,然后通过后向指针来查找整个序列的全部状态。

     

    (七):前向后向算法(Forward-Backward Algorithm

     

          和隐马尔科夫模型相关的有趣的问题就是判断一个模型的实用性(前向算法)和找到一个隐藏在可观察序列背后的隐藏序列(Viterbi算法)。当然,这两个过程都需要知道HMM的一些信息,比如转移矩阵,混淆矩阵以及初始的π向量。

         但是在很多实际的情况下,HMM不能被直接的判断,这就变成了一个学习问题,前向后向算法可以根据一系列可观察序列来对HMM进行评测。一个可能的例子就是一个很大的语音处理数据库,语音序列可能被建模为一个马尔科夫链,可观察的序列可以被建模为可识别的状态,但是不能直接获得一些其他的相关信息。

          前向后向算法理解起来并不困难,但是却要比前向算法和Viterbi算法要复杂,所以这里我们不再详细的介绍。总的来说,这个算法先对一些参数进行猜测,然后再通过评估这些参数的价值来修改这些参数,使得和给定的训练数据的误差变小,这其实是机器学习中的梯度下降的思想。

          前向后向算法的名称来源于对于每一个状态,这个算法既要计算到达这一状态的前一个状态的概率,也要计算产生终止状态的后向状态的概率,这两个概率都可以通过递归的方法来实现。对HMM参数的调整可以提高中间概率的准确性,并且这些调整是算法迭代的基础。


    详细介绍:

    根据观察到的序列集来找到一个最有可能的 HMM。 

      在很多实际的情况下,HMM 不能被直接的判断,这就变成了一个学习问题,因为对于给定的可观察状态序列 O 来说,没有任何一种方法可以精确地找到一组最优的HMM 参数λ 使 P(O | λ) 最大,于是人们寻求使其局部最优的解决办法,而前向后向算法(也称为Baum-Welch算法)就成了HMM学习问题的一个近似的解决方法。

      前向后向算法首先对于HMM 的参数进行一个初始的估计,但这个很可能是一个错误的猜测,然后通过对于给定的数据评估这些参数的的有效性并减少它们所引起的错误来更新HMM 参数,使得和给定的训练数据的误差变小,这其实是机器学习中的梯度下降的思想。

      对于网格中的每一个状态,前向后向算法既计算到达此状态的“前向”概率,又计算生成此模型最终状态的“后向”概率,这些概率都可以通过前面的介绍利用递归进行高效计算。可以通过利用近似的 HMM 模型参数来提高这些中间概率从而进行调整,而这些调整又形成了前向后向算法迭代的基础。

      另外,前向后向算法是 EM 算法的一个特例,它避免了 EM 算法的暴力计算,而采用动态规划思想来解决问题,Jelinek 在其书《Statistical Methods for Speech Recognition》中对前向后向算法与 EM 算法的关系进行了详细描述,有兴趣的读者可以参考这本书。

      类似于上面讲到的前向算法,我们也可以定义后向变量 βt(i) 来计算给定当前隐藏状态 i 时,部分观察序列 ot+1,ot+2,…,oT的概率,即:

      与前向算法类似,我们也可以通过迭代算法有效计算 βt(i),计算公式如下:

      其中

      进一步我们可以发现

      因此

      下面开始介绍前向后向算法

      首先我们需要定义两个辅助变量,这两个变量可以用前文介绍过的前向变量和后向变量进行定义。

      第一个变量定义为 t 时状态 i 和 t+1 时状态 j 的概率,即

      该变量在网格中所代表的关系如下图所示:

      

      该等式等价于

      利用前向变量和后向变量,上式可以表示为

      第二个变量定义为后验概率,也就是在给定观察状态序列和HMM的情况下,t 时状态 i 的概率,即

      利用前向变量和后向变量,上式可以表示为

      因此,下式为在任意时刻状态 i 的期望,也就是从状态 i 转移到观察状态 o 的期望

      同样,下式也就是从状态 i 转移到状态 j 的期望

      我们可以发现定义的这两个变量之间的关系为

      下面介绍前向后向算法的参数学习过程,在学习的过程中,不断更新 HMM 的参数,从而使得 P(O | λ) 最大。我们假设初始的HMM 参数为  λ={ π, A, B },首先计算前向变量 α 和后向变量 β,再根据刚刚介绍的公式计算期望 ξ 和 ζ,最后,根据下面的3个重估计公式更新 HMM 参数

      如果我们定义当前的HMM 模型为 λ={ π,A,B },那么可以利用该模型计算上面三个式子的右端;我们再定义重新估计的HMM 模型为那么上面三个式子的左端就是重估的HMM 模型参数。Baum 及他的同事在70年代证明了因此如果我们迭代地计算上面三个式子,由此不断地重新估计HMM 的参数,那么在多次迭代后可以得到HMM 模型的一个最大似然估计。不过需要注意的是,前向后向算法所得的这个最大似然估计是一个局部最优解。

     


     

    总结(summary)

     

    通常一个特别的模式不是单独的出现,而是作为某一个时间段下的序列出现。对于以时间为单位的过程有一个假设,一个状态的出现之和其前N个时间单位的状态有关系,这样就是一个N阶马尔科夫链,最简单的情况就是一阶马尔科夫链。

    很多情况下,真实的状态序列是不能被直接观察到的,但是可以在一定概率下被间接观察到,这个观察的结果就是另一个可观察的序列,这样我们就可以定义一个隐马尔科夫模型,这个模型在现在的某些领域体现了很大的价值,尤其是语音识别。

    这种关于真实序列的模型有三个相关的问题:

    1. 评价:一个给定的模型在多大的概率下能产生某个可观察的序列,这个问题可以用前向算法来解决。
    2. 解码:给定一个模型和某个可观察序列,最可能的隐藏序列是什么,这个问题可以用Viterbi算法来解决。
    3. 学习:给定某个可观察序列,怎么知道这个模型的一些参数,这个问题可以用前向后向算法来解决。

    隐马尔科夫模型在分析真实系统的时候表现出了巨大的价值,但是它也有一些缺点,一个最大的缺点就是由于之前的假设导致的过于简化——一个状态只依赖其之间的状态,而且这种依赖是时间无关的。

     

    一个更详细的关于HMMs的介绍可以参见

    L R Rabiner and B H Juang, `An introduction to HMMs', iEEE ASSP Magazine, 3, 4-16.


      参考资料:

      1.http://blog.csdn.net/eaglex/article/details/6376826

      2. http://en.wikipedia.org/wiki/Markov_chain

      3. http://en.wikipedia.org/wiki/Hidden_Markov_model

      4. Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.

      5. L. R. Rabiner and B. H. Juang, “An introduction to HMMs,”IEEE ASSP Mag., vol. 3, no. 1, pp. 4-16, 1986.

      6. http://jedlik.phy.bme.hu/~gerjanos/HMM/node2.html

      7. http://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html

      8. 隐马尔可夫模型简介,刘群

           9.这个................................................................................................



    展开全文
  • Javascript的时序和同步机制

    千次阅读 2011-09-28 20:21:22
    http://dev.opera.com/articles/view/timing-and-synchronization-in-javascript/> 时序问题是Javascript应用程序中最难解错误的来源之一。在开发中从来不出现的问题可能在终端用户的慢速网络和机器上冒出

    <译自http://dev.opera.com/articles/view/timing-and-synchronization-in-javascript/>

    时序问题是Javascript应用程序中最难解错误的来源之一。在开发中从来不出现的问题可能在终端用户的慢速网络和机器上冒出来。这些问题也可能是间断性的,难以重现。

    考虑一个简单的例子:一个按钮,以及与之关联的事件处理函数。当按钮被按下时,其它元素被修改。如果用户在将被修改的元素被解析生成前按下按钮,脚本将会失败。开发人员可能不会注意到这个问题,因为他是在快速的网络和机器环境下测试的,在这种环境下整个页面的解析和生成只在一瞬间就完成了。

    本文将尝试解释当前浏览器中各种跟时间有关的Javascript问题。

    基本知识

    浏览器窗口有一个线程来执行HTML的解析、事件派发以及Javascript代码的执行。Javascript代码以下面两种方式之一执行:

    1. 在<script>标签中的顶级代码在页面载入时执行。
    2. 事件处理函数在事件派发过程中被处理。

    由浏览器发起这两种执行,它们都在同一个线程中运行,任何时候都只有一个代码单元在运行。

    基本上浏览器由事件驱动(代码通过响应用户输入而运行),但在页面载入期间,还受解析线程的驱动。

    事件流

    事件是浏览器发出的一个信号,表明窗口正要发生,或者已经发生了某件事。

    事件处理程序是一个Javascript函数,注册到一个对象和事件名上。当对应的事件发生在注册的对象上时,事件处理程序即被调用。

    所有的事件处理程序都是顺序执行,在任何一个事件完全处理完毕(包括事件沿DOM树冒泡及缺省响应)之前,下一下事件不会被处理。

    缺省响应

    缺省响应是浏览器事件模型中的最有意思的一环:它发生在没有任何Javascript代码需要执行的时候。比如,一个链接上的点击事件的缺省响应是导航到该URL上。单选框按钮的点击事件的缺省响应是选中该单选框,等等。

    缺省响应并不是一个事件处理程序,我们不能移除它或者改写它,这一点是与我们的自定义事件处理程序不同的地方。但是,我们可以在事件派发过程中使用'preventDefault'函数来取消缺省响应的执行(在IE中通过event.returnValue来取消)。即使缺省响应被取消,相关的自定义事件处理器仍然会被激发,只是在此之后,缺省响应不再执行。

    派发序列

    象load这样的事件只发生在相应的对象上('window'或者'document')。然而,针对文档里特定元素的事件,则在它们祖先级别节点的事件处理程序也会被激发。
    当事件在目标节点上被激发之前,存在一个'捕获(cpaturing)'阶段,即位于目标节点的祖先节点上的那些节点可能截获事件。然而事件捕获并不是在所有的浏览器上都能可靠工作。
    事件'起泡',即当它们在目标元素上激发之后,会依次在DOM树上的祖先节点上也得到激发,直到遇到document对象,则在所有浏览器上适用。
    事件在所有相关元素上被激发以及执行缺省响应,被称作事件派发。
    对非冒泡事件,派发顺序是:
    1. 捕获阶段:事件从上至下发生在所有祖先节点上。
    2. 事件在目标元素上激发,即注册在该元素上的事件处理程序被执行(以不确定的顺序)。
    3. 缺省动作被执行(如果没被某个处理器取消掉)。

    对冒泡事件,派发顺序是:

    1. 捕获阶段:事件从上至下发生在所有祖先节点上。
    2. 事件在目标元素上激发。
    3. 冒泡阶段:事件在所有祖先元素上被激发,从下而上。
    4. 执行缺省响应(除非被某个事件处理器取消)。

    通过调用'stopPropagation()(在IE中是cancelBubble())可以防止事件继续冒泡,但缺省响应仍然会执行。因此取消冒泡和取消缺省响应是分开和独立的操作。

    事件模型的每个阶段在DOM 3 Events规范中有详细地解释。

    存在着一些奇怪的情况,缺省响应会在事件派发之前产生--但可能依然被取消。举例来说,当一个单选框被点击一,勾选标志被生成,'checked'属性也在事件派发前就已更新。然而,如果缺省动作在事件派发过程中被取消,那么该update会在缺省响应阶段被回滚:勾选标志被移除,'checked'属性被翻转回去。

    批量事件

    一些事件成批到来:用户的一次输入会导致多个事件被派发。比如,当焦点从一个表单字段移到另一个字段时,前一个字段上发生'blur'(失去焦点)事件,后一个字段上发生'focus'(焦点移入)事件。两个事件在概念上是同时发生(因为它们是对同一个用户输入的响应),但实际上还是顺序派发。

    如果是冒泡事件,则只有该事件的捕获/冒泡阶段和缺省响应完全执行以后,下一个事件才会被派发。

    该顺序的一个例子是鼠标点击某个按钮并释放的动作。此时'mouseup'事件和'click'事件都被激发,顺序是:

    'Mouse-up'事件的派发:

    1. 'click'事件的派发阶段--所有捕获事件处理器都已执行。
    2. 目标元素:事件在目标元素上激发。
    3. 'mouseup'的冒泡阶段:事件在所有祖先级元素上激发。
    4. 缺省响应(本事件无缺省响应)。

    'Click'事件的派发

    1. 捕获阶段-所有捕获处理器都已执行。
    2. 目标元素:事件在目标元素上激发。
    3. 冒泡阶段:'click'事件在所有祖先级元素上激发。
    4. 'click'的缺省响应被执行。

    在事件派发中只能取消本事件的缺省响应。例如,'mouseup'事件处理程序取消了缺省响应(无意义,因为'mouseup'没有缺省响应)。这并不会阻止'click'事件的激发,因为它们是不同的事件。

    然而,缺省响应可能引起其它事件。假如在'submit'按钮上发生一个'click'事件,其缺省动作是提交当前的表单,因此进而产生一个'submit'事件。因此,取消'click'事件上的缺省响应也一并取消了下一个事件。

    事件队列

    事件的派发是为了响应用户输入(通过鼠标或者键盘),或者象页面载入完成这样的内部事件。然而,输入和派发是两个异步操作。

    用户输入可能发生在事件处理器正在执行的时候。这时动作被缓冲起来,当事件派发器再次执行时,这些被缓冲的动作对应的事件被一一派发。事件总是以正确的顺序派发,但在动作和事件派发之间可能会有明显的延迟,如果某些事件处理器代码比较花时间的话。

    当事件处理器执行时,IE和Mozilla完全停止对用户的响应,就连工具条也会看上去被锁住一样。尽管用户可能可以进行某些操作,比如点击按钮,但这些动作都只是被缓冲起来,而且不会有任何可见的反馈。这可能看上去让用户困惑,他们极有可能重复点击按钮,从而造成不期望的后果。甚至用户可能认为浏览器已经崩溃,因为它似乎停止响应。

    Opera比起来更能响应用户操作,比如如果在脚本还在执行时点击了一个按钮,它能对用户的操作给出可见的反馈。然而,事件仍然被存入缓冲队列,仍然要顺序派发,就象其它浏览器所做的那样。因此缺省响应直到事件处理完毕之前,也不会被执行。同样,这也会使用户困惑,尽管可能不如象IE和Mozilla那样。

    基本准则是,事件处理代码不能占用太多时间。特别要当心异步的XMLHttpRequest请求,因为它们可能造成显著的延迟,从而冻住浏览器或者文档窗口。

    嵌套事件

    有一个特别的场合,事件不是序列化的,而是嵌套的。如果在脚本中通过dispactchEvent(在IE中是fireEvent方法)方法来显式地发出一个事件,该事件会被立即派发。只有当该事件(也包括缺省响应)处理完成后,原来的脚本才会继续运行。

    同样,DOM变更事件(这些事件在IE中不支持)也会被立即派发,并与DOM变更同步,比如当appendChild()被调用时。

    渲染的时机

    编程方式修改的DOM或者样式并不会立即被渲染呈现给用户。这一切取决于浏览器的实现。

    例如,如果某元素的背景色被改变,DOM会立即反映这一修改(而且DOM修改事件会被立即派发且同步处理),但我们不能确知何时浏览器引擎会将该变化呈现在屏幕上。似乎Opera会立即将修改渲染出来,而Mozilla和IE则会等该事件处理完毕之后才做渲染。

    Timeouts

    方法setTimeout将指定的函数计划在指定的时间以后被调度执行:

    window.setTimeout(someFunc, 1000);

    定时脚本在某种程度上象事件处理器一样工作。尽管它们是响应某个超时,而非用户输入,但象用户事件一样被事件分派线程顺序处理。

    因此,你不能指望超时函数在指定的时间被运行。如果其它事件或者批量事件正在执行,超时脚本会被排入队列等待。基本上我们可以确保该函数会在1秒中以后执行,但可能要等待的时间会长于1秒。

    令入惊讶地由此产生了一个有用的功能。如果一个处理程序注册为超时0秒后执行,处理程序不会被立即执行,而是被立即存入队列。它会在当前事件(包含缺省响应)执行完毕后立即执行。如果超时事件在一批事件的处理程序中间被创建(比如blur/focus,mouseup/click),超时事件会在该批事件完全完成后被调度。

    <译注:在“长时间运行的脚本”一节,作者演示了为什么这个功能实际上相当重要。>

    非用户事件

    其它非用户发起的事件有:

    • 页面加载事件
    • 超时事件
    • 异步XMLHttpRequest操作数据接收完成时的回调

    这些事件象用户发起的其它事件一样被放入事件分发队列。这意味着,XMLHttpRequest响应处理程序不会在数据接收完成时立刻调用,而是被排在事件分发队列中等待执行。

    Alerts

    警告对话框(以及相关联的confirm/prompt对话框)有一些奇怪的特性。

    当脚本发起对话框后,脚本被挂起,只到对话框关闭。从这个意义上讲它们是同步执行的。脚本等待alert()函数返回后才能继续运行。

    微妙的是有一些浏览器在alert对话框出现并等待用户操作时仍然允许事件分发。这意味着当脚本被挂起,等待alert()函数返回时,其它事件分发处理中的还可能有函数运行。

    用户接口事件,比如mouseup和click不会在alert对话框存在期间被激发,因为alert对话框是模态对话框且捕获所有用户输入。但非用户发起的事件,比如页面加载,超时事件和异步XMLHttpRequest事件仍然有可能被激活。

    页面载入

    浏览器下载文档时的同时也渐进式地解析和渲染页面。

    大多数外部资源,如图片,插件媒体,是被异步地载入的。当解析器遇到img,embed,iframe和object标签时,会产生一个新的线程。这个线程会在主页面解析线程之外独立地下载、解析和渲染该外部资源。在iframes中的页面也是异步加载的。

    外部样式表是一个例外。一些浏览器象对待图片一样异步地下载它们,一些浏览器同步下载它们,以避免样式表载入时全部重新渲染整个文档。(这也防止了早期已显示的内容在更换样式表时闪烁)。换句话说,不要依赖这些特殊的行为。

    Javascript块的执行

    脚本元素被同步解析。当一个脚本元素指向外部链接时,页面的解析工作暂停,直到该外部脚本完全下载并解析运行之后才恢复。

    内联脚本块在结束标签遇到时完成解析并执行。

    脚本块的执行

    Javascript脚本分两阶段处理。先是解析,然后是执行。在解析阶段,验证代码是否符合语言规范,如果有语法错误,脚本不会被执行。

    在执行阶段,所有顶级语句会被执行。顶级语句是指除开函数内部代码以外的所有语句。顶级语句可能含有对同一块代码中函数的前向引用,由于函数的声明已经在代码解析阶段被处理过了,所以下面的代码可以工作:

    <script>
      var x = getMagicNumber();
      function getMagicNumber() { return 117; }
    </script>

    然而,下面的代码不会工作,因为函数表达式的求值是在运行时完成的:

    <script>
      var x = getMagicNumber(); // ERROR! getMagicNumber is undefined!
      var getMagicNumber = function() { return 117; }
    </script>

    下面的代码也不能正常工作,因为代码段都是在遇到结束标签时立即执行的:

    <script>
      alert(getMessage());
    </script>
    <script>
      function getMessage() { return "Hello!"; }
    </script>

    使用document.write()

    脚本可能使用document.write()直接产生HTML输出。该输出首先被缓存,直到该段脚本结束执行时才被解析。输出中可能又包含脚本段,它们会在解析的过程中被执行。

    生成的HTML输出紧跟在当前脚本段的后面。

    DOM构建

    解析器在页面加载时增量式地构建DOM树。每遇到一个新标签,一个空的元素就被插入到DOM树中。当开始标签解析完成后,一个非空标签就被插入到DOM中<译注:原文:An empty element is inserted in the DOM when the tag is parsed. A non-empty element is inserted when the opening tag is parsed.可能是指元素的属性值指定在开始标签中,因此当该标签解析完成时,元素就不为空。>例如,当解析器开始解析文档内容时,body元素就在DOM中存在且可用了。

    注意DOM不一定完全对应输入的HTML内容。例如HTML和head标签,即便它们不出现在HTML中,这些元素也会被构建在DOM中。

    如果HTML源代码无效,比如,title元素出现在body元素中,浏览器会重调DOM,使之有效。因此不能认为DOM树的构建是按序构建的。

    延迟的代码段加载

    脚本的同步加载有一个缺点:如果文档头里有太多代码要下载和执行,那么页面的渲染可能就会有显著地延迟。

    为了减轻这个副作用,我们可以使用script元素的defer属性值。该属性指示浏览器可以异步加载脚本。然而,我们不能肯定当脚本执行时,它是在页面加载完成以前还是以后。Opera浏览器则完全忽略该属性。

    <script defer> 
       alert("this message will appear at some unpredictable time during page load"); 
    </script>

    延迟脚本不能使用document.write(),因为它们不与解析器同步。

    脚本块总是按他们在文档中出现的顺序来执行,无论它们是否有着defer属性。因此,如果没有defer属性的脚本元素在有defer属性的元素后面,解析器必须先完成延迟脚本的加载和执行,然后才能进行非延迟脚本的解析和运行。这就消除了defer属性的意义,因此必须将非延迟脚本始终放在延迟脚本的前面。

    由于这些原因,defer属性在决定代码段运行时机上并不可靠,它仅仅允许部分浏览器在处理一个代码段的同时继续解析文档。

    渐进式渲染

    页面的视觉呈现的渲染并非与DOM构建同步。这个时机基本无法预言。取决于网络速度和页面大小,浏览器可能等到整体页面完全下载完毕后再渲染,也可能一次渲染一小部分。

    当页面开始渲染时,用户接口就开始响应用户输入事件。如果事件处理程序引用了还未生成的DOM元素,这就可能导致前向引用问题。

    可能出错的代码示例:

    <button 
    οnclick="document.getElementById('lamp').backgroundColor = 'yellow'">
      Click here to turn on lamp!
    </button>
    <div id='lamp'>O</div>

    问题可能发生在当用户点击按钮时,lamp元素还没有生成。事件处理程序应该避免引用在其后定义的元素。

    在更为复杂的用户接口中,想要在页面控制间避免前向引用可能是不切实际的。相反,所有控制应该一开始处于禁用状态,直到'onload'事件处理程序来激活它们。此时可以确保所有页面元素都已加载。

    注意'onload'事件需要等待所有的图片(以及桢等)完成加载。如果页面上有一些大的图片,这可能需要占用一时间。一个变通方法是在页面底部嵌入一个内联脚本,来激活整个页面。这将在页面完成加载时得到执行,但不依赖外部资源的加载。

    长时间运行的脚本

    理想地,Javascript代码不应该长时间运行,因为它们会中断用户体验。然而有时候可能无法避免这些长时间运行的脚本。在这种情况下,应该给用户显示一个“请等待”的消息或者进度条,来指示浏览器并没有死掉。问题是这条消息必须在可能长时间运行的处理开始之前就要显示。

    下面是一段示例伪代码:

    headlineElement.innerHTML = "Please wait...";
    performLongRunningCalculation();
    headlineElement.innerHTML = "Finished!";

    在IE和Mozilla中,“请等待”的消息并不会向用户显示,因为该消息只在脚本结束时,浏览器才会将其渲染到飞屏幕上。在Opera中,“请等待”消息则会在计算正在进行时显示。

    如果我们想要消息也能正常地在IE和Mozilla中显示,我们必须将立即控制交还给UI,以便消息可以在计算开始前被渲染:

    headlineElement.innerHTML = "Please wait...";
    function doTheWork() {
       performLongRunningCalculation();
       headlineElement.innerHTML = "Finished!";
    }
    setTimeout(doTheWork, 0);

    现在setTimout的技巧保证了消息在浏览器被阻塞前就能显示出来。当然浏览器仍然可能在计算进行时被“冻”住,因此这个技巧并不是十分优雅。如果我们想要完全防止浏览器被“冻”住,则需要将计算进程分解成一些小的函数,并使用setTimeout将它们链接在一起。不过这样立即就增加了代码的复杂度。

    竞争条件

    每个窗口(以及桢)都有自己的消息队列。

    在Opera中,每个窗口都有自己的Javascript线程。在iframes中的窗口也是这样。结果是在不同桢中激活的消息处理程序可能同时执行。如果这些同时执行的代码共享了数据(比如顶层窗口的属性),我们就有可能遇到竞争条件。

    我不在此赘述竞争条件的危害,只想指出这可能导致非常令人困惑的错误。

    解决方案之一是,让消息处理函数始终在顶层窗口的消息处理队列中排队,即使它们是被其它桢激发的事件。

    假设一个页面含有一个iframe。这个iframe有一个页面'onload'处理函数,将在页面中执行。

    // bad onload function in frame:
    window.top.notifyFrameLoaded()

    这样做是危险的,因为'onload'事件可能在包含页面执行其它脚本时执行。该消息可以被放入队列:

    // good onload function in frame
    window.parent.setTimeout(window.top.notifyFrameLoaded, 0)

    这段代码中重要的部分是使用setTimeout将消息处理排入父窗口消息队列中。

    关于时间的建议

    • 不要写长时间运行的脚本
    • 不要使用同步的XMLHttpRequest
    • 不要使在不同桢中激活代码访问全局状态。
    • 不要使用alert对话框来调试,因为这有可能完全改变程序的逻辑。
    展开全文
  • 分析方法的选择 在分析预测中主要提供了几种时间序列的分析方法包括指数平滑法ARIMA模型和季节调整方法 在分析预测中提供了时间序列分析的图形工具包括序列(Sequence)自相关函数和偏自相关函数等 另外也可利用...
  • 通过对数据的分析,我们就可以知道: ①1是根据trend画出来的,2是根据weekly画出来的,3是根据yearly画出来的。 ②因为是加法模型,有:forecast['additive_terms'] = forecast['weekly'] + forecast['yearly...
  • 再后来的嵌入式开发使用DSP处理器和RTOS实时操作系统,硬件部分也变得集成度更高更复杂,嵌入式工程师对硬件方面的掌控和要求也越来越低,仅限于看原理,配置一些I/O引脚和寄存器,原理设计基本都交给专门的硬件...
  • 麦克斯韦预言了电磁波的存在,总结出电场和磁场的强度仅用电流和电压就可以简单的关联起来。著名的麦克斯韦方程最初是由近20个方程来表示电路的几个可测性质之间的关系,海维塞修订了麦克斯韦理论形成了4个方程,...
  • Linux常用的英文总结

    千次阅读 2017-08-13 12:59:37
    1. file [fail] n。文件;诉 保存文件 2。命令[k ??mɑ:nd] n。命令,指令 3。使用[ju:z,ju:s] v。使用,用途 4。程序[?pr?ugr?m] n。程序 5。line [lain] n。(数据,程序)行,线路 ...设置,n...
  • 在实时系统中,操作的正确性不仅依赖于逻辑设计的正确程度,而且与这些操作进行的时间有关,也就是说,实时系统对逻辑和时序的要求非常严格,如果逻辑和时序控制出现偏差将会产生严重后果。 实时系统 主要通过三个...
  • 【杂文】宇宙思辨

    2016-12-16 23:20:16
    在管理的角度来说,如何让多人形成一个团队协同工作,就是要把人的大脑链接在一起,有时序地进行工作,这个非常类似大型计算系统,将多个计算节点链接在一起进行计算,组成一个整体服务,目前已经有科学家探索如何...
  • 决策树的功能是预言一个新的记录属于哪一类。 决策树分为分类树和回归树两种,分类树对离散变量做决策树,回归树对连续变量做决策树。 通过递归分割的过程来构建决策树:1 寻找初始分裂,整个训练集作为产生...
  • Turing,1912-1954)发表了著名的《论应用于决定问题的可计算数字》一文,提出了思考实验原理计算机— 灵机的概念。 以后经过一百多年的电磁学、电工学、电子学以及真空电子二极管、电子三极管的发展和应用,为...
  • 常用计算机英语词汇

    千次阅读 2007-10-21 09:35:00
    1. file n. 文件;v. 保存文件 2. command n. 命令,指令 3. use v. 使用,用途 4. program n. 程序 5. line n. (数据,程序)行,线路 6. if conj. 如果 7. display vt. 显示,显示器 8.
  • 点击左上方蓝字关注我们今晚,「李宏毅机器学习特训营」第五场大神直播直播准时到达!吴恩达曾预言:“未来,真正的人工智能会落在无监督学习和强化学习上。”然而目前的研究深度还无法到达这一水平,...
  • 宇宙起源的奥秘与引力波的发现

    千次阅读 2014-04-29 05:30:55
    请看下:  这是设立在南极的大型射电望远镜,专门用于探索宇宙起源的奥秘。大家知道,南极洲是地球上最少受到人类无线电干扰的地区,因为这个射电望远镜的使命是探测宇宙中最微弱的无线电信号,不能受...
  • 并发编程虽不是新的概念,最近却逐渐热门起来。一些编程语言,如Erlang、Haskell、Go...正如摩尔定律①所预言的那样,芯片性能仍在不断提高,但相比加快CPU的速度,计算机正在向多核化方向②发展。正如Herb Sutter所...
  • 并发模型

    千次阅读 2015-06-11 10:21:18
    原文地址: 并发编程虽不是新的概念,最近却逐渐热门起来。...正如摩尔定律①所预言的那样,芯片性能仍在不断提高,但相比加快CPU的速度,计算机正在向多核化方向②发展。正如Herb Sutter所说,“免
  • 诱人的Siri 开启人机交互的大门

    千次阅读 2011-11-20 17:14:40
    Siri,苹果新发布的手机 iPhone 4S 的语音助手功能,正在成为大家热议的话题,而我们预言,它极有可能开启个人电脑类产品应用的新篇章,人机交互将真正进入大家的生活。   智慧诱人的 Siri 带来人机交互热 一场...
  • 走钢索的人---走出软件作坊:三五个人十来条枪 如何成为开发正规军(十七)http://blog.csdn.net/david_lv/archive/2008/06/15/2548210.aspx读后感:如果说程序员是艺术的创造者,那么架构师就是艺术的预言家。...
  • 引言 众所周知,自从20世纪70年代出现蜂窝网通信以来,世界各地移动通信行业得到了迅猛的发展,而蜂窝网的技术本身也得到了长足的进步。...不少专家预言,21世纪将是CDMA通信广泛应用的时代。 CDMA蜂窝网...
  • 人月神话读后感言2

    2013-03-08 08:31:46
    三、《人月神话》是预言了未来还是控制了未来?  事实是:我们现在的很多工程知识,——无论是从书上看到的,还是从实践中体验到的——大多未曾脱离《人月神话》之所言。  我在开篇中说《人月神话》“是一本可怕...
  • 三、《人月神话》是预言了未来还是控制了未来? ===== 事实是:我们现在的很多工程知识,——无论是从书上看到的,还是从实践中体验到的——大多未曾脱离《人月神话》之所言。 我在开篇中说《人月神话》“是...
  • 2007年03月14日 01:43:00 >>==上一节===== 三、《人月神话》是预言了未来还是控制了未来?=====事实是:我们现在的很多工程知识,--无论是从书上看到的,还是从实践中体验到的--大多未曾脱离《人月...
  • @新智元神经网络金融时序数据处理 @爱可可-爱生活基于Scikit-Learn的多标签分类模块 @爱可可-爱生活单图像去模糊算法比较研究 @爱可可-爱生活OpenAI Baselines:DQN @网路冷眼 @好东西传送门 出品,由@AI100运营...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 347
精华内容 138
关键字:

时序图语言