VOITSORT – spoj

Đề bài:

Thuật toán:

Trong bài toán này, ta nhận thấy không còn cách nào khác ngoài việc xây dựng
tất cả K hoán vị theo yêu cầu và kiểm tra từng hoán vị.

Để full điểm, ngoài việc kiểm tra như trong đề bài mô tả, ta cần có thêm
một số cái nhìn tinh tế hơn.

Thứ nhất, do lượng hoán vị cần xét là
$K \leq 10^6 < 10!$ , do vậy mọi hoán
vị cần xét dường như chỉ xoay quanh việc thay đổi thứ tự 10 phần tử cuối
cùng. Trên thực tế, sẽ có tối đa một lần có hơn 10 phần tử cuối cùng thay
đổi trong dãy hoán vị và việc này không làm ảnh hưởng nhiều tới tính hiệu
quả của nhận xét này.

Thứ hay, có thể phát biểu thuật toán T(p) với một chút khác biệt như :

  • p có không nhiều hơn 1 phần tử, T(p) = true
  • p có nhiều hơn 1 phần tử, gọi X là vị trí của phần tử lớn nhất trong p,
    pL là các phần tử bên trái của X và pL là các phần tử bên phải của X, khi đó
    T(p) = true khi:

    • T(pL) = T(pR) = true
    • Tất cả các phần tử trong pL nhỏ hơn tất cả các phần tử trong p

Cách phát biểu khác biệt này đưa ra một nhận xét tổng quát hơn: “T(p) = true
khi và chỉ khi không tồn tại 3 vị trí $i < j < k$ mà $p_k < p_i < p_j$

Cách phát biểu mới này giúp ta có một thuật toán kiểm tra T(p) hiệu quả hơn
như sau: Để đảm bảo T(p) = true, với mọi vị trí j nằm trong p, gọi R là phần
tử nhỏ nhất phía bên phải j và L là phần tử lớn nhất nhỏ hơn $p_j$ phía trái
j, ta phải đảm bảo rằng $L < R$

Tuy nhiên, trong thực tế ta chỉ cần kiểm tra điều kiện trên cho những phần
tử bị thay đổi so với hoán vị trước (khoảng 10 phần tử cuối cùng) nên thuật
toán có thể chạy trong thời gian cho phép.

Code:

#include <cstdio>
#include <vector>
using namespace std;
 
// Hàm sinh hoán vị tiếp theo trong thứ tự từ điển.
// Trả về `k` là vị trí mà hoán vị bắt đầu thay
// đổi so với hoán vị trước.
// k < 0 nếu đây đã là hoán vị cuối cùng.
int next(vector<int> &a) {
    int k, l, n = a.size();
    for (k = n-2; k>=0; k--) if (a[k] < a[k+1]) break;
    if (k<0) return k;
    for (l = n-1; l>k; l--) if (a[k] < a[l]) break;
    swap(a[k], a[l]);
    for (int i=k+1, j=n-1; i<j; i++, j--) swap(a[i], a[j]);
    return k;
}
 
bool f[1000];
int seed = 0;
int cache[1001];
 
// Kiểm tra xem tại a[i] có thỏa điều kiện L < R
// như đã giải thích ở trên hay không.
bool check(const vector<int> &a, int i) {
    int n = a.size();
    seed += 1;
    int r = 1e9;
    // Tìm R là giá trị nhỏ nhất ở bên phải a[i]
    // Đồng thời đánh dấu các giá trị xuất hiện
    // ở bên phải a[i]
    for (int j=i+1; j<n; j++) {
        cache[a[j]] = seed;
        r = min(r, a[j]);
    }
    // Tìm L là giá trị lớn nhất nhỏ hơn a[i]
    // ở bên trái a[i] => L không xuất hiện ở bên phải
    int l = 0;
    for (int j=a[i]-1; j>=1; j--) {
        if (cache[j] != seed) {
            l = j;
            break;
        }
    }
    return l < r;
}
 
// Lần lượt kiểm tra và cập nhật các phần tử
// từ a[k] trở lên, đồng thời kiểm tra xem
// tất cả các phần tử có thỏa mãn điều kiện
// L < R hay không.
bool ok(const vector<int> &a, int k) {
    int n = a.size();
    for (int i=k; i<n; i++) {
        f[i] = check(a, i);
        if (i>0) f[i] &= f[i-1];
    }
    return f[n-1];
}
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> a(n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
 
    int k = 0, count = 0;
    while (m--) {
        if (ok(a, k)) count++;
        k = next(a);
        if (k < 0) break;
    }
 
    printf("%d", count);
    return 0;
}

ML #3 – Overfitting và những triết lý cuộc đời

Chào các bạn, chúng ta chào đón nhau bằng một nụ cười thật tươi và chúc bạn một ngày mới với những niềm vui mới. Các bạn thân mến của tôi, có lẽ rằng với rất nhiều người, khoa học tự nhiên vốn là khoa học của những con số, những công thức, những giải thuật và vô hình chung người ta đã quan niệm rằng nó tách biệt hoàn toàn với khoa học xã hội – khoa học của các triết lý, khoa học của nhân sinh quan, thế giới quan… Chúng vốn dĩ đã là hai ngành khoa học chẳng thể tách rời nhưng có lẽ vì một lý do nào đó mà rất nhiều người đã không nhìn ra rằng có một sợi dây vô hình song rất bền chặt gắn kết chúng lại với nhau, rằng từ những con số tưởng chừng rất khô khan luôn luôn tiềm tàng một triết lý sống mà đôi khi chúng ta phải mất cả một cuộc đời để trải nghiệm. Điều mà tôi muốn nói đến ngày hôm nay không phải là một vấn đề mới, thậm chí còn là cũ mèm. Over filting – một thuật ngữ có lẽ đã quá quen thuộc đối với những người nghiên cứu các giải thuật thống kê và đặc biệt là lĩnh vực Machine Learning nhưng ẩn sâu trong nó là những bài học về nhân sinh thật sự kì diệu. Và bạn….chính bạn chứ không phải ai khác, bạn đã sẵn sàng cho con đường tìm ra mối liên hệ rất tự nhiên mà lại kì diệu đó chưa???

