C++11原子操作atomic的内存顺序(memory_order)的理解

关于无锁数据类型的详细叙述,可以在无锁数据结构里面看,而内存顺序,则在无锁编程教程:简介 里面有讲。

在学习C++11的原子数据类型中,不免会遇到这样的语句——

其中第一个参数很容易理解,但第二个参数就比较奇怪了。实际上,内存乱序是由于编译器和处理器为了提升单线程程序运行效率所引入的,而第二个参数就是尝试去告诉编译器和处理器,哪些地方千万不要自以为是的乱序。

从cplusplus.com上面可以看到更加详细的定义:

可以发现,基本所有涉及到加“锁”,放“锁”的地方,都会存在这样一个memory_order参数!

要理解到这个参数的意思,还得从C++编译器的优化说起。对于一个顺序执行的语句

看起来确实是按顺序执行,先修改a的值,再修改b的值。

但是我们可以发现第3行和第4行在cpu中的顺序可以完全交换,因为a,b内存地址是独立的,交换执行顺序并不会导致任何的错误。甚至,在大部分情况下,这两个语句的执行顺序交换或重叠可以使得程序跑的更快!

在摩尔定律几近失效的今天,当然不能放过任何的优化空间,处理器在执行代码时会按照自己的理解将这类独立的语句按照另一种顺序执行。对于单线程程序,完全没有问题。但是到了多线程里面,这样的交换顺序就不对了。

这是一个通过bool实现自旋锁的代码——

不过这个程序第3行和第4行不是一个原子操作,也就是说其他线程可能在这个时候切入,导致数据访问错误。

而倘若将读取、判断、赋值合并为了一个操作。这样自旋锁就work了!这里用到了C++11的atomic<bool>类型

一个小小的问题,之前谈到了编译器会按照自己的想法交换一些代码的位置,也就是说其他线程的TODO2的代码和TODO0的代码块都有可能在编译器的优化下越过我们的加锁位置跳到TODO1里面(只要没有严格先后次序的语句都是可以随便交换顺序的)。在多线程里面,这是一个致命的问题,这个优化导致了之前的努力全部泡汤了!

怎么办呢,别忘了我们还有memory_order参数——

  • memory_order_acquire:执行该操作时,加入一个内存屏障,需要等待其他线程完成所有内存读
  • memory_order_release:执行该操作时,加入一个内存屏障,需要等待本线程完成所有内存写

有了这两个操作,TODO1中的读写语句就严格和外部的语句隔离开了,潜在的风险也就没有了。

当然,memory_order不只这些,还包括

  • memory_order_relaxed:完全不添加任何屏障
  • memory_order_consume:同acquire,但是该屏障并不阻塞无关的读操作,只阻塞有依赖关系的读写(不知道如何做到的,比较神奇)
  • memory_order_acq_rel:清空自己所在cpu的读写依赖
  • memory_order_seq_cst:最严格的屏障,要求所有cpu的读写严格依赖

这些都是我自己从网上的博客中总结的,如果有什么不对的地方还请留言告诉我。

不过看起来挺靠谱的~v~

参考链接1:https://blog.poxiao.me/p/spinlock-implementation-in-cpp11/

参考链接2:http://blog.csdn.net/yockie/article/details/8838661

参考链接3:http://www.cplusplus.com/reference/atomic/memory_order/

Alpha-Nebula:Deep Learning Stock Volatility with Google Domestic Trends

论文链接:Deep Learning Stock Volatility with Google Domestic Trends

课件链接:mhy-Deep Learning Stock Volatility with Google Domestic Trends_pptx

概述

这篇文章核心目标是,通过长短期记忆循环神经网络(LSTM)预测股市波动率,其中输入数据依赖于Google Domestic Trend这样一个搜索量指数。

Google Domestic Trend里面提取了Google中每一个关键词相对于时间的搜索量变化,当然,如果说联想到国内数据,百度指数提供了相似的操作

首先,选取若干具有代表性的词语,如bankruptcy,auto trading, travel等,将其热度指数同股价一起输入LSTM,来预测波动率。

波动率的计算公式比较有意思,

    \[\sigma = 0.511(u-d)^2 - 0.019[c(u+d)-2ud]-0.383c^2\]

其中 u=log(\frac{High}{Open})d=log(\frac{Low}{Open})c=log(\frac{Close}{Open}).

即该公式仅仅依赖于四个价格,他和MACD用不同的算法导出了几乎相似的指数,这也是一个非常美妙的地方。

本文在预测\sigma之外,也同时尝试了预测价格变化量,即

    \[r_i = log(\frac{Close_i}{Close_{i-1}})\]

只是一个label不同的问题,就不详述了。

