A humble introduction to Machine Learning, Information Extraction, and Bootstrapping Method

Nghia Bui, Saigon, Christmas 2016

Machine Learning

From the beginning days of computers, people have wondered whether computers can be programmed to learn. If we can make them to learn, the effect would be so amazing. For example, ML is frequently used in cancer diagnosis and detection. Cruz and Wishart [CW06] showed that ML methods can be used to substantially (15-25%) improve the accuracy of predicting cancer susceptibility, recurrence and mortality. Indeed, recently [Ng16], it was reported that IBM’s Watson gave proper diagnosis for Japanese leukemia patient after doctors were stumped for months. The supercomputer, sifted through 20 million cancer research papers, was able to find out the proper diagnosis within 10 minutes, and also suggested a new treatment that has since been more effective.

With an undoubted impression about applications of ML, let our discussion continue with the formal definitions and basic concepts of this subfield of computer science.

Continue reading “A humble introduction to Machine Learning, Information Extraction, and Bootstrapping Method”

Advertisements

The universe is 4D?

This statement:

Little did they know that the universe is four dimensional and even the orbit of planets is an illusion produced when straight motion in a four dimensional space is projected into three dimensions (or something).

immediately reminded me about projective geometry which is one of the most beautiful systems of mathematics.

So the universe is 4D? I don’t know. But if it was true then we could use the concepts of projective geometry to interpret something interesting.

Continue reading “The universe is 4D?”

Hình học xạ ảnh (P.2)

Phần 1

Ở phần trước, tôi đã hỏi bạn về hệ thống Dog Cat mà nếu thỏa mãn hai tiên đề căn bản, thì có được gọi là projective geometry hay không? Thực ra thì danh sách đầy đủ các tiên đề của projective geometry như sau:

  • Qua hai điểm xác định duy nhất một đường thẳng.
  • Qua hai đường thẳng xác định duy nhất một điểm.
  • Mỗi đường thẳng chứa ít nhất 3 điểm.
  • Không có một đường thẳng nào chứa hết tất cả các điểm của mặt phẳng.

Dĩ nhiên, bất kể thứ gì trên đời bao gồm Dog Cat, nếu chúng thỏa mãn hệ thống tiên đề trên, thì đều gọi là projective geometry được. Bạn có thể hỏi: suy diễn như thế phỏng có ích gì? Đang hình dung điểm, đường thẳng rất quen thuộc, sao phải chuyển sang Dog Cat? Tất nhiên là tôi có lý do rồi.

Continue reading “Hình học xạ ảnh (P.2)”

Hình học xạ ảnh (P.1)

Hình học xạ ảnh (projective geometry) ám ảnh tôi trong suốt một thời gian dài. Đó là vào khoảng cuối năm 2011, khi mà OpenGL ES 2.0 trở nên thịnh hành trên những game cho thiết bị di động. Hệ điều hành iOS của Apple bắt đầu hỗ trợ OpenGL ES 2.0 từ iOS 5.0, còn phía Android là bắt đầu từ Android 2.2 (Froyo). Vì tính chất công việc, tôi bắt buộc phải cập nhật kiến thức để theo kịp công nghệ.

Continue reading “Hình học xạ ảnh (P.1)”

Tìm n số nguyên dương có tổng bằng tích (n≥3)

Trước hết ta chứng minh rằng trong n số ấy phải có đúng (n-2) số bằng 1, thật vậy:

  • Nếu có tới (n-1) số bằng 1 hoặc cả n số bằng 1 thì dễ thấy đều không thỏa mãn tổng bằng tích.
  • Nếu có ít hơn (n-2) số bằng 1 .

Vậy thì tồn tại 3 số ≥ 2.

Xét mệnh đề P(n) với n≥3 phát biểu như sau:

Nếu chọn ra bất kỳ n số nguyên dương x[1], x[2], …, x[n] sao cho tồn tại 3 số đều ≥ 2 thì ta luôn có: x[1] + x[2] + … + x[n] < x[1] * x[2] * … * x[n]

Ta sẽ chứng minh P(n) đúng với mọi n≥3 bằng quy nạp.

Với n = 3 thì ko mất tính tổng quát: x[1] ≥ x[2] ≥ x[3] ≥ 2 có thể xem là x ≥ y ≥ z ≥ 2 cho dễ viết, ta có:

x(yz – 1) ≥ x(2.2 – 1) = 3x > 2x = x + x ≥ y + z hay x + y + z < xyz

Vậy P(3) đúng, giờ giả sử có P(k) đúng với k ≥ 4, ta phải chứng minh P(k+1) cũng đúng, tức là chứng minh:

x[1] + x[2] + … + x[k] + x[k+1] < x[1] * x[2] * … * x[k] * x[k+1] với mọi x[i] (i=1 đến k+1) nguyên dương và có 3 số đều 2

Từ (5) suy ra để chứng minh (4) ta cần chứng minh:

a[1] * a[2] * … * a[n] + a[n+1] < a[1] * a[2] * … * a[n] * a[n+1] (6)

Do (2) nên a[n – 1] ≥ a[n] ≥ a[n+1] ≥ 2 (7), chia cả 2 vế của (6) cho a[1]*a[2]*…*a[n] ta có (6) tương đương với:

1 + a[n+1] / (a[1] * a[2] * … * a[n]) < a[n+1] đặt là 1 + A < a[n+1]

Do (7) nên A < 1 dẫn đến 1 + A < 2a[n+1] ≥ 2 suy ra 1 + A < a[n+1]

Vậy (6) đúng và giả thiết quy nạp là đúng.

Khi trong n số ấy có đúng (n-2) số bằng 1, ta viết lại (1):

n – 2 + x + y = x * y <=> (x-1)(y-1) = (n-1)

Kết luận: công thức nghiệm tổng quát là: (n-2) số 1, k + 1, ((n-1) / k) + 1 với k là ước số nguyên dương của (n-1).

Tìm 3 số tự nhiên có tổng bằng tích

Gọi 3 số cần tìm là x, y, z thì x + y + z = xyz (*).

Dễ thấy nếu một trong 3 số bằng 0 thì cả 3 số bằng 0 luôn. Vậy (x, y, z) = (0, 0, 0) thỏa mãn. Giờ ta chỉ xét x, y, z > 0 hay x, y, z ≥ 1.

Không mất tính tổng quát, giả sử x ≥ y ≥ z ≥ 1. Nhận xét z phải bằng 1, vì nếu z ≥ 2 thì x ≥ y ≥ z ≥ 2, ta có:

x(yz-1) ≥ x(2.2-1) = 3x > 2x = x + x ≥ y +z
tức là xyz – x > y +z hay xyz > x + y + z, không thỏa mãn (*).

Vậy z = 1, khi đó (*) trở thành: x + y + 1 = xy tương đương (x-1)(y-1) = 2 suy ra (x-1) = 2(y-1) = 1 nên x = 3y = 2.

Kết luận: (x, y, z) = (0 , 0, 0) hoặc (3, 2, 1).

Phép biến đổi Fourier nhanh (Fast Fourier Transform)

Một trong những ứng dụng thường gặp của phép biến đổi Fourier nhanh (FFT) là nhân hai số nguyên lớn (vì việc này cũng coi như là nhân 2 đa thức biến x = 10).

Fabrice Bellard là một nhà khoa học máy tính người Pháp đã viết được chương trình C tính ra giá trị của: (2 mũ 43112609) – 1. Đây là số nguyên tố lớn nhất cho đến giờ con người tìm ra.

Quy tắc của ông như sau: thay vì phải có (43112609 – 1 = 43112608) phép tính nhân các số 2 lại với nhau, thì nên tận dụng lại các kết quả tính ra trong quá trình đó, thế này: viết 43112609 thành dạng nhị phân 1010010001110110001010000. Ban đầu khởi tạo một biến tích lũy s = 1, đi từ trái qua phải trên dãy nhị phân, nếu gặp bit 1 thì bình phương s rồi nhân với 2. Cứ như vậy cuối cùng s = 2 mũ 43112609.

Phép nhân một số với số 2 ko có gì đáng nói, còn phép bình phương thì chính là ứng dụng trên của FFT. Ở đây đặc biệt là hai số nguyên đem nhân là giống nhau, nên thời gian thực hiện FFT sẽ nhanh hơn.

Code của Fabrice Bellard (compile trên GCC), vâng, cực kì tinh vi và khó hiểu:

Continue reading “Phép biến đổi Fourier nhanh (Fast Fourier Transform)”