Bạn hiểu thế nào về Over-fitting

Bản chất của Machine Learning chính là việc sử dụng máy tính để mô hình hóa dữ liệu rồi từ các mô hình đó chúng ta đưa ra các dự đoán cho tương lai. Chúng ta có thể sử dụng rất nhiều các thuật toán khác nhau phục vụ cho việc mô hình hóa dữ liệu của chúng ta, tìm kiếm ra các mối tương quan ẩn chứa trong tập dữ liệu mà chúng ta thu thập được trong quá khứ (chúng ta gọi đó là tập dữ liệu huấn luyện). Suy nghĩ của đại đa số người chính là một mô hình tốt nhất trên tập dữ liệu huấn luyện thì cũng sẽ tốt nhất khi áp dụng vào thực tế (tức là khi chạy trên tập dữ liệu kiểm tra). Điều này đôi khi là một sai lầm, bằng chứng là cho thấy có rất nhiều mô hình cho kết quả rất tốt đối với tập dữ liệu hiện tại nhưng lại hoàn toàn không thể đem áp dụng trên thực tế vì kêt quả dự đoán quá thấp. Hiện tượng mà mô hình dữ liệu làm việc tốt trên tập dữ liệu mẫu nhưng lại bất lực trước việc dự đoán dữ liệu thực tế được gọi là Over Fitting mà theo ngôn ngữ kiếm hiệp người ta gọi là tẩu hỏa nhập ma. Chúng ta cùng xem xét một ví dụ như sau:

Bài toán dự đoán độ hài lòng của các cặp đôi sau hôn nhân Bằng các cuộc khảo sát nhiều cặp vợ chồng, các nhà nghiên cứu tâm lý học đã thu được một biểu đồ thể hiện được mức độ hài lòng của các cặp vợ chồng sau khi kết hôn. Chúng ta có thể thấy, nhìn chung thì mức độ hài lòng suy giảm theo thời gian, nhưng mối liên quan với thời gian không hẳn tuân theo phương trình đường thẳng. Trong 3 năm đầu, mức độ suy giảm khá nhanh, nhưng sau đó tăng trong năm thứ 4 và 5; sau 5 năm thành hôn thì mức độ hài lòng lại suy giảm nữa.

Việc cần làm của những nhà nghiên cứu bây giờ là tìm ra mô hình hay phương trình tốt nhất để mô tả sự tương quan trong tập dữ liệu đó. Nếu gọi mức độ hài lòng là y và thời gian là t thì bản chất của chúng ta là đi tìm sự phụ thuộc y = f(t). Dễ thấy được ngay mô hình đơn giản nhất là mô hình hồi quy tuyến tính, tức là đi tìm tham số ab sao cho y = a + b.t. Sử dĩ nó đơn giản vì phương trình chúng ta chỉ phụ thuộc vào duy nhất một tham số b liên quan đến thời gian t mà thôi. Mô hình này giải thích được 90% sự khác biệt của dữ liệu như hình dưới (hồi quy tuyến tính là đường thẳng liền):

Tuy nhiên chúng ta có thể thấy được rằng mức độ hài lòng có sự biến thiên không tuân theo quy luật tuyến tính, điều này thể hiện ở việc mức độ hài lòng tăng vào năm thứ 4-5 và giảm sau đó. Điều này làm ta nghĩ đến một mô hình có bậc cao hơn. Bằng các kĩ thuật nâng bậc của mô hình với sự trợ giúp của các ngôn ngữ lập trình như R hay Python chúng ta dễ dàng tìm được mô hình bậc 2 với 2 tham số dạng:

Mô hình này thể hiện bằng đường nét đứt như biểu đồ trên. Mô hình này thật sự tốt, nó giải thích được 93% sự dị biệt của dữ liệu. Tuy nhiên chúng ta vẫn chưa coi thế là đủ, tư tưởng được đằng chân lân đằng đầu khiến chúng ta kì vọng có được mô hình tốt hơn giải thích được 100% phương sai của biến y. Việc này cũng chẳng khó khăn với các ngôn ngữ lập trình như R chỉ chưa đầy 3 phút chúng ta có thể tìm được một mô hình với 9 tham số, giải thích gần như hoàn toàn sự dị biệt của dữ liệu. Mô hình này thể hiện bằng đường cong in đậm trong hình trên.
Tuy nhiên, mục đích của mô hình được tạo ra không phải để giải thích dữ liệu hiện tại, mà để dự đoán được các dữ liệu tương lai sẽ như thế nào. Vì tương lai là thứ mà chúng ta chưa thể đoán biết được. Vậy câu hỏi đặt ra là 3 mô hình trên (1 tham số, 2 tham số, và 9 tham số) thì mô hình nào dự báo tốt nhất ??? Không ngạc nhiên khi mô hình 1 tham số tiên lượng mức độ hài lòng tiếp tục giảm trong năm 11, còn mô hình 2 tham số cũng tiên lượng giảm nhưng giảm một chút thôi. Nhưng điều kì lạ là mô hình 9 tham số tiên lượng rằng năm thứ 11 sau thành hôn thì mức độ hài lòng giảm như là xe hơi lao dốc xuống núi! Đành rằng mức độ hài lòng có thể suy giảm, nhưng không thể nào giảm đột ngột như mô hình 9 tham số dự báo như thế. Và chúng ta cần phải xem xét lại. Liệu rằng đã có gì đó không đúng chăng???

Nghịch lý: Mô hình giải thích được nhiều dữ liệu trong quá khứ nhất lại là mô hình tiên lượng tồi nhất!

Người mà bạn chọn lựa làm bạn đời là ai???

