Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
Hi, everyone. Welcome to the 23rd lecture of CS 188.
Chào các bạn. Chào mừng đến với bài giảng thứ 23 của CS 188.
Today we're going to wrap up our coverage of neural nets, and we're going to cover decision trees and also a little bit of hints at learning theory.
Hôm nay chúng ta sẽ kết thúc phần mạng nơ-ron, rồi học về cây quyết định và đề cập sơ qua một chút về lý thuyết học.
Before we dive in, a couple quick announcements. Midterm 2 is happening on Thursday. It's coming up very soon. There's a practice midterm which is due tonight.
Trước khi bắt đầu, có vài thông báo nhanh. Midterm 2 diễn ra vào thứ Năm. Sắp đến rất gần rồi. Bài thi thử giữa kỳ phải nộp tối nay.
And there is also homework 10 which is due tonight and which has three parts as usual. Any questions about logistics?
Và bài tập về nhà 10 cũng hạn nộp tối nay, gồm ba phần như thường lệ. Có câu hỏi nào về các vấn đề tổ chức không?
Let's wrap up neural nets. So here was our cartoon neural network.
Giờ ta kết thúc phần mạng nơ-ron. Đây là sơ đồ minh họa mạng nơ-ron của chúng ta.
It has some inputs x1 through xl, which get passed on to a first layer of neurons, which then each neuron process is a weighted combination of its inputs, applies a non-linear activation to that weighted combination which is this equation over here,
Nó có một số đầu vào x1 đến xl, được chuyển đến lớp nơ-ron đầu tiên, mỗi nơ-ron xử lý một tổ hợp có trọng số của các đầu vào, áp dụng một hàm kích hoạt phi tuyến lên tổ hợp đó, chính là phương trình ở đây,
and then passes it on to the next layer.
rồi chuyển sang lớp kế tiếp.
And this repeats, repeats, repeats until at some point here we effectively have generated the features for the problem that we're trying to solve for the current input.
Quá trình này lặp đi lặp lại cho đến một lúc nào đó ta thực sự đã tạo ra các đặc trưng cho bài toán mà ta muốn giải với đầu vào hiện tại.
Those features are fed into this thing here, which is a multi-class logistic regression, and which then hopefully gets trained to provide the right classification.
Các đặc trưng đó được đưa vào phần này, là một hồi quy logistic đa lớp, và hy vọng nó được huấn luyện để đưa ra phân loại đúng.
The way you find the strength of the connections between the neurons, the weights, is by optimizing the log probability of your label, for example i, given the inputs, for example i.
Cách tìm độ mạnh của các kết nối giữa các nơ-ron, tức các trọng số, là tối ưu log xác suất của nhãn, của ví dụ i, khi biết đầu vào của ví dụ i.
And this here is the weights. It corresponds to the weights of all the neurons in the entire network. This is a lot like what we saw before from multi-class logistic regression.
Còn đây là các trọng số. Nó tương ứng với trọng số của mọi nơ-ron trong toàn mạng. Điều này rất giống những gì ta đã thấy ở hồi quy logistic đa lớp.
It's a continuous optimization problem which you can solve by taking a gradient, taking a step in the direction of the gradient, which will, if you take a correctly sized step — not too big — it will increase your objective.
Đó là bài toán tối ưu liên tục, ta giải được bằng cách tính gradient, rồi bước một bước theo hướng của gradient; nếu bước có kích thước phù hợp, không quá lớn, thì hàm mục tiêu sẽ tăng.
And then you compute a gradient at the new spot, and you repeat, gradually climbing up to, hopefully, some good local maximum.
Sau đó ta tính gradient tại vị trí mới, và lặp lại, dần dần leo lên, hy vọng tới một cực đại cục bộ tốt.
While you're doing this, you keep track of the accuracy you achieve on some hold-out data. And whenever you see the hold-out data, accuracy starts going down.
Trong lúc làm vậy, bạn theo dõi độ chính xác trên một tập dữ liệu hold-out. Và khi bạn thấy độ chính xác trên dữ liệu hold-out bắt đầu giảm, nghĩa là bạn bắt đầu quá khớp với dữ liệu huấn luyện.
That means you are starting to over-fit your training data. That is, you're starting to memorize it rather than recognizing the pattern in the training data.
Tức là bạn bắt đầu học thuộc lòng nó thay vì nhận ra quy luật trong dữ liệu huấn luyện.
And you should stop training and call it done, and that's your trained neural network.
Lúc đó bạn nên dừng huấn luyện và coi như xong, và đó là mạng nơ-ron đã huấn luyện của bạn.
We also had a theorem that said that neural networks are universal function approximators.
Ta cũng có một định lý nói rằng mạng nơ-ron là bộ xấp xỉ hàm vạn năng.
A little more precisely, if your neural network is big enough and you need to have non-linear activations in your units, then it can approximate any continuous mapping from input to output up to arbitrary precision.
Chính xác hơn, nếu mạng nơ-ron đủ lớn và các đơn vị có hàm kích hoạt phi tuyến, thì nó xấp xỉ được mọi ánh xạ liên tục từ đầu vào đến đầu ra với độ chính xác tùy ý.
And that's also why we need to be careful about over-fitting, because if we keep going, we'll be able to fit any pattern, including over-fit whatever happens to be in the training data.
Đó cũng là lý do ta phải cẩn thận với quá khớp, vì nếu cứ tiếp tục, ta sẽ khớp được mọi quy luật, kể cả quá khớp với bất cứ thứ gì tình cờ có trong dữ liệu huấn luyện.
So how well does this all work? Let's look at computer vision, where some of the big breakthroughs have happened thanks to training deep neural networks.
Vậy tất cả điều này hiệu quả đến đâu? Hãy xem thị giác máy tính, nơi một số bước đột phá lớn đến nhờ huấn luyện mạng nơ-ron sâu.
So a standard problem in computer vision is to try to find objects in an image.
Một bài toán chuẩn trong thị giác máy tính là tìm các vật thể trong ảnh.
So maybe you're trying to find the human in the lineup of robots, or maybe you're trying to find a car when you're a self-driving car or a pedestrian or a stop sign and so forth.
Có thể bạn muốn tìm người trong hàng robot, hoặc tìm xe khi bạn là xe tự lái, hoặc người đi bộ, biển dừng, v.v.
So the problem here would be, at the time you get evaluated, an image gets fed in to the network, and hopefully it says, there is a person in this region, or something.
Vậy bài toán là, lúc được đánh giá, một ảnh được đưa vào mạng, và hy vọng nó nói rằng có một người ở vùng này, chẳng hạn.
The way people used to solve this problem is by doing a very careful manual feature design. And solve is not the right way to phrase it.
Trước đây người ta giải bài toán này bằng cách thiết kế đặc trưng thủ công rất cẩn thận. Mà nói "giải" thì chưa đúng.
The way people used to try to solve the problem was by doing manual feature design. And there are some interesting intuitions that went into this.
Cách người ta từng cố gắng giải bài toán là thiết kế đặc trưng thủ công. Và có vài trực giác thú vị đằng sau đó.
So you'd say, well, a picture that's red, green, blue pixel values, these values are between 0 and 255, but now if I turn up the light or turn down the light, all these values will drastically change.
Bạn sẽ nói: một bức ảnh gồm các giá trị pixel đỏ, xanh lá, xanh dương, nằm trong khoảng 0 đến 255, nhưng nếu tôi tăng sáng hoặc giảm sáng, tất cả các giá trị này sẽ thay đổi mạnh.
So I'm not so sure about processing those pixels. What can we do to avoid that we're sensitive to the lighting conditions?
Nên tôi không chắc về việc xử lý các pixel đó. Làm sao tránh bị nhạy với điều kiện ánh sáng?
Actually, if we just extract edges and only pass on where the edges are, then lighting going up or down will not matter, short of, of course, making it pitch black.
Thực ra, nếu ta chỉ trích xuất cạnh và chỉ truyền đi vị trí các cạnh, thì ánh sáng tăng hay giảm sẽ không quan trọng, trừ khi tối đen hoàn toàn.
But as long as you have some light, the edges will stay in the same place, and so that might be more stable.
Nhưng miễn là còn một ít ánh sáng, các cạnh vẫn nằm yên chỗ cũ, nên cách đó có thể ổn định hơn.
And then you might say, well, but what now if I move my camera around? I move it a little bit, then all the pixel values change, and even all the edge values change.
Rồi bạn lại hỏi: nhưng nếu tôi di chuyển camera thì sao? Tôi dịch nó một chút, mọi giá trị pixel đều đổi, thậm chí mọi giá trị cạnh cũng đổi.
They've all shifted a little bit. Can I account for that?
Tất cả đều dịch đi một chút. Có tính đến điều đó được không?
And they were like, well, after a lot of thinking, many, many papers, people come up with something called HOG, Histogram of Gradients, which turns the image first into edge image, and from there into this thing, which is a Histogram of Edges.
Và sau rất nhiều suy nghĩ, rất nhiều bài báo, người ta nghĩ ra thứ gọi là HOG, Histogram of Gradients, trước tiên biến ảnh thành ảnh cạnh, rồi từ đó thành thứ này, là một Histogram of Edges.
For every region in the image, how much is there a diagonal this way? How much diagonal that way? How much vertical? How much horizontal?
Với mỗi vùng trong ảnh, có bao nhiêu đường chéo theo hướng này? Bao nhiêu đường chéo hướng kia? Bao nhiêu đường dọc? Bao nhiêu đường ngang?
And now, all of a sudden when you move your camera a little bit, this HOG thing barely changes. So you're invariant to moving your camera and changing your lighting conditions.
Và giờ đây, khi bạn dịch camera một chút, HOG gần như không đổi. Vậy là nó bất biến với việc di chuyển camera và thay đổi điều kiện ánh sáng.
And that's nice because that way you can maybe learn something more robust than if you were sensitive to those things, assuming you're trying to classify, let's say, a person.
Điều đó tốt vì nhờ vậy bạn có thể học được thứ gì đó bền vững hơn so với khi nhạy với những yếu tố đó, giả sử bạn đang cố phân loại, chẳng hạn, một người.
Now of course, you try to classify how bright it is in the room, it's a different question.
Tất nhiên, nếu bạn cố phân loại độ sáng của căn phòng thì đó là một câu hỏi khác.
But most of the challenges are around classifying semantic things like person or dog or car or cat or stop sign, things that don't have to do anything with lighting or precise positioning.
Nhưng phần lớn thách thức nằm ở việc phân loại các thứ mang ngữ nghĩa như người hay chó hay xe hơi, mèo, biển báo dừng, những thứ không liên quan gì đến ánh sáng hay vị trí chính xác.
And then you'd say, well, now I've got this HOG thing.
Rồi bạn nghĩ: giờ mình có cái HOG này.
Maybe now I can feed this thing into a logistic regression or a support vector machine, which we didn't cover but which is very similar to logistic regression but doesn't as directly generalize to neural nets.
Có thể giờ mình đưa nó vào hồi quy logistic hoặc support vector machine, cái mà ta chưa học nhưng rất giống hồi quy logistic mà không khái quát hóa trực tiếp sang mạng nơ-ron bằng.
So it would feed into a logistic regression or a support vector machine and hope it would get some reasonable performance.
Vậy bạn đưa nó vào hồi quy logistic hoặc support vector machine và hy vọng đạt hiệu năng tương đối tốt.
And typically, by designing some version of Histogram of Edges, you would hope that you could write a paper saying your accuracy improved by 0.5% or something.
Thông thường, bằng cách thiết kế một phiên bản Histogram of Edges nào đó, bạn hy vọng có thể viết một bài báo nói độ chính xác tăng thêm 0,5% hay đại loại thế.
And that happened. And in fact, there is something you can see in those things, for example. It's not a bad idea.
Và điều đó đã xảy ra. Thật ra, bạn có thể thấy điều hay trong những thứ này, chẳng hạn. Đây không phải ý tồi.
If you look at this, what do you think is in the original image?
Nhìn cái này, các bạn nghĩ ảnh gốc là gì?
STUDENT
Bike.
Xe đạp.
PROFESSOR
A lot of people saying bike. That seems pretty natural to think. But it doesn't look exactly like a bike.
Nhiều người nói xe đạp. Nghĩ vậy cũng khá tự nhiên. Nhưng nó không giống hệt một chiếc xe đạp.
And in fact, you can imagine that if the lighting conditions change in that room where that picture was taken, this would still look the same.
Và bạn có thể hình dung nếu điều kiện ánh sáng trong căn phòng chụp bức ảnh đó thay đổi, thì cái này vẫn trông như cũ.
If the bike was moved a little bit, this would essentially still look the same.
Nếu chiếc xe đạp bị dịch đi một chút, thì về cơ bản cái này vẫn trông như cũ.
And so maybe you have a good feature representation here that you could train a logistic regression on to output a classification. It was indeed a bike, and this is the original image.
Vậy có lẽ bạn có một biểu diễn đặc trưng tốt để huấn luyện hồi quy logistic đưa ra kết quả phân loại. Đúng là xe đạp, và đây là ảnh gốc.
And the official name for the feature extractor uses HOG for Histogram of Gradients. Well, here's how well people were faring with this approach. So there is a competition called ImageNet.
Tên chính thức của bộ trích xuất đặc trưng này là HOG, viết tắt của Histogram of Gradients. Đây là mức độ người ta đạt được với cách tiếp cận này. Có một cuộc thi tên là ImageNet.
In this competition, to participate you send in a program.
Để tham gia, bạn gửi một chương trình.
And when you send in your program, the organizers will run the program on a secret stash of images, and they will report back out a number, how many errors your program made on classifying what's in the secret stash of images.
Khi bạn gửi chương trình, ban tổ chức sẽ chạy chương trình đó trên một bộ ảnh bí mật, rồi báo lại một con số: chương trình của bạn mắc bao nhiêu lỗi khi phân loại nội dung trong bộ ảnh bí mật đó.
And so you can see in this competition in 2010, the best entry in the competition had a error rate here of about 30%.
Bạn thấy trong cuộc thi năm 2010, bài dự thi tốt nhất có tỉ lệ lỗi khoảng 30%.
And people, of course, who design new Histogram of Edges and so forth and hope to do better. And indeed, in 2011, somebody might have had like half a percent better error rate.
Và tất nhiên người ta thiết kế Histogram of Edges mới và hy vọng làm tốt hơn. Quả thật, năm 2011, có người đạt tỉ lệ lỗi tốt hơn khoảng nửa phần trăm.
But this wasn't really moving very fast. Then, in 2012, things changed.
Nhưng tiến bộ không nhanh lắm. Rồi năm 2012, mọi thứ thay đổi.
Out of Geoff Hinton's laboratory at the University of Toronto, there was an entry into the competition that landed right there.
Từ phòng thí nghiệm của Geoff Hinton ở Đại học Toronto, có một bài dự thi rơi xuống ngay chỗ đó.
So even though traditional approaches were essentially flat-lining, by training a deep neural network called AlexNet, it was possible to halve the error rate. It wasn't just possible to halve the error rate.
Dù các cách tiếp cận truyền thống gần như chững lại, việc huấn luyện một mạng nơ-ron sâu tên AlexNet đã giảm một nửa tỉ lệ lỗi. Không chỉ là giảm được một nửa tỉ lệ lỗi.
People realized this general style of approach might have more promise than what they had been doing so far and switched approaches, and there was a big acceleration in progress.
Mọi người nhận ra phong cách tiếp cận chung này có thể hứa hẹn hơn những gì họ đã làm từ trước đến nay và chuyển hướng, rồi tiến bộ tăng tốc mạnh.
And in fact, by now, this competition has been retired because deep neural nets have been trained to achieve human level error rates.
Thật ra đến nay, cuộc thi này đã bị dừng vì các mạng nơ-ron sâu đã được huấn luyện đạt tỉ lệ lỗi ngang con người.
And so to do more interesting research, people moved to different kind of challenges than this one.
Vì vậy để nghiên cứu thú vị hơn, người ta chuyển sang những thách thức khác.
It's still one that often people benchmark on to just sanity check things, and also often benchmark speed on because, for example, the training of AlexNet here took six days of training time.
Nó vẫn thường được dùng làm chuẩn để kiểm tra nhanh, và cũng để đo tốc độ, vì chẳng hạn, huấn luyện AlexNet mất sáu ngày.
That's a lot of gradient steps, you can imagine. Now, these days, the fastest training times I believe are around 10 minutes, between 10 and 20 minutes somewhere, which is a lot faster.
Bạn có thể hình dung đó là rất nhiều bước gradient. Ngày nay, thời gian huấn luyện nhanh nhất theo tôi biết khoảng 10 phút, đâu đó giữa 10 và 20 phút, nhanh hơn rất nhiều.
They don't necessarily use a whole lot less compute, but they just parallelize a whole lot more, and so the wall clock time is a lot faster. But so this is a drastic change.
Họ không nhất thiết dùng ít tính toán hơn nhiều, mà song song hóa nhiều hơn hẳn, nên thời gian thực nhanh hơn rất nhiều. Nhưng đây là một thay đổi mạnh mẽ.
And at a high level, you might wonder, how is this possible that this kind of jump so far forward — why were there not, let's say, some neural nets maybe here already and maybe here also doing better?
Ở mức tổng quát, bạn có thể thắc mắc, sao lại có bước nhảy vọt lớn như vậy? Sao trước đó không có, chẳng hạn, vài mạng nơ-ron ở đây rồi và cũng ở đây làm tốt hơn?
And how come it was just a big leap forward?
Sao lại chỉ có một bước nhảy vọt lớn?
Big reason is that these neural nets, they just need a lot of data and a lot of compute to train with that lots of data.
Lý do lớn là các mạng nơ-ron này cần rất nhiều dữ liệu và rất nhiều tính toán để huấn luyện với lượng dữ liệu lớn đó.
And if it took six days in 2012 for one of the best programmers in the world to program a GPU to train a neural network on this data set, if he had tried it a year before it would have taken even longer.
Nếu năm 2012 phải mất sáu ngày để một trong những lập trình viên giỏi nhất thế giới lập trình GPU huấn luyện mạng nơ-ron trên tập dữ liệu này, thì thử một năm trước đó sẽ còn lâu hơn nữa.
And as you imagine, with anything machine learning, when you do a run, it usually doesn't succeed. You go in, you look, you change something, you run again.
Và như bạn hình dung, với bất kỳ thứ gì về machine learning, khi chạy một lần thì thường không thành công. Bạn vào xem, đổi cái gì đó, rồi chạy lại.
And if that turnaround time is long — six days is already pretty long, but if it's even longer than that, that might be hard to get everything right so you get a good result. And so it's a confluence of a very large data set which existed since 2010 and enough compute, GPU compute in this days, and the ability of someone, namely Alex Krizhevsky, to program the GPU to train neural nets
Và nếu thời gian chờ lâu, sáu ngày đã khá lâu rồi, mà nếu còn lâu hơn nữa thì rất khó chỉnh mọi thứ cho đúng để có kết quả tốt. Vậy đó là sự hội tụ của một tập dữ liệu rất lớn có từ năm 2010, đủ năng lực tính toán GPU vào thời đó, và khả năng của một người, cụ thể là Alex Krizhevsky, lập trình GPU để huấn luyện mạng nơ-ron
on the GPU at that time. Today, you might say, oh, that sounds easy. Just fire up TensorFlow, Power Torch, and it's on a machine with GPUs and it'll train with GPUs.
trên GPU vào lúc đó. Ngày nay bạn có thể nói, nghe dễ mà. Cứ bật TensorFlow, PyTorch lên, chạy trên máy có GPU là nó huấn luyện bằng GPU.
But back then, those things didn't exist.
Nhưng hồi đó những thứ ấy chưa tồn tại.
The reason they exist is exactly these kind of successes that motivated Facebook and Google to say, oh, we should build a general tool that can do this in more generality so not everybody needs Alex Krizhevsky to get a neural net trained.
Chúng tồn tại chính là nhờ những thành công như vậy đã thúc đẩy Facebook và Google nói rằng: ta nên xây một công cụ chung làm được việc này tổng quát hơn, để không ai cần đến Alex Krizhevsky mới huấn luyện được mạng nơ-ron.
And so Alex, of course, didn't call this network AlexNet. That would be pretty crazy to do.
Và tất nhiên Alex không gọi mạng này là AlexNet. Làm vậy thì hơi điên.
But everybody else in the community was like, oh, well, Alex made this happen, and they called it Alex. So big leap forward, and then big acceleration.
Nhưng mọi người khác trong cộng đồng thì kiểu như, ồ, Alex đã làm nên chuyện này, nên họ gọi nó là Alex. Vậy là một bước tiến lớn, rồi tốc độ phát triển tăng vọt.
Have we covered everything to understand what happened in that paper? There is one part, one fundamental part we haven't covered, but at a high level it's easy to cover.
Chúng ta đã học đủ để hiểu những gì xảy ra trong bài báo đó chưa? Còn một phần, một phần nền tảng mà ta chưa đề cập, nhưng nói ở mức tổng quát thì rất dễ.
This network is gigantic, has 60 million parameters. But actually, in some sense, the way we've been looking at networks, it would be even more.
Mạng này rất lớn, có 60 triệu tham số. Nhưng thật ra, theo một nghĩa nào đó, với cách ta đang nhìn các mạng thì số này còn lớn hơn nữa.
So there's a lot of parameter sharing happening in this network.
Vì có rất nhiều chia sẻ tham số trong mạng này.
So when we talk about old entries in the weight vector, each entry in a weight factor corresponding to one connection, in this network, many of the connections have the same strength.
Khi ta nói về các phần tử của vectơ trọng số, mỗi phần tử trong vectơ trọng số ứng với một kết nối, thì trong mạng này, nhiều kết nối có cùng độ lớn.
So the number is the same on a bunch of connections, on a lot of connections.
Tức là con số giống nhau trên cả loạt kết nối, trên rất nhiều kết nối.
The rationale here is that if you're looking for a diagonal edge in the image, whether you're looking at top, bottom, left, right — it doesn't really matter — you should have the same pattern recognizer.
Lý do là nếu bạn đang tìm một cạnh chéo trong ảnh, dù nó ở trên, dưới, trái hay phải thì cũng không quan trọng, bạn nên dùng cùng một bộ nhận dạng mẫu.
So you might want to share what you do in terms of calculation over the entire image in some translation invariant way. Those are called convolutional layers.
Nên ta có thể chia sẻ phép tính trên toàn bộ ảnh theo kiểu bất biến tịnh tiến. Đó gọi là các tầng tích chập (convolutional layers).
And all of this really is parameter sharing such that you do the same calculation in every region of the image.
Tất cả đều là chia sẻ tham số, để bạn thực hiện cùng một phép tính ở mọi vùng của ảnh.
So you have to do a little bit of trickery to get that working, but that's essentially it. And then, of course, everything we covered.
Cần một chút mẹo kỹ thuật để làm được, nhưng về cơ bản là vậy. Và tất nhiên, mọi thứ còn lại là những gì ta đã học.
And run the optimization, in this case, originally for six days. Now, at the time when this happened, this was a big breakthrough in image recognition. And you could think of it that way.
Rồi chạy tối ưu hóa, trong trường hợp này ban đầu mất sáu ngày. Vào thời điểm đó, đây là một đột phá lớn trong nhận dạng ảnh. Và bạn có thể nghĩ theo hướng đó.
OK, now we can categorize into 1,000 categories. That's pretty cool, because before it didn't seem like it's going to work any time soon, and now maybe it's going to work quickly.
Giờ ta có thể phân loại vào 1.000 loại. Thế là khá hay, vì trước đó có vẻ chưa thể thành công trong thời gian tới, còn giờ có lẽ sẽ nhanh thôi.
But you could also ask the question, can we do more? And so what more could you do with images?
Nhưng bạn cũng có thể hỏi, liệu làm được nhiều hơn không? Vậy có thể làm gì thêm với ảnh?
Well, maybe instead of just recognizing what's in an image, which is a 1,000 output neurons for this case, maybe you can generate a sentence describing what's in the image.
Thay vì chỉ nhận ra có gì trong ảnh, tức 1.000 nơ-ron đầu ra trong trường hợp này, có lẽ ta có thể sinh ra một câu mô tả nội dung ảnh.
You might wonder, well, what do we have to change? Well, what we have to change is we have to have a new data set.
Bạn có thể thắc mắc, vậy phải thay đổi gì? Ta phải có một tập dữ liệu mới.
So now the data set is not just image and label but imagine and sequence of words. What does it mean, sequence of words?
Giờ tập dữ liệu không chỉ là ảnh và nhãn mà là ảnh và một chuỗi từ. Chuỗi từ nghĩa là gì?
Well, there's 200,000 words in English, so it's like having 200,000 labels to choose from. Then again 200,000 labels, again 200,000 1,000 labels.
Tiếng Anh có 200.000 từ, nên giống như chọn trong 200.000 nhãn. Rồi lại 200.000 nhãn, rồi lại 200.000 nhãn nữa.
And that's effectively how the network is set up to train for captioning. Here are some example captions automatically generated by neural networks. So this is pretty impressive, right?
Và về cơ bản mạng được thiết lập như vậy để huấn luyện chú thích ảnh. Đây là vài chú thích mẫu do mạng nơ-ron tự động sinh ra. Khá ấn tượng đúng không?
Look at this one here. "Girl in pink dress is jumping in air." That's a very good caption for what's going on. "Black and white dog jumps over bar."
Hãy nhìn ví dụ này. "Cô bé váy hồng đang nhảy lên không trung." Đó là chú thích rất tốt cho những gì đang diễn ra. "Chú chó đen trắng nhảy qua xà."
Again, very good caption.
Lại một chú thích rất tốt.
Not everything is perfectly accurate, but keep in mind this was achieved in 2015, whereas in 2012, it was even impractical to just say anything reasonable about what it might be in an image.
Không phải cái nào cũng chính xác tuyệt đối, nhưng hãy nhớ điều này đạt được vào năm 2015, còn năm 2012 thì ngay cả việc nói điều gì hợp lý về thứ có thể có trong ảnh cũng chưa khả thi.
Interestingly, this actually happened in eight research labs at the same time.
Thú vị là chuyện này xảy ra ở tám phòng nghiên cứu cùng lúc.
So eight labs within a month of each other had the same results — a lab at Berkeley, a lab at Stanford, a lab at Toronto, Montreal, NYU, Facebook, Baidu, Google.
Tám phòng lab, cách nhau chưa đầy một tháng, đều có cùng kết quả: một lab ở Berkeley, một ở Stanford, một ở Toronto, Montreal, NYU, Facebook, Baidu, Google.
How is it possible that eight labs have essentially the same result and with roughly the same methodology, and not identical but pretty close? Well, it was the time that this data set came out.
Sao tám lab lại có kết quả về cơ bản giống nhau với phương pháp gần như giống nhau, không y hệt nhưng rất gần? Đó là lúc tập dữ liệu này ra mắt.
And it's a total change in mindset in some sense.
Và theo một nghĩa nào đó, đó là một thay đổi hoàn toàn về tư duy.
At this point, if somebody has a data set that's big enough, and you have some experts who can train neural networks on that data set, then you can have a network that recognizes the pattern.
Từ lúc này, nếu ai đó có tập dữ liệu đủ lớn và có vài chuyên gia biết huấn luyện mạng nơ-ron trên tập dữ liệu đó, thì bạn có thể có một mạng nhận ra được mẫu.
Now, it depends on the kind of challenge how much data you might need, but here the data sets came out, and soon thereafter many, many labs had figured out how to train from image to caption.
Cần bao nhiêu dữ liệu thì tùy loại bài toán, nhưng ở đây các tập dữ liệu đã ra đời, và ngay sau đó rất nhiều lab đã biết cách huấn luyện từ ảnh sang chú thích.
Now, some skeptics at the time would still say things like — especially in 2012, would say things like, oh, well, it's nice to have another trick in our bag.
Lúc đó một số người hoài nghi vẫn nói, nhất là năm 2012, kiểu như ồ, có thêm một chiêu trong túi cũng hay.
This whole neural net, it has better features than we could design by hand. My Histograms of Edges look pretty good.
Mạng nơ-ron này có đặc trưng tốt hơn những gì ta tự thiết kế bằng tay. Histogram of Edges của tôi trông cũng khá tốt.
But I guess this has found better features than I could do, so I'm going to use those features. But that's a misunderstanding.
Nhưng có vẻ nó tìm được đặc trưng tốt hơn tôi, nên tôi sẽ dùng những đặc trưng đó. Nhưng đó là hiểu lầm.
It's not just about learning some features you can use, which is of course important. It's about the fact that you can actually, for any data set, start pattern recognizing pretty reliably with this methodology.
Vấn đề không chỉ là học vài đặc trưng để dùng, dù điều đó tất nhiên cũng quan trọng. Mà là với bất kỳ tập dữ liệu nào, bạn đều có thể bắt đầu nhận dạng mẫu khá đáng tin cậy bằng phương pháp này.
You might then wonder, does that solve computer vision? And by no means is computer vision solved. But you could ask the question, what would it take to convince somebody that computer vision is solved?
Vậy liệu điều đó giải quyết xong thị giác máy tính chưa? Hoàn toàn chưa, thị giác máy tính chưa được giải quyết. Nhưng bạn có thể hỏi, cần những gì để thuyết phục ai đó rằng thị giác máy tính đã được giải quyết?
And can pattern recognition solve computer vision? Well, what would it mean? Well, what if we do the following?
Và nhận dạng mẫu có giải quyết được thị giác máy tính không? Vậy điều đó nghĩa là gì? Thử thế này nhé.
What if we say, we have a neural network, and it gets to look at an image, and then you get to ask a question about that image.
Giả sử ta có một mạng nơ-ron, nó được xem một bức ảnh, rồi bạn đặt một câu hỏi về bức ảnh đó.
And if it answers the question correctly, that's good.
Nếu nó trả lời đúng thì tốt.
If it can do that for essentially any image and any question about any image, then maybe we can call that network capable of computer vision, and even some natural language processing to know what's being asked about.
Nếu nó làm được điều đó với hầu như mọi ảnh và mọi câu hỏi về bất kỳ ảnh nào, thì có lẽ ta có thể nói mạng đó có khả năng thị giác máy tính, cộng thêm chút xử lý ngôn ngữ tự nhiên để hiểu câu hỏi.
So people who strongly believe that this might work out start building a data set for exactly that setting.
Những người tin chắc rằng cách này có thể thành công đã bắt đầu xây dựng tập dữ liệu đúng cho bối cảnh đó.
So now the input to the network is an image and a sequence of words, and the output would be an answer. I particularly like this one over here.
Giờ đầu vào của mạng là một ảnh và một chuỗi từ, và đầu ra sẽ là một câu trả lời. Em đặc biệt thích ví dụ ở đây.
The question is, how many school buses? The neural net says two. And the ground truth indeed is two because there's one hiding in the back here. So it knows that, and it answers correctly.
Câu hỏi là: có bao nhiêu chiếc xe buýt trường học? Mạng nơ-ron trả lời là hai. Và đáp án đúng quả thật là hai, vì có một chiếc đang khuất ở phía sau này. Vậy là nó biết điều đó và trả lời đúng.
What sport is this? Baseball. And so forth. By no means does this work at the level humans can answer questions about images.
Đây là môn thể thao gì? Bóng chày. Và cứ thế. Hoàn toàn không có nghĩa là nó đạt mức mà con người trả lời câu hỏi về hình ảnh.
But if you look at this and you're like, wow, this is pretty good, and then you go back to early 2012 before the deep learning revolution kicked in, people were like, it might take another career's worth of work before we recognize what's in an image.
Nhưng nếu nhìn vào đây và bạn nghĩ, wow, khá tốt đấy, rồi quay lại đầu năm 2012, trước khi cuộc cách mạng học sâu bùng nổ, người ta bảo có khi phải mất thêm cả một sự nghiệp nghiên cứu mới nhận ra được thứ có trong một bức ảnh.
Things moved a lot faster than expected.
Mọi thứ tiến nhanh hơn dự kiến rất nhiều.
And in parallel, the same thing happened in speech recognition. So in speech recognition right around the same time, things weren't exactly progressing with more traditional approaches.
Và song song đó, điều tương tự xảy ra với nhận dạng giọng nói. Trong nhận dạng giọng nói, cũng vào khoảng thời gian đó, mọi thứ không thực sự tiến triển với các cách tiếp cận truyền thống hơn.
The deep learning approach, which means train a gigantic network on a large amount of data, of course requiring a large amount of compute, was able to learn a mapping from a sequence of numbers corresponding to the pressure wave coming in to a transcription of what was said.
Cách tiếp cận học sâu, nghĩa là huấn luyện một mạng khổng lồ trên lượng dữ liệu lớn, dĩ nhiên đòi hỏi lượng tính toán lớn, đã học được ánh xạ từ một chuỗi số tương ứng với sóng áp suất đi vào thành bản phiên âm của điều được nói.
Where did this one happen? Also out of Geoff Hinton's lab. A different student, but also out of Geoff's lab in Toronto.
Việc này xảy ra ở đâu? Cũng từ phòng thí nghiệm của Geoff Hinton. Một sinh viên khác, nhưng cũng từ phòng lab của Geoff ở Toronto.
Now, this is not the only pattern recognition task. How about machine translation? And we might get into more detail on these tasks in one of the next lectures.
Đây không phải là bài toán nhận dạng mẫu duy nhất. Còn dịch máy thì sao? Chúng ta có thể đi sâu hơn vào các bài toán này trong một trong các bài giảng tới.
But just at a high level, it's essentially the same problem. You have a sentence in one language going in, and you need to produce a sentence in another language going out.
Nhưng nhìn tổng quát thì về cơ bản đó là cùng một bài toán. Có một câu ở ngôn ngữ này đi vào, và bạn cần tạo ra một câu ở ngôn ngữ khác đi ra.
What do you do? You set up a large neural network, feed it enough paired up sentences of language one into language two, and it learns the pattern.
Bạn làm gì? Bạn thiết lập một mạng nơ-ron lớn, cho nó đủ các cặp câu từ ngôn ngữ một sang ngôn ngữ hai, và nó học ra quy luật.
And again, what does it mean to take in a symbol?
Và một lần nữa, nhận vào một ký hiệu nghĩa là gì?
Taking in a symbol is, let's say, I don't know if there is maybe 10,000 symbols, then you can have a one hot vector where all entries are 0 except for the one indexing into that symbol being fed in as same for words.
Nhận một ký hiệu là, giả sử, em không biết, có thể có 10.000 ký hiệu, thì bạn có thể dùng vectơ one-hot, trong đó mọi phần tử đều bằng 0 trừ phần tử ứng với ký hiệu đó, được đưa vào; với từ cũng tương tự.
If there is 200,000 words, then an output of a word means that you output one hot sector, effectively an activation for which word you want right now out of 200,000 choices.
Nếu có 200.000 từ, thì đầu ra là một từ nghĩa là bạn xuất ra một vectơ one-hot, về bản chất là kích hoạt cho từ bạn muốn lúc này trong 200.000 lựa chọn.
There are also some transcriptions, not only for machine translation but definitely for speech recognition, that don't output words, that just directly output character by character.
Cũng có một số hệ phiên âm, không chỉ cho dịch máy mà chắc chắn là cho nhận dạng giọng nói, không xuất ra từ mà xuất trực tiếp từng ký tự một.
And then you have a smaller output channel, but you need to do it more frequently to get all the characters sequenced together.
Khi đó kênh đầu ra nhỏ hơn, nhưng bạn phải xuất thường xuyên hơn để ghép được toàn bộ các ký tự thành chuỗi.
This is actually put in production for Google machine translation in August 2017.
Cái này thực sự được đưa vào sản phẩm của Google Dịch vào tháng 8 năm 2017.
That's when they — the original result I believe happened in 2015 by Ilya Sutskever and collaborators at Google to train neural network for machine translation that was better than other approaches.
Đó là khi họ... kết quả ban đầu em tin là xuất hiện năm 2015 bởi Ilya Sutskever và các cộng sự ở Google, huấn luyện mạng nơ-ron cho dịch máy tốt hơn các cách tiếp cận khác.
And then it took another two years to really productionize it, make it stable for release at large scale, and that happened in 2017.
Rồi mất thêm hai năm nữa để thực sự đưa nó vào sản phẩm, làm cho nó ổn định để phát hành ở quy mô lớn, và điều đó xảy ra năm 2017.
So that's a few highlights of what is possible with the neural networks and the related ideas of, essentially, you're going to learn a function that goes from input to output, and the neural network formalism gives you a general function class where you can learn any continuous function of the arbitrary accuracy.
Đó là vài điểm nổi bật về những gì có thể làm với mạng nơ-ron và các ý tưởng liên quan, về cơ bản là bạn sẽ học một hàm đi từ đầu vào đến đầu ra, và hình thức mạng nơ-ron cho bạn một lớp hàm tổng quát trong đó bạn có thể học bất kỳ hàm liên tục nào với độ chính xác tùy ý.
And so if you have enough data, enough compute, you can run gradient ascent long enough to find a good setting of the parameters and get a good result.
Vậy nếu có đủ dữ liệu, đủ tính toán, bạn có thể chạy gradient ascent đủ lâu để tìm bộ tham số tốt và có kết quả tốt.
Any questions about neural nets before I move on to some learning theory and decision trees? Yes?
Có câu hỏi nào về mạng nơ-ron không trước khi em chuyển sang lý thuyết học và cây quyết định? Bạn nào?
STUDENT
How should I or anyone learn about stuff like back propagation?
Em hay bất kỳ ai nên học về những thứ như lan truyền ngược bằng cách nào ạ?
PROFESSOR
So I suspect 189 and 182 cover back propagation. I would be surprised if not.
Em đoán là CS 189 và 182 có dạy lan truyền ngược. Nếu không thì em sẽ rất ngạc nhiên.
Just to clarify, at a high level, back propagation is the efficient algorithm to compute all the derivatives that you need to do a gradient update.
Nói rõ thêm, ở mức tổng quát, lan truyền ngược là thuật toán hiệu quả để tính mọi đạo hàm mà bạn cần cho một bước cập nhật gradient.
And so, essentially, there's some kind of backward pass through the network that gives you that. You could check the 189, 182 lectures.
Về cơ bản, có một lượt đi ngược qua mạng để cho bạn các đạo hàm đó. Bạn có thể xem bài giảng của CS 189, 182.
You could also check Mr. Andrej Karpathy's course at Stanford, which is a PhD level course but which also covers it in one of the earlier lectures in the course.
Bạn cũng có thể xem khóa học của anh Andrej Karpathy ở Stanford, là khóa bậc tiến sĩ nhưng cũng dạy nó ở một trong những bài đầu của khóa.
So those would be the resources I'd suggest if you want to learn it soon.
Đó là những nguồn em gợi ý nếu bạn muốn học sớm.
Yes?
Bạn nào?
STUDENT
Isn't it general that the more layers you put in, the more accurate [INAUDIBLE] you don't have a lot of [INAUDIBLE]?
Có phải nói chung càng thêm nhiều lớp thì càng chính xác [KHÔNG NGHE RÕ] mà không có nhiều [KHÔNG NGHE RÕ] không ạ?
PROFESSOR
So it's a good question. Is it the more layers the better? Some of the most successful networks have a large number of layers, but maybe five years from now we'll call it not large.
Đó là câu hỏi hay. Có phải càng nhiều lớp càng tốt? Một số mạng thành công nhất có số lớp lớn, nhưng có thể năm năm nữa ta sẽ không gọi đó là lớn nữa.
People thought eight layers, like AlexNet, was deep. But then ResNet-101 has 101 layers, which is much deeper than eight. Maybe soon people will have like 1,000 layer networks or 100,000 layer networks.
Người ta từng nghĩ tám lớp, như AlexNet, là sâu. Nhưng ResNet-101 có 101 lớp, sâu hơn tám lớp rất nhiều. Có thể sớm thôi sẽ có mạng 1.000 lớp hoặc 100.000 lớp.
Who knows?
Ai biết được?
In some sense, there is a few factors at play here. One is that the bigger the network, the more you can represent, both by being deeper and by being wider.
Theo một nghĩa nào đó, có vài yếu tố tác động ở đây. Một là mạng càng lớn, thì càng biểu diễn được nhiều, cả khi sâu hơn lẫn khi rộng hơn.
You can think of the network as essentially running a computer program. And the width is the parallelization of your program, and the depth is what has to be serialized in your program.
Bạn có thể coi mạng về cơ bản như đang chạy một chương trình máy tính. Và chiều rộng là sự song song hóa của chương trình, còn chiều sâu là phần buộc phải thực hiện tuần tự trong chương trình.
And so if you think about, OK, if I need to do a certain calculation, how much can up parallelize versus how much will really need to happen one after the other?
Nên nếu bạn nghĩ rằng, giả sử tôi cần thực hiện một phép tính, thì bao nhiêu có thể song song hóa, và bao nhiêu thực sự cần xảy ra lần lượt cái này sau cái kia?
That is one way, one analog to think of how much width and depth you might need. Another way to potentially think of it is, what if we just want human level performance?
Đó là một cách, một phép so sánh để nghĩ xem cần bao nhiêu chiều rộng và chiều sâu. Một cách khác để suy nghĩ là, nếu ta chỉ muốn hiệu năng ngang con người thì sao?
Maybe we want to just do human type tasks. And then people study the brain and they say, well, the human visual system might have maybe, I don't know, four or five layers.
Có thể ta chỉ muốn làm các tác vụ kiểu con người. Người ta nghiên cứu bộ não và nói rằng, hệ thị giác của con người có lẽ, tôi không rõ, có bốn hoặc năm tầng.
Each layer actually has, well, four or five sheets. Then each sheet might have six layers in it. So then maybe you say, well, 24 should be enough.
Mỗi tầng thực ra có bốn hoặc năm tấm. Rồi mỗi tấm có thể có sáu lớp. Vậy có lẽ bạn nói, 24 là đủ rồi.
But we don't know exactly how it's wired, and it's wired a lot more randomly than the typical networks people set up in artificial networks.
Nhưng ta không biết chính xác nó được nối dây thế nào, và nó được nối ngẫu nhiên hơn nhiều so với các mạng thông thường mà người ta dựng trong mạng nhân tạo.
So in practice, the deeper networks than just 24 layers have worked better than restricting to 24.
Nên trong thực tế, các mạng sâu hơn 24 lớp hoạt động tốt hơn là giới hạn ở 24.
Initially, people were worried about, if the network's really, really big, maybe you won't generalize as well. And we'll touch upon that a little bit when we do a learning theory.
Ban đầu, người ta lo ngại rằng nếu mạng quá lớn, có thể nó sẽ khái quát hóa kém hơn. Ta sẽ nói sơ qua về điều này khi học về lý thuyết học.
But the high level — it is true. The bigger your network, the more you can represent.
Nhưng ở mức tổng quát — điều đó đúng. Mạng càng lớn thì càng biểu diễn được nhiều.
And in principle, you might over fit more badly, but it turns out that if you are careful about early stopping, that ends up not being an issue in practice.
Về nguyên tắc, bạn có thể bị quá khớp nặng hơn, nhưng hóa ra nếu bạn cẩn thận dừng sớm (early stopping), thì trong thực tế đó không phải là vấn đề.
And so even though your network is big, you're not using all the capacity of your network because once the held-out data accuracy starts decreasing, you stop.
Nên dù mạng của bạn lớn, bạn không dùng hết dung lượng của mạng vì một khi độ chính xác trên dữ liệu held-out bắt đầu giảm, bạn dừng lại.
And so you don't get into the outskirts of the funky functions that you could learn in principle with this gigantic network. You stay far away from that. You stop long before that.
Và như vậy bạn không đi vào vùng rìa của những hàm kỳ quặc mà về nguyên tắc bạn có thể học được với mạng khổng lồ này. Bạn tránh xa vùng đó. Bạn dừng từ rất lâu trước đó.
And so in practice, actually people have often found that the bigger the network, the easier to train because somehow the optimization landscape becomes simpler.
Vì vậy trong thực tế, người ta thường thấy mạng càng lớn thì càng dễ huấn luyện, vì bằng cách nào đó bề mặt tối ưu hóa trở nên đơn giản hơn.
One way to think of it is that if you optimize directly over all possible functions in the world, then you could maybe very easily steer onto the correct one, whereas if you're restricted and you can only have certain types of functions, then you've got to find your path from one to the other, which is more difficult to do.
Một cách nghĩ là nếu bạn tối ưu trực tiếp trên mọi hàm có thể có trên đời, thì có lẽ bạn dễ dàng hướng thẳng tới hàm đúng, còn nếu bạn bị hạn chế và chỉ có một số loại hàm nhất định, thì bạn phải tìm đường đi từ hàm này sang hàm kia, và việc đó khó hơn.
Another way to think of it is that if you have a really big network and it's all randomly initialized, and it's really, really big, like infinitely big, then some subnetwork of that network is already the thing that you want.
Một cách nghĩ khác là nếu bạn có một mạng thật lớn và được khởi tạo ngẫu nhiên hoàn toàn, mà lớn đến mức vô hạn, thì sẽ có một mạng con nào đó của mạng này đã chính là thứ bạn muốn.
And if that's already present — nobody has that big a network, but if that's already present, then you can imagine when you run the back propagation which says in which direction [INAUDIBLE] parameters, it will just say, oh, just pay attention to this subnetwork.
Và nếu nó đã có sẵn — không ai có mạng lớn đến thế, nhưng nếu nó đã có sẵn, thì bạn có thể hình dung khi chạy lan truyền ngược, thứ cho biết nên đi theo hướng nào [KHÔNG NGHE RÕ] tham số, nó sẽ nói: à, cứ chú ý vào mạng con này.
And that'll make the biggest improvement, and you'll learn very quickly.
Và điều đó sẽ cải thiện nhiều nhất, và bạn sẽ học rất nhanh.
Of course, there's all caveats to that and you need to worry about over fitting, but in general, the optimization landscape is seemingly better conditioned with bigger networks.
Tất nhiên có nhiều lưu ý với điều này và bạn cần lo về quá khớp, nhưng nhìn chung, bề mặt tối ưu hóa có vẻ được điều kiện hóa tốt hơn với mạng lớn hơn.
There are some tricks you have to play with initialization. So because of the non-linearities, if you have a sigmoid, it's flat and flat and then transitions.
Có một số mẹo cần dùng với việc khởi tạo. Do các hàm phi tuyến, nếu bạn có sigmoid, nó phẳng, phẳng rồi mới chuyển tiếp.
You only get single on the transition, not on the flats. Same for the [INAUDIBLE]. You don't get signal on the flats, only in a transition, for the value only on the steep part.
Bạn chỉ nhận được tín hiệu ở đoạn chuyển tiếp, không phải ở đoạn phẳng. Tương tự với [KHÔNG NGHE RÕ]. Bạn không có tín hiệu ở đoạn phẳng, chỉ ở đoạn chuyển tiếp, với hàm value thì chỉ ở phần dốc.
Now, you might wonder, well, should we then just keep it all just linear? That doesn't work either because we need a non-linearity in there.
Bạn có thể thắc mắc, vậy sao ta không giữ mọi thứ tuyến tính? Cách đó cũng không được vì ta cần tính phi tuyến trong đó.
And it's OK if, let's say, 90% of the time you're in the flat part, but maybe 10% of the time you should be in the steep part so you get some signal for that neuron, what it should be doing.
Và không sao nếu, giả sử, 90% thời gian bạn ở phần phẳng, nhưng 10% thời gian bạn nên ở phần dốc để nhận được tín hiệu cho nơ-ron đó về việc nó nên làm gì.
And so there's initialization tricks and re-normalization of the data tricks that ensure that usually you're — for most neurons, ideally all neurons, you're at least a certain fraction of the time in the regime where you get signal and your optimization will work well.
Vì vậy có các mẹo khởi tạo và mẹo chuẩn hóa lại dữ liệu để đảm bảo rằng thường thì — với hầu hết nơ-ron, lý tưởng là mọi nơ-ron, ít nhất một tỷ lệ thời gian nhất định chúng nằm trong vùng mà bạn nhận được tín hiệu và tối ưu hóa chạy tốt.
Was there a question there?
Ở đó có câu hỏi không?
STUDENT
Yeah. My question is how do we [INAUDIBLE]??
Vâng. Câu hỏi của em là làm sao ta [KHÔNG NGHE RÕ]?
PROFESSOR
Yeah. So that goes back to what we just talked about, the slight variation.
Vâng. Điều đó quay lại với những gì ta vừa nói, về biến thể nhỏ đó.
So the question here is, if your network is really, really deep and — what happens when you compute the derivative, you get a — we saw the chain rule for derivatives shows that derivative of a function of a function of a function is a product of derivatives.
Câu hỏi ở đây là, nếu mạng của bạn rất, rất sâu và — điều xảy ra khi tính đạo hàm là, bạn có — ta đã thấy quy tắc chuỗi cho đạo hàm cho thấy đạo hàm của hàm của hàm của một hàm là tích của các đạo hàm.
And so if you have many, many layers, then that means you'll end up with a product of many, many derivatives multiplied together to get a derivative with respect to especially the weights early on.
Nên nếu có rất nhiều lớp, thì bạn sẽ có một tích của rất nhiều đạo hàm nhân với nhau để ra đạo hàm theo các trọng số, đặc biệt là ở các lớp đầu .
That product, if all the numbers are above one, will explode to infinity if your network is deeper and deeper. If they're all below one, it'll start going towards 0 easily.
Tích đó, nếu mọi số đều lớn hơn một, sẽ nổ lên vô cùng khi mạng càng sâu. Nếu chúng đều nhỏ hơn một, nó sẽ dễ dàng tiến về 0.
And so that's one of the tricky parts. The deeper your network, the more relevant it becomes to play tricks that help your optimization.
Đó là một trong những phần khó. Mạng càng sâu thì càng cần dùng các mẹo giúp tối ưu hóa.
So one standard trick is to essentially, rather than having by default just what the network does, as you set it up, you have an identity function passing everything on, and the network is just an adjustment to the identity function.
Một mẹo chuẩn là, thay vì để mạng mặc định làm gì thì làm khi bạn dựng nó, bạn có một hàm đồng nhất truyền mọi thứ đi tiếp, và mạng chỉ là một sự điều chỉnh cho hàm đồng nhất đó.
And that way you get centered around the identity, which is a good place to be centered around, and you have less to worry about in terms of propagation going up or down too quickly.
Như vậy bạn được căn quanh hàm đồng nhất, mà là một điểm xuất phát tốt để làm tâm, và bạn đỡ phải lo hơn về việc lan truyền đi lên hay đi xuống quá nhanh.
In really deep networks that are, let's say, recurrent, like HMMs where you can keep running them forever, they never really stop, people often just cut it off.
Với những mạng thật sâu, giả sử là mạng hồi quy, như HMM mà bạn có thể chạy mãi mãi, chúng không bao giờ dừng, người ta thường chỉ cắt bớt.
They'll say, define 30 for this weight here. I'm only going to start back propagating from maybe 20 in the future. And back propagate over 20 and not anything further.
Họ sẽ nói, đặt 30 cho trọng số này. Tôi chỉ bắt đầu lan truyền ngược từ khoảng 20 bước phía sau trong tương lai. Và lan truyền ngược qua 20 bước, không đi xa hơn.
You can imagine doing some discounting like we do in reinforcement learning, different things you can do to try to attenuate the effect of what comes earlier. Yes?
Bạn có thể hình dung việc chiết khấu như trong học tăng cường, có nhiều cách khác nhau để làm giảm ảnh hưởng của những gì xảy ra sớm hơn. Bạn hỏi đi?
STUDENT
Quick question. You mentioned that [INAUDIBLE] data [INAUDIBLE].. Is it possible that [INAUDIBLE]?
Em hỏi nhanh một câu. Thầy có nói rằng dữ liệu [KHÔNG NGHE RÕ]. Liệu có thể [KHÔNG NGHE RÕ] không ạ?
PROFESSOR
Yeah, it's definitely possible. That would be a little quirky.
Vâng, hoàn toàn có thể. Chuyện đó hơi kỳ lạ.
But if your held-out data set is on the smaller side, if you have some kind of funny random seed effect where that happens, it's definitely possible.
Nhưng nếu tập held-out khá nhỏ, nếu có hiệu ứng ngẫu nhiên kỳ quặc nào đó từ random seed khiến điều đó xảy ra thì hoàn toàn có thể.
So often, you would actually not literally stop when it starts going down. You'd run for quite a while and then go back and see where it was highest.
Vì vậy thường bạn sẽ không dừng ngay khi nó bắt đầu giảm. Bạn chạy khá lâu rồi quay lại xem nó cao nhất ở đâu.
And at some point, you'll see it doesn't make sense to keep running because it's been going down for such a long time it's very unlikely going to come back up.
Và đến một lúc nào đó, bạn thấy chạy tiếp là vô nghĩa vì nó đã giảm quá lâu nên rất khó có khả năng tăng trở lại.
That's it for neural nets. Let's think a little bit about learning theory. So one reference frame you could potentially have is a scientific discovery.
Vậy là hết phần mạng nơ-ron. Giờ ta nghĩ một chút về lý thuyết học. Một khung tham chiếu mà bạn có thể dùng là khám phá khoa học.
Let's say you do physics. We never directly measure the laws of physics. The equations are not — we cannot go measure the equations.
Giả sử bạn làm vật lý. Ta không bao giờ đo trực tiếp các định luật vật lý. Các phương trình thì không, ta không thể đi đo các phương trình.
We just measure data points, and those data points then allow us to conclude, well, maybe this equation is a really good equation to use to predict what future measurements will be like.
Ta chỉ đo các điểm dữ liệu, và những điểm dữ liệu đó cho phép ta kết luận rằng có lẽ phương trình này rất tốt để dự đoán các phép đo trong tương lai sẽ thế nào.
And so that's the analogy that we're going to be thinking about here, is, OK, well, how can we think about this? And are we really doing the right thing?
Và đó là phép tương tự mà ta sẽ nghĩ đến ở đây: ta có thể nhìn nhận chuyện này thế nào? Và ta có thực sự làm đúng không?
We get some data points. And are we getting out a hypothesis about how this data set works, or in science how physics might work, that might have a chance of being correct?
Ta có một số điểm dữ liệu. Và ta có thu được một giả thuyết về cách tập dữ liệu này vận hành, hay trong khoa học là vật lý có thể vận hành ra sao, mà có cơ hội đúng không?
So formalizing learning a little bit, in the simplest form, what we're doing is we learn a function from examples.
Hình thức hóa việc học một chút, ở dạng đơn giản nhất, việc ta làm là học một hàm từ các ví dụ.
So we have a target function g, which we try to learn from pairs. x g of x. g of x we have often called y, the label.
Ta có hàm mục tiêu g, và ta cố học từ các cặp x, g của x. g của x ta thường gọi là y, nhãn.
And then x could be an email, and g of x is spam or ham. x could be a house, and g of x could be the selling price.
x có thể là một email, và g của x là spam hoặc ham. x có thể là một ngôi nhà, và g của x là giá bán.
So that's a standard machine learning problem we've been looking at for a few lectures now. We're trying to find this target function, but we never have direct access to the target function.
Đó là bài toán machine learning chuẩn mà ta đã xem qua vài bài giảng nay. Ta đang cố tìm hàm mục tiêu này, nhưng ta không bao giờ truy cập trực tiếp được hàm mục tiêu.
Nobody allows us to look at g. But what we get to see is samples. The problem we're trying to solve is we want to somehow find g or something close to g.
Không ai cho ta xem g. Cái ta được thấy là các mẫu. Bài toán ta cần giải là bằng cách nào đó tìm g hoặc thứ gì gần với g.
Since we don't know g, we might not be able to know what representation we should use to be able to find it.
Vì không biết g, có thể ta không biết nên dùng biểu diễn nào để tìm ra nó.
So maybe we have a hypothesis space shown by a blue set here. And we say, within this hypothesis space, those are all the functions we're willing to consider.
Nên có thể ta có một không gian giả thuyết, là tập màu xanh ở đây. Và ta nói, trong không gian giả thuyết này, đó là mọi hàm ta sẵn lòng xem xét.
For example, we have a three-layer network. Each layer has 10 units. All functions representable by any choice of weights in this three-layer networks with 10 units in every layer.
Ví dụ, ta có mạng ba lớp. Mỗi lớp có 10 đơn vị. Mọi hàm biểu diễn được bằng bất kỳ cách chọn trọng số nào trong mạng ba lớp này với 10 đơn vị mỗi lớp.
All those functions that are possible to represent are our hypothesis space. The real function g might be outside of that.
Tất cả những hàm có thể biểu diễn được đó là không gian giả thuyết của ta. Hàm thật g có thể nằm ngoài đó.
And then we're trying to find h's as close as possible to the real function g. And what we have to try to find that h is the training examples.
Và ta cố tìm h càng gần hàm thật g càng tốt. Và thứ ta có để tìm h là các ví dụ huấn luyện.
And this drawing here then, we'd hope we find this h over here.
Còn trong hình này, ta hy vọng tìm được h ở đằng này.
We've most looked in the context of classification, where there is discrete outputs of the function, but it could also be with real numbers. Same ideas apply.
Phần lớn ta xét trong bối cảnh phân loại, khi đầu ra của hàm là rời rạc, nhưng cũng có thể là số thực. Các ý tưởng vẫn áp dụng.
So how do the ideas fit in that we've covered so far?
Vậy các ý tưởng ta đã học khớp vào đây thế nào?
I've alluded to the neural network version, where hypothesis space contains all the functions from input to output you can represent with your choice of network. How about naive Bayes?
Tôi đã nhắc đến phiên bản mạng nơ-ron, trong đó không gian giả thuyết chứa mọi hàm từ đầu vào đến đầu ra mà bạn biểu diễn được với cách chọn mạng của mình. Còn naive Bayes thì sao?
How does that fit in? Well, naive Bayes, we train a Bayesian network, and then we make a decision to go from features to a label y prediction.
Nó khớp vào đâu? Với naive Bayes, ta huấn luyện một mạng Bayes, rồi ra quyết định để đi từ các đặc trưng đến dự đoán nhãn y. dự đoán.
So what would be the hypothesis space for naive Bayes?
Vậy không gian giả thuyết của naive Bayes là gì?
It would be something along the lines of I'm willing to consider any network where there's a y here and then maybe feature 1, feature 2, feature 3.
Đại loại là tôi sẵn lòng xem xét mọi mạng có y ở đây rồi có thể là đặc trưng 1, đặc trưng 2, đặc trưng 3.
Now, I'm willing to consider any hypothesis that is of the form p of y given some feature values under my choice of the — we'll call it theta, then.
Tôi sẵn lòng xem xét mọi giả thuyết có dạng p của y cho trước một số giá trị đặc trưng dưới cách chọn của tôi về ta gọi nó là theta.
Theta, which is the parameters and is Bayes net. If we chose a different Bayes net structure, that hypothesis space could become larger or smaller.
Theta, là các tham số và là mạng Bayes. Nếu ta chọn cấu trúc mạng Bayes khác, không gian giả thuyết đó có thể lớn hơn hoặc nhỏ hơn.
For example, if we added additional connections, maybe here and here and here, now we have a full Bayes net fully connected.
Ví dụ, nếu ta thêm các kết nối, có thể ở đây, đây và đây, giờ ta có một mạng Bayes kết nối đầy đủ.
So now the hypothesis space will be maximal for anything we can represent with a Bayes net over those variables and bigger than what we can represent with just the naive Bayes network.
Lúc đó không gian giả thuyết sẽ là lớn nhất cho mọi thứ biểu diễn được bằng mạng Bayes trên các biến đó, và lớn hơn những gì ta biểu diễn được chỉ với mạng naive Bayes.
You can imagine that learning theory is essentially about the notion of, OK, just using the biggest hypothesis space and using the best fit ti the training data is not actually the best thing to do because then things would be simple.
Bạn có thể hình dung lý thuyết học về cơ bản xoay quanh ý rằng, chỉ dùng không gian giả thuyết lớn nhất và khớp tốt nhất với dữ liệu huấn luyện thực ra không phải điều tốt nhất nên làm, vì khi đó mọi thứ sẽ đơn giản.
You need to be a little more careful than that. And so just fully connecting the Bayes net might not be the right thing to do.
Ta cần cẩn thận hơn thế một chút. Vì vậy, chỉ việc nối đầy đủ mạng Bayes có thể không phải là điều nên làm.
Even though it grows your hypothesis space, you might not find a better result in terms of predictive capabilities after learning. So for example, let's say we're doing regression.
Dù nó làm không gian giả thuyết lớn hơn, bạn có thể không tìm được kết quả tốt hơn về khả năng dự đoán sau khi học. Ví dụ, giả sử ta đang làm hồi quy.
If we have this set of points fitting a line, yeah, it's not perfect, that's for sure — it's missing a bunch of points — but maybe that's OK.
Nếu có tập điểm này và khớp một đường thẳng, đúng là nó không hoàn hảo, chắc chắn rồi, nó bỏ sót khá nhiều điểm, nhưng có thể vậy cũng ổn.
It has good predictive capability for future things we might want to do. Maybe this is a little better. Maybe it's worse. Hard to say.
Nó dự đoán tốt cho những trường hợp sau này mà ta muốn làm. Có thể cái này tốt hơn một chút. Có thể nó tệ hơn. Khó nói.
Ideally, we'd have kept aside some hold-out data and we then compare. Is the parabola or the line better on the hold-out data? And maybe we'd go with whichever one is doing better.
Lý tưởng nhất là ta giữ riêng một ít dữ liệu hold-out rồi so sánh. Parabol hay đường thẳng tốt hơn trên dữ liệu hold-out? Và ta chọn cái nào cho kết quả tốt hơn.
This, probably worse. It would be very unlikely that this would be the way to go for this data set, but it does hit more of the points more closely.
Cái này, có lẽ tệ hơn. Rất khó có khả năng đây là hướng đi đúng cho tập dữ liệu này, nhưng nó đi qua nhiều điểm hơn và sát hơn.
And so what this shows is that choosing from a wider hypothesis space, something that then fits more closely your data, might not be the thing you want to do.
Điều này cho thấy việc chọn từ một không gian giả thuyết rộng hơn, thứ khớp dữ liệu sát hơn, có thể không phải là điều bạn muốn. là điều bạn nên làm.
This one, even worse. So there is a trade-off here between consistency and simplicity. Usually, simple functions we expect will generalize to new data better.
Cái này còn tệ hơn. Vì vậy ở đây có sự đánh đổi giữa tính nhất quán và sự đơn giản. Thường ta kỳ vọng các hàm đơn giản sẽ tổng quát hóa tốt hơn cho dữ liệu mới.
And consistency — well, things that are consistent with the training data, that's a good thing of course.
Còn tính nhất quán, tức là khớp với dữ liệu huấn luyện, dĩ nhiên là điều tốt.
But often, achieving both at the same time is hard to do, and you need to make a trade-off. A standard trade-off people try to make is called Occam's Razor.
Nhưng thường khó đạt cả hai cùng lúc, và bạn phải đánh đổi. Một cách đánh đổi tiêu chuẩn mà người ta hay dùng gọi là Occam's Razor.
What it says is that try to find the simplest explanation of your data.
Nó nói rằng hãy cố tìm lời giải thích đơn giản nhất cho dữ liệu.
So if a line fits your data well, well, then a line might be better bit of a parabola, which might be better than a high order polynomial.
Nếu một đường thẳng khớp tốt với dữ liệu, thì đường thẳng có thể tốt hơn parabol, và parabol có thể tốt hơn đa thức bậc cao.
Of course, a little subtle, because who says a line is simpler than a parabola? And how do you even quantify the notion that a line is simpler than on a parabola?
Dĩ nhiên điều này hơi tinh tế, vì ai bảo đường thẳng đơn giản hơn parabol? Và làm sao định lượng được ý niệm đường thẳng đơn giản hơn parabol?
They both are in some sense simple. That often ties into how many parameters you get to learn. A parabola has three coefficients. A line only has two coefficients.
Theo một nghĩa nào đó cả hai đều đơn giản. Điều đó thường liên quan đến số tham số bạn phải học. Parabol có ba hệ số. Đường thẳng chỉ có hai hệ số.
So a parabola has a bigger hypothesis space, and if you choose from a bigger hypothesis space to find your solution, then it's more likely you're over fitting than if you choose from a smaller hypothesis space.
Vậy parabol có không gian giả thuyết lớn hơn, và nếu bạn chọn lời giải từ không gian giả thuyết lớn hơn, thì khả năng quá khớp cao hơn so với khi chọn từ không gian giả thuyết nhỏ hơn.
So that's a trade-off involved, bias versus variance. If you take too small a hypothesis space, you have something called bias. It means that you can't even match the training data.
Đó là sự đánh đổi giữa bias và variance. Nếu bạn lấy không gian giả thuyết quá nhỏ, bạn sẽ có cái gọi là bias. Nghĩa là bạn thậm chí không khớp nổi dữ liệu huấn luyện.
You are guaranteed to be off because you're not rich enough to hit the training data points even. But you might have low variance.
Chắc chắn bạn sẽ bị lệch vì mô hình không đủ phong phú để chạm tới các điểm dữ liệu huấn luyện. Nhưng bạn có thể có variance thấp.
Variance here refers to the fact that, if you look at how well you did on the training data, it's likely you're going to do about equally well on future data because your hypothesis space was so small, and so it's likely that whatever you picked from that small space, whatever performance it has, it'll be representative of performance it'll have in the future.
Variance ở đây nghĩa là, nếu bạn xem mình làm tốt đến đâu trên dữ liệu huấn luyện, thì nhiều khả năng bạn sẽ làm tốt xấp xỉ trên dữ liệu tương lai, vì không gian giả thuyết quá nhỏ, nên rất có thể bất kể bạn chọn gì từ không gian nhỏ đó, hiệu năng của nó cũng đại diện cho hiệu năng nó sẽ có trong tương lai.
Now, if you take something very complex, let's say massive, biggest neural network ever to fit your data, then your bias will likely be very small. It'll perfectly fit to your data.
Còn nếu bạn lấy thứ rất phức tạp, chẳng hạn mạng nơ-ron khổng lồ nhất từng có để khớp dữ liệu, thì bias nhiều khả năng sẽ rất nhỏ. Nó sẽ khớp hoàn hảo với dữ liệu.
You might have even zero bias. But what you expect could happen on some other data will have very high variance because you chose from such a massive hypothesis space.
Thậm chí bias có thể bằng không. Nhưng điều bạn có thể kỳ vọng trên dữ liệu khác sẽ có variance rất cao vì bạn chọn từ một không gian giả thuyết khổng lồ.
And you chose the one that looks best in your training so you really picked a very particular one to get it to fit your training data.
Và bạn chọn cái trông tốt nhất trên tập huấn luyện, nên bạn thực sự chọn một cái rất đặc thù để nó khớp dữ liệu huấn luyện.
That might have some weird quirks like we saw here on other data.
Nó có thể có vài điểm kỳ quặc như ta đã thấy ở đây trên dữ liệu khác.
So most algorithms tend to favor consistency or tend to try to drive bias as low as possible. Why is that?
Hầu hết thuật toán có xu hướng ưu tiên tính nhất quán hay cố đưa bias xuống thấp nhất có thể. Tại sao vậy?
Well, usually the way that we define the algorithms essentially drive training error to 0.
Thường thì cách ta định nghĩa các thuật toán về bản chất là đưa lỗi huấn luyện về 0.
So essentially, just asking it to do that, the way we define the algorithms, we're trying to drive error to 0.
Về cơ bản, chỉ bằng việc yêu cầu như vậy, theo cách ta định nghĩa thuật toán, ta đang cố đưa lỗi về 0.
So to make sure we don't have too much variance, we need to operationalize this Occam's Razor or this notion of keeping things simple.
Vì vậy để không bị variance quá lớn, ta cần hiện thực hóa Occam's Razor, hay ý niệm giữ mọi thứ đơn giản.
And this will be a little different for every learning approach that you consider, and we'll see something yet different with decision trees in the second half of this lecture.
Điều này sẽ hơi khác với mỗi cách tiếp cận học mà bạn xét, và ta sẽ thấy một cách khác nữa với cây quyết định ở nửa sau bài giảng.
But it could mean two things.
Nhưng nó có thể có hai nghĩa.
Reducing the hypothesis space, that's a hard decision. You say, these are the only functions you're allowed to learn when you're fitting to this data.
Thu hẹp không gian giả thuyết, đó là một quyết định cứng. Bạn nói, đây là những hàm duy nhất bạn được phép học khi khớp dữ liệu này.
And if you make that space small enough, then it's less likely you're over-fitting.
Và nếu bạn làm không gian đó đủ nhỏ, thì ít có khả năng bị quá khớp hơn.
So in naive Bayes, this was done by, well, a lot of edges were missing from being fully capable of representing any distribution.
Trong naive Bayes, điều này được thực hiện bằng cách bỏ đi nhiều cạnh so với mạng nối đầy đủ có thể biểu diễn mọi phân phối.
Those are assumptions you make that reduce your hypothesis space, hence favor simplicity.
Đó là những giả định bạn đặt ra để thu hẹp không gian giả thuyết, nhờ đó ưu tiên sự đơn giản.
Now, when you train with maximum likelihood, you'll still try to favor accuracy, but the hypothesis space is too small possibly to over-fit.
Khi huấn luyện bằng maximum likelihood, bạn vẫn cố ưu tiên độ chính xác, nhưng không gian giả thuyết có thể quá nhỏ để quá khớp.
Another thing people might do is reduce the number of features, because the more features you have, the higher chance you might over-fit. The polynomial fitting essentially is an expansion of features.
Một cách khác là giảm số lượng đặc trưng, vì bạn có càng nhiều đặc trưng, khả năng quá khớp càng cao. Việc khớp đa thức về cơ bản là một sự mở rộng các đặc trưng.
A line has as a feature the bias term 1 and just the x. A parabola has as features 1, x, and x squared.
Một đường thẳng có đặc trưng là số hạng bias 1 và chỉ có x. Một parabol có các đặc trưng 1, x và x bình phương.
A cubic polynomial has as features 1, x, x squared, x to the third, and so forth. The more features, the more chance of over-fitting.
Một đa thức bậc ba có các đặc trưng 1, x, x bình phương, x mũ ba, và cứ tiếp tục như vậy. Càng nhiều đặc trưng thì càng dễ bị quá khớp.
You might also want to use other structural imitations we will look at in decision trees or in neural networks.
Bạn cũng có thể muốn dùng các giới hạn về cấu trúc khác mà ta sẽ xem trong cây quyết định hoặc mạng nơ-ron.
You might say, I want my network only to be this big, not bigger than that. And that will limit your hypothesis space. What's the other thing you can do?
Bạn có thể nói: tôi muốn mạng của mình chỉ lớn đến mức này, không lớn hơn mức đó. Và điều đó sẽ giới hạn không gian giả thuyết của bạn. Còn cách nào khác nữa?
In regularization, you have in principle a large hypothesis space, but you keep away from the weird parts of that hypothesis space in some sense, the outskirts where you think it's more likely you're over-fitting.
Với regularization, về nguyên tắc bạn có một không gian giả thuyết lớn, nhưng bạn tránh xa những phần kỳ quặc của không gian giả thuyết đó, theo một nghĩa nào đó, tức vùng rìa, nơi bạn nghĩ khả năng bị quá khớp cao hơn.
So what's an example? In naive Bayes, we did smoothing of the counts because we thought having 0 parabolas and parabolas of 1 are not very likely to capture.
Vậy ví dụ là gì? Trong naive Bayes, ta làm trơn các số đếm vì ta cho rằng việc có 0 parabol và parabol bằng 1 thì không có nhiều khả năng nắm bắt được dữ liệu.
That's in the outskirts of the hypothesis space, and we want to avoid that.
Đó là vùng rìa của không gian giả thuyết, và ta muốn tránh nó.
Today we'll see something about pruning with decision trees. In neural nets, you essentially get the last thing here, you're training.
Hôm nay ta sẽ thấy cắt tỉa với cây quyết định. Với mạng nơ-ron, về cơ bản ta có điều cuối cùng ở đây, đó là quá trình huấn luyện.
If you have a gigantic neural net, you could get anywhere, in principle, if you keep training forever.
Nếu bạn có một mạng nơ-ron khổng lồ, về nguyên tắc bạn có thể đến bất cứ đâu, nếu bạn huấn luyện mãi mãi.
But if you stop training after, let's say, 100 updates, you have not had the chance to hit that many points of the hypothesis space you on principle would get to with infinitely many updates.
Nhưng nếu bạn dừng huấn luyện sau, chẳng hạn, 100 lần cập nhật, bạn chưa có cơ hội chạm tới nhiều điểm trong không gian giả thuyết mà về nguyên tắc bạn sẽ đến được với vô hạn lần cập nhật.
And so your hypothesis space becomes restricted by the number of updates you allow, which you could either set by hand, only this many updates, or often you do, of course, adaptively.
Và vì vậy không gian giả thuyết của bạn bị hạn chế bởi số lần cập nhật mà bạn cho phép, số này bạn có thể đặt thủ công, chỉ chừng này lần cập nhật, hoặc thường thì tất nhiên là làm thích nghi.
Whenever your held-out accuracy starts going down, you say, OK, at this point I'm probably starting hitting parts of the space that I should not allow anymore, and you effectively keep your hypothesis space small by stopping early.
Bất cứ khi nào độ chính xác trên tập giữ lại bắt đầu giảm, bạn nói: được rồi, đến đây có lẽ tôi đang bắt đầu chạm vào những phần của không gian mà tôi không nên cho phép nữa, và bạn thực chất giữ không gian giả thuyết nhỏ bằng cách dừng sớm.
Any questions about these ideas? So current is short, but want to get the main intuitions across.
Có câu hỏi nào về các ý tưởng này không? Phần này ngắn, nhưng tôi muốn truyền đạt các ý chính.
OK. Let's take a break here, and then in the second half let's look at decision trees.
Được rồi. Ta nghỉ giải lao ở đây, rồi nửa sau ta sẽ xem cây quyết định.
STUDENT
Excuse me, Professor?
Thưa thầy, cho em hỏi?
PROFESSOR
All right. Let's restart. Any questions about the first half?
Được rồi. Ta bắt đầu lại nhé. Có câu hỏi nào về nửa đầu không?
OK. Let's look at decision trees then. Actually, let's take one step back for a moment. So decision trees are a alternative to things we've already covered.
Được rồi. Vậy ta xem cây quyết định. Thật ra, ta lùi lại một bước một chút. Cây quyết định là một phương án thay thế cho những thứ ta đã học.
We've covered naive Bayes. We've covered perceptron. We've covered logistic regression. We've covered neural networks.
Ta đã học naive Bayes. Ta đã học perceptron. Ta đã học hồi quy logistic. Ta đã học mạng nơ-ron.
Now we'll cover decision trees.
Giờ ta sẽ học cây quyết định.
So it's one of several methods available to us to do classification or potentially regression, though we don't really cover regression in 188.
Đây là một trong nhiều phương pháp ta có để phân loại hoặc có thể là hồi quy, dù trong CS 188 ta không thực sự học hồi quy.
OK. So let's say we want to solve this problem here. What is this problem?
Được rồi. Giả sử ta muốn giải bài toán này. Bài toán này là gì?
We're trying to build a predictor for whether somebody is willing to wait to get seated or they will just go somewhere else at a restaurant.
Ta đang xây dựng một bộ dự đoán xem ai đó có sẵn lòng chờ để được xếp chỗ hay họ sẽ đi chỗ khác, tại một nhà hàng.
So there is an example with a first patron, second patron, and so forth. And then there is whether they waited or didn't wait to get seated.
Có ví dụ với khách thứ nhất, khách thứ hai, và cứ thế. Rồi có việc họ đã chờ hay không chờ để được xếp chỗ.
And then there's a bunch of attributes that we have. Is there an alternative option nearby? Is there a bar at the restaurant they can hang out at while waiting?
Và có một loạt thuộc tính mà ta có. Gần đó có lựa chọn thay thế không? Nhà hàng có quầy bar để họ ngồi chơi trong lúc chờ không?
Is it Friday or Saturday? Is it a hungry patron or not? Is it a restaurant that nobody's in there and you're made to wait?
Có phải thứ Sáu hoặc thứ Bảy không? Khách có đang đói không? Có phải nhà hàng mà không có ai bên trong mà bạn vẫn bị bắt chờ không?
You might not want to wait if even if nobody else is there they're not going to let you in versus when there is some people there or it's completely full.
Bạn có thể không muốn chờ nếu dù không có ai khác ở đó họ cũng không cho bạn vào, so với khi có một ít người hoặc nhà hàng hoàn toàn đầy.
Price might matter. Whether it's raining or not. Whether they had a reservation or not. The type of restaurant.
Giá cả có thể quan trọng. Trời có mưa hay không. Họ có đặt chỗ trước hay không. Loại nhà hàng.
And maybe also what you say. You say, well, the estimated wait time is 0 to 10 minutes might affect whether they wait or not.
Và có thể cả điều bạn được báo. Bạn nói, thời gian chờ ước tính là 0 đến 10 phút có thể ảnh hưởng đến việc họ chờ hay không.
So you could imagine that you collect a bunch of data.
Vậy bạn có thể hình dung là bạn thu thập một loạt dữ liệu.
This happens to be your relatively small data set that fits on a slide with 12 samples of whether people waited or not and the attributes in that situation.
Đây là tập dữ liệu khá nhỏ vừa trong một slide, với 12 mẫu về việc mọi người có chờ hay không và các thuộc tính trong tình huống đó.
So in principle, you could either train naive Bayes or we could train a perceptron or we could train logistic aggressively.
Về nguyên tắc, ta có thể huấn luyện naive Bayes hoặc huấn luyện perceptron hoặc huấn luyện hồi quy logistic.
We could train a neural network to try to learn the mapping from attributes to target value, the label. But now we'll use this as a running example to explain decision trees.
Ta có thể huấn luyện một mạng nơ-ron để thử học ánh xạ từ các thuộc tính sang giá trị đích, tức nhãn. Nhưng giờ ta sẽ dùng nó làm ví dụ xuyên suốt để giải thích cây quyết định.
And in the process, we'll also touch a bit on learning theory and also information theory.
Và trong quá trình đó, ta cũng sẽ đụng một chút đến lý thuyết học và cả lý thuyết thông tin.
What is a decision tree look like? Well, it's something like this. It's a lot like maybe the way you might write a program by hand to decide what a pattern is in some data.
Một cây quyết định trông như thế nào? Nó trông đại loại như thế này. Nó khá giống cách bạn có thể viết một chương trình thủ công để quyết định quy luật trong dữ liệu là gì.
You have a if statement. Based on what value patrons take on, non, some, or full, you go down a branch.
Bạn có một câu lệnh if. Tùy giá trị của patrons là none, some hay full, bạn đi xuống một nhánh.
Then it seems like when there is no patrons and somebody has to wait, they never wait in this decision tree. Just not taking that for an answer.
Rồi có vẻ như khi không có khách và ai đó phải chờ, họ không bao giờ chờ trong cây quyết định này. Họ không chấp nhận câu trả lời đó.
Then some, it seems like, people were always waiting according to this decision tree, the way it describes it.
Còn với some, có vẻ như mọi người luôn chờ theo cây quyết định này, theo cách cây quyết định này mô tả.
And then when the restaurant is full, it's not easy to say whether people will wait or not. You need to look at more attributes. And it might depend then on the wait estimate.
Còn khi nhà hàng đã đầy, thì không dễ nói người ta có chờ hay không. Bạn cần xem thêm các thuộc tính khác. Và nó có thể phụ thuộc vào thời gian chờ ước tính.
After you know the wait estimate, then you might be able to predict pretty well they'll leave if it's more than an hour, they'll stay if it's less than 10 minutes.
Sau khi biết thời gian chờ ước tính, bạn có thể dự đoán khá tốt: họ sẽ bỏ đi nếu phải chờ hơn một giờ, họ sẽ ở lại nếu chờ dưới 10 phút.
If it's between 10 and 60 minutes, well, then there's other questions to be asked to be able to predict what might happen. And so that's how this tree works.
Nếu khoảng từ 10 đến 60 phút, thì còn có những câu hỏi khác cần đặt ra để dự đoán điều có thể xảy ra. Cây này hoạt động như vậy đó.
You can refine how many things you need to know before you come to your decision based on what you've found out so far.
Bạn có thể tinh chỉnh xem cần biết bao nhiêu thứ trước khi đưa ra quyết định, dựa trên những gì đã tìm ra cho đến lúc đó.
What this is representing is a function that for any vector of attribute values, this decision tree will tell you true or false is the decision.
Cái này biểu diễn một hàm: với bất kỳ vectơ giá trị thuộc tính nào, cây quyết định này sẽ cho bạn quyết định là true hay false.
In principle you can make them probabilistic too. You could have a leaf of a decision treat that says it's 50% true, 50% falls, or 70/30.
Về nguyên tắc, bạn cũng có thể làm chúng mang tính xác suất. Một lá của cây quyết định có thể ghi là 50% true, 50% false, hoặc 70/30.
But key here is that for any combination of attribute values, you can use that to traverse the tree to hit the leaf node, and the leaf node tells you a value.
Nhưng điểm mấu chốt là với mọi tổ hợp giá trị thuộc tính, bạn dùng nó để duyệt cây tới nút lá, và nút lá cho bạn một giá trị.
If this is really what's happening and if this is really how we believe people decide whether to wait or not, then this decision tree represents the true function.
Nếu đây thực sự là điều đang xảy ra và đúng là cách chúng ta tin người ta quyết định có chờ hay không, thì cây quyết định này biểu diễn hàm thật.
And if we allow any decision tree over these attributes, then our hypothesis space is big enough to capture this decision tree, and we can realize consistency with any data, any training data we get.
Và nếu cho phép mọi cây quyết định trên các thuộc tính này, thì không gian giả thuyết đủ lớn để chứa cây này, và ta có thể khớp nhất quán với mọi dữ liệu, mọi tập huấn luyện ta nhận được.
So let's think about how expressive these trees are. How about XOR function? Yes, a decision tree could represent a XOR function.
Hãy nghĩ xem các cây này biểu diễn được những gì. Còn hàm XOR thì sao? Có, cây quyết định biểu diễn được hàm XOR.
It's a nice example because it's something that a perceptron could not represent but a decision tree can. Here is the table representation, and here's the decision tree representation of a XOR.
Đây là ví dụ hay vì đó là thứ mà perceptron không biểu diễn được nhưng cây quyết định thì được. Đây là biểu diễn dạng bảng, và đây là biểu diễn XOR bằng cây quyết định.
The first bit is false. The second bit is false. Then overall answer is false. False and true is true.
Bit đầu là false. Bit thứ hai là false. Thì kết quả chung là false. False và true thì ra true.
And similarly on the other side. Now, what we did here is build a tree that is as big as the table. If our trees are as big as the tables, we don't gain anything.
Và tương tự ở nhánh bên kia. Ở đây ta đã xây một cây lớn bằng cái bảng. Nếu cây lớn bằng bảng thì ta chẳng được lợi gì.
Tabular representations tend to be notoriously bad, actually, for learning a pattern, because if you have a table representation, you allow for every possible hypothesis that could possibly exist.
Thật ra biểu diễn dạng bảng nổi tiếng là tệ cho việc học một mẫu, vì nếu bạn dùng bảng, bạn cho phép mọi giả thuyết có thể tồn tại.
Then it's less likely you generalize. So we'd like to find small trees that capture patterns in there.
Khi đó khả năng khái quát hóa thấp hơn. Vì vậy ta muốn tìm các cây nhỏ nắm bắt được mẫu trong dữ liệu.
So let's revisit this notion a little bit and compare it to perceptrons. Let's say we have the same problem again. What is the expressiveness of a perceptron over these features?
Hãy xem lại ý này một chút và so sánh với perceptron. Giả sử ta lại có cùng bài toán đó. Perceptron trên các đặc trưng này biểu diễn được gì?
Well, for a perceptron, every feature is either weighted positively or negatively. And so a feature either can [INAUDIBLE] positively or negatively, but there's no interaction between features.
Với perceptron, mỗi đặc trưng được gán trọng số dương hoặc âm. Nên một đặc trưng có thể [KHÔNG NGHE RÕ] theo hướng dương hoặc âm, nhưng không có tương tác giữa các đặc trưng.
Something like patrons equal full and wait equals 60, if that combined means one thing, maybe a positive, but otherwise, independently, they're a negative, a perception cannot capture that because independent contributions of each.
Ví dụ patrons bằng full và wait bằng 60, nếu kết hợp lại có một ý nghĩa, chẳng hạn dương, nhưng riêng lẻ thì đều âm, thì perceptron không nắm được, vì mỗi đặc trưng đóng góp độc lập.
Same for naive Bayes. Everything contributes independently. Neural network can combine things with multiple layers to contribute through combinations. Same thing for decision trees.
Naive Bayes cũng vậy. Mọi thứ đều đóng góp độc lập. Mạng nơ-ron có thể kết hợp các thứ qua nhiều tầng để đóng góp thông qua các tổ hợp. Cây quyết định cũng thế.
We can have combined feature values have one sign, maybe positive contribution, whereas each individual might have a negative contribution.
Tổ hợp các giá trị đặc trưng có thể mang một dấu, chẳng hạn đóng góp dương, trong khi từng đặc trưng riêng lẻ có thể đóng góp âm.
With decision trees, as we build that tree, effectively you are inventing the features as you go along.
Với cây quyết định, khi xây cây, thực chất bạn đang tự tạo ra các đặc trưng dần dần.
You're saying, first I'll look at this attribute, and then if this one is true, I'll also look at this one. And you find a combination of features that allows you to make a decision.
Bạn nói: trước hết tôi xem thuộc tính này, rồi nếu nó đúng, tôi xem thêm thuộc tính kia. Và bạn tìm ra một tổ hợp đặc trưng cho phép bạn ra quyết định.
So it's very, very different and much more expressive than the linear classifiers. It's much more comparable to neural networks.
Vì vậy nó rất khác và biểu diễn mạnh hơn nhiều so với các bộ phân loại tuyến tính. Nó giống mạng nơ-ron hơn nhiều.
So let's count how many hypotheses you might consider. Let's say we are allowed to build decision trees with n Boolean attributes.
Giờ hãy đếm xem có bao nhiêu giả thuyết ta có thể xét. Giả sử ta được xây cây quyết định với n thuộc tính Boolean.
So we have n Boolean attribute, and we say any decision tree over these n Boolean attributes is OK. How many different trees can we build?
Vậy ta có n thuộc tính Boolean, và ta nói mọi cây quyết định trên n thuộc tính Boolean này đều được. Ta xây được bao nhiêu cây khác nhau?
Or maybe asked in a different way, this is not so much about how many trees we can build, it's about how many functions can we present?
Hoặc hỏi theo cách khác, không hẳn là xây được bao nhiêu cây, mà là biểu diễn được bao nhiêu hàm?
How many functions do there exist over n Boolean attributes?
Có bao nhiêu hàm tồn tại trên n thuộc tính Boolean?
Well, what does it mean to write out one function? To write out one function over n Boolean attributes, we need to write a table.
Viết ra một hàm nghĩa là gì? Để viết một hàm trên n thuộc tính Boolean, ta cần viết một bảng.
And that table will have 2 to the n entries because every possible combination of attributes will need to have a function value. So that's 2 to the n.
Bảng đó có 2 mũ n dòng vì mỗi tổ hợp thuộc tính có thể đều cần có một giá trị hàm. Vậy là 2 mũ n.
Then, for each of those rows, you get to choose either true or false. So 2 to the n times. You get to make a choice of true or false.
Rồi với mỗi dòng đó, bạn chọn true hoặc false. Vậy 2 mũ n lần. Bạn được chọn true hoặc false.
So this is number of rows.
Đây là số dòng.
And the number of functions we have, we get to make a choice for every row out of two possibilities to the power number of rows, which if we write it out fully again will be 2 to the 2 to the n.
Còn số hàm thì ta chọn cho mỗi dòng một trong hai khả năng, lũy thừa số dòng, tức là lấy 2 mũ số dòng, viết đầy đủ ra sẽ là 2 mũ 2 mũ n.
You might wonder, is that a big number? A small number? Well, we can see. If n is just 6, this is how high that number is.
Bạn có thể tự hỏi, số đó lớn hay nhỏ? Ta cùng xem. Nếu n chỉ bằng 6, thì số này lớn như thế này.
So this number grows pretty quickly because you exponentiate the exponent, just like it's making it doubly exponential, which makes it grow a lot faster even than a regular exponential.
Số này tăng rất nhanh vì bạn lấy lũy thừa của một số mũ, tức là như thể nó thành hàm mũ kép vậy, nên nó tăng nhanh hơn rất nhiều so với hàm mũ thông thường.
So you might say, oh, any decision tree over 6 attributes is a pretty big hypothesis space already.
Vậy bạn có thể nói: bất kỳ cây quyết định nào trên 6 thuộc tính cũng đã là một không gian giả thuyết khá lớn rồi.
We need to be careful about over-fitting even when we just consider 6 attributes and allow for any decision tree. So maybe we should not allow for any decision tree.
Ta phải cẩn thận với quá khớp, ngay cả khi chỉ xét 6 thuộc tính và cho phép mọi cây quyết định. Nên có lẽ ta không nên cho phép mọi cây quyết định.
Maybe we should only allow for short decision trees where you can't make conditioning on as many attributes. How many trees are there of depth 1, often called decision stumps?
Có lẽ chỉ nên cho phép các cây quyết định ngắn, nơi ta không thể đặt điều kiện trên quá nhiều thuộc tính. Có bao nhiêu cây có độ sâu 1, thường gọi là decision stump?
Well, depth 1 means you only get to choose one attribute, but to choose that attribute, you get to choose out of n. So you have n choices of that one attribute.
Độ sâu 1 nghĩa là bạn chỉ được chọn một thuộc tính, nhưng để chọn thuộc tính đó, bạn chọn trong n thuộc tính. Vậy có n cách chọn thuộc tính đó.
Then, after you make that choice of the attribute, then you have to choose for the true value of that attribute and the false value, so there's two rows.
Sau khi chọn thuộc tính xong, bạn phải chọn kết quả cho giá trị đúng và giá trị sai của thuộc tính đó, nên có hai dòng.
So then there's two rows, and for each of those rows you have to choose true or false.
Có hai dòng, và với mỗi dòng bạn phải chọn đúng hoặc sai.
So we have true or false, which is two choices which you make twice. And so we have four n possible decision stumps with n attributes.
Vậy đúng hoặc sai là hai lựa chọn, và bạn chọn hai lần. Do đó có 4n decision stump khả dĩ với n thuộc tính.
So for 6, that would be 24, which is a lot smaller than this gigantic number we have on top. So that might be one way to go. And often people do this.
Với n = 6 thì là 24, con số nhỏ hơn rất nhiều so với con số khổng lồ ở trên. Vậy đây có thể là một hướng đi. Và người ta thường làm như vậy.
They limit the depth of the tree to make sure the hypothesis space doesn't grow too large because a hypothesis space too large, you might be over-fitting and not generalize to new data.
Họ giới hạn độ sâu của cây để không gian giả thuyết không quá lớn, vì không gian giả thuyết quá lớn thì có thể bị quá khớp và không tổng quát hóa được cho dữ liệu mới.
So going back to the learning theory, if you have a large hypothesis space, you allow for any tree let's say, then you have low bias because you're not forced to stay away from fitting your training data.
Quay lại lý thuyết học, nếu không gian giả thuyết lớn, chẳng hạn cho phép mọi cây, thì độ chệch (bias) thấp vì bạn không bị buộc phải tránh khớp với dữ liệu huấn luyện.
But the flip side, you might have pretty high variance because if there was a small change in your training data, you might have come up with a completely different answer when fitting to your training data.
Nhưng mặt trái là phương sai (variance) có thể khá cao, vì chỉ cần dữ liệu huấn luyện thay đổi nhỏ, bạn có thể ra một kết quả hoàn toàn khác khi khớp với dữ liệu huấn luyện.
What's the procedure for decision tree learning? Let's start in the main loop over here, and then we'll look at the exit conditions later.
Quy trình học cây quyết định là gì? Hãy bắt đầu với vòng lặp chính ở đây, rồi lát nữa ta xem các điều kiện thoát.
You look at the set of attributes you have and the set of examples and you choose a best attribute. What might that be? We don't know yet.
Bạn xem tập thuộc tính đang có và tập ví dụ, rồi chọn thuộc tính tốt nhất. Đó có thể là gì? Ta chưa biết.
It's a bit like in A* search where we had a heuristic to decide which node should we expand. Same thing here. Which attribute should we split on?
Hơi giống tìm kiếm A* khi ta có hàm heuristic để quyết định nên mở rộng nút nào. Ở đây cũng vậy. Ta nên tách theo thuộc tính nào?
Then, based on an attribute, we're going to build a new tree in that location. That's going to be sub-tree from what we already have built so far.
Sau đó, dựa trên một thuộc tính, ta sẽ xây một cây mới tại vị trí đó. Đó sẽ là cây con của phần ta đã xây cho đến giờ.
Then we'll look at each value that attribute can take on. We'll look at the examples that correspond to that value, and we feed them into a sub-tree.
Rồi ta xét từng giá trị mà thuộc tính đó có thể nhận. Ta xét các ví dụ ứng với giá trị đó, và đưa chúng vào một cây con.
We're going to build a sub-tree that uses only those examples. So as we build a tree, we start with all examples. We have a split.
Ta xây một cây con chỉ dùng những ví dụ đó. Vậy khi xây cây, ta bắt đầu với mọi ví dụ. Ta có một phép tách.
We channel examples based on the attribute values and keep repeating that. Keep going around this loop. At some point, we're down a branch.
Ta dẫn các ví dụ đi theo giá trị thuộc tính và cứ lặp lại như vậy. Cứ chạy vòng lặp này. Đến một lúc nào đó, ta xuống một nhánh.
Maybe, I don't know, restaurant is empty and the wait time was 60 minutes or more, and it's a French restaurant and this and that, and all of a sudden, there is no examples there.
Ví dụ nhà hàng vắng khách và thời gian chờ từ 60 phút trở lên, và là nhà hàng Pháp, v.v., và bỗng nhiên không còn ví dụ nào ở đó.
That's of course, you stop building the tree. There's nothing you can do there.
Dĩ nhiên khi đó bạn dừng xây cây. Ở đó bạn không làm gì được nữa.
If all examples have the same classification, there is no need to keep splitting on more attributes because they all have the same label, so you can just stop and put all those examples in that spot in the tree.
Nếu mọi ví dụ có cùng phân loại, thì không cần tách thêm theo thuộc tính nào nữa vì chúng đều cùng nhãn, nên bạn cứ dừng và đặt tất cả ví dụ đó vào vị trí đó trong cây.
Then, if the attributes are empty, you've looked at every attribute — So we'll say there was 10 attributes. You worked your way down building that tree, and you're somewhere here in the tree.
Tiếp theo, nếu hết thuộc tính, tức là bạn đã xét mọi thuộc tính — Giả sử có 10 thuộc tính. Bạn đã xây cây đi xuống dần, và đang ở đâu đó trong cây.
You looked at all 10 already. There's nothing you can do anymore. You already looked at all 10, and it is what it is.
Bạn đã xét hết cả 10 thuộc tính. Không còn gì để làm nữa. Bạn đã xét hết 10 rồi, và thế là xong.
If you still have a 70/30, then it is 70/30 for that leaf. That's just what you can do. Or you need to go find new features.
Nếu vẫn là 70/30 thì lá đó là 70/30. Chỉ làm được đến vậy. Hoặc bạn phải đi tìm đặc trưng mới.
How do we choose the attribute? Well, let's look at this example here. Which one would do better, left or right as a split?
Làm sao chọn thuộc tính? Hãy xem ví dụ này. Phép tách nào tốt hơn, bên trái hay bên phải?
Well, clearly we'd prefer the left because in the left there's a little bit of information coming out of it that, if the answer is none, it's all red, if the answer is some, then it's all green.
Rõ ràng ta thích bên trái hơn, vì ở bên trái có một chút thông tin thu được: nếu đáp án là none thì toàn màu đỏ, nếu là some thì toàn màu xanh. Còn với full thì lẫn lộn.
And for full, it's a mix. Whereas on the right, it stays 50/50 all along. That's a completely non-informative attribute split, the type split there. So intuitively, this is easy for this example.
Trong khi bên phải thì luôn giữ 50/50. Đó là một phép tách thuộc tính hoàn toàn không có thông tin, phép tách theo type ở đó. Vậy bằng trực giác, ví dụ này khá dễ.
But the question, of course, is can you write a piece of code that can look at splits and decide by looking at the potential split based on one attribute versus another attribute which attribute performs the better split?
Nhưng câu hỏi tất nhiên là bạn có thể viết một đoạn mã xem xét các phép tách và quyết định, bằng cách xét phép tách theo thuộc tính này so với thuộc tính kia, thuộc tính nào tách tốt hơn không? Lý tưởng là ta có một con số nào đó.
And ideally, we'd have some kind of number. We'd be able to say, this attribute has a quality of whatever, 5 or something, this one has a quality of 7.
Ta có thể nói, thuộc tính này có chất lượng là 5 chẳng hạn, thuộc tính kia có chất lượng là 7.
And higher quality is better, and so we'd go with 7, or something along those lines. So some kind of metric quantifying the quality of split. OK.
Chất lượng càng cao càng tốt, nên ta chọn 7, hoặc đại loại như vậy. Tức là một thước đo định lượng nào đó cho chất lượng của phép tách. Được rồi.
To get to that metric, we're going to do a little detour into information theory. Information theory is a pretty big field. A lot of interesting things there.
Để có thước đo đó, ta sẽ đi đường vòng một chút sang lý thuyết thông tin. Lý thuyết thông tin là một lĩnh vực khá lớn. Có rất nhiều điều thú vị.
We're not going to do it justice in two slides because it could be multiple semesters of only information theory. But there are some interesting ideas in here even in just two slides.
Ta sẽ không thể trình bày đầy đủ trong hai Ta sẽ không thể trình bày đầy đủ trong hai slide được, vì riêng lý thuyết thông tin có thể chiếm nhiều học kỳ chỉ để học một mình nó. Nhưng vẫn có vài ý tưởng thú vị ngay trong hai slide này.
So let's think about communication theory. Let's say you want to answer a Boolean question. What do you need to do to ask a question? Need to send either a 0 or a 1.
Hãy nghĩ về lý thuyết truyền thông. Giả sử bạn muốn trả lời một câu hỏi Boolean. Bạn cần làm gì để đặt câu hỏi đó? Cần gửi một số 0 hoặc một số 1.
So you need one bit of information to go across the channel to ask that question. What if it's a four-way question? How many bits do you need to send across?
Vậy cần một bit thông tin đi qua kênh để đặt câu hỏi đó. Nếu là câu hỏi bốn lựa chọn thì sao? Cần gửi bao nhiêu bit?
Well, for a four-way question, well, if you only send 1 bit, you can only send a 0 or 1. You cannot distinguish between sufficiently many things.
Với câu hỏi bốn lựa chọn, nếu chỉ gửi 1 bit, bạn chỉ gửi được 0 hoặc 1. Không đủ để phân biệt từng ấy thứ.
But if you get to send two bits, you can send 00, 01, 10, 11. You have four options, and you have enough. So here we need one bit.
Nhưng gửi được hai bit thì bạn có 00, 01, 10, 11. Có bốn lựa chọn, và thế là đủ. Vậy ở đây cần một bit.
Here we need two bits. How about a four-way question where you know ahead of time the information that's going to be sent is always the fourth entry? Well, we don't even have to communicate.
Ở đây cần hai bit. Còn câu hỏi bốn lựa chọn mà bạn biết trước thông tin sẽ được gửi luôn là mục thứ tư thì sao? Thì ta chẳng cần truyền gì cả.
If you know the answer here, 0 bits is enough. What this shows is that it depends on your distribution over possible things you might want to send maybe how many bits you really need.
Nếu biết trước đáp án, 0 bit là đủ. Điều này cho thấy số bit thực sự cần gửi phụ thuộc vào phân phối trên những thứ có thể gửi.
For example, let's say we have a three-way question. With this distribution, what could be our best strategy here?
Ví dụ, giả sử ta có câu hỏi ba lựa chọn. Với phân phối này, chiến lược tốt nhất là gì?
You could say, oh, well, if I'm either sending one or two bits, one is not enough, so it's going to be two bits, and then I just always send two bits.
Bạn có thể nghĩ: gửi một hoặc hai bit, một bit thì không đủ, nên là hai bit, và cứ luôn gửi hai bit.
And maybe it's 0001 and a 10. That's not optimal. You can instead say, hey, this one's really likely. I'm going to send a 0 for this one.
Có thể là 00, 01 và 10. Vậy chưa tối ưu. Thay vào đó bạn có thể nói: cái này rất có khả năng xảy ra. Tôi sẽ gửi 0 cho nó.
These ones are less likely. I'm going to use a 10 and a 11 for those. And when I do that, how many bits do I need on average?
Những cái này ít khả năng hơn. Tôi dùng 10 và 11 cho chúng. Khi đó trung bình cần bao nhiêu bit?
Well, half the time I send one bit, then one fourth of the time I send two bits, and another one fourth of the time I send two bits.
Một nửa số lần gửi một bit, một phần tư số lần gửi hai bit, và một phần tư số lần còn lại cũng gửi hai bit.
And so this comes down to we send 1/2 plus 1/2 plus 1/2 3/2 bits on average.
Vậy ta có 1/2 cộng 1/2 cộng 1/2, tức trung bình 3/2 bit.
Do we ever send 3 and 1/2 — 3 1/2, so 1 and 1/2 bits. Do we ever send 1 and 1/2 bits?
Có bao giờ ta gửi 3 rưỡi — 3/2, tức 1 bit rưỡi. Có bao giờ ta gửi 1 bit rưỡi không?
No, it's always one or two, but on average we send 1 and 1/2. That's a more efficient encoding scheme than a fixed length encoding. There is a generalization of this idea.
Không, luôn là một hoặc hai, nhưng trung bình là 1 bit rưỡi. Đó là cách mã hóa hiệu quả hơn so với mã hóa độ dài cố định. Ý tưởng này có dạng tổng quát.
And I'm not going to claim this is entirely obvious from just this one example, but the generalization is that if you have a distribution and something has a probability p, then you can get away with sending a code worth of length log 1 over p.
Tôi không nói là chỉ nhìn một ví dụ này đã thấy rõ ngay, nhưng dạng tổng quát là nếu có một phân phối và một thứ có xác suất p, thì bạn có thể gửi một từ mã có độ dài log 1 trên p.
So if something is extremely likely, p is close to one. If p is 1, you send 0 bits because you always have the same information is no information, really.
Nếu một thứ rất có khả năng xảy ra, p gần bằng 1. Nếu p bằng 1, bạn gửi 0 bit vì lúc nào cũng cùng một thông tin thì thực ra chẳng có thông tin gì.
If p is close to 0, then 1 over 0 goes to infinity. Log of infinity is still infinity. There's going to be a very large number.
Nếu p gần 0 thì 1 trên 0 tiến tới vô cùng. Log của vô cùng vẫn là vô cùng. Sẽ là một số rất lớn.
But that's OK because the probability of that thing is so low that the number of times you have to send a large code word is very small.
Nhưng không sao, vì xác suất của thứ đó quá thấp nên số lần bạn phải gửi từ mã dài là rất ít.
And so you get a notion here where on average, you send sum over all possible things, the probability of that thing times the log of 1 over the probability of that thing.
Từ đó ta có khái niệm: trung bình bạn gửi tổng trên mọi thứ có thể, của xác suất của thứ đó nhân log của 1 trên xác suất của thứ đó.
That's how much you have to send. This is the length of the message, the encoding of message i, and this is how often you have to send message i.
Đó là lượng bạn phải gửi. Đây là độ dài của thông điệp, tức mã hóa của thông điệp i, và đây là tần suất bạn phải gửi thông điệp i.
And so it's a redistribution of bits where you use a very small number of bits for highly likely things for a large number of bits for unlikely things.
Đó là sự phân phối lại các bit: dùng rất ít bit cho thứ rất có khả năng xảy ra, và nhiều bit cho thứ ít có khả năng.
So that measure is called entropy. So the summation I just wrote, log of 1 over pi is minus log of pi, this thing here is the entropy denoted by h.
Đại lượng đó gọi là entropy. Tổng tôi vừa viết, log của 1 trên pi là trừ log của pi, biểu thức này là entropy, ký hiệu là H.
And so every distribution has an entropy.
Mỗi phân phối đều có một entropy.
And there's a theorem that says that, if indeed your data comes from that distribution and you choose the optimal encoding scheme, on average the number of bits you have to send is equal to the entropy, that is the weighted sum of the log 1 over p's for each one of them.
Có một định lý nói rằng nếu dữ liệu của bạn thực sự đến từ phân phối đó và bạn chọn cách mã hóa tối ưu, thì số bit trung bình bạn phải gửi bằng entropy, tức tổng có trọng số của log 1 trên p cho từng thứ.
Look at these. OK. Which one has high entropy? Which one has low entropy?
Hãy nhìn những cái này. OK. Cái nào có entropy cao? Cái nào có entropy thấp?
Well, high entropy means that you need to send a lot of bits, meaning that there is a lot of uncertainty about things.
Entropy cao nghĩa là bạn cần gửi nhiều bit, tức là có nhiều bất định về mọi thứ.
So this one's high entropy because you know nothing really ahead of time. This one is really low entropy because you know everything ahead of time.
Cái này entropy cao vì thực ra bạn chẳng biết gì từ trước. Cái này entropy rất thấp vì bạn biết hết mọi thứ từ trước.
And this one here, entropy is somewhere in the middle. You know a little bit ahead of time, but not everything ahead of time.
Còn cái này, entropy ở mức trung bình. Bạn biết trước một chút, nhưng không biết hết.
So what we have now is a way of quantifying the amount of uncertainty we have in a distribution. That is the criterion we're going to use to decide on attributes to do splits on.
Vậy giờ ta có cách định lượng mức bất định trong một phân phối. Đó là tiêu chí ta sẽ dùng để chọn thuộc tính dùng cho việc chia.
Because what we want, as we do splits, we want to reduce uncertainty. And that was the intuition here.
Vì khi chia, điều ta muốn là giảm bất định. Đó là trực giác ở đây.
We liked the one on the left because there was more certainty in the different pockets, whereas the one on the right retained all uncertainty in every pocket.
Ta thích cái bên trái vì trong các nhóm có độ chắc chắn cao hơn, còn cái bên phải vẫn giữ nguyên toàn bộ bất định trong mọi nhóm.
We now have a way to measure that.
Giờ ta đã có cách đo điều đó.
Entropy is the way to measure how much uncertainty there is when we know we're going to get a sample from a distribution but we don't know what the sample is going to be yet.
Entropy là cách đo mức bất định khi ta biết sẽ nhận một mẫu từ một phân phối nhưng chưa biết mẫu đó sẽ là gì.
So it's very easy to compute, just a weighted sum of log 1 over p's. And so when we look at this, we can say, OK, what is the resulting entropy here versus here?
Nó rất dễ tính, chỉ là tổng có trọng số của log 1 trên p. Và khi nhìn vào đây, ta có thể nói, OK, vậy entropy kết quả ở đây so với ở đây là bao nhiêu?
Well, this guy has 0, this guy has 0, and this guy has something in the middle. And these are all somewhere in the middle.
Cái này bằng 0, cái này cũng bằng 0, còn cái này nằm ở khoảng giữa. Và những cái này đều nằm đâu đó ở giữa.
Now of course, there's multiple pockets, and when you choose an attribute, you generate all those pockets.
Tất nhiên, có nhiều nhóm, và khi bạn chọn một thuộc tính, bạn tạo ra tất cả các nhóm đó.
So we're going to take an average of the entropy in each one of the pockets, in each one of the branches, to decide which one has the better resulting entropy.
Vì vậy ta sẽ lấy trung bình entropy của từng nhóm, của từng nhánh, để quyết định thuộc tính nào cho entropy kết quả tốt hơn.
So we compute the expected entropy. We might produce something called information gain, which might remind you of value of perfect information.
Tức là ta tính entropy kỳ vọng. Ta có thể tạo ra một đại lượng gọi là information gain, có thể gợi bạn nhớ đến giá trị của thông tin hoàn hảo.
Here what it is, you compute the — information gain is entropy of this guy minus weighted entropy of all of these guys.
Ở đây, bạn tính — information gain là entropy của nút này trừ đi entropy có trọng số của tất cả các nút con này.
And if that entropy drops by a lot, it means you chose a good split because your uncertainty is reduced.
Nếu entropy giảm nhiều, nghĩa là bạn đã chọn một phép tách tốt vì độ bất định giảm đi.
If entropy goes up, that would be pretty bad, but that typically shouldn't be possible or we shouldn't let that happen. Here on the right, it stayed the same, everything uniform.
Nếu entropy tăng thì khá tệ, nhưng thường điều đó không thể xảy ra hoặc ta không để nó xảy ra. Ở bên phải, entropy giữ nguyên, mọi thứ đều đồng đều.
That's as bad as it can be for entropy. That's definitely the worst possible attribute to pick.
Đó là mức tệ nhất có thể của entropy. Chắc chắn đó là thuộc tính tệ nhất để chọn.
So now we can do this. We can decide split on patrons makes more sense because the entropy drops. We have information gain. After we do that, we can repeat.
Giờ ta có thể làm thế này. Ta quyết định tách theo patrons là hợp lý hơn vì entropy giảm. Ta có information gain. Sau đó, ta có thể lặp lại.
We could run through this algorithm that we covered a few slides ago. The only thing we did in those which attribute to pick. We now do it based on information gate.
Ta có thể chạy thuật toán mà ta đã học vài slide trước. Điều duy nhất ta làm là chọn thuộc tính nào. Giờ ta chọn dựa trên information gain.
Here is the tree that we end up with. Remember the tree at the very beginning of the second half of lecture that was the true hypothesis, it was bigger.
Đây là cây mà ta thu được. Hãy nhớ cái cây ở đầu nửa sau của bài giảng, đó là giả thuyết đúng, nó lớn hơn.
It was not exactly like this. It was a little different. But we didn't have enough data to recover that tree.
Nó không hoàn toàn giống thế này. Nó hơi khác một chút. Nhưng ta không có đủ dữ liệu để khôi phục cái cây đó.
If we had infinite data, we might have found that tree, but we didn't have infinite data. We're ended up finding this tree.
Nếu có dữ liệu vô hạn, có thể ta đã tìm ra cái cây đó, nhưng ta không có dữ liệu vô hạn. Cuối cùng ta tìm được cái cây này.
So there's no guarantee when you run this you find that ground truth hypothesis, just like any machine learning. You're just fitting the data.
Vậy nên không có gì đảm bảo khi bạn chạy thuật toán này thì sẽ tìm ra giả thuyết ground truth, giống như mọi bài toán machine learning. Bạn chỉ đang khớp dữ liệu.
So it's actually a lot simpler, which might be a good thing, because it might generalize well, but it's not correct for all scenarios. Here's another example.
Nên nó đơn giản hơn nhiều, có thể là điều tốt, vì nó có thể tổng quát hóa tốt, nhưng không đúng cho mọi tình huống. Đây là một ví dụ khác.
Let's say we want to predict whether a car has good miles per gallon. And we can predict it from cylinders, displacement, horsepower, weight, acceleration, model year, and maker.
Giả sử ta muốn dự đoán xem một chiếc xe có số dặm trên mỗi gallon tốt hay không. Ta có thể dự đoán từ số xi-lanh, dung tích, mã lực, trọng lượng, gia tốc, năm sản xuất, và hãng sản xuất.
Again, in principle, if this is a out in the wild thing you're trying to solve, you would think about, oh, maybe I'll try naive Bayes. Maybe I'll try logistic regression.
Một lần nữa, về nguyên tắc, nếu đây là bài toán thực tế bạn cần giải, bạn sẽ nghĩ, ồ, có thể mình sẽ thử naive Bayes. Có thể thử hồi quy logistic.
Maybe I'll try a neural network, or maybe I'll try a decision tree. And this lecture right now, we're going to do it with a decision tree to cover more ideas centered around decision trees.
Có thể thử mạng nơ-ron, hoặc có thể thử cây quyết định. Còn trong bài giảng này, ta sẽ làm với cây quyết định để đề cập thêm các ý tưởng xoay quanh cây quyết định.
So we look at the information gain for each attribute. We could say, OK, if we split on cylinders, what you end up with?
Vậy ta xem information gain của từng thuộc tính. Ta có thể nói, nếu tách theo số xi-lanh, thì sẽ thu được gì?
Here are the distributions shown, and then this is the information gain, the entropy we had before the split, and the weighted entropy we have after the split.
Đây là các phân phối được hiển thị, và đây là information gain, entropy trước khi tách, và entropy có trọng số sau khi tách.
Information gain if we split on displacement, on horsepower, on weight, and acceleration, a model year, on maker.
Information gain nếu tách theo dung tích, mã lực, trọng lượng, gia tốc, năm sản xuất, hãng sản xuất.
Information gain is highest if splitting on cylinders, so we split on cylinders. Now here is what we end up with as we run this algorithm.
Information gain cao nhất khi tách theo số xi-lanh, nên ta tách theo số xi-lanh. Đây là kết quả khi ta chạy thuật toán này.
We started with all the data at the root, but this data now has been distributed over different branches depending on how many cylinders was the value of the attribute for that data sample.
Ta bắt đầu với toàn bộ dữ liệu ở gốc, nhưng giờ dữ liệu này đã được phân bổ vào các nhánh khác nhau tùy theo giá trị số xi-lanh của thuộc tính ở mẫu dữ liệu đó.
Over here, there's zero data, so nothing left to be done. Over here there's still a lot of data. Here there's not much data left. Probably can stop branching there.
Ở đây không có dữ liệu nào, nên không còn gì để làm. Ở đây vẫn còn rất nhiều dữ liệu. Ở đây còn không nhiều dữ liệu. Có lẽ có thể dừng phân nhánh ở đó.
There's only one left. Here also, everything's the same. Everything's bad. So that's the prediction we stick with.
Chỉ còn một mẫu. Ở đây cũng vậy, mọi thứ đều giống nhau. Tất cả đều xấu. Nên đó là dự đoán ta giữ lại.
Here — well, here it's more debatable should you continue or not Because 9 to 1 is already pretty extreme. Might be over-fitting if we do one more split or not.
Ở đây thì còn tranh cãi là có nên tiếp tục hay không, vì 9 trên 1 đã khá cực đoan rồi. Tách thêm một lần nữa có thể gây quá khớp, hoặc không.
Not clear. Let's ignore that for now. Let's think about this one here and see where we want to do there. Let's split it.
Không rõ. Tạm thời bỏ qua chỗ đó. Hãy nghĩ về nút này ở đây và xem ta muốn làm gì với nó. Hãy tách nó.
And here, maker had the highest information gain. And then over here, horsepower had the highest information gain. You have more splits to do to get to all the way where everything is deterministic.
Ở đây, hãng sản xuất có information gain cao nhất. Còn ở đây, mã lực có information gain cao nhất. Bạn còn phải tách thêm để đi đến mức mà mọi thứ đều xác định.
Let's see. Do some more splits. After you keep running the algorithm I described, this is what you end up with.
Xem nào. Tách thêm vài lần nữa. Sau khi tiếp tục chạy thuật toán tôi vừa mô tả, đây là kết quả bạn nhận được.
Definitely you should be worried about over-fitting here because we fitted all the training data perfectly, except for this guy over here. That one is unexpandable. What does that mean?
Chắc chắn bạn nên lo về quá khớp ở đây vì ta đã khớp hoàn hảo toàn bộ dữ liệu huấn luyện, trừ nút này ở đây. Nút đó không thể mở rộng. Điều đó nghĩa là gì?
It means that no matter which attribute we split on, it's not going to make any difference anymore. We can't improve this anymore. It's just the function happens to be stochastic, apparently, which can happen.
Nghĩa là dù ta tách theo thuộc tính nào, cũng không còn tạo ra khác biệt nào nữa. Ta không thể cải thiện thêm được nữa. Có vẻ hàm này tình cờ mang tính ngẫu nhiên, điều này có thể xảy ra.
Not all functions are deterministic. And that's what this would be modeling. Or maybe somebody mislabeled something. So this is our big final tree.
Không phải hàm nào cũng xác định. Và đó là điều mà nút này đang mô hình hóa. Hoặc có thể ai đó đã gán nhãn sai. Đây là cây cuối cùng rất lớn của chúng ta.
Will it generalize? Your guess should be not. You're probably over-fitting at this point because you fit every pattern that's in the training data. In naive Bayes, we did smoothing to avoid that.
Nó có tổng quát hóa được không? Các em nên đoán là không. Đến lúc này có lẽ ta đang bị quá khớp vì đã khớp mọi mẫu có trong tập huấn luyện. Với naive Bayes, ta dùng smoothing để tránh điều đó.
In perceptron we did early stopping. Well, let's take a look here. Percentage wrong on training data, 2.5%. Percentage wrong on test data, 21%.
Với perceptron, ta dùng early stopping. Hãy xem ở đây. Tỷ lệ sai trên dữ liệu huấn luyện là 2,5%. Tỷ lệ sai trên dữ liệu kiểm tra là 21%.
Clearly we're over-fitting. We do much better on the training data than it would in test data. That's exactly what means over-fitting. OK.
Rõ ràng là ta đang bị quá khớp. Ta làm tốt hơn nhiều trên dữ liệu huấn luyện so với trên dữ liệu kiểm tra. Đó chính xác là ý nghĩa của quá khớp. OK.
So what now? Consider this split over here. Put an extra number in here, p chance. What does that thing mean?
Vậy giờ làm gì? Hãy xét lần chia ở đây. Có thêm một con số ở đây, p chance. Con số đó nghĩa là gì?
You could do a calculation and say, let's say I had an attribute and I assigned values to that attribute randomly.
Ta có thể tính toán và nói rằng, giả sử tôi có một thuộc tính và gán các giá trị cho thuộc tính đó một cách ngẫu nhiên.
So for each row in my table, I just have this extra column, and I just assign the value of that attribute randomly. And I do a split on that random attribute.
Tức là mỗi hàng trong bảng có thêm một cột, và tôi gán giá trị của thuộc tính đó ngẫu nhiên. Rồi tôi chia theo thuộc tính ngẫu nhiên đó.
How much information gain would I get? If the information gain's really good, it means you're doing information gain on what is really memorizing the training data, not on the pattern in your data.
Tôi sẽ thu được bao nhiêu information gain? Nếu information gain rất tốt, nghĩa là ta đang tính information gain trên thứ thực chất là ghi nhớ dữ liệu huấn luyện, chứ không phải trên mẫu thực sự trong dữ liệu.
We're not getting into the specifics of how you compute this probability, but the intuition should be clear that if somebody introduces a random feature and you think splitting based on that random feature is equivalent to splitting on this thing that you think is a real feature, well, maybe it's not that real a feature.
Ta sẽ không đi vào chi tiết cách tính xác suất này, nhưng trực giác khá rõ: nếu ai đó thêm vào một đặc trưng ngẫu nhiên và chia theo đặc trưng ngẫu nhiên đó mà tương đương với chia theo thứ mà em tưởng là đặc trưng thật, thì có lẽ nó không thật sự là đặc trưng thật.
Maybe you should think of it as also a random feature and not split on it anymore. So you can do a comparison.
Có lẽ nên coi nó cũng là đặc trưng ngẫu nhiên và đừng chia theo nó nữa. Vậy ta có thể so sánh.
What is the information gain when you split on a random feature versus split on one of the real attributes? And if it's comparable, maybe you should stop splitting.
Information gain là bao nhiêu khi chia theo một đặc trưng ngẫu nhiên so với chia theo một thuộc tính thật? Nếu chúng tương đương, có lẽ nên dừng chia.
So we're not going in the math of how to do this, but we don't want to do extra splits when just chance would also have led to similar information gains.
Ta sẽ không đi vào phần toán của cách làm này, nhưng ta không muốn chia thêm khi chỉ do ngẫu nhiên cũng có thể cho information gain tương tự.
So we'll attach significance values, p chance, which were in the tree, which is the probability of a split that turns two blues and one red into one blue, one blue, one red, and an empty.
Vì vậy ta gắn các giá trị ý nghĩa, p chance, có trong cây, là xác suất của một lần chia mà biến hai xanh một đỏ thành một xanh, một xanh một đỏ, và một nhóm rỗng.
What's the probability of this kind of outcome if it was a chance attribute split. And then, if that probability is too high, too close to chance, then we just don't do the split.
Xác suất của kiểu kết quả này là bao nhiêu nếu đó là lần chia theo một thuộc tính ngẫu nhiên. Nếu xác suất đó quá cao, quá gần với ngẫu nhiên, thì ta không thực hiện lần chia đó.
So in practice, people do it slightly differently.
Trong thực tế, người ta làm hơi khác một chút.
What they do is they build the entire tree and then do a second pass up the tree removing splits that don't satisfied the criterion.
Họ xây toàn bộ cây rồi duyệt lượt hai đi ngược lên, loại bỏ các lần chia không thỏa tiêu chí.
You might say, why not just do it on the way down and just stop the work? Think back to, for example, the XOR.
Có thể em hỏi sao không làm luôn lúc đi xuống và dừng ngay? Hãy nhớ lại ví dụ XOR.
The XOR you could not — in the first split, you gained nothing. It's only when you did the second split you could see the correlation between two attributes.
Với XOR, ở lần chia đầu tiên em không thu được gì. Chỉ khi chia lần thứ hai em mới thấy tương quan giữa hai thuộc tính.
And so whenever there's attributes that might be correlated and that's the information you need to get, you need to allow for two consecutive splits before you see any signal.
Vì vậy khi có những thuộc tính có thể tương quan và đó là thông tin cần có, em phải cho phép hai lần chia liên tiếp trước khi thấy bất kỳ tín hiệu nào.
And so by allowing you to go all the way to the bottom since you over-fit your training data, but make sure you don't miss any signal that way.
Nên bằng cách cho phép đi hết xuống đáy, dù quá khớp dữ liệu huấn luyện, ta đảm bảo không bỏ lỡ tín hiệu nào.
You at least capture all signal, but also some non-signal, and then work your way back. You might get something better that can capture more of the pattern in your data while still not over-fitting.
Ít nhất ta nắm được mọi tín hiệu, cùng với một ít nhiễu, rồi sau đó quay ngược lên. Em có thể được một cây tốt hơn nắm được nhiều mẫu hơn trong dữ liệu mà vẫn không bị quá khớp.
So you would start from the bottom, and for each split, check, OK, what the probability of this split compared to probably of doing it under chance?
Vậy ta bắt đầu từ đáy, và với mỗi lần chia, kiểm tra xem xác suất của lần chia này so với xác suất đạt được do ngẫu nhiên là bao nhiêu?
And if it's on the wrong side of that equation, then just get rid of the split and combine all the data into the node above.
Nếu nó nằm ở phía không tốt của phép so sánh đó, thì bỏ lần chia đó và gộp toàn bộ dữ liệu vào nút phía trên.
Here's this example in action. What it ends up with is a very short decision tree which only splits on cylinders and no other splits.
Đây là ví dụ khi áp dụng. Kết quả là một cây quyết định rất ngắn chỉ chia theo cylinders và không chia gì khác.
Training set accuracy used to be — training set error used to be 2.5%. Now it's 12.5%, which is worse, but test set error used to be something — 40%, I think.
Độ chính xác trên tập huấn luyện trước đây là — lỗi trên tập huấn luyện trước đây là 2,5%. Giờ là 12,5%, tệ hơn, nhưng lỗi trên tập kiểm tra trước đây là khoảng — 40%, tôi nghĩ vậy.
Something pretty bad. I forgot what the number is. Let's see, what was it? 21%.
Khá tệ. Tôi quên con số rồi. Để xem, là bao nhiêu nhỉ? 21%.
And now it is 16%. So we actually improved our decision making capabilities on future data, or at least we expect that to be the case on future data.
Và giờ là 16%. Vậy ta thực sự đã cải thiện khả năng ra quyết định trên dữ liệu tương lai, hay ít nhất ta kỳ vọng là như vậy trên dữ liệu tương lai.
This is a form of regularization we've seen a few different forms of regularization now, and that's really one of the key ideas that you should keep in mind as you do anything machine learning, is you want to make sure your hypothesis space isn't too big.
Đây là một dạng regularization, ta đã thấy vài dạng regularization khác nhau rồi, và đó thực sự là một ý tưởng then chốt mà các em cần nhớ khi làm bất kỳ việc gì về machine learning: là phải đảm bảo không gian giả thuyết không quá lớn.
You either keep it small by design. You say, no bigger trees than this. No bigger network than this. No more features than this.
Hoặc em giữ nó nhỏ ngay từ thiết kế. Em nói, không dùng cây lớn hơn thế này. Không dùng mạng lớn hơn thế này. Không dùng nhiều đặc trưng hơn thế này.
Or you regularize. In principle, your hypothesis space is big, but then you don't let things get all the way to the outskirts of that hypothesis space.
Hoặc em dùng regularization. Về nguyên tắc không gian giả thuyết lớn, nhưng em không để mọi thứ đi hết ra vùng rìa của không gian giả thuyết đó.
For decision trees, the outskirts is fully built-out decision trees with branch in every possible attribute and every path down to a leaf. That's too big. That's likely over-fitting.
Với cây quyết định, vùng rìa là những cây quyết định được xây đầy đủ với nhánh ở mọi thuộc tính có thể và mọi đường đi xuống tới lá. Như vậy là quá lớn. Nhiều khả năng là quá khớp.
You want to re-prune that. That's the regularization.
Bạn muốn cắt tỉa lại cây đó. Đó chính là regularization.
So if you are — the further you go in training, the higher variance, the bigger the tree you end up with, and then as you go back pruning, you might have used a little bit of bias.
Vậy nếu bạn... huấn luyện càng lâu thì phương sai càng cao, cây bạn thu được càng lớn, và khi bạn cắt tỉa ngược lại, bạn có thể phải chịu thêm một chút bias.
You might reduce a little bit of signal that you could have extracted, but you'll reduce variance.
Bạn có thể bỏ lỡ một chút tín hiệu lẽ ra có thể khai thác, nhưng bạn sẽ giảm được phương sai.
So there are two ways of controlling over-fitting, limiting the hypothesis space or regularizing how you select from the hypothesis space. Both of them are used.
Vậy có hai cách kiểm soát quá khớp: giới hạn không gian giả thuyết, hoặc regularize cách chọn từ không gian giả thuyết đó. Cả hai cách đều được dùng.
Often when you want something really expressive, it's the second one. You make it real expressive and regularized to make sure that you don't get into the weird parts of the space.
Thường khi bạn muốn mô hình thật sự biểu đạt tốt, thì sẽ dùng cách thứ hai. Bạn làm cho nó rất biểu đạt và có regularization để đảm bảo không rơi vào những vùng kỳ quặc của không gian.
OK. That's it for the core materials of 188. You have a midterm on Thursday, and in the next couple of lectures, we'll look at applications of the materials we already covered.
Được rồi. Vậy là hết phần nội dung cốt lõi của CS 188. Thứ Năm các bạn có bài thi giữa kỳ, và trong vài bài giảng tới, chúng ta sẽ xem các ứng dụng của những nội dung đã học.
OK. Good luck on Thursday.
Được rồi. Chúc các bạn thi tốt vào thứ Năm.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.