Tag Archives: algorithm

GrabFood 用定位資料修正餐廳的資訊

Grab 的「How we harnessed the wisdom of crowds to improve restaurant location accuracy」這篇是他們的 data team 整理出來,如何使用既有的資料快速的修正餐廳資訊。裡面提到的方法不需要用到 machine learning,光是一些簡單的統計算法就可以快速修正現有的架構。

這些資訊其實是透過司機用的 driver app 蒐集來的,在 driver app 上有大量的資訊傳回伺服器 (像是定時回報的 GPS 位置,以及取餐狀態),而這些司機因為地緣關係,腦袋裡的資訊比地圖會準不少:

One of the biggest advantages we have is the huge driver-partner fleet we have on the ground in cities across Southeast Asia. They know the roads and cities like the back of their hand, and they are resourceful. As a result, they are often able to find the restaurants and complete orders even if the location was registered incorrectly.

所以透過這些資訊他們就可以反過來改善地圖資料,像是透過司機按下「取餐」的按鈕的地點與待的時間,就可以估算餐聽可能的位置,然後拿這個資訊比對地圖上的資料,就很容易發現搬家但是地圖上沒更新的情況:

Fraction of the orders where the pick-up location was not “at” the restaurant: This fraction indicates the number of orders with a pick-up location not near the registered restaurant location (with near being defined both spatially and temporally as above). A higher value indicates a higher likelihood of the restaurant not being in the registered location subject to order volume

Median distance between registered and estimated locations: This factor is used to rank restaurants by a notion of “importance”. A restaurant which is just outside the fixed radius from above can be addressed after another restaurant which is a kilometer away.

另外也有不少其他的改善 (像是必須在離餐聽某個距離內才能點「取餐」,這個「距離」會因為餐聽可能在室內商場而需要的調整),整個成果就會反應在訂單的取消率大幅下降:

整體看起來是系統產生清單後讓人工後續處理 (像是打電話去店家問?),但這個方式所提供的清單準確度應該很高 (因為司機不會沒事跟自己時間過不去,跑到奇怪地方按下取餐),用這些資料跑簡單的演算法就能夠快速修正不少問題...

Word2Vec:透過向量猜測其他詞彙的意思

2013 年時在「Automatic Translation Without Dictionaries」這邊看到關於機器翻譯時的自我學習方式,裡面提到了「How Google Converted Language Translation Into a Problem of Vector Space Mathematics」這篇報導,而裡面提到的論文則是 Google 發表在 arXiv 上的「Exploiting Similarities among Languages for Machine Translation」這篇。

最近看到「The Illustrated Word2vec」這篇,把五年多前的記錄交叉拉出來看... 這個算式算是給了大家基本的想法,透過公式來解釋文字的意義:

拉出這樣的關係後,就有機會學習新的詞彙... 進而用在其他語言的翻譯上。

用 NN 演算法重製 Full HD 版的 Star Trek: DS9

看到「Remastering Star Trek: Deep Space Nine With Machine Learning」這篇,裡面用了類神經網路演算法,將本來只有 480p (SD) 的 Star Trek: DS9 升到 1080p (Full HD) 的版本,而且看起來效果還不錯...

意外的看到有人拿 Star Trek 的材料來玩... 依照作者的說明,DS9 一直沒有 Full HD 版的其中一個原因反而是因為「數位化」了。使用類比膠卷的母帶可以透過更高規格的重新掃描而得到高畫質版本,但 DS9 的母帶似乎已經是數位版了,所以反而造成無法透過重新掃描的方式取得 Full HD 版本:

While you can rescan analog film at a higher resolution, video is digital and can't be rescanned. This makes it much costlier to remaster this TV show, which is one of the reasons why it hasn't happened.

現有的 upscale 技術主要都還是以圖片為主,所以作者本來以為對於動態畫面的處理會遇到問題,但蠻意外的超出預期,從影片可以看出來:

看起來之後的 remaster 版本有可能可以靠這個方法先做初步,然後再讓人進去修?