Mỗi con người trong chúng ta đều có những tiêu chuẩn riêng để lựa chọn người sẽ đi cùng ta suốt cả cuộc đời. Chúng ta thôi không bàn đến những triết lý của ngôn tình như chỉ cần tình yêu là đủ ở đây. Tình yêu là chuyện của con tim, còn tiêu chuẩn để lựa chọn là chuyện của lý trí. Một người thiếu trái tim – người đó chết. Một người mất đi lý trí – người đó chẳng thể sống được. Vậy nên đứng trước những sự lựa chọn lớn lao của cuộc đời, chúng ta cần tuân thủ rất nhiều nguyên tắc, rất nhiều tiêu chuẩn. Tuy nhiên, thực tế lại chứng minh rằng chúng ta đừng lựa chọn quá nhiều, đừng áp đặt lên người khác quá nhiều tiêu chuẩn. Over fitting thể hiện trong việc chọn lựa bạn đời là việc chúng ta cố gắng áp đặt quá nhiều tiêu chuẩn cho người bạn đời của chúng ta nhưng lại quên mất rằng, tất cả những tiêu chuẩn đó chỉ được xem xét trong quá khứ và hiện tại, mà biểu hiện của con người đó ở tương lai như thế nào không ai có thể biết trước được. Và bạn có muốn người bạn đời của mình giống như một mô hình dữ liệu, dù rất tốt khi xem xét ở hiện tại nhưng hoàn toàn bất lực với những thay đổi ở tương lai không. Vậy nên:

Không có tiêu chuẩn để lựa chọn – bạn đang đánh cược với tương lai. Có quá nhiều tiêu chuẩn để lựa chọn – chính tương lai đang đánh cược với bạn

Quá khứ chỉ là kỉ niệm. Đừng sống mãi trong chiếc bong bóng của riêng mình

Vấn đề của Over fitting không hẳn chỉ là một vấn đề trong ngành khoa học máy tính. Đôi khi chúng ta thấy thật sự nó rất đời thường, rất nhân sinh. Có lẽ không ít người trong mỗi chúng ta đang ở trong một chiếc bong bóng vô hình mà không hay biết. Không ít người trong số chúng ta thường có xu hướng nói nhiều về quá khứ hơn là nhắc đến tương lai. Có rất nhiều người thích lặp đi lặp lại những chuyện Xưa rồi Diễm, rằng ngày xưa tôi đã từng rất giỏi, ngày xưa tôi đã từng rất hạnh phúc, ngày xưa tôi đã…..Stop. Chúng ta là những con người đang sống ở hiện tại và tương lai là những điều chưa ai có thể biết trước. Đừng mải mê trong quá khứ vàng son và cũng đừng bi lụy vì một quá khứ lầm lỗi. Dù bạn là ai, bạn có quyền được quyết định chính tương lai của bạn và thay đổi để sống tốt hơn, sống đẹp hơn chưa bao giờ là muộn cả. Và nếu như ranh giới giữa những hạnh phúc hay khổ đau của quá khứ với những điều kì diệu của tương lai cũng mong manh như một bong bóng xà phòng, thị bạn đã sẵn sàng thoát ra khỏi chiếc bong bóng của mình đễ ngắm nhìn một thế giới tốt đẹp hơn chưa???

Đừng quá cầu toàn. Mọi thứ có thể thay đổi và quan trọng là biết thích nghi

Bạn có tin là có những thứ đến Google cũng không có câu trả lời cho bạn không??? Đúng là như vậy đấy, tôi đang nói riêng về phương diện tìm kiếm tri thức thôi, chúng ta dã là quá nhỏ bé rồi. Đến cả Google cũng không thể nói rằng biết hết 100% về mọi lĩnh vực thì huống gì chúng ta. Tôi biết có rất nhiều người rất cầu toàn, sự cầu toàn không phải là một cái gì đó sai trái, nó giúp cho con người ta biết chu toàn bổn phận và trách nhiệm của bản thân mình một cách nghiêm khắc hơn. Tuy nhiên, sự cầu toàn thái quá dễ dẫn con người ta đến cảm giác tiêu cực, cảm giác bị thất bại khi có một mục tiểu không hoàn thành. Có một điều bạn phải chấp nhận rằng:

Chúng ta không bao giờ có thể là người hoàn hảo

Có lẽ bạn thấy một con người rất giỏi về lập trình phần mềm và bạn ngưỡng mộ người đó vì đó là chuyên môn của bạn, nhưng chính bản thân người đó lại rất yếu kém ở một mảng khác ngoài chuyên môn ví dụ như nấu ăn chẳng hạn. Cuộc sống luôn cần những khoảng trống để lấp đầy, nếu một ai đó mà chẳng có một khoảng trống nào để lấp đầy thì họ thật cô đơn biết bao???

Đừng thần tượng hóa ai cả. Hi vọng càng nhiều thì thất vọng càng lớn

Tôi biết có rất nhiều người thực sự rất đáng để chúng ta ngưỡng mộ, có rất nhiều người thực sự rất có khả năng trong một lĩnh vực nào đó và họ xứng đáng được xã hội công nhận. Tuy nhiên có rất nhiều người mắc một căn bệnh mà giới trẻ bây giờ gọi là bênh Fan cuồng. Tôi còn nhớ một câu chuyện kể rằng khi Bi Rain – một diễn viên, một ca sĩ nổi tiếng của Hàn Quốc – trong một lần sang lưu diễn tại Việt Nam đã thu hút rất nhiều Fan hâm mộ trẻ đến cổ vũ. Việc đó thì cũng chẳng có gì là lạ cho đến một ngày người ta đưa lên mạng một đoạn video khi Bi Rain rời đi thì một đám đông các Fan cuồng chạy lên chiếc ghế mà anh ta ngồi thi nhau hít hà chiếc ghế đó như thể hít một thứ sinh khí từ trời ban xuống vậy. Thật là ngô nghê buồn cười, sự thần tượng hóa một ai đó giống như việc chúng ta đang cố gắng tập trung một cách thái quá vào dữ liệu mà chúng ta thu thập được mà quên đi mất bản chất của vấn đề. Thậm chí chính sự thần tượng hóa đó lại gây ra những hệ lụy vô cùng to lớn khi chúng ta biết được sự thật rằng trên thực tế có thể thần tượng của ta không được như chúng ta mong đợi. Thần tượng hóa là một thể hiện của Over fitting trong đời sống con người, nó có thể làm con người ta lạc quan hơn, nhưng cũng có thể làm cho người ta thất vọng hơn khi quay về với thực tại. Vậy nên, tốt nhất là Đừng thần tượng hóa ai cả

 