技巧1:平滑

细粒度的数据存在较大的杂音,故希望通过增大粒度来去除杂音。这里增大粒度就存在值得合并问题

\Delta t为平滑的时间区间.

收益率由于已经取过log了,所以可以直接求和

    \[r_i^{\Delta t} = \sum^{i \Delta t}_{t=(i-1)\Delta t +1} r_t\]

搜索量合并是一个算数平均的过程

    \[d_i^{\Delta t} = \frac{1}{\Delta t} \sum^{i \Delta t}_{t=(i-1)\Delta t +1} d_t\]

波动率是一个几何平均过程

    \[\sigma_i^{\Delta t} = \sqrt{\sum^{i \Delta t}_{t=(i-1)\Delta t +1} \sigma_t^2}\]

技巧2:归一

对于任意序列A,都有归一化公式

    \[Z = \frac{A_i - mean(A)}{std(A)}\]

而对于时序A,可以加一个滑动窗口时长K进行仿照

    \[Z^A_{k,i} = \frac{A_i - mean(A_{i-k:i})}{std(A_{i-k:i})}\]

这样的归一方法,既保证了短期趋势的完整复制,还可以避免长期趋势导致的值不平均。

结论

如其他论文一样,这里还是借助其他模型进行比较,结论是:比其他模型效果更好。不过恐怕也是五十步笑百步了吧~

就这个问题而言,如果预测r_i,可能会比较有实用价值,但是预测效果会很差,毕竟确实想不出来涨跌会和这东西有什么关系。但是如果是预测\sigma_i,虽然效果不错,但是实用价值又不太高。总之感觉很鸡肋啊。

Alpha-Nebula:Short-term stock price prediction based on echo state networks

原文链接:Short-term stock price prediction based on echo state networks

展示课件链接:Short-Term Stock Price Prediction based on Echo State Network

这篇文章讲的是将Echo State Network(回声状态网络)应用于股票数据的短期预测中。我之前没有听说过ESN,而这篇文章在ESN之外的创新也不多,所以算是介绍这样一个工具吧。

Echo State Network

ESN是什么呢?这里直接应用一篇个人认为写的很好的教学文章,不过这里我也准备用简单的语言讲一讲个人的理解。

ESN拥有一个叫做reservoir的状态储存池,我们将其记为x(i)向量,对于这个x(i)向量进行某种迭代

(1)   \begin{equation*}  x(i+1) = f(W*x(i)) \end{equation*}

其中f是任意非线性函数。现在我们x(i)充当了一种Memory的角色。

接着令u(i)表示第i时刻的输入,y(i)表示第i时刻的目标输出,我们将这个输入输出加到刚才的 (1)里面,得到实际的迭代式

(2)   \begin{equation*}  x(t+1) &= f(W^{in}u(t+1) + W x(t) + W^{back} y(t)) \end{equation*}

是不是感觉这里面x(t)就像回声一样在里面荡来荡去,这里就对了。

最后输出为

(3)   \begin{equation*}  y'(t+1) = W^{out} concat(u(n+1),x(n+1),y(n)) \end{equation*}

在式子(3)里面,y'(t+1),concat(u(n+1),x(n+1),y(n))以及y(t+1)已知,则可以用线性回归训练啦。

可以看出该算法有如下特点:

  • 训练是最小二乘法,速度快
  • 不会陷入局部最优解

另外也有一些需要注意的地方:

  • W不能太大,否则可能越乘越大,可以通过W的特征值的最大值的大小来限制
  • 为了使效果更优,W最好是稀疏矩阵(比如95%的零)

使用ESN预测短期股价

先说一些论文中的细节

  • 论文中非线性函数f(x)的选择为

    (4)   \begin{equation*}  f(x)  = \frac{1}{1+e^{-\alpha x + v}} \end{equation*}

  • 通过赫斯特指数选择训练输入数据,文章里面选择了Hurst指数最接近1的序列进行训练,原因不明…… 也许是因为hurst接近1的时候,序列特征更持久?
    相关文献:Some comments on Hurst exponent and the long memory processes on capital markets
  • 通过各种技术指标可以有效的提高效果,但是可能存在过拟合,所以通过PCA来进行数据降维。

想法与疑问

  • 一般的论文都通过平均百分比误差来表示效果,感觉这东西还是不太容易量化实际的收益……
  • 这里的LinearRegression是最简单的版本,我们是否可以给他加入更多的优化,比如局部回归,或者对于不同的部分采用不同的回归,甚至可以把决策树套进来。

 

RNN学习笔记 之 回声状态网络

教程:http://jlearning.cn/2017/05/29/ESN-basic-tutorial/

