機器學習的演算法和普通《演算法導論》里的演算法有什麼本質上的異同?

本人非計算機專業出身,對這些方向感興趣,所以有此一問。曾經問過一些人,說是機器學習全是數學,是用數學的方式試圖去描述和理解我們的世界,而《演算法導論》里的這些演算法主要是如何用計算機的思維去處理一些實際的問題。我似懂非懂,還是沒能抓住最根源上的東西。希望能有一些專業的,通俗的回答,謝謝了

本題已加入圓桌 ? 數據挖掘應用,更多「數據挖掘」相關的話題歡迎關注討論


區別不大。演算法的目的都是一樣的:定一個目標,加一些約束,求一個比較好的結果。

  • 相同點:演算法是用來求解優化模型,《演算法導論》和機器學習在這一點上是一回事。
  • 區別:《演算法導論》里幾乎都是組合優化;而機器學習里主要是連續的問題,凸優化較多,也有很多非凸優化。機器學習演算法自然大都是梯度下降、坐標下降、蒙特卡洛 這樣的演算法,與《演算法導論》里的演算法長得很不像。
  • 是機器學習里也有組合優化,比如聚類、比如概率圖模型。在這一點上,跟演算法導論區別不大。

為什麼《演算法導論》里大多是組合優化?我拿排序問題舉個栗子。

  • 排序問題就是個組合優化。給定n個實數,要求按降序排列。
  • 目標函數:常數(沒有目標函數)
  • 可行域是n維空間一個子集,集合的元素都是向量a,滿足:a_1 geq a_2 geq cdots geq a_n.
  • 為了求解這樣一個組合優化模型,可以有很多演算法,比如快排、堆排、冒泡。

如果你能理解排序是個組合優化問題,你肯定能理解 網路流、最短路 等等問題都是組合優化。


拿機器學習里常用的最小二乘回歸對比一下。

  • 最小二乘是個凸優化問題。
  • 目標函數:||X eta - y ||_2^2
  • 可行域:整個空間
  • 為了求解這個凸優化模型,可以用梯度下降、共軛梯度、坐標下降等演算法
  • 你也可以用概率模型描述這個問題:y是eta的線性函數 + 高斯雜訊。然後可以用蒙特卡洛演算法來求eta

機器學習里也有組合優化,比如k-means。

  • k-means要求把集合{1, ..., n}劃分成k個子集,使得對應的向量離cluster中心的平均距離最短。
  • k-means有具體的組合優化模型,我不寫了。對應的組合優化模型被證明是NP hard。
  • 有很多近似演算法求解k-means,最常用的是Lloyd Algorithm。

==========

注意,method和algorithm是兩個東西。例如,

  • k-means是method,有幾種優化問題model,有很多求解的algorithms。你們最常用的那種迭代演算法是Lloyd Algorithm。
  • LDA是method也是model(這種method就一種model),這個model的求解是個NP Hard的問題(我記得Arora文章里證明過)。有很多種演算法求解LDA,比如variational inference、MCMC、tensor decomposition。
  • word2vec是method,用來解決NLP的一些問題;有很多models,比如skip-gram、深度學習;每種model都有很多演算法求解。

把method和algorithm混為一談是典型的「野路子」從業人員的特徵。比如,很多人喜歡把Lloyd演算法稱為kmeans。

經提醒,method和model有區別,但是界限不明,很多時候可以混用。但是algorithm和method絕對不能混用。


演算法導論里的演算法本質上是對有精確解的問題,如何更有效率地求得這個解。這個效率可以是計算時間更短,也可以是計算過程所需要的空間更少。

一個簡單的例子是,給定一個亂序數組,如何快速的將其按從小到大的順序重新排列,或者找到其中的中位數。這些問題都有確定且唯一的答案,一般都會有一個笨方法(窮舉或遍歷),只要一步一步來就可以解,所謂演算法只是如何精簡步驟,更快更省事地找到這個解。這些演算法處理的數據也都是結構簡潔且乾淨的類型,比如數組,二叉樹,圖之類的數據結構。數據規模對於這些演算法而言,影響的是計算所需的時間和空間,不會因為規模改變而影響演算法本身的邏輯以及計算的結果。