Và cuối cùng. Hãy học cách sống trung dung

Tôi biết rằng khi đứng trước một vấn đề của cuộc sống, có rất nhiều người hay có thói quen suy nghĩ rất nhiều, đôi khi là phức tạp hóa vấn đề đến mức tối đa. Tuy nhiên suy nghĩ nhiều quá có thể giúp chúng ta giải thích được những gì mình quan sát trong quá khứ (và hiện tại), nhưng nó không hẳn giúp ích chúng ta trong quyết định cho tương lai mà có thể làm cho tình hình rối lên. Trái ngược lại có những người chẳng suy nghĩ, hoặc suy nghĩ rất ít trước một vấn đề. Thái độ mặc đời trôi của những người như vậy cũng không cho chúng ta một cách giải quyết hiệu quả cho tương lai. Hiện tượng đó tương tự như under-fitting trong khoa học dữ liệu, nó bỏ sót và tiên lượng kém chính xác. Thành ra, nghệ thuật của mô hình hoá các mối liên quan là tìm một mô hình không có quá nhiều tham số mà cũng không có quá ít tham số. Nghệ thuật này cũng là nghệ thuật sống: tìm cách sống trung dung.. Hãy sống ôn hòa, bình thản trước mọi vấn đề của cuộc sống, không tầm thường hóa nhưng cũng không cường điều hóa vấn đè.

Cần phải giữ cho ý nghĩ và việc làm luôn luôn ở mức trung hòa, không thái quá, không bất cập và phải cố gắng ở đời theo nhân, nghĩa, lễ, trí, tín, cho thành người quân tửSách Trung Dung – Tử Tư

Lời kết

Từ một vấn đề tưởng chừng đã quá quen thuộc như Over fitting vẫn luôn tiềm ẩn trong nó những triết lý nhân sinh mà chúng ta đáng học hỏi mà cuối cùng tựu chung lại đó là cách sống trung dung trước mọi vấn đề xảy ra trong cuộc đời. Đứng trước những sự việc xảy ra bạn sẽ chọn cách nhìn nhận nó như thế nào. Và đứng trước cả vũ trụ rộng lớn – bạn sẽ chọn bạn là ai???

ML #2 – Cái máy nó học như thế nào

Giới thiệu

Lần đầu tiên nghe thấy khái niệm về Machine Learning tôi cũng không khỏi “hoang mang style” bởi cái thuật ngữ này và tôi biết có khá nhiều người mới bắt đầu cũng có cảm giác tương tự. Tôi cứ tưởng máy tính chỉ có thể bảo gì làm nấy thôi chứ sao có thể “học” được… Nếu các bạn cũng có những suy nghĩ như vậy thì bài viết này sẽ giải thích chi tiết cho bạn Làm thế nào máy có thể học và các bước cơ bản khi thực hiện một bài toán Machine Learning là như thế nào. OK chúng ta bắt đầu thôi

Vì sao máy tính có thể học

Có lẽ từ học không còn xa lạ gì đối với mỗi chúng ta nữa. Ngay từ khi sinh ra chúng ta đã phải học rất rất nhiều thứ như học ăn, học uống, học nói, học đọc, học viết… Nhớ lại những thời tôi đi học tôi thường sợ nhất là môn Lịch sử và không hiểu vì sao mà kiến thức lịch sử của tôi chỉ tồn tại trong đầu đúng từ tối hôm trước cho đến hết tiết Sử của ngày hôm sau, ngay sau khi cô giáo kiểm tra xong bài cũ là tôi cũng quên hết sạch. Rõ ràng đối với mỗi chúng ta người ta phân biệt hiện tượng học vẹt và sự thông minh thực sự. Và các bạn cũng sẽ thấy trong học máy cũng có những khái niệm như vậy.

vet-yeulaptrinh.pw

Machine Learning khác với if…else

Nếu bạn coi rằng người có trí nhớ tốt thì có khả năng học giỏi thì cũng có vẻ hợp lý vì với con người thì trí nhớ tốt đồng nghĩa với sự thông minh. Nhưng đừng nhầm lẫn với anh bạn máy tính nhé. Với những ổ SSD hàng Petabyte thì gần như trí nhớ của chúng là vô hạn tuy nhiên điều này chẳng liên quan gì đến việc một chiếc máy có thông minh thực sự hay không cả.

Hãy tưởng tượng bạn làm một chat bot nhắn tin cho người yêu bằng cách thu thập các đoạn hội thoại của các đôi tình nhân. Bộ nhớ của máy tính tầm vài TB đủ cho bạn lưu hàng tỉ cuộc hội thoại như thế. Tuy nhiên có hai hướng tiếp cận cho vấn đề này.

Cách 1

if Q in questions then print answer of Q else return Null

Cách này có nghĩa là bạn sẽ phải tìm kiếm chính xác câu hỏi của người hỏi trong tập dữ liệu và trả lời lại với answer tương ứng. Điều này chính là cách nghĩ cơ bản trong lập trình. Tuy nhiên nó hoàn toàn thất bại nếu như tập dữ liệu không đủ lớn, chưa kể rằng nó sẽ chẳng thể nào đem lại những cảm giác thú vị cho người dùng vì những câu trả lời bị lặp lại một cách nhàm chán. Giống y như việc mình học lịch sử hồi xưa vậy. Rõ ràng chiếc máy tính này đang học vẹt và không hề có một chút Machine Learning nào trong này cả. Một hệ thống chatbot thông minh sẽ không làm như thế.

Một hệ thống chatbot thông minh sẽ biết cách tự suy diễn xem với mỗi câu hỏi nào thì nên trả lời thế nào. Cũng giống như việc con người sẽ giải quyết được nhiều vấn đề hơn thông qua suy luận chứ không phải dựa trên sự học tủ, học vẹt nữa.

