1. 云栖社区>
  2. 博客列表>
  3. 正文

简洁的序列预测算法

沙漠之鹰123 2016-04-21 13:51:24 浏览431 评论0

摘要: 计算机和人的最大区别在于,人具备彻底的学习和强大的联想能力,而计算机则不同,只能在程序员给定的框架内进行简单的学习(与其说是学习,不如说是参数微调)。 人类可以很容易的发现特有的模式,比如看下面几个例子: 然而,如此简单的模式,计算机却无法发现,但如果能让计算机学习这种模式,那无疑是非常有价值的。

计算机和人的最大区别在于,人具备彻底的学习和强大的联想能力,而计算机则不同,只能在程序员给定的框架内进行简单的学习(与其说是学习,不如说是参数微调)。
人类可以很容易的发现特有的模式,比如看下面几个例子:

image

然而,如此简单的模式,计算机却无法发现,但如果能让计算机学习这种模式,那无疑是非常有价值的。
我们的目标,是给定一串序列:

image

找出其中的规律,并能够推断之后的序列sn,直到无穷,或是序列结束。本文是笔者独立思考得到的,没有参考其他学术论文,如果有更好的方法,欢迎批评指正。


如果不限制模式的长度,那么这个问题可能是无解的,即使出现一长串的A,我们也不能就只认定这就是A的重复序列,很有可能后面会出现B。因此,必须给问题增加限制条件。

模式是递归定义的,对ID=2的例子,是ABC的重复,内部又是一个递增数组。ID=1的例子,则外部是递增数组,内部是重复。若是ABCCBAABCCBA, 则是重复,重复结构是ABCCBA。 如果要求更高,可以发现内部是一个回环。

重复

重复是最基本,最常见的模式,例如AAAAA,ABCABCABC。处理起来也非常容易:

从起始长度n=1为起点,判断之后的结构是否满足重复条件,如果满足,则算法终止,否则n++,直到n=min(MAXREPEATLEN,len(S)),此时序列不存在重复模式。

我们通常需要对重复段的长度增加限制,比如不超过10。

发现重复后,其表达就是数组[Mode]+ ,Mode为子序列,此时即可推导之后的元素。

值递增递减

考虑这样的序列:


ABCDEF...
ABCCDEEFG...
ABCEFGIJK...

它们没有重复模式,但存在子结构,子结构之间有递增和递减关系。我们的思路,是尽可能地将这种模式退化为重复模式,即可使用重复的方法。
聪明的读者可能已经想到,既然是递增递减,则可使用差分。
对第一个序列,后一个元素减去前面的元素,可得:


11111111....

第二个序列:


110110110....

第三个序列:


112112112...

之后,即可调用重复模式的分析思路,解决问题。


我们似乎还没有讨论这样的序列:


AA AB AC AD....

差分求解后,得到的是0,0,1,-1,2,-2,3,-3....这并不是一个重复的序列。
但如果按照相隔一个元素求差分,则顿时开朗:


0101010101...

因此,我们可总结值递增递减的模式分析方法:

从起始差分步进长度n=1为起点,判断之后的结构是否满足值递增递减条件,如果满足,则算法转换为处理重复模式,否则n++,直到n=min(MAXLEN,len(S)),此时序列不存在递增递减模式。

长度递增递减

这种模式,分析起来更为复杂,看下面的例子:


A AB ABC ABCD...
B EF IJK NOPQ...
1 12 112 1112 11112...

(中间的空格,是手工加上便于看清规律的)
这种规律很明显,但并不是重复,也不是值递增递减,它的子结构发生了长度上的变化。
按照上一节的思路,从左到右依次差分计算:


0,1,-1,1,1,-2,1,1,1,-3,1,1,1,1,-4....
2,1,2,1,1,2,1,1,1,1...
0,1,-1,0,0,1,-1,0,0,0,1,-1....