機器學習要解決的問題一般沒有精確解,也不能用窮舉或遍歷這種步驟明確的方法找到解,而且需要強調的是「學習」這個屬性,即希望演算法本身能夠根據給定的數據或計算環境的改變而動態的發現新的規律,甚至改變演算法程序的邏輯和行為。

舉例來說,可以是把一千份文檔歸類到不同的幾個類別里。最簡單的可以是給定幾個類別,比如新聞,小說,詩歌等,演算法來根據文章內容自動劃分到對應的類別里。這裡可以看出這個問題即使讓人做,也有很多模糊不能確定的地方,比如一篇法制晚報上的犯罪紀實是應該划到新聞,還是小說呢?或者說一篇長詩比如荷馬史詩是應該歸在小說還是詩歌呢?機器學習演算法想要解決的,就是根據從文章內容里找到的規律,來自動的給出一個劃分。而不同演算法可以給出不同的解,這些解都可以是「正確」的,所以一般還需要人為設計一個評判標準來決定孰優孰劣。

也可以不事先給定類別,而是讓演算法自己去發現文章中的規律,把相似度高的文章劃分到一起。這樣不同的演算法可能給出不同數量的類別劃分,可能是三個,四個,或者五個,也都可以是「正確」的劃分。甚至什麼是「相似度」,不同演算法也可以給出不同解釋,可以是名詞動詞形容詞的詞頻及比例,也可以是句子的語法結構等。

更進一步的,你可能還希望這個演算法能夠用來判斷一份新的文檔的類別。而輸入的新文檔越多,也會進一步擴大初始數據集的規模,規模變大以後,原來數據中不明顯的規律可能就變明顯了。比如說原來一千份文檔中只有一篇議論文,可能大多演算法都無法把它單獨划出一個類別,但當你持續輸入一百份議論文後,數據中議論文的比例就變成了101/1100,差不多10%,這時候演算法就應該劃分出單獨的議論文類別。在這個意義上,數據本身也對演算法有很大的影響,這也是和演算法導論中的演算法的一個本質區別。

技術上說,演算法導論中的演算法關注點在數據結構和計算複雜度,屬於離散數學的一個分支,不涉及微積分等高等數學概念。機器學習的演算法本身是基於概率,統計和優化(optimization)等理論和技術,從這個角度上說給人感覺更「數學」一點。

在具體的實現細節上,機器學習的演算法會大量應用演算法導論中的技術來改進計算效率。但需要強調這僅僅是對底層實現來說,在演算法本身的邏輯上,二者沒有太多聯繫。換句話說,演算法導論中的技術可以幫助你寫出更快的程序來運行機器學習演算法,但是這對機器學習要解決的問題本身是沒有什麼幫助的。熟練使用二叉樹散列表,準確估算一個圖演算法的複雜度,都沒有任何可能幫助你猜到在女朋友過生日時送什麼禮物最好(使用了機器學習演算法的淘寶君卻很可能知道!)。因此不要把它們看成是搭積木拼構件的關係。

最後,如果以上解釋仍然讓你費解,那麼還有一個更通俗的解釋:演算法導論是教你如何數數,而機器學習基本上相當於星座算命。一個很機械,一個靠忽悠,差不多就是這樣吧。


謝邀。
1,機器學習里的問題,很多都是判定問題或者聚類問題;它是對數據如何產生,數據有什麼規律感興趣;演算法導論里的演算法,數據是如何產生的我不知道,我也不在乎,現在是有數據了,強調的是數據的組織(數據結構)和處理(增刪改查排序等)。
我個人認為,這個是它們的本質區別。