Cái máy nó học thế nào

Hãy tưởng tượng lại xem hồi bé chúng ta được bố mẹ dạy nhận biết đồ vật từ cái ca đến con bò con chó như thế nào. Ban đầu chúng ta còn ngập ngừng chưa biết được hết mặt các con vật nhưng sau đó chúng ta gặp lại càng nhiều lần thì không còn bỡ ngỡ nữa. Các trường mẫu giáo cũng hay sử dụng các Flash card để dạy trẻ con nhận biết đồ vật.

Mọi người thấy không, muốn học được một điều gì đó thì phải có người dạy và muốn máy có thể học thì chúng ta cũng cần phải dạy nó. Nhưng trước tiên muốn dạy được nó chúng ta cần phải có một tập dữ liệu, hiểu đơn giản giống như việc chúng ta phải có con bò, con chó thật hoặc có tranh ảnh về chúng thì mới có hi vọng dạy được đứa trẻ vậy. Khá dễ hiểu phải không bạn. Hãy nhớ rằng:

Không có dữ liệu thì sẽ không học được

Tuy nhiên việc có dữ liệu chuẩn rồi thì vấn đề tiếp theo đó chính là chọn một người thầy tốt. Rõ ràng rằng chúng ta sẽ không thể học được điều gì hay ho từ một ông thầy kém hiểu biết cả. Đối với máy cũng có những thầy giáo để dạy cho nó phải học cái gì từ tập dữ liệu của mình và những thầy giáo đó chính là các thuật toán học máy. Việc lựa chọn một ông thầy dạy cho con hay điều mà tôi muốn ám chỉ là việc lựa chọn một giải thuật tốt cho một bài toán học máy là một bước khá quan trọng. Có một lưu ý rằng:

Không phải cứ thuật toán phức tạp là hiệu quả sẽ cao

Việc lựa chọn thuật toán còn phụ thuộc vào bản thân của tập dữ liệu đối với những tập dữ liệu đơn giản, ít feature thì không cần phải training bằng một thuật toán quá phức tạp. Cũng giống như không ai lấy một giáo sư về Machine Learning để đi dạy trẻ con nhận biết đồ vật qua Flash card cả. Vậy nên trong Machine Learning không có khái niệm thuật toán này tốt, thuật toán kia không tốt. Mỗi thuật toán đều có cái ưu và nhược điểm riêng đối với từng tập dữ liệu. Việc áp dụng và phát huy nhó như thế nào là việc của mỗi chúng ta.

Machine Learning Workflow

Tôi đã thảo luận với các bạn cách dạy máy học như thế nào. Giờ tôi sẽ nói với các bạn về các bước thực hiện một bài toán Machine Learning. Tựu chung lại thì Machine Learning có thể được chia làm ba bước chính như sau:

  • Modeling: là bước mô hình hóa bài toán. Với mỗi một loại bài toán lại có một mô hình phù hợp như hồi quy hoặc phân lớp hoặc tuyến tính hoặc phi tuyến tính. Nhắc lại một lần nữa TÙY YÊU CẦU BÀI TOÁN. Sau bước này ta sẽ tìm ra được một số thuật toán phù hợp cho bước tiếp theo.
  • Learning: sau khi đã lựa chọn được thuật toán thì bước tiếp theo đó chính là bước học tức là sử dụng thuật toán đó để training trên tập dữ liệu đã cho. Sau bước này chúng ta thu được một bộ tham số được gọi là model
  • Predicting: sau khi có model chúng ta sử dụng nó để dự đoán các dữ liệu mới. Mọi người lưu ý rằng các dữ liệu mới này phải là các dữ liệu CHƯA ĐƯỢC TRAINING BAO GIỜ thì mới có thể sử dụng để đánh giá độ tốt của model thu được.

Đó là 3 bước chính, ngoài ra còn một số bước tiền xử lý dữ liệu được thực hiện giống như sơ đồ sau:

Nó có thể giải thích kĩ hơn như sau:

  • Từ người dùng ta thu thập được dữ liệu
  • Từ dữ liệu ta tiến hành tiền xử lý làm sạch dữ liệu
  • Sau khi tiền xử lý ta modeling lựa chọn giải thuật
  • Sau đó ta tiến hành tách dữ liệu thành hai tập traintest
  • Sau đó ta tiến hành thay đổi giải thuật cho đến khi có kết quả tốt nhất
  • Lựa chọn mô hình tốt nhất để trả lại feedback cho người dùng

Ví dụ minh họa

Chúng ta sẽ cùng tìm hiểu về các bước làm bài toán Machine Learning thông qua ví dụ minh họa cho bài toán phân loại hoa với ngôn ngữ Python. Và tôi cũng sẽ sử dụng Python làm ngôn ngữ chính cho tất cả các ví dụ trong blog này của tôi. Bây giờ chúng ta sẽ bắt đầu từng bước nhé

Giới thiệu bài toán

Dựa trên một tập dữ liệu về các đặc điểm của bông hoa, tôi sẽ sử dụng Machine Learning để dự đoán xem nó là loài hoa nào. Đây là một bài toán phân lớp hay trong tài liệu tiếng anh gọi là classification.

Tập dữ liệu

Do mục đích để minh họa nên tôi sử dụng một tập dữ liệu mẫu khá nổi tiếng cho bài toán này đó chính là tập dữ liệu hoa Iris

Tập dữ liệu này bao gồm 3 class tương ứng với số liệu của ba họ hoa iris được mô tả trong hình sau:

Chính vì tập dữ liệu đã được chuẩn hóa và được sử dụng nhiều cho mục đích nghiên cứu nên tôi bỏ qua bước tiền xử lý dữ liệu đối với tập dữ liệu này. Mặc dù trên thực tế thì quả thực là đời không như mơ. Thậm chí bước tiền xử lý dữ liệu là bước tốn nhiều thời gian và công sức nhất trong quá trính làm Machine Learning. Giờ đã xong bước tiền xử lý dữ liệu, chúng ta sẽ đến bước tiếp theo đó là lựa chọn thuật toán.