我想尽办法,试图能通过某种变换,获得像刚才那样简单有效的转换,发现无果。换一个思路,通过类似概率的手段来分析。仔细观察会发现,出现最多的数字是步进值,第一行和第二行都是1,第三行是0。之后按照步进值分割,就成了下面的增减/重复序列:


0,-1,-2,-3....
1,-1,1,-1,1,-1...

而且,步进值出现的次数,也是一个递增,递减序列:


1 | 1,1 | 1,1,1 | 1,1,1,1| ....
0 | 0,0 | 0,0,0....

又可以按照增减,重复序列的方式处理。

总结一下这种方式的伪代码:
原始序列S1从左到右依次差分,得到的序列S2,求取出现次数最多的数字,以此为特征分隔符,即可将序列S2分割为两个序列:

image

其中SA和SB分别为增减/重复序列。

其他更复杂的序列

大家看了以上的处理思路,是不是希望让计算机去求解公务员考试题目?不好意思,复杂的序列非常多,比如下面的序列:

image

image

这个问题靠计算机搜索,几乎是不可解的。如果硬要处理,最终会变成一个离散的多项式拟合问题,到了那个时候就一点都不酷了。

好在,现实世界的流程和结构一般没有那么复杂,比如网页的结构,消息出现的样式,重复占据了绝大多数情况。可能最多出现递增递减和重复嵌套的情况。如果是复杂的序列,上面的检测方法最少能告诉我们,这个序列不是重复/递增递减序列,可能需要用更复杂的方式来处理。对于一般的情形,这样的思路基本够用了。
另外要注意的问题是相等性。我们简化了问题的描述,将序列简化为有明确标示和序号的串。看下面的例子:


<name>zhao</name>
<job>coding</job>
<name>wang<name>
<job>eating</job>
...

这是个name,job不断重复的xml文档,在解决模式推断之前,你需要一些手段告诉计算机,第一行和第三行,在一定程度上是相等的。如果不相等,这事没戏了。

额外的有益讨论

从刚才那个例子,可以看出文法推断在自动解析上的好处:

  • 如果能够发现序列的规律,就能自动将其结构化
  • 能在一定程度上预测下一条数据是什么类型,从而提升命中效率
  • 能够发现隐含在数据结构中的规律

文法推断是一项相当复杂的命题,即使序列有特定的规律,即使能找到问题的解,解的数量可能也是非常庞大的。通常使用奥卡姆剃刀原理,即认为正确的文法总是最简单的那个。本文描述的,也只是文法推断中一个最为简单的命题,即序列的模式发现。
更多的真实情况,是序列有规律,但却是符合概率的。下面的例子:


AAC AAC AAD AAC AAC AAC AAD...

多数情况出现的是AAC,但有较低的可能性出现AAD,如果能从其中找出规律并推算概率,那么也能解决相当多的问题。不过,就需要大量的数学知识和技巧了,笔者望洋兴叹,只能感慨于造物主对人类大脑的恩赐。

一方面,在表面上看起来毫无意义的噪声,经过某种特定的数学变换,却能从中发现稳定的规律。
只要愿意,任何一串序列都能转换为一个特定的整数,而整数处理起来比序列更为简单和纯粹。序列的分解,可以对应为整数的分解。质数为什么如此重要?因为质数提供了乘法计算中不可分解的“元”。

有任何问题,欢迎各位随时讨论。 


版权声明:本文内容由互联网用户自发贡献,本社区不拥有所有权,也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:yqgroup@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

用云栖社区APP,舒服~

【云栖快讯】哪个编程语言最热门?各个专业领域的技术趋势是什么?如何才能更快速的踏上技术进阶之路……云栖社区2017中国开发者大调查火热进行!答卷可抽奖,红轴机械键盘、天猫精灵,丰富好礼大概率抽取  详情请点击

网友评论

用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 更多>

基于全网公开发布数据、传播路径和受众群体画像,利用语义分析、情感算法和机器学习,分析公众对品牌形象、热点事件和公... 更多>

大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人协同工作等功能,为您... 更多>

为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效率,降低 IT 成本... 更多>
安全技术百问

安全技术百问