LinkedIn 用機器學習提供雇主可能的職缺對象

先前看到「Learning Hiring Preferences: The AI Behind LinkedIn Jobs」這篇,LinkedIn 用機器學習提供雇主可能的對象。

依照官方的說法,這次提到的改進是透過雇主的行為調整推薦。當雇主對某個人有興趣的時候,LinkedIn 就會調整演算法去配合雇主有興趣的條件:

Based on how you interact with candidates, our algorithm learns your preferences and delivers increasingly relevant candidates across the Jobs product. If you’re consistently interested in candidates who are, say, accountants with leadership skills, or project managers who are adept at social media, we’ll send you more of those. And this all happens online in real time so that your feedback is taken instantly into account.

透過模擬 20% 的加成:

This new algorithm, which is used throughout the Jobs platform, performs nearly 20% better than the previous version in generating recommendations when we simulate our members' past hiring activity.

在 social network 這種演算法其實就是同溫層 (Echo chamber、Filter bubble),在 LinkedIn 這樣的行為不知道會不會牽扯到 Discrimination 的議題...

Mercury Web Parser 開源

看到「Mercury Goes Open Source!」這篇,Postlight 的團隊開源了 Mercury Web Parser,程式碼在 GitHub 上的 postlight/mercury-parser 可以取得。

這個版本是用 Node.js 寫的,可以從範例看出用法以及結果:

import Mercury from '@postlight/mercury-parser';
Mercury.parse(url).then(result => console.log(result););
{
  "title": "Thunder (mascot)",
  "content": "<div><div><p>This is the content of the page!</div></div>",
  "author": "Wikipedia Contributors",
  "date_published": "2016-09-16T20:56:00.000Z",
  "lead_image_url": null,
  "dek": null,
  "next_page_url": null,
  "url": "https://en.wikipedia.org/wiki/Thunder_(mascot)",
  "domain": "en.wikipedia.org",
  "excerpt": "Thunder Thunder is the stage name for the horse who is the official live animal mascot for the Denver Broncos",
  "word_count": 4677,
  "direction": "ltr",
  "total_pages": 1,
  "rendered_pages": 1
}

先前其他的軟體與服務可以參考「Evaluating Text Extraction Algorithms」這篇的整理與比較,不過這篇連原網站都不見了... 只能從 Internet Archive 上翻出來。

這個主題有不少團隊都做過 (給一個 html 網頁,抓出實際的內容塊落),但也死了不少團隊... 比較有印象的是 Readability,在 2016 年收掉了:「The Readability bookmarking service will shut down on September 30, 2016.」。

要撈資料可以拿來用...

DynamoDB Autoscaling 的各種眉眉角角...

AdRollDynamoDB Autoscaling 的踩雷記錄,裡面有些資訊如果不是跳下去玩應該不會注意到 (魔鬼藏在細節裡的感覺):「Managing DynamoDB Autoscaling with Lambda and Cloudwatch」。

第一個提到的問題是 autoscaling 的觀察對象:

Ideally, the table should scale based on the number of requests that we are making , not the number of requests that are successful.

另外一個是 autoscaling 遇到完全不用的情況下不會 scale down,看起來是某種保護機制。但這使得平常只有拿來讀取的表格在跑完 batch job 後得自己處理 write scale down 問題:

Additionally, at the time of implementing this algorithm, the DynamoDB capacity could not be brought down automatically if the consumption was exactly zero, which can happen if you write to your table in batch instead of realtime, for example.

This meant that, when enabling autoscaling, tables that were read in realtime, but written to in batch, still needed manual intervention to bring the write capacity down after our jobs were done writing.

另外一個問題是 scale down 是有次數限制的:

Another interesting point that might bite users is that capacity decreases are an expensive operation for AWS, so they’re limited.

The number of decreases cited in the documentation can be achieved under very special conditions, since you need to have 4 decreases in the first hour of the day plus one for each of the remaining hours, for a total of 4 (first hour) + 23 (1 hourly) = 27.

