Geometric transformations in Computer Vision

Cũng như hầu hết các lớp dạy về Computer Vision hay Computer Graphics, lớp của UC Berkeley trên coursera cũng bắt đầu  bằng mô hình pinhole camera (tất nhiên là sau một bài tổng quan về computer vision, với nhiều nội dung thú vị mà ta có thể trở lại khi có dịp). Điều hơi “bất ngờ” là ngay sau đó, nội dung quan trọng thứ 2 là nói về các phép biến đổi hình học trong 2D và 3D, bao gồm Rigid body transformation, orthogonal transformation, affine transformation, biểu diễn phép quay trong 3D v.v…

Bài này sẽ tóm tắt một số ý chính của các phép biến đổi hình học, coi như là một trong những bài trực tiếp về Computer Vision hiếm hoi trên blog này, mặc dù mục tiêu ban đầu và xuyên suốt của blog là viết về Computer Vision

1. Khái niệm Pose và Shape

Trong mô hình pinhole camera, một điểm trong không gian được gán cho một tọa độ 3D với hệ trục tọa độ là cố định đối với camera. Khi một điểm di chuyển, tọa độ của nó thay đổi. Chẳng hạn một cái bàn trong không gian có thể thay đổi vị trí của nó so với camera nhưng bản thân cái bàn không thay đổi. Trong computer graphics, ta gắn cho cái bàn thêm một hệ trục tọa độ nữa (gọi là object coordinates) bên cạnh world coordinates gắn với camera. Trong computer vision, ta nắm bắt thực tế này bằng 2 khái niệm là pose và shape.

Logistic regression in 35 lines of code

This entry is just for a bookmark. This paper provides a short-and-sweet implementation of logistic regression in 35 lines of C.

I believe there are many sweetie ML implementations like this out there…

(Toy) Data Analysis

Số lượng user theo năm sinh của Tencent Weibo

Trong ảnh là biểu đồ số lượng người dùng theo năm sinh của 2.320.895 người dùng trong mạng xã hội Weibo của Tencent.

Trong dataset này, năm sinh là do người dùng xác định, do đó có một số nhiễu và dữ liệu không chính xác. Tuy nhiên về tổng thể thì có thể tin được phần lớn thông tin này là năm sinh thật của user. Điều thú vị là đồ thị này có dáng vẻ của phân phối exponential, với peak là năm 1990 với  199.837 người dùng.

Dữ liệu này được công bố trong KDDCup2012, do Tencent tài trợ. Sau khi import hết hơn 3GB dữ liệu của Track 1 vào Oracle XE thì nó ngốn gần 13GB ổ cứng. Một câu query đơn giản trong Oracle cũng phải mất hơn 1 phút mới xong, và có nhiều query không chạy được do giới hạn 5000 dòng và 4 GB của Oracle XE. Lần đầu tiên nghịch dataset cỡ này.

Còn đây là 1 chương trích từ một trong những report lãng nhách nhất từng viết. Download ở đây.

Graphical model (2)

Trong bài trước, ta đã điểm qua khái niệm về graphical model. Bài này sẽ viết về một thuật toán quan trọng là Bayes Ball, sau đó nói về các khái niệm Cái mền của Markov (Markov blanket), Markov equivalent, faithfulness… của graphical model. Bài tiếp theo của loạt này hi vọng sẽ nói về một số thuật toán suy diễn trong graphical model, bao gồm Message passing và Junction tree.

(FYI: Lớp Probabilistic Graphical Models của Stanford sắp khai trương, ngoài ra lớp Computer Vision cũng có vẻ thú vị).

1. Thuật toán Bayes ball

Cho graphical model bất kì. Một câu hỏi quan trọng là: cho biết giá trị của tập biến ngẫu nhiên Z, xác định xem hai biến ngẫu nhiên A và B là độc lập hay phụ thuộc. Nói cách khác, ta muốn xác định hay , nghĩa là xác định sự độc lập/phụ thuộc có điều kiện giữa 2 biến ngẫu nhiên bất kì. Đây chính là mục tiêu của thuật toán  Bayes Ball.

