Orion's Blog

摘要： 對于更復雜的模型（比如神經網絡）和更復雜的優化方法（比如二階方法），確定性優化方法的計算量會更大。那么如何解決這個問題呢？統計方法能給我們很大的幫助。雖然大數據的數據量和數據維度都很大，但我們可以通過對樣本和維度進行隨機采樣來得到對更新量的有效估計或者替代。相應地，從確定性優化算法出發，我們可以開發出各種隨機優化算法，如隨機梯度下降法、隨機坐標下降法、隨機方差縮減梯度法、隨機（擬）牛頓法等。注意，對于隨機優化算法而言，收斂性分析與確定性算法不同，需要針對算法中的隨機采樣取期望。 閱讀全文

摘要： 我們在上一篇博客中主要介紹了單機數值優化中一些經典的一階確定性算法，本篇文章我們將會介紹二階確定性算法和對偶方法。牛頓法的基本思想是將目標函數在當前迭代點處進行二階泰勒展開，然后最小化這個近似目標函數。如果該海森矩陣是正定的，則問題的最優值在特定處取到，牛頓法將其做為下一時刻的狀態。 閱讀全文

摘要： 我們在上一篇博客中介紹了數值優化算法的歷史發展、分類及其收斂性/復雜度分析基礎。本篇博客我們重點關注一階確定性優化算法及其收斂性分析。梯度下降法的基本思想是：最小化目標函數在當前迭代點處的一階泰勒展開，從而近似地優化目標函數本身。具體地，對函數 ??:???→? ，將其在第 t 輪迭代點 ????處求解最小化問題。梯度下降法有兩個局限，一是只適用于無約束優化問題，二是只適用于梯度存在的目標函數。投影次梯度法可以解決梯度下降法的這兩個局限性。 閱讀全文

摘要： 不同的優化算法采用不同的方法對目標函數進行優化，以尋找最優預測模型。其中最重要的兩個特性就是收斂速率和復雜度。優化算法最初都是確定性的，不過近年來隨著機器學習中數據規模的不斷增大，優化問題復雜度不斷增高，原來越多的優化算法發展出了隨機版本和并行化版本。依據算法在優化過程中所利用的是一階導數信息還是二階導數信息，還可把優化算法分為一階方法和二階方法。 閱讀全文

摘要： 目前對圖算法進行并行化的主要思想是將大圖切分為多個子圖，然后將這些子圖分布到不同的機器上進行并行計算，在必要時進行跨機器通信同步計算得出結果。學術界和工業界提出了多種將大圖切分為子圖的劃分方法，主要包括兩種，邊劃分(Edge Cut)和點劃分(Vertex Cut)?？偠灾?，邊劃分將節點分布到不同機器中(可能劃分不平衡)，而點劃分將邊分布到不同機器中(劃分較為平衡)。接下來我們使用的算法為邊劃分。我們下面的算法是簡化版，沒有處理懸掛節點的問題。 閱讀全文

摘要： 邏輯回歸的目標函數常采用梯度下降法求解，該算法的并行化可以采用Map-Reduce架構。先將第??t輪迭代的權重廣播到各worker，各worker計算一個局部梯度（map過程），然后再將每個節點的梯度聚合（reduce過程），最終對參數進行更新。在Spark中每個task對應一個分區，決定了計算的并行度。在Spark的實現過程中，map階段各task運行map()函數對每個樣本(????,????)計算梯度????， 然后對每個樣本對應的梯度運行進行本地聚合，以減少后面的數據傳輸量。 閱讀全文

摘要： 我們在上一篇博客中學習了如何用Hadoop-MapReduce實現單詞計數，現在我們來看如何用Spark來實現同樣的功能。Spark框架也是MapReduce-like模型，采用“分治-聚合”策略來對數據分布進行分布并行處理。不過該框架相比Hadoop-MapReduce，具有以下兩個特點：對大數據處理框架的輸入/輸出，中間數據進行建模，將這些數據抽象為統一的數據結構命名為彈性分布式數據集。 閱讀全文

摘要： 首先，Hadoop會把輸入數據劃分成等長的輸入分片(input split) 或分片發送到MapReduce。Hadoop為每個分片創建一個map任務，由它來運行用戶自定義的map函數以分析每個分片中的記錄。在我們的單詞計數例子中，輸入是多個文件，一般一個文件對應一個分片，如果文件太大則會劃分為多個分片。map函數的輸入以 閱讀全文

摘要： .gitignore針對每個語言都有對應的模板，在GitHub創建項目時就可以選擇（你可以在GitHub提供的.gitignore模板大全中找到它）。但是這些往往是不夠的的。如我們在Mac系統下用VSCode開發，那么常常還需要添加其它項目。如.vscode/表示忽略.vscode這個包含項目配置文件的隱藏目錄(注意是包括目錄一起忽略，.DS_Store表示忽略掉Mac操作系統下存儲目錄自定義屬性的隱藏文件。此外機器學習相關的項目中，數據和模型通常異常巨大，我們并不想將它們放到項目文件夾下。 閱讀全文

摘要： 強轉int類型會直接對浮點數的小數部分進行截斷（無論是正還是負）。還有一種方法是math.ceil和math.floor。無論是正數還是負數，都遵循：ceil往數軸正方向取整，floor往數軸負方向取整。round原型為round(value, ndigits)，可以將一個浮點數取整到固定的小數位。該函數對正數和負數都采取就近取整原則，而當某個值恰好等于兩個整數間一半時，取整操作會取到離該值最近的那個偶數。 閱讀全文