Lựa chọn thuật toán

Do bài toán này thuộc vào dạng classification nên chúng ta sẽ thử sử dụng một vài phương pháp thông dụng trong phân lớp như SVM hay Random Forest hay Naive Bayes hoặc cao siêu hơn một chút như Neural Network để áp dụng lên bài toán này. Giờ chúng ta sẽ tiến hành sử dụng Python để minh họa một số giải thuật nói trên

Minh họa bằng Python

Chúng ta đã định hướng trước sẽ sử dụng một số thuật toán trong classification để giải quyết bài toán phân loại hoa với bộ dữ liệu Iris. Bây giờ chúng ta sẽ học cách triên khai nó trên Python với bộ thư viên Sklearn vô cùng hữu ích. Trong bộ thư viện này bộ dữ liệu hoa iris đã được build-in sẵn rồi chúng ta chỉ việc lấy ra sử dụng thôi.

Đầu tiên là import nó vào

from sklearn.datasets import load_iris

Sau đó thì làm thế nào nhỉ. Chúng ta cùng thử xem nó hoạt động chưa bằng hàm main như sau:

if __name__ == "__main__":
    iris = load_iris()
    print "Size of data", iris.data.shape

Câu lệnh trên in ra kết quả là

Size of data (150, 4)

Có nghĩa là data của chúng ta bao gồm 150 bông hoa với 4 thuộc tính của mỗi bông hoa. Để in các class tương ứng với mỗi bông hoa chúng ta làm như sau:

print "Target", iris.target

Chúng ta sẽ thấy đươc các class tương ứng là [0, 1, 2] với ba loại hoa iris mô tả ở phần trên.

Bước tiếp theo chúng ta cần làm đó là tách tập dữ liệu thành hai phần trainingtesting. Chúng ta sử dụng thư viện train_test_split của sklearn như sau:

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2)

Đoạn code trên tách tập dữ liệu với ratio = 0.2 tức là 80% để training20% dùng để testing

Tiếp theo chúng ta sẽ áp dụng thử một thuật toán phân lớp đó là SVC với kernel tuyến tính thuộc bộ thư viện sklearn

from sklearn import svm
clf = svm.SVC(kernel='linear')
clf.fit(X_train, y_train)

Sau khi chạy xong đoạn code trên chúng ta đã lưu được một model sử dụng để dự đoán. Lưu ý là model này mới chỉ được sinh ra trên tập training. Chúng ta cần kiểm tra kết quả dự đoán với tập dữ liệu testing. Tôi hay sử dụng thư viện classification_report để in kết quả phân lớp. Xây dựng hàm in kêt quả như sau:

def evaluate_model(X_test, y_test):
    y_true, y_pred = y_test, clf.predict(X_test)
    print(classification_report(y_true, y_pred))

Và trong hàmmain chúng ta thêm vào đoạn code sau đoạn training như sau:

# Evaluate SVC
evaluate_model(X_test, y_test)

Tiến hành chạy thử model thu được kết quả:

Ở đây có hai chỉ số các bạn cân quan tâm đó chính là precisionrecall ta định nghĩa chúng như sau:

Precision bao nhiêu cái đúng được lấy ra

Một cách toán học thì

$$Precision=\frac{y_{true} \cap y_{selected}}{y_{selected}}$$

Recall bao nhiêu cái được lấy ra là đúng

Hay tức là

$$Recall=\frac{y_{true} \cap y_{selected}}{y_{true}}$$

Từ đó chỉ số thứ 3 ở trên f1-score được định nghĩa là:

$$2.\frac{Precision.Recall}{Precision+Recall}$$

Giờ chúng ta sẽ thử nghiệm mô hình với một số thuật toán khác trên cùng một tập dữ liệu để đánh giá được hiệu năng của từng thuật toán. Ở đây tôi sẽ so sánh với các thuật toán Random Forest, Naive Bayes còn về Neural Network xin hẹn các bạn một dịp sau.

Full Code

Các bạn có thể tham khảo Full code của bài viết này tại đây

Kết quả

Sau đây là kết quả chúng ta estimate sau khi training xong cả 3 model với cùng một tập dữ liệu

Chúng ta thấy rằng 3 model trên cùng một tập dữ liệu thì SVC cho kêt quả tốt nhất và Naive Bayes cho kết quả kém nhất. Bằng việc so sánh các phương pháp này chúng ta sẽ lựa chọn được model tốt hơn. Sau khi lựa chọn được model chúng ta sẽ lưu lại model tốt nhất để sử dụng cho lần sau.

Tổng kết

Qua bài viết này tôi đã cùng các bạn trao đổi về cách thực hiện một bài toán Machine Learning cơ bản. Rất hi vọng được các bạn ủng hộ để tôi có nhiều động lực viết thêm những chủ đề hay và bổ ích hơn.

Trân trọng

Tạo form trong HTML

FORM được sử dụng để chuyển dữ liệu liệu từ người dùng nhập vào đến web server.
Form bao gồm các thành phần nhập liệu (input elements) như: Text box, hộp kiểm, nút tùy chọn, Submit…
Bài viết này mình sẽ hướng dẫn các bạn một số các thành phần của Form hay được sử dụng nhất. Mình sẽ cố gắng giải thích để mọi người có thể hiểu.
Trong tài liệu HTML form được định nghĩa bằng cặp thẻ <form></form>
Các thẻ nằm giữa cặp thẻ <form></form> được gọi là các thành phần của Form

Các thành phần Form

Thành phần được sử dụng nhiều nhất trong form là thẻ <input />. Ta sử dụng <input /> để định nghĩa các thành phần của form như: Trường nhập liệu Text, các hộp kiểm, các nút tùy chọn, trường password, thành phần submit, các button, File upload.

1. Trường text
User name:

Code:

<input type="text" name="username" size="30" />

2. Trường password
Pass:

Code:

<input name="pass" size="30" type="password" />

3. Checkbox (Hộp kiểm)