2,當我們面對一個具體的機器學習里的問題時,這時候,某個演算法是否work,可能我們不知道。一般的做法是,假設數據的分布,設計演算法,驗證,重新評估重新設計。而演算法導論里的演算法,是很確定性的,因為我們此時對於輸入是比較清楚的;能不能解決這個問題,多長時間能解決這個問題,基本上是確定的(除了啟發式和概率演算法)。

3,機器學習里的演算法,大家似乎都不是很care時間和空間複雜度,其中一個原因是,很多演算法的時間複雜度顯而易見;演算法導論里的演算法,大家對時空複雜度(分析)非常care。

這其實也反應了評價這兩種演算法的好壞優劣的標準不同。在機器學習里,比如說準確率啊,召回率啊,NDCG啊,F1-score啊,AUC啊等等,除此之外,還有模型是否stable啊,是否容易並行啊等等也都是常見的角度和指標;而演算法導論里的演算法,最常見的,無非就是空間複雜度和時間複雜度了吧

4,還有很多。以後補充吧。

不過,它們都有一個共同特點,就是演算法和數據的關係非常密切:
機器學習方面,不同的數據集,不同的數據分布,得使用不同演算法。
演算法導論里的演算法,不同的數據,你得使用不同的排序方法,你知道,快速排序不是萬能的。
同理,LR/SVM/K-means也不是萬能的。

還有一個共同點,那就是先表達,再建模。
機器學習里的表達,很多是把輸入的樣本表示成feature們,然後模型。
演算法導論里的表達,就是把輸入的數據,組織成字元串啦、數組啦、鏈表啦、x-fast trie啦,treap啦,k-d tree啦等等數據結構,然後演算法。

學好演算法導論里的演算法,對優化機器學習演算法的設計和實現,有時候也有幫助。舉幾個例子吧。
動態規劃。馬爾科夫過程中優化計算。
堆。這種數據結構的使用,對於層次聚類的時間複雜度優化有幫助。
二分查找。對於確定k-means中的k有幫助。
等等等等。


這是個很好的問題。如果只是看演算法的「樣子」,可能會比較迷惑,機器學習演算法中也使用了經典演算法策略,例如監督學習的決策樹用了分治、流型學習的isomap用了最短路徑,強化學習的策略評估是動態規劃等等,看上去也沒什麼區別,但是直覺上機器學習演算法與經典演算法又很不一樣,這裡面的關鍵區別在哪呢,我們可以嘗試從另一個視角來看待演算法。

在一些人眼裡,演算法是解決問題的步驟,在另一些人眼裡,演算法只是一個證明,是關於一個問題可以在多少時間內求解到何種程度的證明。後者更關心的,是哪些問題可以求解哪些問題不可以、可以求解的問題哪些是能高效求解的等等。於是有了關於問題類的定義,例如可(有效)計算的類別——NP類問題的(優化)定義大致可以描述為

存在非確定圖靈機,對於任給問題的實例,能在關於問題規模的多項式時間找到該問題的解。

相似的,對於學習問題也有類別劃分,Leslie Valiant給出了可(有效)(監督)學習問題類的定義——近似概率正確可學習,大致描述為

對於任給的[0,1]間的誤差常數和概率常數,存在演算法A對於任給學習問題的實例,使用不超過關於誤差常數和概率常數(實際上是它們的倒數)的多項式個獨立同分布採樣的樣本,就能以足夠的概率(1-概率常數)找到一個模型,其真實誤差小於誤差常數。

從上面的定義中可以看到,對於經典問題類的定義非常清晰:圖靈機有形式定義,「問題的解」指優化問題最優解,定義中不存在任何不確定的部分。然而學習問題的定義中包含了一處很不確定的地方:演算法的輸入是有限樣本,輸出卻是關於真實誤差。在輸入有限樣本時,演算法無從得知真實誤差。從經典演算法角度,這是要解決一個看不見的問題,也就是不適定問題,是沒法解決的。因此在學習問題的定義中,加入了概率,讓演算法去猜面臨的問題是什麼,容忍一定猜錯的可能。