为什么还可以设计出这么优美的算法!老套路,sin函数预测,使用Ridge回归测得无帮助预测一千个迭代次数后的信号,平方误差约为2.97056501322e-08。倘若将回归方法改为线性回归,则误差进一步降至3.72410472914e-28。不过如果把预测函数改为x*sin(x),则就没有那么好了,线性回归产生了一个完全随机的波动函数,而Ridge回归则产生了一个波长为(大约为输入数据中位数)长度的稳定波。不过,这是无信息预测,如果知道前一个迭代的实际结果,应该会好很多,这里就不尝试了~

RNN学习笔记 之 利用tensorflow-lstm实现sin预测

RNN用于处理不定长的序列数据,而简谐波预测就是一个很好的例子,显然,对于机器学习,sin(x)、cos(x)、a*sin(x) + b*cos(x)甚至x*sin(x)都没有任何难度上的差别。

那么我们就用RNN来预测吧!

(CNMB……由于一个偶然的错误,我发现这个问题直接线性规划类型的神经网络就可以很精确的计算出来!!!而且LSTM根本比不上!!!)

考虑

sin(a(k-1)+b)、sin(ak+b) 和sin(a(k+1)+b)的关系

sin(a(k-1)+b) = sin(ak+b-a) = sin(ak+b)cos(a) – cos(ak+b)sin(a)

sin(a(k+1)+b) = sin(ak+b+a) = sin(ak+b)cos(a) + cos(ak+b)sin(a)

sin(a(k+1)+b) = -sin(a(k-1)+b) + 2sin(ak+b)cos(a)

其中由于a我取的是整数,所以非常容易估计,于是实际上sin数列的每一项可以由前两项线性表示出来……

即使a不是整数,也可通过三角带换,得到近似于线性表达的公式

但是现在就出现这样一个问题。

既然是如此简单的问题,LSTM的表现为啥这么渣呢???

原因可能如下:

  1. LSTM变量太多了,训练会出现梯度消失的问题
  2. 使用LSTM,倒数第二项作用于倒数第一项,中间有若干非线性层,导致本来非常简单的线性组合变得非常难以模拟了!
  3. 写错了……

脑残的把最后一层加了一个sigmoid函数,然而并不知道sigmoid的返回值是一个正数,并不包含sin(x)的值域区间

 

RNN学习笔记2-Tensorflow代码阅读

Tensorflow中文文档中有非常详细的RNN实现教程,链接:

tensorflow中文文档:http://www.tensorfly.cn/tfdoc/tutorials/overview.html

但是其中对于模型本身的原理没有涉及,故理解RNN、LSTM需要另找资料:

一篇LSTM英文教程:http://colah.github.io/posts/2015-08-Understanding-LSTMs/

从文章中看出,对LSTM的理解其实就是对这张图的理解。

尝试阅读如下代码:

RNN实现文本感情判断:https://github.com/roopalgarg/lstm-tensorflow

RNN学习笔记1-RNN学习方法探究

很久没有更新了,进入了喜大普奔的暑假,也有更多时间开自己喜欢的坑了。

首先我们需要对RNN有一个初步的感觉。但是说实话百度百科搜出来的东西还真是不太靠谱。都是一堆大话连篇,没有一个附了代码……

经过一晚上的摸索,大概知道这种东西该怎么学了:

  1. Github上面搜索RNN会出现按照Star排序的RNN相关仓库,对于查找工程代码非常有用!
  2. Tensorflow中文文档中有一章专门讲RNN的,适合学习算法细节使用。

 

Tensorflow学习笔记2-MNIST数字识别

很早之前写的,鉴于之前Tensorflow学习笔记有1,不能这么轻易弃坑,所以又加了这一部分。

这是最简单的线性回归算法,理解了这种算法,其实就可以搞懂Tensorflow的运行机制了,大概就是把梯度下降的图提前建出来,然后在对于训练数据一次次在图上迭代。

接下来是我自己写的CNN代码,自以为是的用了多个不同的卷积核,具体有没有用?Who Knows?毕竟玄学

 

Python修饰器小应用——级数求和算法简化

假设我们遇到了

    \[\sum_{n=1}^{\infty} \frac{3n+5}{3^n}\]

这样一个东西,我们算出了结果,并且需要用python验算。

通过抽象,我们需要计算

    \[\sum_{n=1}^{\infty} f(x,n)\]

用普通的for语句比较麻烦,正巧python有一个叫做修饰器的东西可以简化运算,我们每次只需要把sigma内部的公式输入即可。

series_sum为一个修饰器,只用输入一次,之后我们只需要将我们的f(x,n)用series_sum函数修饰就好了,超级优美!