Cho phép chọn nhiều thành phần từ danh sách đưa ra

Send my to email
Send my to phone

<input name="opt" type="checkbox" /> Send my to email
<input name="opt" type="checkbox" />Send my to phone

4. Radio button

Khác với checkbox, Radio chỉ phép phép chọn một thành phần từ danh sách đưa ra, các phần tử trong danh sách phải có cùng tên, như ví dụ sau ta
sẽ tạo ra hai thành phần Radio button có cùng tên là name=”gender”

Male
Female

<input type="radio" name="gender" checked /> Male 
<input type="radio" name="gender" /> Female

5. File upload

<input type="file" name="FILE" size="40" />

6. Button

Tạo ra một nút bấm trên form

<input type="button" name="button" value="Click me" />

7. Submit Button

Tạo nút submit trên form. Khi nút Submit được nhấn, dữ liệu trên form sẽ đuợc xử lý và gửi đi

<input type="submit" name="submit" value="Submit" />

8. Reset Button

Tạo nút Reset trên form. Khi nhấn nút Reset dữ liệu nhập vào form sẽ được reset về giá trị ban đầu của form

<input type="reset" name="cancel" value="Reset" />

Ta nhận thấy sự khác biệt giữa các thành phần input là thuộc tính type. Thuộc tính type sẽ quy định thành phần input này là Text, password, checkbox, hay button …

9. Dropdown list

Student
Bussiness
Manager
Other…

<select name="job">
      <option value="Student">Student</option>
      <option value="Bussiness">Bussiness</option>
      <option value="Manager">Manager</option>
      <option value="Other">Other...</option>
</select>

KẾT LUẬN

– Mỗi thành phần form đều được gán một tên (name=”ten_thanh_phan”): đây chính là tên biến được sử dụng trong các ngôn ngữ lập trình web như php hay asp.net…, Riêng thành phần Radio trong cùng một nhóm sẽ được đặt cùng tên.

– Thuộc tính value=”Giá trị”: đây là giá trị (dữ liệu) ban đầu của thành phần form, các thành phần không có thuộc tính value giá có giá trị ban đầu là rỗng (null).

– Các Phương thức hoạt động của form bạn có thể xem ở các bài tiếp thep.

Top 5 trường đại học tốt nhất để học công nghệ thông tin

Nếu bạn chọn theo học ngành CNTT nhưng vẫn chưa chọn được trường đại học thì bài viết này là dành cho bạn. Dưới đây là những trường đại học tốt nhất để học CNTT.

Đại học Bách khoa Hà Nội

Đây là một trong những nơi đào tạo ngành công nghệ thông tin đầu tiên trên cả nước. Với lịch sử lâu đời và bề dày kinh nghiệm, kỹ sư Bách Khoa vẫn là luôn được xã hội đánh giá cao.

Viện Công nghệ thông tin và Truyền thông gồm các đơn vị trực thuộc sau:

* Khối các đơn vị giảng dạy

– Bộ môn Công nghệ phần mềm

– Bộ môn Hệ thống thông tin

– Bộ môn Khoa học máy tính

– Bộ môn Kỹ thuật máy tính

– Bộ môn Mạng và truyền thông

– Trung tâm máy tính

– Chương trình đào tạo Việt Nhật (dự án HEDSPI)

– Các phòng thí nghiệm phục vụ công tác đào tạo

* Trung tâm nghiên cứu, phát triển và ứng dụng CNTT-TT

– PTN Công nghệ phần mềm và Quản trị CNTT

– PTN Công nghệ tri thức và dữ liệu

– PTN Công nghệ mạng và Truyền thông

– PTN Thiết kế hệ nhúng và ứng dụng

– PTN Công nghệ tính toán, đa phương tiện và mô phỏng

Địa chỉ viện: https://soict.hust.edu.vn/

Đại học Công Nghệ – ĐHQGHN

Đại học Công nghệ nổi bật với chất lượng đào tạo hàng đầu về CNTT kể cả giáo dục mũi nhọn, với các thầy cô trong khoa đều là các giáo sư, tiến sĩ đầu ngành. Trong các kỳ thi CNTT trong nước, Đại học Công nghệ luôn đứng ở những top đầu.

Sinh viên Đại học Công nghệ rất năng động. Vào đây bạn sẽ được dạo quang khuôn viên của ĐHQGHN vô cùng đẹp và ở cạnh rất nhiều đại học khác.

Địa chỉ khoa: http://fit.uet.vnu.edu.vn/

Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM

Trường ĐH KHTN là trung tâm đào tạo đại học, sau đại học, cung cấp nguồn nhân lực, đội ngũ chuyên gia trình độ cao trong các lĩnh vực khoa học cơ bản, khoa học liên ngành, khoa học công nghệ mũi nhọn, có năng lực sáng tạo, làm việc trong môi trường cạnh tranh quốc tế; là nơi thực hiện những nghiên cứu khoa học đỉnh cao tạo ra các sản phẩm tinh hoa đáp ứng nhu cầu phát triển KHCN và yêu cầu phát triển kinh tế – xã hội ngày càng cao của đất nước, phù hợp với xu thế phát triển thế giới.

Trường Đại học FPT

Là một trường Đại học tư thục tại Việt Nam, thuộc tập đoàn công nghệ FPT. Học ở đây bạn sẽ có cơ hội học tập rất thực tiễn và tiếp xúc nhiều với doanh nghiệp, cơ hội việc làm sau khi ra trường là khá cao.

Trường cáo đào tạo một số ngành: Kỹ thuật phần mềm, Khoa học máy tính, An toàn thông tin.

Trở thành lập trình viên chuyên nghiệp từ một tay chơi poker – Haseeb Qureshi

Hôm nay mình sẽ kể cho các bạn nghe về câu chuyện về Haseeb Qureshi. Anh từ một tay chơi Poker chuyên nghiệp đến một nhà lập trình viên xuất sắc, nhận được 8 offer của các công ty lớn trong đó có Google, Uber, Airbnb…

yeulaptrinh.pw