Tư tưởng của  Bayes ball rất đơn giản. Ta đánh dấu (shade) các biến ngẫu nhiên trong Z, với hàm ý là những biến này đã biết. Sau đó “thả” quả bóng Bayes ball từ A. Bayes ball di chuyển trong đồ thị theo một số quy tắc nhất định. Nếu Bayes ball có thể đi từ A đến B thì A và B là phụ thuộc với điều kiện Z. Mặc dù các cạnh trong graphical model là có hướng (đồ thị này là directed acyclic graph – DAG) nhưng Bayes ball có thể di chuyển ngược hướng với các cạnh.

Graphical model (1)

Graphical model (còn gọi là Bayesian network, Belief network) là tên gọi chung dành cho lớp các mô hình xác suất mà trong đó mối liên hệ giữa các biến ngẫu nhiên (độc lập/phụ thuộc) được khai thác để đơn giản hoá việc tính phân phối xác suất đồng thời (joint distribution). Blog này đã có lần đề cập đến các mô hình Markov như một trường hợp riêng của graphical model. Trong chuỗi bài này, ta sẽ lần lượt giới thiệu các vấn đề liên quan đến graphical model: định nghĩa, suy diễn (inference) và huấn luyện (training). Bài đầu tiên sẽ viết về các vấn đề cơ bản: khái niệm về độc lập có điều kiện (conditionally independent) và graphical model, V-structure. Các vấn đề khác gồm thuật toán Bayes Ball, Markov blanket và Markov equivalence được trình bày trong bài sau.

1. Nhắc lại xác suất

Biến ngẫu nhiên A và B gọi là độc lập có điều kiện đối với C (conditionally independent to C) nếu và chỉ nếu:

Khi đó ta kí hiệu .

Một cách nôm na, khi đã biết C thì việc biết thêm B cũng không cho ta thêm được chút thông tin nào về A. Chẳng hạn nếu C là sự kiện “hôm nay có triều cường ở SG”, A là “hôm nay kẹt xe ở SG” và B là “anh Vươn bị cưỡng chế đất”, thì nếu biết C, xác suất xảy ra A là khá cao, bất kể anh Vươn có bị cưỡng chế hay không.

Một công thức quan trọng nữa là chain rule, dùng để tính xác suất đồng thời dựa vào các xác suất có điều kiện, theo đó:

Click-through rate, Computational Advertising hay là bài toán cơ bản của ngành công nghiệp Internet

Quảng cáo có lịch sử rất lâu đời. Người ta tìm thấy những mẫu quảng cáo được dùng năm 1806 ở Nhật hay mẫu quảng cáo Coca-cola rất cầu kì từ những năm 1890. Tại Việt Nam ta cũng thấy những thông điệp quảng cáo kiểu như “Chồng tôi mê gái chỉ vì tôi không đọc tờ Tuần báo đàn bà” hay là “Hynos phosphate, đánh răng sớm chiều, răng vững bền nhiều” ngay từ những năm đầu thế kỉ 20.

Quảng cáo kem đánh răng. Nguồn http://rgb.vn.

Ngày nay, quảng cáo trên internet ngày càng có nhiều ưu thế so với quảng cáo truyền thống. Nếu như quảng cáo truyền thống có chi phí cao mà đại lí nhận quảng cáo lại không nhiều (quảng cáo trên báo, tạp chí, pano ngoài trời…), không có khả năng định hướng khách hàng tiềm năng và rất khó để đo mức độ hiệu quả; thì quảng cáo trực tuyến (online advertising) lại lấp đầy hoàn toàn những khiếm khuyết này: khả năng tùy biến cao, đại lí quảng cáo vô kể (số lượng website trên Internet chắc nhiều hơn số tờ báo, tạp chí… hiện có) và rất dễ đánh giá định lượng mức độ hiệu quả.

