导读：强化学习入门，先依次学习了q-learning，DQN，Dueling DQN；
近日在知乎浏览，发现openai更偏爱policy gradient，知乎大佬讲解说，是因为policy gradient相比dqn所需数据更少。使用较少训练数据而得到较好的结果，恰恰能减少线上成本，因此希望能理清楚为什么policy gradient能使用更少的训练数据？其与dqn的区别在哪里。
我们知道，在DQN中，我们将state经过nn网络产生Q值，根据Q值大小来选取action，而policy gradient则是将state经过nn网络直接产生采取每个action的概率，直接选取action。可是该如何判断
导读
本文主要对论文Dueling DQN https://arxiv.org/pdf/1511.06581.pdf 提出的背景知识，解决的问题，带来的优势及其原因进行一些解读和分享。
强化学习入门先学习了Q-Learning，因为states可能有千千万万，对应states*action个q-value值，随着states的增加，会有内存不够的问题。怎么办？DQN(Deep Q Network)出现了，其原理就是将state&action共同作为输入，所有action对应的q-value作为输出，将q-value函数的模拟，由DQN网络参数来替代。DQN的原理不再赘述，简单回顾一下数学公式：
$L{i}(\theta{i})=E{s,a,r,s’}[(y{i}^{QDN}-Q(s,a;\theta_{i}))^{2}]$
$y{i}^{DQN}=r+\gamma max{a} Q(s’,a’;\theta^{-})$
在这里我们依然可以用q-learning的方法去估计 $\theta$ ，但是实际这样做表现比较差（为什么？文章没说）。
后来有人提出，可以将q-target网络参数固定几轮，与此同时更新q-eval。采用这种方法，可以极大提高算法的稳定性。这种方法是属于off-policy的，因为其选择action的时候，是根据线下的greedy policy，而不是根据线上实时学到的policy。
另外一个DQN很重要的方法，是experience replay。也就是说DQN网络不仅仅记住当前的state，它还会记忆之前的state，存到memory，每次更新的时候，随机从memory里选取一些state，也就是random sample一个mini-batch的states出来。experience replay通过重复利用数据，增加了数据的有效性，又因为每次随机从记忆池抽样，可以减少每次更新所用样本的方差。
ACM（国际计算机学会）主办的推荐系统专场（Recsys）是推荐系统圈子的顶级会议，2018年ACM和spotify联合举办的Recsys challenge，本次比赛一共分为两个track，main track，只能用比赛方提供的数据，creative track，除了比赛方提供的数据还可以用外部数据。我和队友们在本次比赛的main track中，取得public board第六名的成绩，整个比赛，感谢我的老板兼队友提供的很多很好的idea，也让我对数据挖掘有了很多新的思考，这条路我还需要很多持之以恒的努力。
http://www.recsyschallenge.com/2018/
本次比赛由ACM Recsys和Spotify联合举办的recsys challenge，赛题给定了一百万的歌单数据集，版权由spotify所有，本文之后将简称该数据集为MSD，具体数据详情见以下：
每个歌单metadata包括
playlist_duration, 歌单整体时长
playlist_title, 歌单名称
track_num, 歌单的单曲数量
last_modified_time, 最后一次修改歌单的时间
track, 每首单曲
each track’s position in the playlist, 每首单曲在歌单中的位置
每首单曲的metadata包括
track_name, 单曲歌名
track_duration, 单曲时长
artist, 单曲歌手
album, 单曲所属专辑
比赛的大目标，即是自动延续歌单，给定一个歌单，歌单已经含有1-250首歌不等，要求预测出500首更高概率会出现在歌单里的单曲，按概率从高到低提交，这个任务在研究领域有个专业名称，playlist auto continuation, 本次比赛分为十个子任务：
因为此次比赛属于推荐性质的问题，大方法上，我们采用的是based-on item collaborative filtering, 针对赛题里十个子任务各自的特性，我们将十个子任务按其数据特性，分为4种case，对原有cf算法作了4个不同的改进。也是这次比赛，更让我体会到这类推荐任务，甚至数据挖掘想做好的前提，就是要深刻理解数据，根据数据的特性，来采用有效的方法，想起上周同一个比赛，老板eda发现的magic feature，提升了3个百分点，扯远了…
这个算法不作过多介绍，推荐算法老牌战斗机，简单概述就是，如果很多user喜欢item A, B, C，那么对于喜欢itemA, B的user，我给他也推荐C，简单的逻辑，好用的算法；
优点：相比based-on user collaborative filtering, based-on item计算更加efficency，因为绝大数多场景，user的数量总是远远过于item的，另外因为user的偏好往往更多元，举个例子，一个人喜欢听周杰伦的‘告白气球’，他也可能喜欢听钢琴曲‘土耳其进行曲’，这是很常见的，可是这两首歌在同一歌单出现的概率，应该不太大，同一歌单中的单曲，应该总有某个部分的相似性，促使它们被放在同一歌单。
缺点：协同过滤的算法，往往会更倾向推荐热门的歌单，使得一些小众的歌得不到重视。
上面提到，我们根据不同子任务的数据特性，将2，3，4，5，6这五种子任务，归为同一种任务，按同一算法来推荐；所用的主要方法就是based on item collaborative filtering, 这个方法几乎用在了除子任务1以外的每个子任务：
先根据提供的MSD data构建一个大的item-user矩阵，MSD data中共有100万个歌单，和2262292首distinct的单曲，歌单即是user，单曲即是item，那么这里把所有原始数据构造成了一个大的[2262292, 1000000]的矩阵，本文以后将简称这个矩阵为大矩阵， 注意，就像绝大多数推荐系统的item-user矩阵一样，这个大矩阵有很强的稀疏性，如果初始化用一个稠密矩阵去做，很可能内存就爆了，我们采用了稀疏矩阵的办法，极大的节省了内存
`
import scipy.sparse as sp
mat = sp.dok_matrix((2262292, 1000000), dtype=np.float32)
for song, pids in dic.items():
for pid in pids:
mat[song, pid] = 1
mat = mat.tocsr().sorted_indices()
`
假定歌单中有[A, B, C, D, E]五首歌，先计算A和所有歌曲（2262292）每首歌的相似度，这里的相似度就是依赖A和每首歌曲的共同歌单的数量，对于A和任一单曲，song1，假设只有单曲A出现在歌单list1, list2, list3，song1出现在歌单list3， list4，那么A和song1共同歌单的数量就是1，对song1的打分就是1，依次用A去对2262292每首歌计算共同歌曲分数；再用B去对2262292每首歌计算共同歌曲分数，接着C, D, E，把每首歌的5个结果求平均，再按每首歌得分从高到低排列，选取除掉已出现在歌单中的[A, B, C, D, E]五首歌，剩下的top500，即为我们的推荐歌单；
但这里的问题是，仅仅用共同歌单数，会导致那些热门歌曲，出现在很多歌单的歌，有更高的概率被推荐，这个时候热门的因素会胜过相似的因素，怎么办？很自然可以想到，我们可以用共同歌单数量，除以每首歌各自出现的歌单数量；这样不就可以平衡热门单曲的因素了吗。
在这个思路上，我们参考了这位大佬的论文：
http://www.ke.tu-darmstadt.de/events/PL-12/papers/08-aiolli.pdf
大佬在论文提出了一个创新的公式，简单概括，这个公式的分母除以了这首歌和被推荐的歌的出现频率的n次方的积；这样可以很好的平衡掉热门歌曲的因素，使得一些小众歌也可以被“平等对待”；
大佬的源码也给出来了，给了我们很好的参考，我们在此基础上作了修改和一些优化，因为我们的数据集更大，同时很稀疏，我们采用了稀疏矩阵方式进行计算，极大的提高了计算速度。
这两个子任务都是给定一个歌单的前n首歌，来预测推荐的500首歌。相比之前只给1首歌，5首歌，10首歌，这里的25首歌和100首歌会有一定的序列特征，这个比赛最有意思的地方，就是同一大任务下小任务各自的数据特性，深入挖掘数据特性，应数据制宜，才是提高推荐效果的关键。怎么利用这里的序列特性？之前在Task1中采用的算法，歌单的每首歌都被同等对待了，所有歌曲中一首歌和这整个歌单的相似度，由这首歌和歌单每首歌相似度的平均值来计算；但这里，我们对在靠近尾部的歌，其计算的相似度给了更高的权重，之前是简单的average, 加权重以后变成了weighted average.
这两个子任务是给定一个歌单随机位置的n首歌，来预测推荐的500首歌。我们在基本算法的基础上，应用上了SLIM。
之所以把子任务1放到最后来写，是因为这里有很有意思的创新，分享出来希望也能帮到大家。我们以上的基本算法是根据单曲-歌单的共现关系计算相似度进而推荐，但子任务1只给定了歌单名，除此之外没有过多的信息。我们想到，歌单的名字在一定程度上和歌单里的单曲是有很大的关系的，比如一个歌单叫”爱的进行时“，那很大程度，它含有大量的爱情相关的单曲，比如”告白气球“，比如”你问我爱你有多深“，等等；这个时候另一个歌单叫”爱的故事“，那这两个歌单在单曲上应该会有相当大的一部分交集，也就是说，歌单的词-单曲的共现关系也是可以用起来的！延续基本算法，我们构建了词-单曲的稀疏矩阵，作了类似cf的算法，来说说实现细节：
（1）首先是这些歌单名作了一些简单的自然语言处理，pipeline如下：
lower words -> remove repetition characters -> remove special characters
先小写所有字母，去除一个单词中连续重复出现2次以上的字母，只保留一个，最后去掉一些字母以外的特殊符号，这里因为都是英文所以不需要分词处理，source code也给出来了，参考着一个kaggle大佬的kernel写的
（2）我们在第一步处理完，可以得到clean title，这个时候，根据所有单词的unique数量，和所有单曲的数量，做一个 词-单曲的稀疏矩阵，矩阵shape是[词数量，单曲数量2262292]，假设歌单名叫’party’，把’party’这个词那一行，对应的该歌单所有出现的单曲的位置+1，当另一个歌单叫’party dance’，我们把’party’和‘dance‘对应的两行，对应的该歌单所有出现的单曲的位置+1，这样在最终预测时，比如歌单名叫’happy party’, 我们找到’happy’和’party’对应的那两行，[2, 2262292]的相似度小矩阵，求平均，得到[1,2262292]的相似度矩阵，然后和之前一样，按概率从高到低选取top500。
赛后感觉还是有很多可以提高的方法：
task 4中自然语言处理的那部分可以做得再细一点，比如去掉停用词；比如词性stemmerazation和lemmatization，这个在nltk都是有现成的python包的，可以直接调用；
再比如歌单名找词的时候，遇到没有对应词的情况，我直接返回了随机的500首，其实可以用一些fasttext预训练的word embedding, 找出现在矩阵中词集合最相似的近义词；
有一点遗憾，可能加上这些方法，应该会取得更好的名次，但学习的路漫漫，持之以恒才是王道呀。
word2vec其实本质用得也是单曲间共现的关系；类似文本，我们把每个歌单当作一个document，把每首歌当做一个单词，扔到gensim word2vec模型去训练，然后找和歌单中出现的单曲集合最相似的不包含歌单单曲的500首单曲，gensim把代码封装的很好，直接将这个集合丢进去就可以了，不需要每首歌依次计算求平均，这里的代码也分享出来吧
训练的：
https://github.com/LauraBowenHe/Recsys-Spotify-2018-challenge/blob/master/try/word2vec.py
预测的：
https://github.com/LauraBowenHe/Recsys-Spotify-2018-challenge/blob/master/try/prediction_v12.py
但效果并没有协同过滤好，印象中r-precision相差3～4个百分点。
我们想到，既然能用单曲-歌单的关系，那么artist-歌单的关系，album-歌单的关系，应该都能用吧，计算出来的相似度加权平均效果应该会更好，但实验结果发现，ensemble并无显示提高，有时候甚至有一点点下降，可能的原因，只利用这些例如单曲-歌单的共现关系的话，单曲中已经涵盖了artist和album的信息，很有可能再单独加入使得信息冗余，进而降低准确率。
facebook发了一篇很牛逼的论文，大概是说embedding everything，相关代码也开源了，尝试了一下不是很会用。。时间紧迫就没有作过多的探索放弃了
因为举办方要求所有参赛选手把代码开源，于是上github欣赏了一下其他参赛选手的方法，看到挺有意思的也作了简单的总结：
今天太累了…
待续…
Reference:
https://web.stanford.edu/class/cs224n/lectures/cs224n-2017-lecture2.pdf
正式开笔前，说说废话，下定决心把Stanford这个系列的课上一遍，好好打打自然语言处理的基础，而又因为纯听课的效果对我而言比不上同时更blog做笔记来得好，因此每日多花些时间来写一写。
说到用vector来表达词，一种很常见的方法是离散化的表达，比如one-hot representation, 什么one-hot representation? 假设一个大词库有N个词，想表达Xi, 那么我们就定义一个维度为N的vector，除了第i位为1，其他全为0，举个例子吧：
词库：I have a computer.
每个词的vector为如下形式：
I: [1, 0, 0, 0]
have: [0, 1, 0, 0]
a: [0, 0, 1, 0]
computer: [0, 0, 0, 1]
可是这样离散化表达有什么缺点呢？
于是～word2vec模型上线，相对于离散化的表达(discrete representation)， word2vec模型属于分布式表达（distributional representation)，which means “distribution of weights across weight”， 也就是说，区别于长度为整个词库数量N的vector，通常用来表示每个词的vector的维数不会很大，而每个element都有一个数，例如lingusitic: [0.7, 0.3, 0.1, 0.2, 0.5]， 这个vector称为词向量，而从单词map到vector这一步，称为word embedding。可见，word2vec通过使用较小维度的vector降低了训练模型需要的space and time complexity，词向量可以通过multiplication(点乘)计算相似性。
这个算法，是根据给定的词预测词上下文: target -> context
input layer是给定的词，output layer是预测的词上下文，盗了一张参考链接的图：
在这个模型里，我们把给定的词用one-hot representation表示，vector的长度V即为词库的词数，从input layer映射到hidden layer，我们需要初始化一个W1(VxN)将one-hot转成词向量，因为one-hot的特殊性质举例：[1, 0, 0, 0]，除了特定位置为1，其他位置都为0，因此这个转换词向量的过程，仅仅需要将词向量元素=1的对应的Wmatrix那一行copy就好了，再将hidden layer层乘以W2，得到C个v维词向量，C为word context的词数，每个词向量中，对应位置对高概率的那个词，即为预测词。
和skip-gram相反，CBOW根据词上下文环境(word context)来预测这个环境中缺失的那个词，举例
I was born in _, so my native language is Madarine. 这里很明显缺失的那个词为China, 而整个语句为word context，我们的output就是要预测的缺失的词。
再盗图一张，来自相同reference链接。
在这个模型中，input layer中输入的是给定word context中所有词(C个)的one-hot vector(V)，与weights矩阵W1(VxN)相乘，分别得到多词向量vector(N), 取平均值即为hidden layer，再由hidden layer乘以weights矩阵W2(NxV)得到output词向量v，维度为V，最高分数的那一维度对应的词就是predict word。
今天看一份代码的时候，有些python function不知其何用，想来写个博客把每次遇到的总结在一篇blog，可以时常看看。
print(__doc__)这个可以print出python file or function中注释部分，比如：
in module.py:
|
|
|
|
|
|
|
|
|
|
本文所用数据来源于https://www.kaggle.com/c/dog-breed-identification, 将基于google tensorflow中的预训练的mobilenet模型和inception v3模型，对新dataset中10200张不同狗品种照片训练新的图片分类。
|
|
https://www.kaggle.com/c/dog-breed-identification, 下载training dataset, labels.csv和test dataset,
我们直接下载得到的训练数据集中，只有所有的图片在同一个数据集，我们需要整理成模型需要的格式，即在同一个directory下，将每个label建一个subdirectory，将所有对应的图片放入当前subdirectory下，参考code可见:
|
|
注意这里：
IMAGE_SIZE, 即image resolution配置的参数：128,160,192, or 224px。当然越高的resolution可以带来更高的accuray，同时也需要更多的训练时间。
相对模型size占最大largest MobileNet的比例: 1.0, 0.75, 0.50, or 0.25. 同样，所占比例越大，accuracy越高，也需要更多的训练时间。
在这个任务中，我们希望获得更可能高的accuray，所以采取以上配置。
|
|
在后台启用tensorboard，tensorboard可以用来监控训练过程，帮助我们更好判断是否过拟合等。
训练完成后，可以在浏览器输入
or http://0.0.0.0:6006即可看到tensorboard为我们绘画的各种训练过程图像。
|
|
注意：
在这里，把我们之前预处理过的数据集，让在tf_files directory下。
optionally，我们可以添加更多的训练参数，详情可以参考
|
|
调节training steps， training rate， train batch size等等。
对于单个图片，可以用source code中的label_image.py
|
|
而针对这个狗品种分类器的任务，我们把从kaggle上下载的test dataset也放入tf_files directory下，修改了一下source中的label_image.py，增加新的文件generate_result.py, 对每个文件依次调用label_image.py，code可见
https://github.com/LauraBowenHe/dog-breed-identification/tree/master/MobileNet
|
|
这一步预测时间会比较长，大概7-8小时，生成的文件会存在/tensorflow-poets-2/output/下，我们在训练前可先手动创建这个文件夹。
inception v3的搭建和mobilenet很相似，只有在get code时有所不同。
|
|
参考以上
retrain的代码在/examples/image_retraining，我们可以直接用刚刚mobilenet模型中，/tensorflow-for-poet-2/tf_files，因为我们之前已经有把数据集都放在那里了，当然即使没有也没关系，新建一个tf_files就行
|
|
python -m retrain.py -h 可以查阅可以添加的参数
附一张训练结束的图，可见当前分类器的validation accuracy是90.3%。
调节training steps， training rate， train batch size等等。
因为我们已将生成的模型放入tf_files。我们把从kaggle上下载的test dataset也放入tf_files directory下，创建了一份label_image_inceptionV3.py，增加新的文件generate_result_inceptionV3.py, 对每个文件依次调用label_image_inceptionV3.py，code可见
|
|
这一步预测时间会比较长，比MobileNet所用的时间更长，大概在十四个小时，生成的文件会存在/tensorflow-poets-2/output/下，我们在训练前可先手动创建这个文件夹。
http://cs231n.github.io/transfer-learning/
https://codelabs.developers.google.com/codelabs/tensorflow-for-poets/#0
https://www.ouyangsong.com/2017/05/20/image-classification-retrained-based-on-inceptionv3/
string.strip([c])
//This method returns a copy of the string in which all chars have been stripped from the beginning and the end of the string.
返回一个string，是原string的copy但删除了所有的c字符。
Reference: https://www.tutorialspoint.com/python/string_strip.htm
.strip() removes all whitespace at the start and end, including spaces, tabs, newlines and carriage returns.
Reference: https://stackoverflow.com/questions/13013734/string-strip-in-python
|
|
//str是分隔符，默认是space
举例说明吧，
|
|
结果：
|
|
Reference: https://www.tutorialspoint.com/python/string_split.htm
A character is not, not, not a byte. a character is the platonic ideal of the smallest unit of textA. character encoding defines a mapping between our platonic characters and some way of representing them as bytes. Because there are many ways of representing the same character as bytes, this means that if you have a series of bytes, but do not know their encoding - even if you know the data is textual - the data is meaningless. First thing before everything, is knowing the encoding.
In python, there are three distict string types:
Conversion between the two types is meaningless without an encoding, Python relies on a ‘default encoding’, specified by sys.setdefaultencoding().
Simply set encoding with function sys.setdefaultencoding() is a solution but may not that good, since the web may use multiple different text encoding.
Here is a correction solution, referenced from: http://blog.notdot.net/2010/07/Getting-unicode-right-in-Python
var.decode('utf-8'), with the correct encoding. To encode a text string as bytes, use var.encode(encoding).str() on a unicode string, or unicode() on a byte string without a second argument specifying the encoding.Usually in python 2, for a web crawler python file, I see a lot:
|
|
But in python3, default is UTF-8 already. No point to write this again.
requests library enables use to handle form on website, is algo good at setting headers. HTTP headers contains attributes, preferences, sent by you every time you make a request to server.
Header used by a typical Python scraper using the default url lib library might send:
Accept-Encoding: identity
User-Agent: Python-urllib/3.4
Good website, https://www.whatismybrowser.com , to test browser properties viewable by server.
Usually the one setting, that really matters for websites to check for “humanness” based on, is “User-Agent”.
let’s say you need some Chinese material, just simply changing Accept-language: en-US to Accept-Language: zh.
Mobile devices have a different version of web page, so set as this:
User-Agent: Mozilla/5.0 (iPhone; CPU iPhone OS 7_1_2 like Mac OS X AppleWebKi/537.51.2 (KHTML, like Gecko) Version/7.0 Mobile/11D257)
brings a great change.
Cookies can keep you logged in on a site.
There are a number of browser plug-ins that can show you how cookies are being set as you visit and move, https://www.editthiscookie.com/ , a Chrome extension, is very good.
Request library will be unsable to handle many of the cookies produced by modern software, use Selenium and PhantomJS packages.
|
|
Even sometimes use multithreaded jobs can make your scraper faster than one single thread, but keep individual page loads and data requests to a minimum, can try to space them by a few seconds,
time.sleep(3).
Reference:
Book: Web Scraping with Python: Collecting Data from the Modern Web.
server-side redirect, depending on how it is handled, can be easily traversed by Python’s urllib library without any help from Selenium;
client-side redirects won’t be handled at all unless something is actually executing the javascript.
selenium is capable of handling these Javascript redirects in the same way; when to stop page execution? how to tell when a page is done rediecting?
Detect that redirected in a clever way by watcing an element in the DOM when the page initially loads, then repeatedly calling the element until Selenium throws a StaleElementReferenceException, the element is no longer attached to the page’s DOM and the site has redirected.
Pillow allows you to easily import and manipulate images iwth a variety of filters, masks, and even pixel-specifc transformations.
from PIL import import Image, ImageFilter
kitten = Image.open(“kitten.jpg”)
blurryKitten = kitten.filter(ImageFilter.GaussianBlur)
blurryKitten.save(“kitten_blurred.jpg”)
blurrykitten.show()
for more useful, http://pillow.readthedocs.org/
scrape text from images on webste.
Given an expression s includes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.
Examples = abc3[a] return abcaaa
s = 3[abc] return abcabcabc
s = 4[ac]dy, return acacacacdy
s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz
语法整理：
Integer.valueOf(int i)//returns an integer object holds the value of specified primitives, 返回一个保存原指定数的整数对象。
Integer.valueOf(String s)//This returns an Integer object holding the value of the specified string representation.返回一个保存原指定string的整数对象。
Stack
Character.isDigit(c) //check if a character is ‘0’-‘9’
Integer count = (Integer)stack.pop();
instanceof //check type of the object
public class Solution {
/**
* @param s an expression includes numbers, letters and brackets
* @return a string
*/
public String expressionExpand(String s) {
// Write your code here
Stack<Object> stack = new Stack<Object>();
int number = 0;
for(char c: s.toCharArray()){
if(Character.isDigit(c)){
number = number * 10 + (c-'0');
}else if(c == '['){
stack.push(Integer.valueOf(number));
number = 0;
}else if(c == ']'){
String temp = popStack(stack);
Integer count = (Integer)stack.pop();
while(count > 0){
stack.push(temp);
count--;
}
}else{
stack.push(String.valueOf(c));
}
}
return popStack(stack);
}
String popStack(Stack<Object> stack){
Stack<String> container = new Stack<String>();
while(!stack.empty() && (stack.peek() instanceof String)){
container.push((String)stack.pop());
}
StringBuilder sb = new StringBuilder();
while(!container.empty()){
sb.append(container.pop());
}
return sb.toString();
}
}