Haseeb Qureshi chơi Poker từ năm 16 tuổi, anh nhanh chống trở thành một trong những người chơi Poker đẳng cấp thế giới và kiếm được khá nhiều tiền. Năm 21 tuổi, sau một scandal xảy ra trong nghề nghiệp của mình, anh quyết định từ bỏ việc chơi Poker.

Trở về nhà, anh dành nhiều thời gian suy ngẫm về quá khứ của mình, sau đó hoàn tất việc học Anh Ngữ/Triết Học của mình tại The University of Texas. Tháng 12/2013 Haseed cho ra đời quyển sách “How to Be a Poker Player: The Philosophy of Poker” và nó nhanh chống trở thành một trong những quyển sách viết về Poker bán rất chạy thời đó.

Tuy nhiên Haseeb cảm thấy thật sự không hạnh phúc, ông quyên góp toàn bộ số tiền mình kiếm được cho từ thiện và cho gia đình mình, anh giữ lại 10.000 USD để học những gì mình yêu thích.

Năm 2014 Haseed bắt đầu dấn thân vào ngành công nghiệp công nghệ cao, anh chọn Công Nghệ Thông Tin là bước đi tiếp theo của mình. Anh bắt đầu tự học thêm kiến thức cho mình. Để đi một con đường mới là không hề dễ dàng và Haseed lên kế hoạch và lộ trình học tập cho riêng mình.

Sau đây là từng bước chiến lược học tập của Haseed, mình xin chia sẽ với các bạn:
————-
1. Tham gia khóa học Thuật Toán miễn phí trên Coursera “Princeton Coursera course on algorithms”
Link: https://www.coursera.org/learn/algorithms-part1.

2. Đọc quyển “The Algorithm Design Manual” của Steven S Skiena để bổ sung các kiến thức nền tảng về Cấu Trúc Dữ Liệu và Giải Thuật.

3. Đọc quyển “Cracking the Coding Interview” Gayle Laakmann McDowell để lấy kinh nghiệm và lên chiến lược Interview phù hợp.

4. Nghe thường xuyên các tin tức về Software Engineering trên các trang như:
– Software Engineering Daily: http://softwareengineeringdaily.com/category/podcast/
– The Bike Shed: http://bikeshed.fm/
– Đọc tên tin tức tại Hacker News: https://news.ycombinator.com/

Theo Haseed thì có thể ban đầu việc nghe sẽ rất khó khăn với bạn nhưng bạn chỉ nghe thôi không cần hiểu dần dần bạn sẽ quen. Việc Nghe tin tức về lĩnh vực bạn sẽ giúp bạn nắm bắt nhanh các xu thế CNTT hiện nay, quen dần với các thuật ngữ phổ biến bằng Tiếng Anh trong CNTT và đó cũng là cách để bạn có thể nói chuyện với các Developer khác một cách chuyên nghiệp.

5. Về phần System Design and Architecture, Haseed khuyên bạn nên đọc các kiến thức tại:
– HiredInTech: http://www.hiredintech.com/system-design
– High Scalability: http://highscalability.com/all-time-favorites/
————–

Sau đó Haseed tham dự bootcamp một khóa học ngắn hạn (12 tuần) để Review lại kiến thức của mình tại App Academy. Với Haseed điều quan trọng nhất là bạn phải “study study study” và không được nản chí. Anh là người thường xuyên đến sớm nhất và về trể nhất trong các buổi học.

Năm 2016 là năm thành công rực rỡ của Haseed anh nhận được 8 lời mời làm việc tại Google, Uber, Yelp, and Airbnb… Sau đó anh quyết định gia nhập Airbnb và hiện nay đang là kỹ sư phần mềm quan trọng của Airbnb.

Haseed là tấm gương điển hình mà chúng ta nên lấy đó là động lực để phấn đấu. Mình hi vọng những chia sẽ này sẽ giúp ích cho các bạn.

Tác giả: thầy Phạm Nguyễn Sơn Tùng – HCMUS

NDCCARD – spoj

Đề bài:

Thuật toán:

  • Dùng mảng f[i] đánh dấu giá trị lớn nhất <= i trong dãy A.
  • Vậy nên các cặp 3 số là a[i], a[j], f[m-a[i]-a[j]].
  • Chú ý đề bài cho dãy A đôi một khác nhau nhé.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int oo = 500001;
const int MAXN = 10001;
int i, j, n, m, a[MAXN], tmp, res, f[oo];
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    tmp = 0;
    for (int i = a[1]; i <= m; i++) {
        if ((tmp < n) && (i >= a[tmp+1])) tmp++;
        f[i] = a[tmp];
    }
    for (int i = 1; i<= n-2; i++) {
        for (int j = i+1; j <= n-1; j++) {
            tmp = m - a[i] - a[j];
            if (tmp < 1) continue;
            tmp = f[tmp];
            if (tmp <= a[j]) continue;
            res = max(res, a[i] + a[j] + tmp);
        }
    }
    cout << res;
    return 0;
}
CONST fin='';
     fout='';
VAR res, i, j, n, m, x, min: longint;
    a, ok: array[1..1000000] of longint;
    f: text;
BEGIN
  Assign(f,fin);
  Reset(f);
  Readln(f,n,m);
  min:=maxlongint-1;
  For i:=1 to n do
    Begin
      Read(f,a[i]);
      ok[a[i]]:=a[i];
      If a[i]<min then min:=a[i];
    End;
  Close(f);
  For i:=min+1 to  1000000 do
    If ok[i]=0 then ok[i]:=ok[i-1];
  res:=0;
  For i:=1 to n-1 do
    For j:=i+1 to n do
      Begin
        x:=m-a[i]-a[j];
        If x>0 then
          Begin
            If (ok[x]<>a[i]) and (ok[x]<>a[j]) and (ok[i]<>0) then
              If a[i]+a[j]+ok[x]>res then res:=a[i]+a[j]+ok[x];
          End;
      End;
  Assign(f,fout);
  Rewrite(f);
  Writeln(f,res);
  Close(f);
END.