因此,經典演算法是在解決問題,然而學習演算法中有些環節並不是在解決問題,而是在猜測問題,有了對問題的猜測,才開始解決問題,不同的學習演算法就包含了不同的猜問題的策略,也就是歸納偏執(inductive bias)。這一部分就是經典演算法中所沒有的部分,是機器學習研究的核心。

機器學習論文看起來常常以優化技術為中心,容易讓人誤以為機器學習就是優化。Pedro Domingos 2012年在CACM發表的《A Few Useful Things to Know about Machine Learning》http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf是一篇有意思的文章,裡面給出了一個定義:

學習=表示+評價+優化

大體來講,「表示」指數據和模型的表達形式,例如數據是一個向量還是一個圖、模型是神經網路還是決策樹;「評價」定義了我們想要什麼樣的模型;「優化」則是學習過程的實施者。從這個定義看,"優化"對應了經典演算法(包括組合優化、凸優化等),而"表示+評價"則是機器學習獨有的,決定了學習系統能夠達到的泛化能力。不同的"表示+評價",關係到猜問題的策略,定義了優化要解決的問題是什麼。因此也可以看到,機器學習演算法,不僅包含了如何解決問題的部分,還包含了如何定義問題的部分。

總的來說,經典演算法是在適定(well-defined)問題下的求解過程,機器學習演算法是在病態(ill-posed)問題下的問題重定義與求解的過程。個人理解僅供參考。

====
寫了個開頭有這麼多人點贊,感覺很慚愧,自己挖的坑,趕在年三十前,含淚也要填完。。。

另外「非精確求解」和「概率求解」都不是機器學習演算法的特徵,在經典演算法中同樣有近似演算法和隨機演算法,這些演算法本身並不認為是機器學習演算法(當然可以用於機器學習),因為它們仍然面對的是適定問題。


《演算法導論》的演算法與機器學習演算法的關係,就好像做數學題和數學建模的關係。
贊同 @董可人的說法,演算法導論的演算法是面向有精確解的問題的求解方法。而機器學習演算法更多的是一種面向無精確解(或精確解很難得到)的問題的一種逼近策略。

舉個栗子:
做一道數學題(演算法題),用到了麥克勞林公式(動態規劃演算法),得到了一個精確的解(最優的方案)。其中,數學題中精確的解、演算法問題中的最優方案,都是唯一的、精確的。《演算法導論》中涉及的演算法大多都是上述這樣有精確解的問題的求解方法。

而當需要預測明天的天氣時,沒有演算法可以百分之百地保證預測一定是準確的,不到明天沒有人能精確知道明天的天氣。但我可以了解今天晚上的風向、濕度等等信息,利用機器學習演算法來預測明天是否會下雨。最後的預測結果會or不會下雨都不是一個精確的結果,機器學習預測的結果只是一個估計的、近似的結果,但仍是有價值。另外,機器學習演算法的一大特點是,它沒有面向問題直接編寫程序,而是建立學習模型解決問題,也是其與演算法導論中的演算法的一大不同。


機器學習是數學,其實演算法導論也是數學……比如離散數學之類。
演算法導論里的演算法用於那些定義良好,有明確精確答案的問題。機器學習的演算法用於那些問題很模糊,答案也模糊的問題。
在運用於實際數據時,演算法導論里的程序就是那些演算法本身,機器學習的程序則是演算法+訓練數據的總結。也就是說機器學習的演算法本身是無法直接用於計算實際數據的,它必須先輸入訓練數據,才能用於實際數據求解。訓練數據的好壞直接影響計算實際數據時的準確度。


個人感覺其實機器學習里的「演算法」應該叫做「模型」更貼切。


兩者都涵蓋演算法的某些子集,對演算法有個整體的認識才能了解清楚。

首先需要理解數學與演算法的關係,數學用來對實際問題建模,如何用程序求解需要演算法。與機器學習關係緊密的是數值方法和優化方法 (主要是非線性),而演算法導論關係較密的是離散數學和離散域優化方法,演算法導論中非數學相關部分才是純計算機的計算基礎。