後面就是自己研究什麼 algorithm 可以調整的更細,然後用 lambda 重寫... 最後省下 30% 的成本:

Here is where we detected our costs for our batch tables dropping to around 30% of the initial cost.

AdRoll 的規模應該是不小,所以為了省 30% 可以花不少力氣在上面...

所以要開始開發 CECPQ2 了...

CECPQ1Google 在研究對抗量子電腦的演算法,作為測試用的演算法,曾經在 Google Chrome 的 54 beta 版 (2016 年) 存活過一段時間,最近又開始在開發新一代的演算法 CECPQ2 了,這次會是基於 TLS 1.3 上測試:「CECPQ2」。

CECPQ2 will be moving slowly: It depends on TLS 1.3 and, as mentioned, 1.3 is taking a while. The larger messages may take some time to deploy if we hit middlebox- or server-compatibility issues. Also the messages are currently too large to include in QUIC. But working though these problems now is a lot of the reason for doing CECPQ2—to ensure that post-quantum TLS remains feasible.

目前對抗量子電腦的演算法好像都跟 Lattice 有關,找時間來補一下基礎理論... @_@

HTTP/3 (QUIC) 的反面看法

這篇整理了 HTTP/3 (QUIC) 的反面看法,算是常見的疑慮都列出來了:「QUIC and HTTP/3 : Too big to fail?!」。

其實大多都是使用 UDP 而導致的問題:

  • 因為 UDP 導致 firewall 可能沒開,以及可能會需要等 timeout 走回 TCP 的問題。
  • 因為 UDP 變成很多事情在 userland 處理,而導致的 CPU 使用率比使用 TCP 的 TLS 1.2/1.3 高很多。
  • 因為 UDP 導致 amplification attack 的安全性問題,以及對應的 workaround 產生的頻寬議題。
  • 由於 UDP 會需要自己控制擁塞,等於是在 UDP 上面又重做了一次 TCP congestion algorithm,而且因為重作所以得考慮與 TCP 搶資源的公平性。

整篇文章算是整理了一般對 HTTP/3 的疑慮,之後如果有進展的話,可以再拿出來當 checklist 再確認有哪些有改善...

AWS 的推薦演算法服務:Amazon Personalize

AWS 把推薦演算法包成服務拿來來賣,叫做 Amazon Personalize:「Amazon Personalize – Real-Time Personalization and Recommendation for Everyone」。

把後面的演算法隱藏起來,只要給使用者的評價資料就可以了,像是文章裡的範例:

userId,movieId,rating,timestamp
1,2,3.5,1112486027
1,29,3.5,1112484676
1,32,3.5,1112484819
1,47,3.5,1112484727
1,50,3.5,1112484580

可以看出來這個使用者對 2,29,32,47,50 這些 movieId 在不同的時間點都給了 3.5 分的評分。

然後經過一連串的 API 操作 (有些參數可以調整,但主要是叫 AWS 運算,並且建立 real-time 的服務),就可以看到推薦哪些其他的 item 了:

$ aws personalize-rec get-recommendations --campaign-arn $CAMPAIGN_ARN --user-id $USER_ID --query "itemList[*].itemId"
["1210", "260", "2571", "110", "296", "1193", ...]

而從 Pricing 的頁面可以看到支援 real-time data 與 batch data:

DATA INGESTION
You are charged per GB of data uploaded to Amazon Personalize. This includes real-time data streamed to Amazon Personalize and batch data uploaded via Amazon S3.

這其實是很多網站都很需要的功能...

GitHub 移除 HTTPS 中的 TLSv1/TLSv1.1,以及 SSH 中 SHA1 相關的協定

GitHub 完全移除掉 TLSv1/TLSv1.1 以及 SSH 中 SHA1 相關的協定了:「Weak cryptographic standards removed」。其中 TLSv1 與 TLSv1.1 的部份也可以從 SSL Report: github.com 這邊看到:

這是之前就預告的關閉,可以參考先前提到的文章:「GitHub 停用過時加密演算法的計畫」。