1700507311
数据科学家养成手册 11.1 离散的世界
1700507312
1700507313
电子计算机使用的寄存器、内存单元、磁介质存储单元、半导体介质存储单元都有一个共同的特性,那就是每个基本单元只有“导通”(1)和“截止”(0)两个状态,这是由最初的电子计算机的物理实现基础所导致的。所以,一切计算机中的数理逻辑也只能用1和0来表示。如果用1位(bit)来表示数据含义,最多只能表示2个不同的数据含义;2位就是4个;32位就是4294967296个,这也是32位电子计算机在不开启PAE(1)模式的情况下所支持的最大寻址空间——4G;64位就是18446744073709551616——16E(2)(1844.7亿亿),在现阶段的民用领域是非常巨大的数字了。
1700507314
1700507315
虽然18446744073709551616这个数字非常巨大,但在表示实数这样稠密的数据集合时仍然捉襟见肘。根据实数稠密性原理,任意两个不相等的实数之间都有无穷多个实数,也就是说,不论未来电子计算机的寻址能力是128位、256位还是32768位,对于描述整个实数域来说仍远远不够。所以,小数(浮点数)的表示只能用类似科学计数法的方式用“有效数字”乘以“10的n次方”表示。
1700507316
1700507317
在电子计算器上,通常用科学计数法表示巨大的计算结果(如图11-1所示)。根据微软的相关技术白皮书,双精度Double变量以带符号的IEEE 64位(8字节)双精度浮点数形式存储,负值的取值范围为-1.79769313486231570E+308到-4.94065645841246544E-324,正值的取值范围为4.94065645841246544E-324到1.79769313486231570E+308(3)。虽然对无限稠密的实数来说,这保留下来的区区18位有效数字和理想的实数域有着天壤之别,可对于人类现阶段的绝大部分工商业活动来说已经足够了。与有损压缩中的哲学思维一样,这些即使舍弃也对人的感知影响极为微小的因素是可以在考虑“性价比”的前提下做适当取舍的。这种思维方式在数据科学领域的实践过程中始终如一。
1700507318
1700507319
在以有限去仿真无限,以离散去仿真连续的情况下,永远存在这种问题。所以,对那些我们无法精确感知的,感知了也无法把控的,把控了也对提高效益没有意义的场合,确实需要斟酌精度提升的必要性。
1700507320
1700507321
在离散数学里有一个非常重要的概念叫作“笛卡儿乘积”(Cartesian Product)。笛卡儿乘积实际上是离散的面积、体积的概念。假设有一个集合X,有n个元素 {x1, x2,…, xn};另外有一个集合Y,有m个元素 {y1, y2,…, ym}:
1700507322
1700507323
1700507324
1700507325
1700507326
图11-1 电子计算器上的科学计数法
1700507327
1700507328
1700507329
1700507330
1700507331
用一个矩阵表示这个笛卡儿乘积的结果x2y1, x2y2, …, x2ym
1700507332
1700507333
1700507334
1700507335
1700507336
通过观察可以发现,在这样一个矩阵中,每个元素的和相当于整个矩阵的面积,也就是这样一个表达式
1700507337
1700507338
1700507339
1700507340
1700507341
与长和宽分别为n和m的矩形的面积公式
1700507342
1700507343
1700507344
1700507345
1700507346
相比。这种笛卡儿乘积同样是把正交的2个维度做了一种二重循环式的叠加,而且这种叠加在笛卡儿乘积中可以应用到多个正交维度——扩展到3个、4个或更多个维度。这种离散的视角在使用计算机解决问题的过程中非常普遍。在计算机中,建立包含很多描述对象的模型时也会用到这种视角。例如,在关系型数据库系统中,多个表之间使用JOIN连接,实际上相当于把一张一张的表看成一个一个独立的维度,进行JOIN的过程相当于在这种相乘之后的面积上进行谓词过滤或聚合操作(Group By)。
1700507347
1700507348
1700507349
1700507350
1700507352
数据科学家养成手册 11.2 成本的度量
1700507353
1700507354
理想的算法要求计算结果“准确无误”。在模型的解空间中,如果元素是离散的,就通常是计算机擅长的范围。例如,经典的“八皇后问题”(4)就是要求出所有符合要求的解(如图11-2所示),不重、不漏、不错。在这种要求下,算法的优劣就只和处理的效率有关,也就是更快的算法更好。
1700507355
1700507356
1700507357
1700507358
1700507359
图11-2 八皇后问题的一组解
[
上一页 ]
[ :1.70050731e+09 ]
[
下一页 ]