我的看法是:兩類演算法都旨在解決優化問題。但機器學習演算法側重在連續優化問題,而《演算法導論》中的演算法側重於離散優化問題。


部份同意天行的答案。

所謂機器學習拆開來看是兩大塊,一塊是數學建模,一塊是優化求解。前者包括描述什麼對象,使用什麼結構,怎樣衡量好壞,加如什麼regularization,需要一定的數學和統計知識,還需要一些對應用的理解以及想像力。後者主要涉及優化演算法和數值方法,前一步定義出來的問題,用什麼方法來解決。

演算法導論裡面涉及的內容一般不包括數學建模,這是最最重要的區別。有了建模這一步,演算法上太複雜的問題可以在建模這一步就考慮某種簡化或者變化。這種思路單單通過學習演算法是不能掌握和發展的。

另外,雖然優化問題也可以籠統的歸類到演算法下面,但是和演算法導論討論的,以各種數據結構為基礎的演算法還是有區分的。更常見的情況是這類演算法通常是優化求解方法具體實現過程中的子問題。也可能某個優化問題正好和某個經典演算法問題不謀而合,相對少見了。


所應用數學的深度決定了2者的區別;
演算法導論只用到了:數學分析、簡單概率論、線性代數;基本是工科大一大二所學;
而能用到的,基本都是證明演算法的正確性;不需要證明的話,基本用不到數學工具,實際應用,照抄其中的代碼,可以直接應用到工程中;如果不考慮證明,基本不存在什麼數學模型(圖論除外),而是人們對實際工程應用的巧妙構思和巧妙解法。

而想要參透機器學習,除了上述基本數學工具,必須掌握:概率論、數理統計、最優化、凸分析、甚至是泛函分析等等高級數學工具,這些就已經基本涉及到應用數學專業大三、大四的數學水平了。這裡面基本都是數學模型,解法基於數學理論;如果不搞懂這裡面的數學,連基本的原理都無法搞清楚,更何談應用了。


怒答,反對上面一切答案~(終於有個裝逼的機會了╮(╯_╰)╭)
評論區有人說:

答主,你的答案光介紹了【演算法導論這本書寫了什麼】和【機器學習包括哪些內容】,並沒有說到【演算法導論中的演算法】和【機器學習中的演算法】有哪些區別啊。建議修改。

所以對答案進行一次修改如下:之後如果首位答案贊數夠多我再補充逐條反對內容啥的吧~

--------------------------------------------以下答題--------------------------------------
先說《演算法導論》的演算法,《演算法導論》到底在說什麼?我的理解是《演算法導論》主要在傳授演算法分析和演算法設計的基本思想和方法,並以一些非常基礎的數據結構和演算法對此進行說明和演示。所以《演算法導論》裡面涉及的內容實際上都非常基礎的,它給我們打開了一扇門,讓我們對數據結構和演算法窺其一斑,為以後的學習和工作打下基礎,就像書名《Introduction to Algorithms》所說一樣,這裡面的內容就是最基本的介紹,是每一個計算機研發工作者都應該掌握的。

然後再說機器學習,機器學習實際上是一門應用學科,在解決其中的問題時用到了大量的初中高級演算法,包括最基本的查找排序,到進階點的動態規劃、梯度下降、退火等優化演算法,再到各種數值計算演算法,數據結構也從基礎的線性表到各種圖表示結構,再到各種樹都會涉及。那麼機器學習過程算不算演算法呢?按照《演算法導論》的定義,演算法就是定義良好的計算過程,它取一個或一組值作為輸入,併產生一個或一組值作為輸出。亦即,演算法就是一系列的計算步驟,用來將輸入數據轉換成輸出結果。所以機器學習過程當然也是演算法。那麼這二者的區別在哪兒呢?評論區里 @李巨格 的一個比喻很好:

演算法是混凝土構件,而機器學習是用構件拼出的一種建築。

