1 概述什么是自然语言处理？图灵测试图灵测试是 Alan Turing 在1950年提出的一种判断机器是否能像人类一样思考的测试。标准的图灵测试如下图所示，测试者C同时与一台机器A和一个人B进行对话，三者相互隔离并且只能通过文本的方式交流，比如键盘或者屏幕，在经过若干轮问答后，倘若测试者C不能准确地区分出A、B哪个是人哪个是机器，则机器通过测试，反之失败。NLP的定义Natural language processing (NLP) is a study of the computational treatment of human natural language.自然语言处理是语言学、计算机科学、信息工程和人工智能的一个分支，研究计算机和人类语言的交互，特别是如何通过计算机编程来处理和分析大量的语言数据。这是一轮机器与人对话的示意图，语言可以拆分为三个层次：声音信号、符号表示、语义，机器以语义作为输入输出，而人则以声音信号作为输入输出。从机器到人：$Intention \rightarrow Generation \rightarrow Synthesis$从人到机器：$Perception \rightarrow Interpretation \rightarrow Incorporation$为什么需要自然语言处理？本质上来说，自然语言是非常丰富的M. Hamel spoke of the French tongue, saying it was the most beautiful language in the world, the most clear, the most sensible. We must keep it ourselves and never forget it, because when a people if they hold onto their language it is like holding the prison key... --- The Last Lesson by Alphonse DaudetIn the beginning was the Word, and the Word was with God, and the Word was God.--- John 1:1 in the Bible从功能上来说，语言是高效而普遍的如何完成NLP任务？NLP的难点在哪里？语言是模棱两可的（ambiguous）Children make delicious snacksFried Chicken makes delicious snacksStolen wallet is found by treeStolen wallet is found by MacTrump wins on budget, more lies ahead中国足球大败德国中国乒乓球大败德国我们知道中国的乒乓球很强，所以“大败”指的是中国战胜了德国，而由于足球实在弱不禁风，肯定是输给德国了。这里有个basic concept在里面，就是人们对一个国家在不同运动领域擅长程度的判断，人类很容易做到，而机器想做到却很难。He is an unbelievable worker. (Extremely good vs. Not trustful)Vancouver Police shoot man Holding box cutter. (温哥华警察射杀持刀男子 or 温哥华警察持刀射杀男子)语境解释，比如说根据上下文确定代词的指代，这对于人类来说很简单，但对机器来说很难The book does not fit the bag, because it is too bigThe book does not fit the bag, because it is too smallEvery American has a motherEvery American has a president有时候语法正确不代表语义正确Beautiful a has Monica Flower. (syntax and semantics right)Colorless green ideas sleep furiously. (syntax right but semantics wrong)第一个句子非常正常，而第二个句子虽然语法上没有错误，但是意思上完全说不通，一个idea怎么能sleep呢？2 其他机器翻译的评价指标《机器翻译评价指标 — BLEU算法》：https://www.cnblogs.com/jiangxinyang/p/10523585.html《机器翻译评价指标》：https://www.cnblogs.com/xinbaby829/p/6955687.html
View source code on Github pageUse Gensim to train a word2vec modelUse Gensim tool to tain a word embedding model on text8 dataset and the training process is based on skip-gram architecture.Reference: [1] https://rare-technologies.com/deep-learning-with-word2vec-and-gensim/[2] https://radimrehurek.com/gensim/models/keyedvectors.html#gensim.models.keyedvectors.WordEmbeddingsKeyedVectors# import modules and set up logging from gensim.models import word2vec import logging logging.basicConfig(format='%(asctime)s : %(levelname)s : %(message)s', level=logging.INFO) # load up unzipped corpus from http://mattmahoney.net/dc/text8.zip sentences = word2vec.Text8Corpus('data/text8')# train the skip-gram model; default window=5 model = word2vec.Word2Vec(sentences, size=200)Task 1 Analogy PredictionInput: a pair of words <a,b> and a third word cOutput: the forth word d which holds "a is to be as c is to d"For example"man -> woman" => "king -> queen""Japan -> Japanese" => "Australia -> Australian""Paris -> France" => "Beijing -> China"The above task can describe as Math form:Given word vector $w_a,w_b,w_c$ to find a word vector $w_d$ satisfying:$$ w_d-w_c\approx w_b-w_a\Leftrightarrow w_d\approx w_b-w_a+w_c $$Then we solve$$ d=\mathop {\text{arg}\max}_{d\in V}\cos \left( w_b-w_a+w_c,w_d \right) =\mathop {\text{arg}\max}_{d\in V}\frac{\left( w_b-w_a+w_c,w_d \right) \cdot w_d}{|w_b-w_a+w_c,w_d|\cdot |w_d|} $$# Use gensim api test_groups = [ ('man', 'woman', 'king'), ('small', 'smaller', 'big'), ('italy', 'italian', 'china'), ('japan', 'tokyo', 'china'), ('cool', 'coolest', 'cold'), ('dark', 'darkest', 'easy'), ('listening', 'listened', 'moving'), ('looking', 'looked', 'swimming'), ('playing', 'played', 'taking'), ('increase', 'increases', 'decrease'), ('predict', 'predicts', 'shuffle'), ('provide', 'provides', 'search'), ('say', 'says', 'speak'), ('Austria', 'Austrian', 'Sweden'), ('Cambodia', 'Cambodian', 'Australia'), ('paying', 'paid', 'striking'), ('running', 'ran', 'taking'), ('selling', 'sold', 'thinking'), ('shrinking', 'shrank', 'jumping') ] for w in test_groups: print("%s -> %s like %s -> %s" % (w[0], w[1], w[2], model.wv.most_similar(positive=[w[1].lower(), w[2].lower()], negative=[w[0].lower()], topn=1)[0][0]))man -> woman like king -> queen small -> smaller like big -> bigger italy -> italian like china -> chinese japan -> tokyo like china -> shanghai cool -> coolest like cold -> kargil dark -> darkest like easy -> customers listening -> listened like moving -> penetrated looking -> looked like swimming -> rides playing -> played like taking -> took increase -> increases like decrease -> decreases predict -> predicts like shuffle -> gutter provide -> provides like search -> tutorial say -> says like speak -> speaks Austria -> Austrian like Sweden -> swedish Cambodia -> Cambodian like Australia -> canada paying -> paid like striking -> noticeable running -> ran like taking -> took selling -> sold like thinking -> thought shrinking -> shrank like jumping -> kicking words = model.wv.vocab.keys() # contains all vocabularies word2vec = model.wv # Get a certain word vector by word2vec[word]# Difine naive most_similar() function import numpy as np def cal_cosine(vec_a, vec_b): """ Compute the cosine similarity between vec_a and vec_b Input: two word vectors vec_a and vec_b Output: the cosine similarity of the two vectors """ numerator = np.dot(vec_a.T,vec_b) denominator = np.sqrt(sum(np.square(vec_a))) * np.sqrt(sum(np.square(vec_b))) return numerator / denominator def find_analogy(a, b, c): """ Find the analogy word Input: a pair of words <a,b> and a third word c Output: the forth word d which holds "a is to be as c is to d" """ a, b, c = a.lower(), b.lower(), c.lower() # lower all the letters max_cosine = -1 # initial the max_cosine value = -1 for word in words: if word in [a, b, c]: continue cosine = cal_cosine(word2vec[b] - word2vec[a] + word2vec[c], word2vec[word]) # if find a bigger cosine value, then save the cosine value and related word if cosine > max_cosine: max_cosine = cosine d = word return d for w in test_groups: print("%s -> %s like %s -> %s" % (w[0], w[1], w[2], find_analogy(w[0], w[1], w[2])))man -> woman like king -> queen small -> smaller like big -> bigger italy -> italian like china -> chinese japan -> tokyo like china -> beijing cool -> coolest like cold -> falklands dark -> darkest like easy -> difficult listening -> listened like moving -> moves looking -> looked like swimming -> perished playing -> played like taking -> took increase -> increases like decrease -> decreases predict -> predicts like shuffle -> lodewijk provide -> provides like search -> summarizes say -> says like speak -> speaks Austria -> Austrian like Sweden -> swedish Cambodia -> Cambodian like Australia -> canada paying -> paid like striking -> caught running -> ran like taking -> took selling -> sold like thinking -> realized shrinking -> shrank like jumping -> kicking # Testing data is downloaded from https://code.google.com/archive/p/word2vec/source/default/source # load the testing data set with open("data/questions-words.txt", "r") as f: total_line = 0 count = 0 no_key_num = 0 for line in f.readlines(): v = line.strip().split(" ") if v[0] == ':': # if the line begins with ":", do nothing continue try: pred_word = model.wv.most_similar(positive=[v[1].lower(), v[2].lower()], negative=[v[0].lower()], topn=1)[0][0] except KeyError: # if the word doesn't appear in the model vacabulary list no_key_num += 1 else: # v[3] is the right answer if pred_word == v[3]: count += 1 total_line += 1 acc = count / total_line print("The accuracy on the test data = %s" % acc) print("%s pairs of data were not used because of no matched word in the model" % no_key_num)The accuracy on the test data = 0.160793194874061 1440 pairs of data were not used because of no matched word in the model # Gensim API to evaluate the analogy prediction task model.wv.evaluate_word_analogies(questions="data/questions-words.txt")C:\Users\yelbee\Anaconda3\lib\site-packages\ipykernel_launcher.py:1: DeprecationWarning: Call to deprecated `accuracy` (Method will be removed in 4.0.0, use self.evaluate_word_analogies() instead). """Entry point for launching an IPython kernel. 2020-04-05 17:06:55,747 : INFO : capital-common-countries: 34.2% (173/506) 2020-04-05 17:07:01,033 : INFO : capital-world: 18.7% (271/1452) 2020-04-05 17:07:02,009 : INFO : currency: 12.7% (34/268) 2020-04-05 17:07:07,788 : INFO : city-in-state: 11.0% (173/1571) 2020-04-05 17:07:08,987 : INFO : family: 81.4% (249/306) 2020-04-05 17:07:11,881 : INFO : gram1-adjective-to-adverb: 12.3% (93/756) 2020-04-05 17:07:12,983 : INFO : gram2-opposite: 17.3% (53/306) 2020-04-05 17:07:18,473 : INFO : gram3-comparative: 63.9% (805/1260) 2020-04-05 17:07:20,422 : INFO : gram4-superlative: 34.4% (174/506) 2020-04-05 17:07:24,023 : INFO : gram5-present-participle: 30.6% (304/992) 2020-04-05 17:07:30,591 : INFO : gram6-nationality-adjective: 56.1% (769/1371) 2020-04-05 17:07:36,784 : INFO : gram7-past-tense: 27.0% (359/1332) 2020-04-05 17:07:40,974 : INFO : gram8-plural: 43.6% (433/992) 2020-04-05 17:07:43,601 : INFO : gram9-plural-verbs: 35.1% (228/650) 2020-04-05 17:07:43,602 : INFO : total: 33.6% (4118/12268) From above, we implement our own naive method to calculate cosine similarity to do analogy prediction task, it run slower than Gensim api method. Most of their prediction results are the same like:man -> woman like king -> queen small -> smaller like big -> bigger italy -> italian like china -> chineseHowever, there are some different prediction results like:Naive Method:japan -> tokyo like china -> (beijing) Gensim API Method: japan -> tokyo like china -> (shanghai) Naive Method: selling -> sold like thinking -> (realized) Gensim API Method: selling -> sold like thinking -> (thought)In the first situation, the Naive Method is right because Beijing is the capital of China and so as Tokyo to Japan. And the second pairs should describe the past tense of a word and the Gensim API Method is more correct.At last, we test our model on the Google Analogy Test Set.Task 2 Clustering TaskIn this task, we use K-Means algorithm to cluter the word into 100 groups.Input:$N$ vectors $x_1, x_2, \cdots, x_N \in \mathbb{R}^n$$k$: the number of cluters we wantOutput:$c_i (i=1,2,\cdots,N)$: the cluter that $x_i$ belongs to$z_j (j=1,2, \cdots, k)$: the representative vector of each clusterInitialization: Initialize $z_1,z_2, \cdots, z_k$ by choosing $k$ vectors from $x_1, x_2, \cdots, x_N$ randomlyStep 1: Given $z_1,z_2, \cdots, z_k$, compute$$ c_i = \mathop{\arg \min}_{j \in \{1,2,\cdots,k\}} \|x_i-z_j\|_2^2, i =1,2,\cdots,N $$and define$$ G_j = \{i | c_i=j\},j=1,2,\cdots,k $$Step 2： Given $G_1,G_2,\cdots,G_k$, compute$$ z_j = \frac{1}{|G_j|}\left(\sum_{i\in F_j} x_i \right) $$Go back Step 1 until convergent# here you load vectors for each word in your model word2vec_vectors = model.wv.vectors # Form a dict that use word to find the index ind_to_word = {model.wv.vocab[word].index : word for word in model.wv.vocab}from sklearn.cluster import KMeans kmeans = KMeans(n_clusters=100, random_state=0).fit(word2vec_vectors)kmeans.labels_array([92, 4, 4, ..., 6, 6, 6]) # Build a cluster structure # Dict{cluster_num : [word list]} clusters = {} index = 0 for n in kmeans.labels_: if n not in clusters.keys(): clusters[n] = [ind_to_word[index]] else: clusters[n].append(ind_to_word[index]) index += 1for n, cluster in clusters.items(): print("%s -> %s" %(n, cluster[:5]))92 -> ['the', 'in', 'for', 'on', 'first'] 4 -> ['of', 'and', 'with', 'making', 'permanent'] 73 -> ['one', 'zero', 'nine', 'two', 'eight'] 10 -> ['a', 'as', 'or', 'an', 'being'] 38 -> ['to', 'can', 'may', 'would', 'will'] 21 -> ['is', 'means', 'uses', 'includes', 'remains'] 78 -> ['s', 'mark', 'don', 'brown', 'ray'] 42 -> ['was', 'became', 'left', 'began', 'took'] 77 -> ['by', 'under', 'initially', 'subsequently', 'jordan'] 1 -> ['that', 'it', 'this', 'which', 'also'] 20 -> ['are', 'use', 'include', 'related', 'believe'] 84 -> ['from', 'according', 'addition', 'giving', 'dedicated'] 97 -> ['his', 'he', 'her', 'him', 'she'] 52 -> ['be', 'make', 'become', 'take', 'run'] 79 -> ['at', 'city', 'home', 'near', 'center'] 61 -> ['have', 'has', 'had', 'having'] 93 -> ['were', 'war', 'against', 'military', 'force'] 37 -> ['other', 'their', 'some', 'all', 'such'] 96 -> ['its', 'power', 'due', 'control', 'development'] 81 -> ['more', 'most', 'very', 'less', 'particularly'] 51 -> ['been', 'made', 'led', 'developed', 'included'] 99 -> ['used', 'known', 'called', 'found', 'considered'] 72 -> ['there', 'held', 'created', 'produced', 'established'] 68 -> ['american', 'john', 'james', 'william', 'david'] 48 -> ['time', 'years', 'year', 'day', 'times'] 32 -> ['see', 'links', 'external', 'list', 'information'] 74 -> ['than', 'about', 'over', 'around', 'every'] 26 -> ['world', 'states', 'u', 'national', 'group'] 86 -> ['b', 'd', 'born', 'actor', 'author'] 89 -> ['people', 'population', 'groups', 'living', 'species'] 33 -> ['united', 'british', 'canada', 'spanish', 'australia'] 56 -> ['system', 'computer', 'systems', 'data', 'standard'] 64 -> ['state', 'law', 'court', 'rights', 'act'] 94 -> ['history', 'century', 'modern', 'old', 'greek'] 45 -> ['up', 'out', 'right', 'line', 'back'] 90 -> ['english', 'name', 'language', 'term', 'word'] 54 -> ['well', 'much', 'common', 'popular', 'important'] 19 -> ['e', 'c', 'x', 'g', 't'] 71 -> ['government', 'party', 'members', 'parliament', 'elected'] 95 -> ['m', 'km', 'square', 'miles', 'feet'] 66 -> ['university', 'school', 'college', 'education', 'medical'] 67 -> ['life', 'work', 'way', 'view', 'nature'] 34 -> ['like', 'black', 'white', 'red', 'blue'] 30 -> ['including', 'best', 'famous', 'art', 'writers'] 76 -> ['example', 'form', 'set', 'numbers', 'function'] 14 -> ['french', 'german', 'italian', 'russian', 'prize'] 49 -> ['general', 'president', 'former', 'leader', 'chief'] 85 -> ['high', 'level', 'low', 'rate', 'higher'] 87 -> ['based', 'originally', 'test', 'via', 'multi'] 0 -> ['now', 'principal', 'cook', 'resident', 'venice'] 47 -> ['de', 'l', 'al', 'la', 'san'] 41 -> ['music', 'style', 'band', 'album', 'rock'] 11 -> ['great', 'possibly', 'lives', 'bad', 'apparently'] 27 -> ['south', 'north', 'area', 'west', 'east'] 91 -> ['series', 'film', 'character', 'story', 'films'] 31 -> ['game', 'player', 'games', 'team', 'play'] 57 -> ['country', 'europe', 'france', 'england', 'germany'] 80 -> ['king', 'ii', 'roman', 'empire', 'emperor'] 9 -> ['book', 'works', 'published', 'books', 'text'] 22 -> ['political', 'others', 'social', 'movement', 'anti'] 25 -> ['church', 'god', 'christian', 'jewish', 'religious'] 40 -> ['theory', 'science', 'natural', 'research', 'study'] 55 -> ['using', 'single', 'type', 'lines', 'color'] 70 -> ['human', 'cause', 'effects', 'health', 'blood'] 5 -> ['point', 'field', 'above', 'position', 'range'] 50 -> ['public', 'us', 'company', 'economic', 'production'] 98 -> ['man', 'men', 'children', 'person', 'women'] 69 -> ['york', 'london', 'california', 'county', 'founded'] 62 -> ['house', 'official', 'member', 'minister', 'council'] 24 -> ['water', 'energy', 'material', 'cell', 'chemical'] 46 -> ['original', 'version', 'released', 'video', 'release'] 53 -> ['air', 'service', 'fire', 'aircraft', 'nuclear'] 65 -> ['space', 'earth', 'light', 'image', 'star'] 88 -> ['said', 'claim', 'claims', 'stated', 'says'] 18 -> ['along', 'across', 'ice', 'cold', 'upper'] 58 -> ['show', 'television', 'uk', 'radio', 'live'] 63 -> ['january', 'march', 'december', 'july', 'june'] 59 -> ['areas', 'parts', 'cities', 'outside', 'currently'] 15 -> ['terms', 'forms', 'cases', 'elements', 'events'] 13 -> ['japanese', 'etc', 'except', 'unlike', 'respectively'] 3 -> ['class', 'bond', 'composition', 'partial', 'representing'] 7 -> ['whose', 'raised', 'executed', 'serving', 'attacked'] 83 -> ['my', 'big', 'dead', 'cover', 'dark'] 16 -> ['irish', 'becoming', 'historically', 'amongst', 'elsewhere'] 29 -> ['action', 'defense', 'police', 'acts', 'intelligence'] 17 -> ['food', 'animals', 'gold', 'animal', 'iron'] 28 -> ['co', 'am', 'na', 'die', 'ch'] 8 -> ['award', 'grand', 'race', 'fame', 'super'] 6 -> ['previously', 'fourteen', 'handful', 'polls', 'fortunes'] 75 -> ['cycle', 'formation', 'secondary', 'producing', 'naturally'] 60 -> ['regarding', 'concerning', 'describing', 'aristotle', 'oral'] 23 -> ['semi', 'showing', 'apart', 'gates', 'whilst'] 35 -> ['honor', 'adam', 'abraham', 'muhammad', 'passage'] 82 -> ['partially', 'locally', 'carefully', 'lacking', 'attraction'] 12 -> ['moreover', 'consequently', 'besides', 'repeatedly', 'likewise'] 36 -> ['independently', 'comprises', 'marking', 'excluding', 'astronomers'] 39 -> ['associate', 'publishers', 'eds', 'chair', 'wesley'] 44 -> ['thirteen', 'eighteen', 'culminating', 'seventy', 'narrowly'] 2 -> ['ironically', 'nice', 'sixteen', 'stamp', 'nights'] 43 -> ['onwards', 'popularly', 'atta', 'eighty', 'variously'] We need to illustrate how to pick best clusters, i.e. how to evaluate a cluster's good or bad? We use the L2-norm of the vectors compared with the center vector in a cluster to evaluate.Define score$$ score=\sum_{i\in Cluster}{|}w_i-w_{center}|_{2}^{2} $$Hence, the lower the score, the better the cluster.for n, cluster in clusters.items(): scores = 0 for word in cluster: # the smaller the score, the better the cluster scores += sum(np.square(word2vec[word] - kmeans.cluster_centers_[n])) # Original clusters => Dict{cluster_num : [word list]} # Now it becomes Dict(cluster_num : ([word list], score)) clusters[n] = (clusters[n], scores)sorted(clusters.items(), key = lambda x: x[1][1])[:5] # sortedby score ascending[(63, (['january', 'march', 'december', 'july', 'june', 'november', 'april', 'september', 'august', 'october', 'february'], 165.74816360414897)), (61, (['have', 'has', 'had', 'having'], 586.166584790995)), (81, (['more', 'most', 'very', 'less', 'particularly', 'too', 'highly', 'enough', 'relatively', 'quite', 'extremely', 'somewhat', 'increasingly', 'fairly'], 1517.4123485378213)), (86, (['b', 'd', 'born', 'actor', 'author', 'writer', 'singer', 'actress', 'composer', 'poet', 'musician', 'artist', 'politician', 'philosopher', 'mathematician', 'painter', 'journalist', 'footballer', 'novelist'], 2115.24780004326)), (47, (['de', 'l', 'al', 'la', 'san', 'paris', 'et', 'le', 'el', 'der', 'des', 'bwv', 'del', 'da', 'di', 'il', 'du', 'en', 'ma', 'santa', 'te', 'les', 'fran', 'ne', 'juan', 'und', 'sur'], 2692.603341114255))] According to the above results, we pick up top 4 best clusters:Cluster#63 => {'january','march','december','july','june',november','april','september','august','october','february'}score = 165.75This cluster contains monthsCluster#61 => {'have', 'has', 'had', 'having'}socre = 586.17This cluster contains different tense of word haveCluster#81 =>{'more','most','very','less','particularly','too','highly','enough','relatively','quite','extremely','somewhat','fairly'}score = 1517.41They are some kinds of degree adverbCluster#86 =>{'b','d','born','actor','author','writer','singer','actress','composer','poet','musician','artist','politician','philosopher','mathematician','painter','journalist','footballer','novelist'}score = 2115.25This cluster contains many occupations
原文作者：Ilya Pestov，英文版译者Vasily Zubarev，中文翻译来自机器之心的Panda。英文版《Machine Translation - From the Cold War to Deep Learning》，俄文版请访问http://vas3k.com/blog/machine_translation/我打开谷歌翻译的频率是打开 Facebook 的两倍，价格标签的即时翻译对我而言再也不是赛博朋克了。这已经成为了现实。很难想象这是机器翻译算法百年研发之战的结果，而且在那段时间的一半时间里其实都没什么明显的成功。我在本文中讨论的确切发展将立足于所有的现代语言处理系统——从搜索引擎到声控微波。我将探讨的是当今的在线翻译技术的演化和结构。1 历史轨迹1.1 起初故事开始于 1933 年。苏联科学家 Peter Troyanskii 向苏联科学院提交了《用于在将一种语言翻译成另一种语言时选择和打印词的机器》。这项发明非常简单——它有四种语言的卡片、一台打字机和一台旧式胶片相机。操作员先取文本的第一个词，然后找到对应的卡片，拍一张照片，再在打字机上键入其形态特征（名词、复数、性别等）。这台打字机的按键编码了其中一项特征。打字带和相机胶片是同时使用的，从而得到一组带有词及它们的形态的帧。尽管看起来很不错，但和苏联的很多事情都一样，人们认为这项发明是「没用的」。Troyanskii 用了 20 年时间试图完成他的发明，之后因心绞痛逝世。在 1956 年两位苏联科学家找到他的父母之前，这世上没人知道这种机器。那是冷战的铁幕刚刚降下的时候。在 1954 年 1 月 7 日，IBM 在纽约的总部启动了 Georgetown-IBM 实验。IBM 701 计算机有史以来第一次自动将 60 个俄语句子翻译成了英语。「一位不认识任何一个苏联语言词汇的女孩在 IBM 卡片上敲出了这些俄语消息。这个「大脑」以每秒两行半的惊人速度在一台自动打印机上赶制出了它的英语翻译。」——IBM 的新闻稿但是，宣告胜利的头条新闻里却隐藏了一个小小的细节。没人提到这些翻译得到的样本是经过精心挑选和测试过的，从而排除了歧义性。对于日常使用而言，该系统并不比口袋里的常用语手册更好。尽管如此，军备竞赛还是开始了：加拿大、德国、法国以及（特别是）日本全都加入到了机器翻译竞赛中。1.2 机器翻译竞赛改进机器翻译的徒劳工作持续了四十年之久。1966 年，US ALPAC 在其著名的报告中称机器翻译是昂贵的、不准确的和毫无希望的。他们转而建议将重点放在词典开发上，这将美国研究者排除在了竞赛之外近十年时间。即便如此，仅凭科学家和他们的尝试、研究和开发，现代自然语言处理的基础还是建立了起来。多亏了这些彼此监视的国家，当今所有的搜索引擎、垃圾信息过滤器和个人助理都出现了。2 机器翻译的进化史2.1 基于规则的机器翻译（RBMT）最早的基于规则的机器翻译思想出现于 70 年代。科学家研究了翻译员的工作，试图让当时还极其缓慢的计算机也能重复这些行为。这些系统包含：双语词典（比如，俄语->英语）每种语言一套语言学规则（比如，以 -heit、-keit、-ung 等特定后缀结尾的名词都是阴性词）这就是这种系统的全部。如有需要，该系统还能得到一些补充，比如增加姓名列表、拼写纠错器和音译功能。PROMPT 和 Systran 是 RBMT 系统中最有名的案例。如果你想感受下那个黄金时代的柔和气息，去试试 Aliexpress 吧。但即使它们也有一些细微差别和亚种。直接机器翻译这是机器翻译中最直接的类型。它会将文本分成词，然后翻译这些词，再稍微校正一下形态，最后协调句法得到结果；或多或少听起来还行。当太阳落山后，训练有素的语言学家还在为每个词编写规则。其输出会返回某种类型的翻译结果。通常情况下，结果很糟糕。就好像是这些语言学家白白浪费了自己的时间。现代系统完全不会使用这种方法，现代语言学家对此感激不尽。基于迁移的机器翻译与直接翻译相比，我们翻译时要做准备——首先确定句子的语法结构，就像上学时老师教的那样。然后我们再操作整个结构，而不是一个个的词。这有助于在翻译中得到相当好的词序转换。理论上是这样。但在实践中，这仍然会得到逐词翻译的结果并会让语言学家身疲力竭。一方面，它带来的是简化过的一般性语法规则。但另一方面，由于词结构的数量比单个的词要多得多，所以这又会变得更加复杂。语际机器翻译在这种方法中，源文本会被转换成中间表征，并且会被统一用于全世界的所有语言（中间语言）。这正是笛卡尔所梦想的那种中间语言：一种元语言，遵循普适的规则并且可以将翻译变成一种简单的「来回切换」任务。接下来，中间语言可以转换成任何目标语言，而这就是奇点！正是由于存在这种转换，所以语际机器翻译常常会和基于迁移的系统混淆。语际机器翻译的不同之处是语言学规则是针对每种单独的语言和中间语言的，而不是针对语言对。这意味着我们可以向语际系统加入第三种语言并且在它们三者之间彼此翻译。而我们无法在基于迁移的系统中做到这一点。看起来很完美，但实际并不。创建这样一种通用的中间语言极其困难——很多科学家都在这上面投入了一生。他们还没有取得成功，但多亏了他们，我们现在有了形态层面、句法层面、甚至语义层面的表征。但只有语义-文本理论（Meaning-text theory）耗费了巨资！中间语言的思想还会再回来的。让我们再等等看。如你所见，所有的 RBMT 都很蠢笨和可怕，所以它们很少得到使用，除了一些特定的案例（比如天气报告翻译等）。RBMT 最常被提及的优点有形态准确性（不会混淆词）、结果的可再现性（所有翻译器的结果都一样）和调节到特定学科领域的能力（比如为了教授经济学家或特定于程序员的术语）。就算有人真的成功创造出了一个完美的 RBMT，语言学家也用所有的拼写规则强化了它，但还是会存在某些例外情况：英语中的不规则动词、德语中的可分前缀、俄语中的后缀以及人们的表达方式存在差异的情况。任何试图涵盖所有细微差别的行为都会耗费数以百万小时计的工作时间。还不要忘记多义词。同一个词在不同的语境中可能会具有不同的含义，这会得到不同的翻译结果。你试试能从这句话中理解到几种含义：I saw a man on a hill with a telescope?语言不会按照什么固定的规则而发展——语言学家倒是喜欢这个事实。过去三百年中的侵略活动对语言的影响非常大。你怎么能向机器解释这一点？四十年的冷战没能帮助找到任何明确的解决方案。RBMT 已死。2.2 基于实例的机器翻译（EBMT）日本对机器翻译竞赛尤其感兴趣。原因不是冷战，而另有其它：这个国家理解英语的人非常少。这在即将到来的全球化方面是一个很严重的问题。所以日本人非常积极地想要找到一种可行的机器翻译方法。基于规则的英日翻译极其复杂。这两种语言的语言结构完全不一样，几乎所有词都需要重新排列，而且还需要添加新词。1984 年，京都大学的長尾真提出了一个思想：使用现成的短语而不是重复进行翻译。假设我们想翻译一个简单的句子——「I'm going to the cinema.」而且我们之前已经翻译了一个类似的句子——「I'm going to the theater.」而且我们也能在词典中找到「cinema」这个词。那么我们只需找到这两个句子的不同之处、翻译缺失的词、不要搞错了即可。我们拥有的实例越多，翻译结果就会越好。我正是采用这种方式构建了下面的我不熟悉的外语短语！EBMT 让全世界的科学家看到了方向：事实证明，你可以直接向机器输入已有的翻译，而不必花费多年时间构建规则和例外。革命还没有发生，但显然已经迈出了第一步。革命性的统计机器翻译发明将在那之后短短五年内诞生。2.3 统计机器翻译（SMT）1990 年初，IBM 研究中心首次展示了一个对规则和语言学一无所知的机器翻译系统。它分析了两种语言的相似文本并且试图理解其中的模式。这是一个简洁而又优美的思想。两种语言中的同一句子被分成单词，然后再进行匹配。这种操作重复了近 5 亿次，记录下了很多模式，比如「Das Haus」被翻译成「house」或「building」或「construction」等词的次数。如果大多数时候源词都被翻译成「house」，那么机器就会使用这一结果。注意我们没有使用任何规则，也没有使用任何词典——所有的结论都是由机器完成的，其指导方针是统计结果和这样的逻辑——「如果人们这样翻译，我也这样翻译」。统计翻译由此诞生。这个方法比之前的所有方法都更加有效和准确。而且无需语言学家。我们使用的文本越多，我们得到的翻译结果就越好。谷歌的统计翻译内部情况示例。它不仅给出了概率，而且还显示了反向翻译结果统计仍然还有一个遗留问题：机器该怎样将「Das Haus」与「building」对应起来呢——我们又怎么知道翻译结果是正确的？答案是我们没法知道。一开始，机器会假设「Das Haus」一词与来自翻译句子的任意词都有同等的关联。接下来，当「Das Haus」出现在其它句子中时，与「house」关联的数量会增多。这就是词对齐算法，这是大学级机器翻译的典型任务之一。机器需要成百万上千万的双语句子才能收集到每个词的相关统计结果。我们如何得到这些数据？好吧，我们决定取用欧洲议会和联合国安理会会议的摘录，这些都是以所有成员国的语言提供的，而且可供下载：UN Corpora：https://catalog.ldc.upenn.edu/LDC2013T06Europarl Corpora：http://www.statmt.org/europarl基于词的 SMT一开始的时候，最早期的统计翻译系统的工作方式是将句子分成词，因为这种方法很直观而且符合逻辑。IBM 的第一个统计翻译模型被称为 Model 1。名字也相当优雅，对吧？猜猜他们的第二个模型叫什么？Model 1：逐词对应Model 1 使用了一种经典方法来将句子分成词和记录统计信息。这个过程不考虑词序。唯一要用的技巧是将一个词翻译成多个词。比如「Der Staubsauger」可能会变成「Vacuum Cleaner」，但并不意味着反过来也可以。这里有一些基于 Python 的简单实现：https://github.com/shawa/IBM-Model-1Model 2：考虑句子中的词序缺乏语言词序知识是 Model 1 的一个问题，而且这个问题在某些情况下很重要。Model 2 解决了这个问题：它记忆了输出句子中词通常出现的位置，并且会通过一个中间步骤将词排列成更自然的形式。结果变得更好了，但仍然不尽人意。Model 3：额外增添翻译结果中常常会出现新词，比如德语的冠词或英语否定句中的「do」。比如「Ich will keine Persimonen」→「I do not want Persimmons.」为了解决这个问题，Model 3 又增加了两个步骤：如果机器认为有加入新词的必要性，则插入 NULL 标记为每个标记词的对齐选择合适的小品词或词Model 4：词对齐Model 2 考虑了词对齐，但对词序重排一无所知。比如，形容词常会与名词交换位置，所以不管词序记忆得多好，都不会让输出结果更好。因此，Model 4 考虑了所谓的「相对顺序」——如果两个词总是交换位置，模型就能学到。Model 5：修正错误这里没什么新鲜的。Model 5 所要学习的参数更多了，而且修正了词位置冲突的问题。尽管基于词的系统本身是革命性的，但它们仍然无法处理格、性和同义词。每一个词都只有单一一种翻译方式。现在我们已经不再使用这种系统了，因为它们已经被更为先进的基于短语的方法替代。基于短语的 SMT这种方法基于所有基于词的翻译原则：统计、重新排序和词法分析。但是，在学习时，它不仅会将文本分成词，还会分成短语。确切地说，这些是 n-gram，即 n 个词连在一起构成的连续序列。因此，这个机器能学习翻译稳定的词组合，这能显著提升准确度。其中的诀窍在于，这里的短语并不总是简单的句法结构，而且如果有人明白语言学并干预了其中的句子结构，那么翻译的质量就会大幅下降。计算语言学先驱 Frederick Jelinek 曾经开玩笑地说：「每次我炒掉一个语言学家，语音识别器的表现就会上升一点。」除了提升准确度，基于短语的翻译在选择所要学习的双语文本上提供了更多选择。对于基于词的翻译，源文本之间的准确匹配是至关重要的，这就排除了让任何文学翻译或自由翻译。基于短语的翻译则可以从中学习。为了提升翻译质量，研究者甚至开始解析不同语言的新闻网站。自 2006 年以来，每个人都开始使用这种方法。谷歌翻译、Yandex、必应等一些著名的在线翻译工具将基于短语的方法用到了 2016 年。你们可能都还记得谷歌要么得到毫无差错的翻译句子，要么得到毫无意义的结果的时候吧？这种毫无意义就来自基于短语的功能。老一辈基于规则的方法总是会得到可预测的但也很糟糕的结果。统计方法则总是会得到出人意料和让人困惑的结果。谷歌翻译会毫不犹豫地将「three hundred」变成「300」。这就是所谓的统计异常（statistical anomaly）。基于短语的翻译已经变得非常流行，当你听到人们说「统计机器翻译」时，多半就是指它。在 2016 年之前，所有的研究都称赞基于短语的翻译是表现最好的。那时候，甚至没人认为谷歌已经在燃起战火，准备改变整个机器翻译图景了。基于句法的 SMT这种方法应当被简要提及一下。在神经网络出现的很多年前，基于句法的翻译被认为是「翻译的未来」，但这一思想并未迎来腾飞。基于句法的翻译的支持者相信它有可能与基于规则的方法融合。它需要对句子进行相当准确的句法分析——以确定主语、谓语和句子的其它部分，然后再构建一个句子树。机器可以使用它来学习转换语言之间的句法单元并根据词或短语来翻译其余部分。那应该可以一劳永逸地解决词对齐问题。来自 Yamada and Knight [2001] 的示例（http://www.aclweb.org/anthology/P01-1067）以及这个很棒的幻灯片（http://homepages.inf.ed.ac.uk/pkoehn/publications/esslli-slides-day5.pdf）问题是句法分析的效果很差，尽管事实上我们认为这在之前已经得到了解决（因为我们有很多语言的现成可用的库）。我曾经试过使用句法树来解决比单纯地解析主语和谓语更复杂的任务。但我每次都放弃了，然后使用了另一种方法。如果你成功过至少一次，请让我知道。2.4 神经网络机器翻译（NMT）2014 年，一篇关于将神经网络用于机器翻译的出色论文发布：https://arxiv.org/abs/1406.1078。互联网并没关注这项研究，但谷歌除外——他们挽起袖子就干了起来。两年之后的 2016 年 9 月，谷歌发布了改变机器翻译领域的公告，参阅《重磅 | 谷歌翻译整合神经网络：机器翻译实现颠覆性突破》。这一思想接近照片之间的风格迁移。知道 Prisma 这样的应用吗？它能用某幅著名艺术作品的风格来渲染图片。但这不是魔法。是神经网络学会了识别艺术家的画作。接下来，包含网络决策的最后一层被移除了。所得到的风格化图像只是网络所得到的中间图像。这是网络自己的幻想，而我们觉得这很美。如果我们可以迁移照片的风格，那我们能不能将另一种语言施加到源文本上呢？我们可以将文本看作是带有某种「艺术家风格」，我们希望在迁移这个风格的同时又保证这些文本的本质不变。想象一下，假如我要描述我的狗——平均个头、尖鼻子、短尾巴、老是叫唤。如果我把这些狗的特征给你并且描述是准确的，你就可以画出它，即使你从没见过它。现在，再想象源文本是特定特征的集合。基本上而言，这意味着你可以编码它，然后再让其它神经网络将其解码回文本——但是另一种语言的文本。解码器只知道自己的语言。它对这些特征的来源一无所知，但它可以用西班牙语等语言将其表达出来。再继续前面的比喻，不管你是怎么画这条狗的（用蜡笔、水彩或你的手指），你都可以把它画出来。再说明一次：一个神经网络只能将句子编码成特定的特征集合，另一个神经网络只能将其解码成文本。这两者彼此都不知情，而且都只各自了解自己的语言。想起什么没有？「中间语言」回来了！问题是，我们如何找到这些特征？对于狗来说，特征当然很明显，但文本的特征是怎样的？三十年前科学家就已经在尝试创建通用语言代码了，但最终以失败告终。尽管如此，我们现在有深度学习了。寻找特征是它的基本任务！深度学习和经典神经网络之间的主要区别是搜索这些特定特征的能力，而无需对这些特征的本质有任何了解。如果神经网络足够大，而且有数千块显卡可用，那就能很好地找到文本中的这些特征。理论上讲，我们可以将这些神经网络得到的特征交给语言学家，这样他们就可以为自己打开一片新视野了。但问题是编码和解码应该使用哪种类型的神经网络呢？卷积神经网络（CNN）完美适用于图像，因为它们可以操作独立的像素块。但文本中没有独立的块——每个词都取决于自己的语境。文本、语音、音乐都是连续的。所以循环神经网络（RNN）是处理它们的最佳选择，因为它们能记住之前的结果——在这里即是之前的词。现在很多应用都已经使用了 RNN，包括 Siri 的语音识别（解析声音序列，其中后一个声音取决于前一个声音）、键盘提示（记住之前的经历，猜测下一个词）、音乐生成和聊天机器人。致像我一样的技术宅：事实上，神经翻译器的架构非常多样。一开始是用的常规 RNN，后来升级成了双向 RNN，其中翻译器不仅要考虑源词之前的词，还有考虑其后的词。这要高效得多。然后它又使用了带有 LSTM 单元的多层 RNN，可以实现翻译语境的长期存储。短短两年时间，神经网络在翻译上的表现就超越了过去 20 年来的一切。神经翻译的词序错误少了 50%、词汇错误减少了 17%、语法错误减少了 19%。神经网络甚至学会了协调不同语言的性和格。而且并没有人教它们这样做。这一领域最值得提及的进展是从没使用过直接翻译。统计机器翻译方法总是可以使用英语作为关键源。因此，如果你要将俄语翻译成德语，机器会首先将俄语翻译成英语，然后再将英语翻译成德语，这会造成双倍损失。神经翻译无需这样做——只需要一个解码器就行了。没有共同词典的语言之间也能实现直接翻译，这是有史以来的第一次。3 成果3.1 谷歌翻译（自 2016 年以来）2016 年，谷歌为 9 种语言启用了神经翻译。他们开发出了名为谷歌神经机器翻译（GNMT）的系统。它由 8 个编码器和 8 个解码器 RNN 层构成，另外还有来自解码器网络的注意连接。他们不仅会切分句子，而且还会切分词。这正是他们解决 NMT 一大主要难题的方法——即罕见词问题。但出现了它们词汇库中没有的词时，NMT 是无能为力的。比如说「Vas3k」。我估计没人让神经网络学习翻译我的昵称。在遇到罕见词时，GNMT 会尝试将词分解成词片段，然后根据这些片段得到翻译结果。很聪明的做法。提示：浏览器中用于网站翻译的谷歌翻译仍然用的是老旧的基于短语的算法。不知为何谷歌没有升级，而且其翻译结果和在线版本谷歌翻译相比差距其实相当大。在线版本的谷歌翻译使用了众包机制。人们可以选择他们认为最正确的版本，而且如果很多用户都认同，那么谷歌就会一直按这种方式翻译这个短语并将其标注为一个特例。对于「Let』s go to the cinema」或「I』m waiting for you」等日常使用的短句而言，这种做法效果很好。谷歌的英语会话水平比我还好，不开森～微软必应的工作方式和谷歌翻译差不多。但 Yandex 不一样。3.2 Yandex Translate（自 2017 年以来）Yandex 于 2017 年推出了自己的神经翻译系统。该公司宣称其主要特色是混合性（hybridity）。Yandex 将神经方法和统计方法组合到了一起来执行翻译，然后再使用其最喜欢的 CatBoost 算法从中选出最好的一个。问题是神经翻译在翻译短句时常常出错，因为它需要使用上下文来选择正确的词。如果一个词在训练数据中出现的次数非常少，那就很难得到正确的结果。在这种情况下，简单的统计翻译能轻松快捷地找到正确的词。在句子末尾加上句号后，Yandex 的翻译结果更好了，因为这时候它启用了神经网络机器翻译。Yandex 没有分享具体的技术细节。它用营销新闻稿搪塞了我们。好吧。看起来谷歌使用了 SMT 来执行词和短句的翻译。他们没有在任何文章中提及这一点，但如果你查看短表达和长表达之间的差别，你就能相当明显地注意到。此外，SMT 也被用来展示词的统计情况。4 结论和未来每个人都仍然为「巴别鱼」（即时语音翻译）的构想感到兴奋。谷歌已经带着 Pixel Buds 耳机向这个方向迈出了一步，但事实上这仍然达不到我们梦想的效果。即时语音翻译与通常的翻译不同。系统需要知道何时开始翻译以及何时闭嘴聆听。我还没见到过任何能够解决这一问题的方法。也许，Skype 还行吧……而且有待推进的领域不止这一个：所有的学习都受限于并列文本块的集合。最深度的神经网络仍然是在并列文本中学习。如果不向神经网络提供资源，它就无法学习。而人类可以通过阅读书籍和文章来扩增自己的词汇库，即使不会将其翻译成自己的母语。如果人类能做到，神经网络就也能做到。理论上讲是这样。我只发现了一个原型设计试图开发出能让知晓一种语言的网络能通过阅读另一种语言的文本来获取经验：https://arxiv.org/abs/1710.04087。我倒是想自己试试看，但我很笨。好了，就这样吧。
ML-HW3 PDFUpdate on November 11, 2019: ML-HW3 Solution PDFQuestion 1(a) According to the initail values that the question is given. When feeding $(x_1,x_2)=(1,2)$ to the network. The outputs of the hidden units$$ \begin{aligned} h_{11} &= x_1w_{11}^{(1)}+x_2w_{21}^{(1)} = 1 \times 1 + 2 \times (-1) = -1\\ \mu_{11} &= ReLU(h_{11}) = 0\\ h_{12} &= x_1w_{12}^{(1)}+x_2w_{22}^{(1)} = 1 \times (-1) + 2 \times 1 = 1\\ \mu_{12} &= ReLU(h_{12}) = 1\\ h_{21} &= \mu_{11}w_{11}^{(2)}+\mu_{21}w_{21}^{(2)} = 0 \times (-1) + 1 \times 1 = 1\\ \mu_{21} &= ReLU(h_{21}) = 1\\ h_{22} &= \mu_{11}w_{12}^{(2)}+\mu_{12}w_{22}^{(2)} = 0 \times (-1) + 1 \times 1 = 1\\ \mu_{22} &= ReLU(h_{22}) = 1 \end{aligned} $$Therefore, the logit is$$ \sigma(z) = \sigma(\mu_{21}w_1^{(3)} + \mu_{22}w_2^{(3)}) = \sigma(1 \times 1 + 1 \times 1) = \sigma(2) = \frac{e^2}{e^2+1} = 0.88 $$The output distribution of the output units$$ P(y\mid x_1=1,x_2=2,\theta) = P(y\mid z=2) = \left\{ \begin{aligned} &\sigma(2),y=1\\ &\sigma(-2),y=0 \end{aligned} \right. = \sigma((2y-1)\cdot 2) = \sigma(4y-2) $$(b) The given loss function can be written to$$ L = -logP(y=0|z)= -log\sigma(-z) = -log(\frac{1}{1+e^z}) = log(1+e^z) $$So the derivative of error of the output unit$$ \frac{\partial L}{\partial z} = \frac{\partial}{\partial z}log(1+e^z) = \frac{e^z}{1+e^z} = \sigma(z) $$Then the derivative error of the hidden units$$ \delta_{21} = \frac{\partial L}{\partial h_{21}} = \frac{\partial L}{\partial z} \frac{\partial z}{\partial \mu_{21}} \frac{\partial \mu_{21}}{\partial h_{21}} = w_1^{(3)} = \sigma(2) = 0.88 $$$$ \delta_{22} = \frac{\partial L}{\partial h_{22}} = \frac{\partial L}{\partial \mu_{22}} \frac{\partial \mu_{22}}{\partial h_{22}} = w_2^{(3)} = \sigma(2) = 0.88 $$$$ \delta_{11} = \frac{\partial L}{\partial h_{11}} = \delta_{21} \frac{\partial h_{21}}{\partial \mu_{11}} \frac{\partial \mu_{11}}{\partial h_{11}} + \delta_{22} \frac{\partial h_{22}}{\partial \mu_{11}} \frac{\partial \mu_{11}}{\partial h_{11}} $$Because $\frac{\partial \mu_{11}}{\partial h_{11}}=0$ then $\delta_{11}=0$$$ \delta_{12} = \frac{\partial L}{\partial h_{12}} = \delta_{21} \frac{\partial h_{21}}{\partial \mu_{11}} \frac{\partial \mu_{11}}{\partial h_{11}} + \delta_{22} \frac{\partial h_{22}}{\partial \mu_{12}} \frac{\partial \mu_{12}}{\partial h_{12}} = 2 \sigma(2) = 1.76 $$We use the chain rule, we can get$$ \frac{\partial L}{\partial w_{22}^{(2)}} = \delta_{22} \cdot \frac{\partial h_{22}}{\partial w_{22}^{(2)}} = \delta_{22} \cdot \mu_{12} = \sigma(2) \times 1 = 0.88 $$$$ \frac{\partial L}{\partial w_{22}^{(1)}} = \delta_{12} \cdot \frac{\partial h_{12}}{\partial w_{22}^{(1)}} = \delta_{22} \cdot x_2= = 2\sigma(2) \times 2 = 4\sigma(2) = 3.52 $$If we want to reduce the loss on the example$$ \frac{\partial L}{\partial w_{22}^{(2)}} = \delta_{22} \cdot \mu_{12} \Rightarrow \delta_{22}>0, \mu_{12}>0 \Rightarrow \text{Decrease the parameter of } w_{22}^{(2)} $$$$ \frac{\partial L}{\partial w_{22}^{(1)}} = \delta_{12} \cdot x_2 \Rightarrow \delta_{12}>0, x_2>0 \Rightarrow \text{Decrease the parameter of } w_{22}^{(1)} $$Question 2Why is the sigmoid activation function not recommended for hidden units, but it is fine for an output unit.The sigmoid units are not recommeded for hidden units because they saturates across most of their domains. The function curve becomes flat and easily causes gradient disappearing. However, they are fine as the output units because the negative log-likelihood helps to prevent the problem.Question 3What is dropout used for in deep learning? How does it work? Why does it work? Answer brieflyDropout is used with minibatch-based algorithms such as SGD in deep learning. For each minibatch, dropout first randomly sample values for mask variables, and then carry out one step of gradient descent (i.e. randomly make some units not updated). Actually, Dropout is a kind of regularization method. It reduces overfitting by preventing complex co-adaptations of parameters on training data.Question 4What are the key ideas behind the Adam algorithm for training deep neural networks? Answerbriefly.Adam algorithm is roughly a combination of RMSProp and momentum, with bias correction. SGD maintains a single learning rate for all weight updates and the learning rate does not change during training. Momentum method brorrows the concept of momentum in Pysics. By accumulating momentum, it reduces the Zigzag effect during gradient descent and accelerates the process of converging to the minimum. RMSProp also try to reduce the Zigzag effect but using the accumulation of Root Mean Square of the gradient and it converges faster and have less fluctuation than Momentum method. However, this also means that the RMSProp prevents exploring in the direction of vibration. Therefore, it's the key idea of Adam method that combining both of them should have a better performance. In figure 2, we can see Adam uses Momentum and RMSProp to update the first and the second moment estimate and applies bias correction after that.Question 5The input of a convolutional layer has shape 27 × 27 × 256 (width, height, depth). The layer uses 384 3 × 3 filters applied at stride 1 with no zero padding. What is the shape of the output of the layer? How many parameters are there? How many float multiplication operations it will take to compute the net inputs of the all the output units?According to the question. Set the INPUT $W_2\times H_1 \times D_1$, $K$ number of $ F \times F$ filters, stride$=S$, zero padding$= P$. The OUTPUT $W_2 \times H_2 \times D_2$The output$$ \begin{aligned} &W_2 = \frac{W_1+2P-F}{S} + 1 = 27 - 3 + 1 = 25\\ &H_2 = \frac{H_1+2P-F}{S} + 1 = 27 - 3 + 1 = 25\\ &D_2 = K = 384 \end{aligned} $$Therefore the shape of the output layer is $25 \times 25 \times 384$. And because we have 384 number of $3 \times 3$ filters, the number of parameters$$ n = (FFD_1 + 1)\cdot K= (3 \times 3 \times 256 + 1)\times 384 = 885,120 $$The number of float textbf{multiplication} operations it takes$$ m = FFD_1 \times W_2H_2D_2 = (3 \times 3 \times 256) \times (25 \times 25 \times 384) = 552,960,000 $$Question 6(a) Is it a good idea to apply dropout to a convolutional neural network? If so, which part of the model should we apply dropout to? Answer briefly.(b) Is it a good idea to apply dropout to a recurrent neural network? If so, which part of the model should we apply dropout to? Answer briefly.(a) Generally, dropout is a widely used regularization method in deep learning including CNN. The dropout just apply on Fully-connected layer because the number of parameters is large but not on convolutional layer for its much smaller number of parameters.(b) Talking about dropout in RNN may be a little bit complicated. We look at the figure 4. textbf{The naive dropout RNN} method was proposed by Zaremba et al. (2014) and Pham et al. (2013). They applied dropout only to the non-recurrent connections and thought it's not a good idea to apply dropout to recurrent layers. This is because noise will be amplified for long sequences and drown the signal.However, Gal and Ghahramani (2015) found this approach would cause overfitting after analysing. They proposed variational dropout where by repeating the same dropout mask at each time step for both inputs, outputs, and recurrent layers (drop the same network units at each time step) using a bayesian interpretaton. And it performed better than naive dropout method in NLP.Question 7(a) For image classification, the adversarial attack is intentionally adding small and special perturbations to image to fool the model. It makes the classifer completely change its original prediction about the image, with high confidence.(b) $Z_t(x'),Z_i(x')$ represent the logits of class $t$ and class i respectively. The CW attack is a targeted and strong attack. The optimization problem can be written as$$ min_{x'}[c||x-x'||_2^2 + max\{max_{i\neq t}Z_i(x')-Z_t(x'),-\kappa\}] $$Focus on the second part, if let $\delta = Z_t(x') - max_{i\neq t}Z_i(x')$$$ max\{max_{i\neq t}Z_i(x')-Z_t(x'),-\kappa\} = max\{-\delta,-\kappa\} = \left\{ \begin{aligned} &-\delta, \delta < \kappa\\ &-\kappa, \delta \geq \kappa \end{aligned} \right. $$Consider minimizing the $max\{-\delta,-\kappa\}$. When $\delta < \kappa$, it's equivalent to maximize $\delta$ (minimize $-\delta$). This means we maximize the difference between the logits of class $t$ and the second best. In other words, we want theprobability of class $t$ be as high as possible relative to other classes. When $\delta \geq \kappa$, we are confident that $x'$ is an adversarial example, and hence turn our attentions to minimize $||x-x'||_2^2$Question 8(a) $f_t$ determines which components of the previous state and how much of them to remember/forget. $i_t$ determines which components of the input from $h^{(t-1)}$ and $x^{(t)}$ and how much of them should go into the current state.(b) Sigmoid activation function is used for the gates so that their values are often close to 0 or 1. However, tanh is used for the output $h^{(t)}$ and memory cell $c_t$ so as to have strong gradient signal during back propagation.
Homework for Course MSBD5004 Mathematical Methods for Data Analysis, BDT, HKUSTQuestion 1Consider the vector space $R^{n}$(a) Check that $\|x\|_{\infty}=\max_{1 \leq i \leq n} |x_{1}|$ is indeed a norm on $\mathbb{R}^n$ According to the definition of norm , we check(1)$\begin{aligned} \| x\|_{\infty} =\max _{1 \leq i \leq n}\left|x_{i}\right| \geq 0, \forall x \in \mathbb{R}^{n}\end{aligned} $ and $\| x\|_{\infty} = 0 \Leftrightarrow |x_i|=0 \Leftrightarrow x=\overrightarrow{0}$(2)$\begin{aligned} \|\alpha x\|_{\infty}=\max _{1 \leq i \leq n}|a x_{i}|=|\alpha| \cdot \max _{1 \leq i \leq n}\left|x_{i}\right|=|\alpha| \cdot \| x\|_{\infty}, \forall x \in \mathbb{R}, \alpha \in \mathbb{R}\end{aligned}$(3)$\begin{aligned}\|x+y\|_{\infty}=\max _{1 \leq i \leq n}\left|x_{i}+y_{i}\right| =\max_{1 \leq i \leq n} \left| x_i \right| +\max_{1 \leq i \leq n}\left| y_{i}\right|=\|x\|_{\infty}+\|y\|_{\infty}, \quad \forall x, y \in \mathbb{R}^{n}\end{aligned}$Therefore, $\|x\|_{\infty}=\max _{1 \leq i \leq n}\left|x_{i}\right|$ is a norm on $\mathbb{R}^{n}$(b) Prove that: for any $x \in \mathbb{R}^{n}, \quad\|x\|_{\infty}= lim_{p \rightarrow \infty} \|x\|_p$Prove:$$ \begin{aligned} &\|x\|_{p}=\left(\sum_{i=1}^{n}\left|x_{i}\right|^{p}\right)^{1 / p} \\ &=\left(\left|x_{1}\right|^{p}+\left|x_{x}\right|^{p}+\cdots+\left|x_{n}\right|^{p}\right)^{1 / p} \end{aligned} $$Let$$ \left|x_{m}\right|=\max \left\{\left|x_{1}\right|,\left|x_{2}\right|, \cdots,\left|x_{n}\right|\right\} $$Because$$ \frac{\left|x_{1} \right|}{\left|x_{m} \right|}, \frac{\left|x_{2} \right|}{\left|x_{m}\right|}, \ldots, \frac{\left|x_{n}\right|}{\left|x_{m}\right|}<1 $$Then we can get this inequality$$ 1 \cdot |x_m| \leq \|x\|_{p}=\left[\left(\frac{x_1}{x_{m}}\right)^{p}+\left(\frac{x_2}{x_{m}}\right)^{p}+ \cdots + \left(\frac{x_n}{x_{m}}\right)^{p} \right]^{\frac{1}{p}} \cdot |x_m| \leq (n)^{\frac{1}{p}} \cdot |x_m| $$when $p \rightarrow \infty, (n)^{\frac{1}{p}} \rightarrow 1$ so $\| x \|_p \rightarrow |x_m|$Finally $\lim _{p \rightarrow \infty}\|x\|_{p}=\left|x_{m}\right|=\max _{1 \leq i \leq n}\left|x_{i}\right| = \|x\|_\infty$. Hence proved.(c) Prove the equivalence$$\|x\|_{\infty} \leqslant \| x\left\|_{1} \leqslant n\right\|x \|_{\infty}, \forall x \in \mathbb{R}^{n}$$Prove: According to the definitionObviously, $\max_{1 \leq i \leq n} \left|x_{i}\right|$ is taken from$\left\{\left|x_{i}\right|,\left|x_{2}\right|, \cdots,\left|x_{n}\right|\right\}$So, $\| x \|_{1}=\sum_{i=1}^{n}\left|x_{1}\right| \geqslant \max _{1 \leq i \leq n}\left|x_{i}\right|= \|x\|_\infty$ Then$$ \left|x_{1}\right| \leq \max_{1 \leq i \leq n} |x_i|\\ \left|x_{2}\right| \leq \max_{1 \leq i \leq n} |x_i|\\ \vdots \\ \left|x_{n}\right| \leq \max_{1 \leq i \leq n}|x_i| $$Therefore $\sum_{i=1}^{n}\left|x_{i}\right|=n \cdot \max_{1 \leq i \leq n} |x_i|=n \cdot\|x\|_{\infty}$Altogether, $\|x\|_{\infty} \leqslant\|x\|_{1} \leqslant n \cdot\|x\|_{\infty}$Question 2For any $A \in \mathbb{R}^{m \times n}$, we have defined$$\|A\|_{2}=\sup _{x \in \mathbb{R}^{n}, x \neq 0} \quad \frac{\|A x\|_{2}}{\|x\|_{2}}$$(a) Prove that$$ \|A\|_{2}=\max _{x \in \mathbb{R}^n, \|x\|_2=1}\|A x\|_{2} $$Prove :$$ \begin{aligned} \|A\|_2 &= \sup _{x \in \mathbb{R}^{n}, x \neq 0}\frac{\|A x\|_{2}}{\|x\|_{2}}\\ &= \sup _{x \in \mathbb{R}^{n}, x \neq 0}\left\|\frac{A x}{\|x\|_{2}}\right\|_{2} \\ &= \sup _{x \in \mathbb{R}^{n}, x \neq 0}\left\|A \cdot \frac{x}{\|x\|_{2}}\right\|_{2} \end{aligned} $$Note that $\frac{x}{\|x\|_2}$ has unit length. So we can express $$\|A\|_2=\sup _{x \in \mathbb{R}^{n},\|x\|_{2}=1} \|A x \|_{2}$$However, $\|A\|_2$ is a continuous function of $x$ and the unit ball $\|x\|_{2}=1$ is closed and bounded. Now, on a closed and bounded set, a continuous function always achieves its maximum and minimum values.Hence, the 'sup' can be replaced by 'max'. i.e.$$ \|A\|_{2}=\max _{x \in R^{n},\|x\|_{2}=1}\|A x\|_{2} $$(b) Prove that $\|\cdot\|_2$ is a norm on $\mathbb{R}^{m \times n}$ Prove: According to the definition of norm we check(1) $\forall A \in \mathbb{R}^{m \times n}$$$ \begin{aligned} \|A\|_{2}=\max _{x \in \mathbb{R}^n, \|x\|_2=1}\|A x\|_{2} \geqslant 0 \end{aligned} $$when $\begin{aligned}\max _{x \in \mathbb{R}^n, \|x\|_2=1}\|A x\|_{2} = 0\end{aligned}$ with $\|A x\|_{2} \geq 0$, we have$$ \|A x\|_{2} = 0, s.t. \|x\|_2=1, x \in \mathbb{R}^n \Rightarrow A=O $$Thus, $\|A x\|_{2} = 0 \Leftrightarrow A=O$(2) $\forall \alpha \in \mathbb{R}, A \in \mathbb{R}^{m \times n}$$$ \begin{aligned} \|\alpha A\|_{2} &= \max _{x \in \mathbb{R}^n, \|x\|_2=1}\|\alpha A x\|_{2} \\ &= |\alpha| \cdot \max _{x \in \mathbb{R}^n, \|x\|_2=1} \|A x\|_{2}\\ &= |\alpha| \cdot \|A\|_2 \end{aligned} $$(3) $\forall A,B \in \mathbb{R}^{m \times n}$$$ \begin{aligned} \|A + B\|_{2} &= \max _{x \in \mathbb{R}^n, \|x\|_2=1}\|(A+B)x\|_{2} \\ &= \max _{x \in \mathbb{R}^n, \|x\|_2=1}\|Ax+Bx\|_{2} \\ &\leq \max _{x \in \mathbb{R}^n, \|x\|_2=1} \left(\|Ax\|_{2} + \|Bx\|_{2}\right) \\ &= \max _{x \in \mathbb{R}^n, \|x\|_2=1}\|Ax\|_{2} + \max _{x \in \mathbb{R}^n, \|x\|_2=1}\|Bx\|_{2}\\ &= \|A\|_2 + \|B\|_2 \end{aligned} $$Altogether, $\|\cdot\|_{2}$ is a norm on $\mathbb{R}^{m \times n}$(c) Prove that $\|A x\|_{2} \leqslant\|A\|_{2}\|x\|_{2}$ for any $A \in \mathbb{R}^{n \times n}$ and $x \in \mathbb{R}^{n}$Prove: Consider the definition of matrix 2-norm, $\forall A \in \mathbb{R}^{m \times n}$$$\|A\|_{2}=\sup _{x \in \mathbb{R}^{n}, x \neq 0} \quad \frac{\|A x\|_{2}}{\|x\|_{2}}$$It reveals that$$ \|A x\|_{2} \leqslant \|A\|_2 \cdot \|x\|_{2} $$Hence proved(d) Prove that $\|A B\|_{2} \leqslant\|A\|_{2} \cdot\|B\|_{2}$ for all $A \in \mathbb{R}^{m \times n}$ and $B \in \mathbb{R}^{n \times p}$Prove: In Question (c) we have proved $\|A x\|_{2} \leqslant\|A\|_{2}\|x\|_{2}$, $A \in \mathbb{R}^{n \times n}$, $x \in \mathbb{R}^{n}$use this inequality twice. Let $B \in \mathbb{R}^{n \times p}, y \in \mathbb{R}^p$$$ \begin{aligned} \|A B y\|_{2} &=\|A(B y)\|_{2} \\ &\leqslant\|A\|_{2} \cdot\|B y\|_{2} \\ &\leqslant\|A\|_{2} \cdot \|B\|_{2} \cdot\|y\|_{2} \end{aligned} $$Then for $y \neq 0$$$ \begin{array}{l} \frac{\|A B y\|_{2}}{\|y\|_{2}} \leqslant\|A\|_{2} \cdot \|B\|_2 \\ \left\|A B \cdot \frac{y}{\|y\|_{2}}\right\|_{2} \leqslant\|A\|_{2} \cdot\|B\|_{2} \end{array} $$Hence, $\|A B\|_{2} \leqslant\|A\|_{2} \cdot \| B \|_{2},$ provedQuestion 3Let $a_{1}, a_{2}, \cdots, a_{m}$ be the $m$ given real numbers. Prove that a median of $a_{1}, a_{2}, \dots, a_{m}$ minimizes $$|a_{1} - b|+\left|a_{2}-b\right|+\cdots+\left|a_{m}-b\right|$$over all $b \in R$ Prove: To prove a median can minimize $\left|a_{1}-b\right|+\left|a_{2}-b\right|+\dots+\left|a_{m}-b\right|$ is equivalent to prove a median minimizes$$ \text { Let } f(b)=\left(a_{1}-b\right)^{2}+\left(a_{2}-b\right)^{2}+\cdots+\left(a_{n}-b\right)^{2} $$$$ \begin{aligned} f^{\prime}(b)&=-2\left[\left(a_{1}-b\right)+\left(a_{2}-b\right)+\cdots+\left(a_{m-b}\right)\right] \\ &=-2\left[\left(a_{1}+a_{2}+\dots+a_{m}\right)-m b\right] \end{aligned} $$Make $f^{\prime}(b)=0, \text { get } b=\frac{1}{m}\left(a_{1}+a_{2}+\dots+a_{m}\right)$Due to $f^{\prime \prime}(t)=2 m>0$Therefore when $b=\frac{1}{m}\left(a_{1}+a_{2}+\dots+a_{m}\right), f(b)$ achieves its minimumi.e. the median minimizes $\left|a_{1}-b\right|+\left|a_{2}-b\right|+\dots+\left|a_{m}-b\right|$Question 4Suppose that the vectors $x_{1}, \ldots . x_{N}$ in $\mathbb{R}^{n}$ are clustered using the K-means algorithm, with group representative $z_1, \cdots, z_{k}$(a) Suppose the original vectors $x_i$ are nonnegative. i.e. their entries are nonnegative. Explain why the representatives $z_j$ output by the k-means algorithm are also nonnegtive.Answer: we see the algorithm step 2 Fix group $G_{1}, G_{2}, \cdots, G_{k}$ and solve$$ \min _{z_1, \cdots, z_k} \sum_{j=1}^{k}\left(\sum_{i \in G_j}\left\|x_{i}-z_{j}\right\|_{2}^{2}\right) $$$$ \text { that } \quad z_{j}=\frac{1}{\left|G_{j}\right|}\left(\sum_{i \in G_j} x_{i}\right) $$Because $x_i$ are nonnegative, according to the equation, $z_j$ is also nonnegative.(b) Suppse the original vector $x_i$ represent proportions, i.e. their entries are nonnegative and sum to one. Explain why the representatives$z_j$ output by k-means algorithms are also represent proportions.Answer: Still consider the equation above, rewrite it to vector form$$ z_{i}=\frac{1}{\left|G_{i}\right|} \sum_{i \in G_{j}}\left(\begin{array}{l} x_{i1} \\ x_{i2} \\ \vdots \\ x_{in} \end{array}\right) $$$$ =\frac{1}{\left|G_{i}\right|} \left(\begin{array}{c} \sum_{i \in G_{j}} x_{i1} \\ \sum_{i \in G_{j}} x_{i2} \\ \vdots\\ \sum_{i \in G_{j}} x_{in} \end{array}\right) $$For $x_{i}+x_{i 2}+\cdots+x_{i n}=1, \quad \sum_{i \in G_{j}} x_{i1}+\sum_{i \in G_{j}} x_{i2}+\cdots+ \sum_{i \in G_{j}} x_{in} = |G_j|$We can get$$ \frac{1}{\left|G_{i}\right|} \left(\sum_{i \in G_{j}} x_{i1}+\sum_{i \in G_{j}} x_{i2}+\cdots+ \sum_{i \in G_{j}} x_{in}\right)=1 $$and $z_j$ nonnegstive is obvious. Hence proved.(c) Suppose the original vector $x_i$ are Boolean. i.e. their entries are either 0 or 1. Give an interpretation of $(z_j)_i$, the i-th entry of the $j$ group representative.Answer:If $(z_j)_i = 0$, it means in group $j$, the number of vectors with i-th entry ZERO is more than those with i-th entry ONEIf $(z_j)_i = 1$ it means in group $j$, the number of vectors with i-th entry ONE is more that those with i-th entry ZERO
Normalization is a big and important topic in machine learning so in this article I collect three important normalization methods which are batch norm, layer norm and group norm. I would also display how the normalizaiton work using CS231n codes as examples.The following figure virtualizes the difference among batch norm, layer norm and group norm.Normalization methods . N as the batch axix, C as the channel axis (Dimension), (H,W) as spatial axes - image height and width. The pixels in blue are normalized by the same mean and variance, computed by aggregating the values of these pixels.1 The Comparison of BN, LN and GNBN - batch normalizationLN - layer normalizationGN - group normalizationNow we have$X$ : Matrix, mini-batch data of shape (N, D)$\gamma$ : Scale parameter$\beta$ : Shift paremeterN is the number of samples in a batch, and D is the number of features. And $x_{i,j}$ to represent the element in matrix X.2 ForwardBatch Normalization ( BN )$$ \begin{aligned} &\mu_j \leftarrow \frac{1}{N}\sum_{i=1}^N x_{i,j} \\ &\sigma_j^2 \leftarrow \frac{1}{N} \sum_{i=1}^N (x_{i,j} - \mu_j)^2 \\ &\hat{x_{i,j}} \leftarrow \frac{x_{i,j} - \mu_j}{\sqrt{\sigma_j^2+\epsilon}} \\ &y_{i,j} \leftarrow \gamma \hat{x_{i,j}} + \beta \equiv BN_{\gamma,\beta}(x_{i,j}) \end{aligned} $$The python code# x: Data of shape (N, D) # gamma: Scale parameter of shape (D,) # beta: Shift paremeter of shape (D,) N, D = x.shape mean = np.mean(x, axis=0, keepdims=True) # (1, D) var = np.var(x, axis=0, keepdims=True) # (1, D) x_norm = (x - mean) / np.sqrt(var + eps) # (N, D) out = x_norm * gamma + beta Layer Normalization ( LN )Batch normalization has proved to be effective in making networks easier to train, but the dependency on batch size makes it less useful in complex networks which have a cap on the input batch size due to hardware limitations.Several alternatives to batch normalization have been proposed to mitigate this problem; one such technique is Layer Normalization. Instead of normalizing over the batch, we normalize over the features. In other words, when using Layer Normalization, each feature vector corresponding to a single datapoint is normalized based on the sum of all terms within that feature vector.Layer Normalization Ba, Jimmy Lei, Jamie Ryan Kiros, and Geoffrey E. Hinton. "Layer Normalization." stat 1050 (2016): 21.The LN's formula is very similar to BN, just the across dimension is different.$$ \begin{aligned} &\mu_i \leftarrow \frac{1}{D}\sum_{j=1}^D x_{i,j} \\ &\sigma_i^2 \leftarrow \frac{1}{D} \sum_{j=1}^D (x_{i,j} - \mu_i)^2 \\ &\hat{x_{i,j}} \leftarrow \frac{x_{i,j} - \mu_i}{\sqrt{\sigma_i^2+\epsilon}} \\ &y_{i,j} \leftarrow \gamma \hat{x_{i,j}} + \beta \equiv LN_{\gamma,\beta}(x_{i,j}) \end{aligned} $$The python codeN, D = x.shape mean = np.mean(x, axis = 1, keepdims = True) # (N, 1) var = np.var(x, axis = 1, keepdims = True) # (N, 1) x_norm = (x - mean) / np.sqrt(var + eps) # (N, D) out = x_norm * gamma + betaSpatial Batch Normalization ( SBN )The BN input data shape is (N, D). But for the CNN's layer, it receives input data with shape (N, C ,H, W) and produce outputs of shape (N, C ,H, W) where the N dimension gives the minibatch size and the (H, W) dimensions give the spatial size of the feature map. Therefore, We need to tweak the BN a bit, then we will get SBN ( Spatial Batch Normalization ).The python code, calling BN function. We need to transpose and reshape before sending the parameter into the batchnorm_forward() function.N, C, H, W = x.shape x_bn = x.transpose((0,2,3,1)).reshape(-1,C) out_bn = batchnorm_forward(x_bn, gamma, beta, bn_param) out = out_bn.reshape(N,H,W,C).transpose((0,3,1,2))numpy.transpose is exchanging the sequence of axis. The original axis sequence is N, C, H, W. After using transpose((0,2,3,1)), the sequence becomes N, W, H, C. The we use reshape(-1, C) to make the matrix become 2 dimension --- the x_bn shape is ( N * W * H, C ).Group Normalization ( GN )In the previous part, we mentioned that Layer Normalization is an alternative normalization technique that mitigates the batch size limitations of Batch Normalization. However, as the authors of Ba, Jimmy Lei, Jamie Ryan Kiros, and Geoffrey E. Hinton. "Layer Normalization." stat 1050 (2016): 21. observed, Layer Normalization does not perform as well as Batch Normalization when used with Convolutional Layers.The authors of Wu, Yuxin, and Kaiming He. "Group Normalization." arXiv preprint arXiv:1803.08494 (2018). propose an intermediary technique. In contrast to Layer Normalization, where you normalize over the entire feature per-datapoint, they suggest a consistent splitting of each per-datapoint feature into G groups, and a per-group per-datapoint normalization instead.Even though an assumption of equal contribution is still being made within each group, the authors hypothesize that this is not as problematic, as innate grouping arises within features for visual recognition. One example they use to illustrate this is that many high-performance handcrafted features in traditional Computer Vision have terms that are explicitly grouped together. Take for example Histogram of Oriented Gradients N. Dalal and B. Triggs. Histograms of oriented gradients for human detection. In Computer Vision and Pattern Recognition (CVPR), 2005.-- after computing histograms per spatially local block, each per-block histogram is normalized before being concatenated together to form the final feature vector.The python codeN, D = x.shape x_group = np.reshape(x, (N, G, D//G)) mean = np.mean(x_group, axis = 2, keepdims = True) var = np.var(x_group, axis = 2, keepdims = True) x_groupnorm = (x_group - mean) / np.sqrt(var + eps) x_norm = np.reshape(x_groupnorm, (N, D)) out = x_norm * gamma + betaSpatial Group Normalization ( SGN )We can understand the nature of SGN by comparing with BN / SBN.The python codeN, C, H, W = x.shape x_group = np.reshape(x, (N, G, C//G, H, W)) mean = np.mean(x_group, axis = (2, 3, 4), keepdims = True) var = np.var(x_group, axis = (2, 3, 4), keepdims = True) x_groupnorm = (x_group - mean) / np.sqrt(var + eps) x_norm = np.reshape(x_groupnorm, (N, C, H, W)) out = x_norm * gamma + betaC//G is that C is divided by G. axis=(2,3,4) is that do meaning to axis 2,3,4 one by one.3 Backward
ML-HW1 PDFUpdate on October 4, 2019: ML-HW1 Solution PDFQuestion 1According to the known condition, make $x_0=1$ i.e. add a column with 1 in matrix $X$:$$ X = \begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1\\ 1 & 1 & 0\\ 1 & 1 & 0 \end{bmatrix} \quad y = \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} $$The OLS solution:$$ \begin{aligned} \hat{W} &= (X^TX)^{-1} \cdot X^T \cdot y \\ &= \left(\begin{bmatrix} 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 0\\ \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1\\ 1 & 1 & 0\\ 1 & 1 & 0 \end{bmatrix}\right)^{-1} \cdot \begin{bmatrix} 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}\\ &= \begin{bmatrix} 5 & 3 & 3\\ 3 & 3 & 1\\ 3 & 1 & 3 \end{bmatrix}^{-1} \cdot \begin{bmatrix} 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}\\ \end{aligned} $$$$ \begin{aligned} \hat{W} &= \begin{bmatrix} 2 & -3/2 & -3/2\\ -3/2 & 3/2 & 1\\ -3/2 & 1 & 3/2 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}\\ &= \begin{bmatrix} 1/2 & 1/2 & -1 & 1/2 & 1/2\\ -1/2 & -1/2 & 1 & 0 & 0\\ 0 & 0 & 1 & -1/2 & -1/2 \end{bmatrix} \cdot \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 2\\ 3/2\\ -3/2 \end{bmatrix} \end{aligned} $$Question 2$\frac{1}{3} \sum_{i=1}^3 (y_i-\omega_0-\omega_1x_i)^2 + \lambda \omega_1^2$ where $\lambda=1$ ---> (c)$\frac{1}{3} \sum_{i=1}^3 (y_i-\omega_0-\omega_1x_i)^2 + \lambda \omega_1^2$ where $\lambda=10$ ---> (b)$\frac{1}{3} \sum_{i=1}^3 (y_i-\omega_0-w_1x_i)^2 + \lambda (\omega_0^2+\omega_1^2)$ where $\lambda=1$ ---> (a)$\frac{1}{3} \sum_{i=1}^3 (y_i-\omega_0-\omega_1x_i)^2 + \lambda (\omega_0^2+\omega_1^2)$ where $\lambda=10$ ---> (d)Explanation If we give the linear regression line an equation $y=kx+b$ then the $\omega_0$ is $b$ and the $\omega_1$ is $k$. The (c) line has lower slope because the $1\cdot \omega_1^2$ will make slope smaller. However too big $\lambda = 10$ will cause nearly no slope in the (b) line. If we add $w_0^2$ to the regularization, it causes both $b$ and $k$ decay. Compared to (1), the answer would be (a) line which has smaller $b$. Obviously, (4) will match (d) line because both $b$ and $k$ are small and the line is underfitting.Question 3Like Question 1, writing down the matrix $X$ and $y$:$$ X = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 & 1\\ 1 & 1 & 0\\ 1 & 1 & 1 \end{bmatrix} \quad y = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} $$Use batch gradient descent algorithm, get the parameter $\omega$ freshing formula$$ \omega_j=\omega_j+\alpha \sum_{i=1}^4[y_i-\sigma(\omega_0+\omega_1 x_1+\omega_2 x_2)]\cdot x_{i,j} $$Suppose $\omega_0 = -2$, $\omega_1 = 1$ and $\omega_2 = 1$ initially and $\alpha = 0.1$. So we can calculate$$ \begin{aligned} \omega_0 = -2 + 0.1\cdot \{& [0-\sigma(-2+0+0)] \cdot 1 +\\ & [0-\sigma(-2+0+1)] \cdot 1 + \\ & [0-\sigma(-2+1+0)] \cdot 1 + \\ & [1-\sigma(-2+1+1)] \cdot 1 \} = -2.02 \end{aligned} $$Similarly, we can calculated$$ \omega_1 =1.02 \quad \omega_2 = 1.02 $$Use sigmoid function$$ \begin{aligned} \hat{y_1} &= \sigma(\omega_0+\omega_1 \cdot 0+\omega_2 \cdot 0) = 0.12 \quad having \ 12\% \ chance \ in \ class \ 1 \ (belong \ to \ class \ 0)\\ \hat{y_2} &= \sigma(\omega_0+\omega_1 \cdot 0+\omega_2 \cdot 1) = 0.27 \quad having \ 27\% \ chance \ in \ class \ 1 \ (belong \ to \ class \ 0)\\ \hat{y_3} &= \sigma(\omega_0+\omega_1 \cdot 1+\omega_2 \cdot 0) = 0.27 \quad having \ 27\% \ chance \ in \ class \ 1 \ (belong \ to \ class \ 0)\\ \hat{y_4} &= \sigma(\omega_0+\omega_1 \cdot 1+\omega_2 \cdot 1) = 0.51 \quad having \ 51\% \ chance \ in \ class \ 1 \ (belong \ to \ class \ 1) \end{aligned} $$The class distribution is [0, 0, 0, 1] so the training error = 0%Question 4use raw featuresIf we use only raw features to classify, we would find that it's a linear-inseparable question. This is because that we cannot find a surface to distinguish the positive and the negative. I use textit{numpy} to help me calculate the batch gradient descent (BGD) process.X4 = np.array([[1,0,0], [1,0,1], [1,1,0], [1,1,1]]) y4 = np.array([1,0,0,1]) w4 = np.array([-2,1,1]) a = 0.1 for i in range(100): w4 = w4 + 0.1 * (y4 - sc.expit(w4.dot(X4.T))).dot(X4) print(w4) # weight print(sc.expit(w4.dot(X4.T))) # y_predictNo matter how many iterations I run, the minimum error only achieves 1. After 100 iterations,weight = [-0.3395675 0.28609699 0.28609699] y_predict = [0.41591454 0.48663556 0.48663556 0.55789577]After 1,000 iterations,weight = [-2.23876505e-07 1.88743639e-07 1.88743639e-07] y_predict = [0.49999994 0.49999999 0.49999999 0.50000004]add an additional featureHowever, if we add an additional feature, it's equivalent to that projecting features from 2D to 3D. This makes the problem become linear-separable. Using the following code, after doing approximately 130 iterations, we can get a model having 0 trainning error (minimum training error).X5 = np.array([[1,0,0, 0], [1,0,1, 0], [1,1,0, 0], [1,1,1, 1]]) y5 = np.array([1,0,0,1]) w5 = np.array([-2,1,1, 1]) a = 0.1 for i in range(130): w5 = w5 + 0.1 * (y5 - sc.expit(w5.dot(X5.T))).dot(X5) print(w5) print(sc.expit(w5.dot(X5.T)))The weight and y_predict after 130 iterations,weight = [ 0.0819811 -0.97091908 -0.97091908 3.39687673] y_predict = [0.5204838 0.29132904 0.29132904 0.82303106]Question 5$$ \omega_1 = \omega_1 + \alpha \sum_{i=1}^N[y_i-\sigma({\omega}^T {x}_i)]x_{i,1} $$If predicted value $\sigma({\omega}^T {x}_i)$ is smaller than the actual value $y_i$, there is reason to increase $w_j$. The increment is proportional to $x_{i,1}$. If predicted value $\sigma({\omega}^T {x}_i)$ is larger than the actual value $y_i$, there is reason to decrease $w_j$. The decrement is proportional to $x_{i,1}$.However, the question has already supposed the feature $x_1$ is binary whose value is unbalanced. The zero value of $x_1$ keeps the $w_1$ from textit{learning} features from the example with LABEL 0. Otherwise, the $\omega_1$ would adjust according to both two classes. Therefore, this rule will force the model to fit example with a small number of training examples with LABEL 1 ( special feature in training set ). This causes textbf{overfitting}.$$ \omega_1 = \omega_1 + \alpha \left[-\lambda \omega_1 + \sum_{i=1}^N[y_i-\sigma({\omega}^T{x}_i)]x_{i,1}\right] $$Then adding the regularization constant is able to textbf{reduce overfitting}. It helps the model not to learn too much from the training set. In the update rule, the $-\lambda \omega_1$ is independent, not influenced by the feature $x_1$.
ML-HW2 PDFUpdate on October 19, 2019: ML-HW2 Solution PDFQuestion 1(a) Considering Naive Bayes model, the features are conditionally independent. And because of the binary features, we can use Bernoulli distribution for the class-conditional probability$$ p(\vec{x}|y=c) = \prod_{j=1}^2Ber(x_j|\mu_{jc}) $$Use Bayes rules, the posterior probability$$ \begin{aligned} p(y=c|\vec{x}) &= \frac{P(\vec{x},y=c)}{P(\vec{x})} \\ &= \frac{P(y=c)}{P(\vec{x})} \cdot p(\vec{x}|y=c) \\ &= \frac{P(y=c)}{P(\vec{x})} \cdot \prod_{j=1}^2Ber(x_j|\mu_{jc}) \end{aligned} $$(b) For instance 1, $\vec{x}=\{x_1,x_2\}=\{0,0\}$$$ P(\vec{x},y=0) = P(y=0) \cdot Ber(x_1|\mu_{10}) \cdot Ber(x_2|\mu_{20}) = \frac{3}{8} \times 0 \times \frac{2}{3} = 0 $$$$ P(\vec{x},y=1) = P(y=1) \cdot Ber(x_1|\mu_{11}) \cdot Ber(x_2|\mu_{21}) = \frac{5}{8} \times \frac{4}{5} \times \frac{2}{5} = \frac{1}{5} $$$$ \therefore P(\vec{x}) = 0 + \frac{1}{5}=\frac{1}{5} $$$$ p(y=0|\vec{x}) = \frac{P(\vec{x},y=0)}{P(\vec{x})} = \frac{0}{1/5} = 0 $$$$ p(y=1|\vec{x}) = \frac{P(\vec{x},y=1)}{P(\vec{x})} = \frac{1/5}{1/5} = 1 $$For instance 7, $\vec{x}=\{x_1,x_2\}=\{1,1\}$$$ P(\vec{x},y=0) = P(y=0) \cdot P(\vec{x}|y=0) = P(y=0) \cdot Ber(x_1|\mu_{10}) \cdot Ber(x_2|\mu_{20}) = \frac{3}{8} \times 1 \times \frac{1}{3} = \frac{1}{8} $$$$ P(\vec{x},y=1) = P(y=1) \cdot Ber(x_1|\mu_{11}) \cdot Ber(x_2|\mu_{21}) = \frac{5}{8} \times \frac{1}{5} \times \frac{3}{5} = \frac{3}{40} $$$$ \therefore P(\vec{x}) = \frac{1}{8} + \frac{3}{40} = \frac{1}{5} $$$$ p(y=0|\vec{x}) = \frac{P(\vec{x},y=0)}{P(\vec{x})} = \frac{1/8}{1/5} = \frac{5}{8} $$$$ p(y=1|\vec{x}) = \frac{P(\vec{x},y=1)}{P(\vec{x})} = \frac{3/40}{1/5} = \frac{3}{8} $$Question 2If all classes shares the same covariance matrix$$ \begin{aligned} P(y=c|\vec{x}) & \propto P(y=c) \cdot P(\vec{x}|y) \\ & \propto \pi_c \cdot e^{-\frac{(\vec{x}-\vec{\mu_c})^T \cdot \Sigma^{-1} \cdot (\vec{x}-\vec{\mu_c)}}{2}} \\ &= \pi_c \cdot e^{-\frac{1}{2}\vec{x}^T\Sigma^{-1}\vec{x}} \cdot e^{\frac{1}{2}\vec{\mu_c}^T\Sigma^{-1}\vec{x} - \frac{1}{2}\vec{\mu_c}^T\Sigma^{-1}\vec{\mu_c}} \\ & \propto e^{\vec{\mu_c}^T\Sigma^{-1}\vec{x} - \frac{1}{2}\vec{\mu_c}^T\Sigma^{-1}\vec{\mu_c} + log\pi_c} \end{aligned} $$Let $\vec{w_c}^T=\vec{\mu_c}^T\Sigma^{-1}$ and $b_c=-\frac{1}{2}\vec{\mu_c}^T\Sigma^{-1}\vec{\mu_c} + log\pi_c$. Then$$P(y=c|\vec{x}) \propto e^{\vec{w_c}^T\vec{x}+b_c}$$According to the above analysis, if all classes shares the same covariance matrix, the GDA goes back to softmax regression. And if let $C=2$, we can get the logistic regression model.ComparisionLogistic RegressionGDADistribution of Data$P(y=c \mid \vec{x},\vec{w})=Ber(y\mid \sigma(\vec{w}^T\vec{x}))$ . It's a weaker assumption but performs more robust. It's a simpler and lower-lever model.$P(\vec{x}\mid y=c)= N(\vec{x}\mid \vec{\mu},\vec{\Sigma})$. It is a stronger assumption but may not be reliable when encountering some extreme situations.Amount of DataIt requires more data so it's harder for training.It requires less data to achieve a certain level of performance than logistic regression. It's easier to learn parameters.Question 3The logistic regression is a kind of dicriminative model and the GDA is a kind of generative model. When we come to the topic of classification, we have other kinds of classifiers. For example, on the one hand, Naive Bayes classifier, Bayesian networks, LDA and etc. belong to generative model. On the other hand, SVM, Softmax, decision tree, neural network. The comparision of generative classifiers and discriminative classifiers is as follows:ComparisionGenerative ClassifierDiscriminative ClassifierParameter EstimationGenerative classifier finds the best class the object belongs to by maximizing the joint probability $P(\vec{x}, y)$ using $P(y)$ and $P(\vec{x}\mid y)$. It's easier to do this because it has closed-form formulae for MLEDiscriminative classifier directly do classificaton by maxizing the conditional probability $P(y\mid \vec{x})$. More complex to do parameter estimation because it requires gradient descent to compute MLEMissing DataNo principled way to handleEM algorithmFeatures TransformHard because the new feature are correlated in complex waysEasy. $\vec{x} \rightarrow \Phi(\vec{x})$. Used in deep learning.Semi-supervised LearningCan use unlabeled data to help with trainingHarderQuestion 4The curve(ii) represents the training error. On the one hand, this is because that generally the test error will be larger than training error. On the other hand, when the training data set is small, the data set cannot well illustrate the nature of the whole data. It's easy to train a model with zero training error but very high test error. When gradually increasing the trainning set, the training error would increase from zero to a stable value and the test error would decrease from a large value to the stable value.The gap is called generalization gap. According to VC Theorem, I use $m$ to represent the sample size and $d=VC(H)$ to represent the model complexity. The gap between training error $\hat{\epsilon}(h)$ and test error $\epsilon(h)$ satisfies an inequality relation as follows:With probability at least $1-\delta$, we have that all for $h\in H$$$ |\epsilon(h)-\hat{\epsilon}(h)| \leq O \left( \sqrt{\frac{d}{m}log\frac{m}{d}+\frac{1}{m}log\frac{1}{\delta}} \right) $$In general, we have $\frac{m}{d}>e$ so in the interval $[e,+\infty]$Fixing m. $d$ increases $\rightarrow$ $\frac{m}{d}$ decreases $\rightarrow$ $\frac{d}{m}log\frac{m}{d}$ increases $\rightarrow$ $O(\cdot)$ increases $\rightarrow$ generalization gap widens. i.e. When increasing the model complexity, the geralization gap would widen. Their relationship can be further illustrated by figure 2. As we see, the gap between green line and blue line is getting bigger and bigger as the model capacity increases.Fixing d. $m$ increases $\rightarrow$ $\frac{m}{d}$ increases $\rightarrow$ $\frac{d}{m}log\frac{m}{d}$ decreases $\rightarrow$ $O(\cdot)$ decreases $\rightarrow$ generalization gap narrows. i.e. The generalization gap narrows as the sample size becomes larger. And this is already shown in figure 1. Hence, more data implies better performance of learning an algorithm.
一直想写一篇文章总结一下机器学习的脉络，网络上零散的知识很多，但我觉得归纳最清晰的还是这张思维导图，来自Vas3k的一篇介绍机器学习（Machine Learning）的文章。从一张思维导图开始机器学习可以分为四大类：经典的机器学习（classical learning）强化学习（reinforcement learning）集成学习（ensemble methods）神经网络和深度学习（neural network and deep learning）当我们数据简单、特征清晰的时候，我们往往采用经典的机器学习方法，你可能会说，我们有那么高级的机器学习方法，譬如强大的神经网络和集成学习，为什么不用呢？当然，不是不能用，比如处理垃圾邮件分类时，我们使用贝叶斯分类器，就能够快速、准确地完成筛选任务，错误率低于1%，我们何必使用复杂数倍的神经网络呢？杀鸡焉用牛刀。而在面对复杂的数据和高维的特征时，我们往往会采用神经网络，甚至深度学习的方法来处理。而三个臭皮匠顶个诸葛亮讲的就是集成学习，当我们对结果的精确度要求较高的时候，我们会训练出多个模型，让它们互相矫正对方的错误，共同参与决策，这样可以提高准确性，降低错误率。但是有时候，我们没有数据，但是我们有能够交互的环境，通过环境的反馈来不断调整自身，最终适应环境，这就是强化学习的思路。这张知识图谱基本覆盖了实际的机器学习应用所用的各种方法，分类、回归、模式搜索、聚类、降维等等，后面我会具体说明，但为了保证知识脉络的完整性，我还会再讲讲我们为什么需要机器学习，而机器学习的三要素又是什么。我们为什么需要机器学习？首先我们需要弄清楚，我们为什么需要机器会学习？这里我引用一下Vas3k的例子。隔壁老王想买一辆车，他首先在互联网上浏览了几十个广告，发现新车大约是20,000美元，一年车龄的二手车是19,000美元，而用过两年的车是18,000美元，依此类推。结果我们聪明的老王同学发现汽车价格取决于车龄，每年下降1,000美元，但不会低于10,000美元。用机器学习的术语，比利发明了回归，他根据已知的历史数据预测了一个价值（价格）。除了估计汽车的价格，人们也尝试过估算iPhone的价格，或者弄清楚烧烤的时候，要根据人数决定带多少串鸡肉串、羊肉串，多少斤金针菇，人们总是这样做。那是不是世界上所有的问题都可以归结为一条简单的公式呢？不幸的是，这是不可能的。让我们回到汽车上。问题是，它们有不同的生产日期，数十种选择，技术条件，季节性需求激增，而估计只有老天爷才知道还有多少其他隐藏的因素。一个普通人在计算价格时，肯定无法将所有这些数据保留在脑海中。人们愚蠢而懒惰，我们需要机器为他们做数学。因此，我们为机器提供一些数据，并要求其查找与价格有关的所有隐藏模式。结果人们发现机器做预测的时候竟然做的比人还好，这让研究人员们异常兴奋。于是机器学习就诞生了。机器学习的三要素数据、特征和算法是机器学习的三要素，理论上而言，所有的机器学习任务都抽象为：根据已知数据对未知结果的预测。我们可以认为这是一个基本命题、基本任务，听起来天方夜谭的人工智能（Artificial Intelligence）也逃脱不了。什么是数据？我们想检测垃圾邮件，那么我们需要分析邮件内容，我们想预测股票，那么我们需要分析过去的股票市场、公司状况、国际市场、政策等等这些信息，这些都是数据。而如何去描述数据，就要用到数据的特征，比如邮件内容中单词出现的频率；而历史股价、成交量、K线、MACD等等这些特征参数则用于描述股票市场，同样，描述公司财务状况，描述国际市场，描述政策，都有不同的特征。最后，算法是我们解决问题的策略、方式和步骤，面对不同的机器学习任务、不同的数据集、不同的特征分布，我们会采取不同的方法，期望以最优的方式完成任务。伴随着机器学习，我们常常听到的数据科学、数据发掘这些名词，它们和机器学习又有什么关系呢？我们可以认为数据科学（Data Science）侧重处理特征，有时候数据的特征不会像文本中的词频这样明显，比如我们需要设计一个人机对话的人工智能，绝对不会仅仅是统计词频这么简单吧？这时候会需要发现或者构造合适的特征参数。而数据发掘（Data Mining）更注重算法这一块，比较著名的一个例子，要从一大段新闻稿中提取出主题（topics），我们需要找到一些频繁一起出现的单词，比如出现data往往后面会跟一个mining，我们会使用Apriori、FP-Growth算法来实现主题的提取。当然这些都是狭义的定义，如今机器学习这个领域里，已经不会太区分数据科学和数据发掘，说什么你是是一个数据科学家，而我是一个数据挖掘家，这样的说法是低级的，因为现在的机器学习任务都是相当复杂和具有挑战性的，我们已经不再严格区分数据科学、数据挖掘、机器学习这些名词的区别了，我们需要综合运用它们。人工智能与机器学习的关系从我步入大学开始，也就是2015-2016年的时候，人工智能、大数据、云计算、机器学习、计算机视觉（CV）、自然语言处理（NLP）等等这些概念就天天被搬上媒体渲染，那么他们之间的关系又是什么呢？这里先跟大家将一个笑话，一个媒体这样报道的《神经网络会替代机器学习吗？》或者一些不知道哪里的科普讲：“线性回归是人工智能”，我们看看下面这张图：在人工智能这个大领域下，机器学习是专门研究怎样让机器拥有“智能”的一门学科，理论基础本质是数学，具体涉及概率统计学、线性代数、离散数学、数学分析、微积分等数学理论，但它不仅仅停留在数学分析上，它与计算机编程紧密结合，别忘了，机器学习研究的目的是落地与现实应用的，让机器拥有“智能”，总而言之，可以理解成让机器能够发掘隐含的信息、分析规律、作出预测、作出决策。我们的理想是想人工智能能像我们人类一样看、像人类一样听说读写，这就需要计算机拥有视觉和处理语言的能力，而这便是现代人工智能领域最热门的两个领域——计算机视觉（CV）和自然语言处理（NLP），他们处理的对象分别是图像（image）和语言（language），所以自然也需要图形学和语言学的一些理论知识，但背后需要坚实的机器学习理论根基。在机器学习中，有许多不同的学习方法，神经网络只是其中一种，也是最玄学、最万能的一种，而我们发现构建一个非常庞大而深层次的网络能够使机器学习得无比强大，在执行某些任务上，达到人类无法企及的程度（比如说AlphaGo围棋、Google翻译、实时对抗游戏、图片分类、人脸识别），这就是深度学习。当然背后是有强大的算力和数据支撑的，也许是成百上千块价值几百万的GPU，也许是一台每秒能做几亿亿次浮点运算的超级计算机，还要有巨量的数据提供训练和学习的知道，这就是云计算和大数据的概念。所以机器学习和神经网络是包含关系，而不是同等关系的。前面媒体报道的《神经网络会替代机器学习吗？》听起来就像“汽车轮胎会替代汽车吗？”一样怪异。而且我想再次强调，机器不会杀死人类，当你真正步入机器学习领域的时候，你会发现现有的数学工具完全不足与勾勒出人类智慧的模型，我们只是在不断地求方程式的最优解而以。我们目前对于人类大脑的运行机制还不深入，人类的意识是怎么诞生的，是以一种什么样的形态存在的，这么多的神经元是怎么协同工作的？很多原理我们还不清楚。目前的机器学习只在某些特定的任务上超越人类，而真正拥有智能的路还有很长。一张机器学习的网络clustering - K-means、DBSCAN、Kernel K-means => Kernelpattern search - apriori、FP-growth降维打击 - PCA、SVD分类 - KNN、Logistic regression=>softmax、SVM、decision tree、贝叶斯分类器回归 - linear regression集成学习bagging 随机森林 Ramdom forestboosting Adaboost、LightGBMstacking不同算法之间的比较、区别、优劣模型的评估与选择错误率与精度查准率、查全率与F1ROC与AUC代价敏感错误率与代价曲线比较验证损失函数zero-one losslogistic losshinge lossexponential losssquared loss正则化L1, L2weight decay权重衰减dropout 随机失活正则化的作用梯度下降法和牛顿法的区别有哪些常用的优化方法SGD、BGD、MBGD牛顿法动量 - SGD with momentumadaptive gradient (learning rate) - AdaGradRMSProp (Root Mean Square) PropagationAdam对偶问题，什么是对偶问题拉格朗日乘子法其他1 聚类聚类（Clustering）算法可以划分为六大类：划分聚类（Partition-based methods）K-MeansK-MedianCLARANS算法层次聚类（Hierarchical Clustering）BIRCH：利用树结构对数据集进行处理，叶结点存储一个聚类，用中心和半径表示，顺序处理每一个对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程。CHEMALOEN：首先由数据集构造成一个K-最近邻图$G_k$，再通过一个图的划分算法将图$G_k$划分成大量的子图，每个子图代表一个初始子簇，最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇。DIANA：属于分裂的层次聚类AGNES：属于凝聚的层次聚类模糊聚类EM算法基于密度的聚类（Density-based methods）DBSCAN：采用空间索引技术来搜索对象的邻域，引入了“核心对象”和“密度可达”等概念，从核心对象出发，把所有密度可达的对象组成一个簇。OPTICS：结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果。基于网格的聚类（Grid-based methods）基于模型的聚类（Model-based methods）树状图（dengrogram）可以用来表示数据之间的层级聚类结构关系。举个例子，如果我们在这个位置切割树状图，可以形成四个簇，图中已用红色的圆圈圈出来了。我们还可以有其他切分的方法，在其他层次切分，我们会得到不同数量和分布的簇，簇是拥有层次关系的，这就是层次聚类的含义。2 集成学习（ensemble learning）总结方法顺序训练还是并行训练如何生成不同的模型方差和偏差的情况Bagging并行训练Bootstrap data减小方差，但是不减小偏差Random Forest并行训练Bootstrap + random subset of features at splitting减小方差Boosting顺序训练每次迭代需要重新分配训练样本的权重两者都减小3 PCA / SVD主成分分析（PCA - Principle Component Analysis）奇异值分解（SVD - Singular Value Decomposition ）静哥哥的博客：https://www.cnblogs.com/endlesscoding/p/10033527.html单位矩阵（identity matrix）矩阵的行列式（determinant）矩阵的特征值（eigenvalues）和特征向量（eigenvectors）
An appreciation about Picasso's works visualization
https://www.nationalgeographic.com/magazine/2018/05/genius-picasso-art-categories-infographic/This visualization presents the works of Picasso in Spanish. It was created after analyzing 8,000 Picasso’s works using Picasso techniques and it's a kind of Convex Treemap. Painted on a canvas, it encodes the number of works that Picasso worked on a given theme by the area of partition. The larger partition is, the more works that he created. The 12 major themes and subcategories are encoded with different color hue, grain, shapes and positions.Why this visualization impresses me? In one word, the visualization builds a bridge between Picasso's art styles and us. For instance, we can see there is a woman face in the middle of the picture. She has eyes, nose and even mouth. Zooming this part, we can see more details. Picasso prefers using orange-yellow and pieces objects to paint human faces. And he’s good at using the combination of pieces to reflect human’s emotion. This is his style and the design of this visualization imitates it. The shape, color and grain of each visualization category are related to the arts styles that it belongs to.Yes, we can have an overview about Picasso's works distribution through watching the partitions size and distribution. The encoding scheme is efficient. However, more importantly, the visualization itself is a work, a reproduction of Picasso's arts, a kind of respect to master Picasso. The color, size, shape and grain --- all these elements not only display the data, but also show the Picasso’s arts styles and his individual spirit on arts. What this visualization conveys is meaningful. We can see all the Picasso's art styles in one picture. It seems that it brings Picasso back to life and make all of us feel the glory of Picasso in the past.