Thực tế, quảng cáo trực tuyến là nguồn thu lớn, đôi khi là quan trọng nhất, của các công ty dịch vụ trực tuyến, tất nhiên trừ một số ít công ty sống được bằng cách thu tiền dịch vụ. Có thể nói quảng cáo trực tuyến là xương sống của cả ngành công nghiệp internet.

Vậy nhưng nghiên cứu khoa học trong lĩnh vực này thì lại rất non trẻ. Thời gian đầu quảng cáo trên internet cũng chỉ là những banner trên các forum, website… với hình ảnh bắt mắt hay thậm chí tìm cách “lừa gạt” người dùng. Cho mãi đến vài năm gần đây, khi nhu cầu quảng cáo tùy biến dựa vào “sở thích” người dùng tăng cao, thì khái niệm Computational Advertising mới bắt đầu xuất hiện và được chấp nhận rộng rãi.

Một trong những sự kiện đánh dấu sự ra đời của khái niệm “Computational Advertising” là một tutorial của Andrei Border tại ACM-SIGIR 2010, và sau đó xuất hiện trên ACM Communications. Andrei Border là phó chủ tịch bộ phận Computational Advertising của Yahoo! research. Cũng chính Andrei sau đó đã dạy 2 lớp Computational Advertising tại Stanford vào mùa thu 2010 và 2011.

Microsoft cũng không đứng ngoài cuộc. Đội ngũ quản lí Bing đã tổ chức một cuộc thi cải tiến thuật toán xếp hạng quảng cáo cho Bing trong nhiều năm liền, và thuật toán thắng giải cuộc thi này trong nhiều năm liên tiếp sau đó được trình bày trong một bài báo ở ICML 2010. Thực tế từ mùa hè năm 2009, thuật toán này đã chính thức thay thế công cụ xếp hạng quảng cáo cũ của Bing. Ta sẽ trở lại với chi tiết bài báo này trong phần sau.

Nói như vậy để thấy rằng Computational Advertising là lĩnh vực đóng góp tiền của rất nhiều cho các công ty dot com, nhưng vẫn còn rất mới mẻ.

Vậy tóm lại Computational Advertising là gì? (trong khi ta đã có quá nhiều thứ “computational”: Computational photography, Computational Linguistics, Computational Economics, Computational Finance… blah blah…)

Probability and Statistics cheat sheet

Download bản rõ hơn (20MB)

Đây là cheat sheet mình dùng ôn thi môn XSTK tuần rồi. Do là cheat sheet nên nội dung ngắn gọn. Thực ra còn một số phần trong hypothesis testing và limit theorems nhưng mình không đưa vào vì dài quá. Hi vọng tuần này thi xong sẽ có thời gian viết về vài chủ đề trong này.

Nội dung gồm:

Constrained optimization – Overview of algorithms

Như đã nói trong bài trước, các thuật toán tối ưu cục bộ đều có chung một tư tưởng để tìm lời giải tối ưu. Tuy nhiên tùy thuộc vào tính chất của hàm mục tiêu và của ràng buộc mà sẽ có các chiến lược khác nhau. Entry ngắn này liệt kê các phương pháp tối ưu cho từng trường hợp cụ thể. Các bài viết sau sẽ lần lượt trình bày các thuật toán này.

Tên bài toán	Hàm mục tiêu	Ràng buộc	Thuật toán
	Tổng quát	Tuyến tính đẳng thức	Thuật toán A
	Bậc 2	Tuyến tính đẳng thức	Thuật toán B
	Tổng quát	Tuyến tính bất đẳng thức	Active set
	Tổng quát	Tuyến tính đẳng thức và bị chặn	Murtagh-Saunders
Linear programming	Tuyến tính	Tuyến tính đẳng thức và bị chặn	Simplex method (bản rút gọn của Murtagh-Saunders dành cho linear programming)
Nonlinearly constrained	Tổng quát	Tổng quát	Augmented Lagrangian, Newton’s method…