不過我覺得這個還不夠精確,準確來說應該是:《演算法導論》里介紹的基礎演算法就像最基本的樂高積木零件,而機器學習演算法則是用一些(甚至很多)零件組裝成的一個中間組件。這個中間組件可以直接使用,也可以用來組裝更nb的組件~

希望以上內容能對題主有所幫助


我想從概率這個角度解釋一下,歡迎大神指正。

數學模型大概可以分為兩種,一種是概率模型,一種是非概率模型。對於機器學習來說,前者使用比較突出,例如貝葉斯模型、隱馬爾科夫鏈和高斯混合模型等等;後者在機器學習中的使用基本上是作為基礎內容或者是一些比較簡單的方向,例如K-means聚類等等。而《演算法導論》里的演算法基本都是非概率模型。

稍微解釋一下概率模型與非概率模型這兩種概念。概率模型就是指我們要學習的模型的形式是P(Y|X),這樣在分類的過程中,我們通過未知數據X可以獲得Y取值的一個概率分布,也就是訓練後模型得到的輸出不是一個具體的值,而是一系列值的概率。而對應於分類問題來說,就是對應於各個不同的類的概率。然後我們可以選取概率最大的那個類作為判決對象,因此使用概率模型進行分類的方法又叫軟分類(Soft assignment)。而非概率模型,就是指我們的模型是一個決策函數Y=f(X),輸入數據X是多少就可以投影得到唯一的一個Y,就是判決結果,因此這種方法又稱硬分類(Hard assignment)。


一圖見分曉


演算法導論:你明確知道你想去哪,我的任務是告訴你哪條路最快(time)或者最省錢(space)或者性價比最高(time/space trade-off)
機器學習:你想要看更美的風景但是你不知道在哪找,我的任務是通過從你和別人那裡收集來的數據,幫你找到更多更美風景的所在地(注意,這不代表給你找到的就是最好的)


學習了李航老師《統計學習》第一章,嘗試回答一下這個問題。

一個具體的機器學習方法,比如Linear Regression, Logistic Regression 或者 Neutral Network等,包含三個要素,同時也是先後進行的三個步驟:1.模型(Model),對問題的數學抽象描述,這一步目的是確定一個解空間;2. 策略(Strategy),設計Cost Function等策略來尋找解空間中的最優解;3.演算法(Algorithm),求解最優解的數學方法,比如凸優化。

演算法導論里的「演算法」指的是解決一個實際問題的步驟,其實和機器學習方法中的演算法是接近的,但後者數學味道更濃。


總之,演算法導論的「演算法」和機器學習方法很不一樣。


可以認為沒有關係,剛買了本統計機器學習來看,上面說機器學習的全稱叫統計機器學習,也可以簡稱統計學習,叫機器學習是商業原因,和計算機領域的演算法根本就是兩個學科。


個人體會
演算法導論裡面的對付的是結構化的數據,是離散的。這類數據都是人造的,比如字元串。
機器學習面對的是連續的數據或者假設空間,至少是拓撲連續的。
所以導致2者的演算法差別很大。


大白話理解:

機器學習的「演算法」包含了模型(model)、方法(method)和演算法(algorithm)。

Model是一個問題的數學化描述,比如小紅和小明相向而行,小紅速度a,小明速度b,倆人距離c,求相遇時間t。

Method是求解Model的方法,例如上述模型用這個方程求解:c=(a+b)*t

Algorithm是如何讓計算機解決這個方程的方法。


差別很大。

演算法導論:精確的可度量的問題。計算方式是代碼可實現。可重複。

機器學習:不精確度量問題,代碼不能直接解決問題,而是建立一個解決問題的模式,用模式解決問題。通常不可重複,每次結果也未必一樣。


推薦閱讀:

大數據在電力行業的應用前景有哪些?
大數據一體機的實質是什麼?大數據分析領域這種一體機真的有市場嗎?
如何成為一名數據科學家?

TAG:演算法 | 機器學習 | 數據結構 | 演算法與數據結構 | 大數據 |