Thuật toán A và thuật toán B chưa được đặt tên nên ta cứ tạm gọi tên như vậy.

Bảng này còn thiếu trong trường hợp tối ưu không ràng buộc, và cho các bài toán tối ưu rời rạc (gọi chung là integer programming). Hi vọng các bài sau sẽ lần lượt trình bày được các thuật toán này.

Constrained Optimization – Intuition for the First and Second order conditions

Trong bài trước, ta liệt kê các điều kiện bậc nhất và bậc 2 cho bài toán tối ưu có ràng buộc. So với tối ưu không ràng buộc, việc xuất hiện toán tử Lagrange làm cho bài toán tối ưu có ràng buộc trở nên ít trực quan hơn. Bài này sẽ giải thích nôm na các điều kiện này, lí giải tại sao nếu một điểm feasible point thỏa cả 2 điều kiện thì nó sẽ là local optimum. Việc hiểu ý nghĩa của các điều kiệu này là rất cần thiết cho việc hiểu các phương pháp tối ưu như active set, simplex method .v.v… mà ta sẽ lần lượt giới thiệu sau.

Ý tưởng chung của các phương pháp tối ưu có ràng buộc là bắt đầu từ vị trí khởi đầu (feasible point), ta di chuyển trong không gian tạo bởi các ràng buộc, sao cho nó tối thiểu hóa hàm mục tiêu. Muốn làm được vậy, tại mỗi vị trí, ta phải tính hướng di chuyển tiếp theo  sao cho đi theo hướng đó thì sẽ giảm được giá trị hàm mục tiêu (hướng như vậy gọi là feasible descent direction). Tuy nhiên vấn đề là đi theo hướng đó một đoạn bao nhiêu. Ta xác định độ dài phải đi (steplength) bằng thuật toán linesearch. Cứ tiếp tục như vậy đến khi không thể tìm được feasible descent direction thì dừng.

Đây là tư tưởng chung nhất của tất cả các thuật toán tối ưu ta sẽ tìm hiểu, tuy nhiên tùy vào đặc trưng của hàm mục tiêu (tuyến tính, bậc 2 hay phi tuyến) và của ràng buộc (ràng buộc tuyến tính đẳng thức hay bất đẳng thức, ràng buộc phi tuyến v.v…) mà cách tính feasible point, feasible descent direction và linesearch sẽ khác nhau. Thực tế phần quan trọng nhất trong thuật toán tối ưu là linesearch. Một cài đặt tốt cho linesearch có thể lên đến vài chục trang mã nguồn vì có quá nhiều điều kiện cần phải kiểm tra, và với mỗi trường hợp lại phải xử lí khác nhau. Tất nhiên mục đích của ta không phải là cài đặt lại các thuật toán này, nhưng nói vậy để thấy sự phức tạp của linesearch và các thuật toán tối ưu nói chung.

Trở lại với các điều kiện bậc nhất và bậc 2, ta sẽ giải thích nôm na các điều kiện này bằng ví dụ đơn giản sau

PCA – Intuition and Maths

Trong bài trước, ta đã trình bày các bước của thuật toán  PCA, nhưng phần giải thích và các công thức chi tiết chưa được làm rõ. Bài này giải thích một cách nôm na ý tưởng chính của PCA, đồng thời chứng minh rằng ý tưởng này dẫn đến việc sử dụng trị riêng trong PCA, lí giải tại sao trong PCA, trị riêng lại đóng vai trò đẹp đẽ đến như thế.

1. Ý tưởng chính của PCA

Như đã nói trong bài trước, mục tiêu của  PCA là tìm trục cho không gian mới sao cho nó biểu diễn tốt nhất mức độ biến thiên của dữ liệu.

Giả sử có ma trận

Trong đó là các điểm trong không gian ban đầu. Nhiệm vụ của PCA là đi tìm không gian mới với số chiều nhỏ hơn m, sao cho biểu diễn tốt n điểm trong X.