BÀI GIẢNG KHAI PHÁ DỮ LIỆU
Nội dung bổ sung về Khai phá dữ liệu
PGS. TS. Hà Quang ThụyHÀ NỘI, 10-2018 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI http://uet.vnu.edu.vn/~thuyhq/
1
Nội dung
1. Một số tài nguyên khai phá dữ liệu 2. Khai phá quy trình 3. Khai phá dữ liệu: Học suốt đời
2
1. Tài nguyên KPDL: 9 kiểu công cụ ▪ Data mining suites (DMS): Gói chứa nhiều phương pháp ▪ Business intelligence packages (BIs): Không tập trung chuyên về KPDL mà hướng tới các chức năng KPDL cơ bản, đặc biệt thống kê trong ứng dụng kinh doanh
▪ Mathematical packages (MATs): Không tập trung chuyên về KPDL mà hướng tới một tập lớn và mở rộng các thuật toán và thủ tục trực quan hóa.
3
Matlab, R… với chức năng hạn chế song rất hữu dụng.
▪ Integration packages (INTs): gói mở rộng nhiều thuật toán nguồn mở khác nhau/phần mềm độc lập (chủ yếu là dựa trên Java). ▪ EXT: tiện ích bổ sung nhỏ cho các công cụ khác như Excel,
như một gói chức năng.
▪ Data mining libraries (LIBs): thực thi các phương pháp KPDL
phương pháp chuyên biệt (mạng nơron, …)
▪ Specialties (SPECs): tương tự như LIB song gồm chỉ một nhóm
July 12, 202 1
Ralf Mikut, Markus Reischl (2011). Data mining tools, Wiley Interdisc. Rew.: Data Mining and Knowledge Discovery 1(5): 431-443 (2011).
▪ RES: thường là sự thi hành lần đầu tiên thuật toán mới, cách tân. ▪ Solutions (SOLs): một nhóm các công cụ được tùy biến cho các lĩnh vực ứng dụng hẹp như khai phá văn bản (GATE), xử lý hình ảnh (ITK, ImageJ) ...
Tài nguyên KPDL: Công cụ TM
Data mining suites BI packages Mathematical packages Integration packages Specialties RES
4
July 12, 202 1
Ralf Mikut, Markus Reischl (2011). Data mining tools, Wiley Interdisc. Rew.: Data Mining and Knowledge Discovery 1(5): 431-443 (2011).
Tài nguyên KPDL: Công cụ TM
5
BI packages Mathematical packages Integration packages Specialties July RES Data mining suites 12, 202 1
Ralf Mikut, Markus Reischl (2011). Data mining tools, Wiley Interdisc. Rew.: Data Mining and Knowledge Discovery 1(5): 431-443 (2011).
Tài nguyên KPDL: Công cụ nguồn mở
Data mining suites BI packages Mathematical packages
6
Integration packages Specialties RES
July 12, 202 1
Ralf Mikut, Markus Reischl (2011). Data mining tools, Wiley Interdisc. Rew.: Data Mining and Knowledge Discovery 1(5): 431-443 (2011).
Tài nguyên KPDL: Công cụ nguồn mở
7
Data mining suites BI packages Mathematical packages Integration packages Specialties RES
July 12, 202 1
Ralf Mikut, Markus Reischl (2011). Data mining tools, Wiley Interdisc. Rew.: Data Mining and Knowledge Discovery 1(5): 431-443 (2011).
Tài nguyên KPDL: Dữ liệu mẫu
8
Kho chứa dữ liệu của nhóm học máy tại University of California, Irvine – UCI (UC Irvine Machine Learning Repository). http://archive.ics.uci.edu/ml/ (11/2015)
July 12, 202 1
http://kdd.org/ : Trang web công đồng DM
9
July 12, 202 1
http://kdd.org/awards/sigkdd-dissertation-award
0 1
Winner: Mining Latent Entity Structures From Massive Unstructured and Interconnected Data. Chi Wang (student) and Jiawei Han (advisor) at University of Illinois at Urbana-Champaign
Runner-up: Modeling Large Social Networks in Context. Qirong Ho (student) and Eric Xing (advisor) at Carnegie Mellon University
July 12, 202 1
Runner-up: Computing Distrust in Social Media. Jiliang Tang (Student) and Huan Liu (Advisor) at Arizona State University. Định hướng Khóa luận đại học K56: Thái Thị Hoài, Nguyễn Quỳnh Nga, Mai Công Đạt
2. Tại sao KPQT: Chỉ số cạnh tranh quốc tế
⚫ Giới thiệu khả năng cạnh tranh
yếu tố xác định mức năng suất của một quốc gia
▪ Diễn đàn Kinh tế Thế giới (World Economic Forum), 2005 ▪ khả năng cạnh tranh: tập chỉ số về thể chế, chính sách, và các
1 1
⚫ Tập chỉ số cạnh tranh quốc gia
▪ Mức năng suất: tập các mức thành công thu được từ nền kinh tế ▪ Đo lường bằng tập chỉ số
▪ Index, còn được gọi là cột trụ (pillar) ▪ 12 cột trụ:
thể chế, hạ tầng, môi trường kinh tế vĩ mô, sức khỏe và giáo dục tiểu học, giáo dục và đào tạo đại học, thị trường hàng hóa hiệu quả, thị trường lao động hiệu quả, phát triển thị trường tài chính, sẵn sàng công nghệ, kích cỡ thị trường, kinh doanh tinh vi (tinh xảo), đổi mới.
4&5, cột trụ 8&9 liên quan cột trụ 6…
▪ Có tương quan nhau, tác động lẫn nhau: cột trụ 12 cột trụ
[WEF13] World Economic Forum (2013). The Global Competitiveness Report 2013– 2014. http://www3.weforum.org/docs/WEF_GlobalCompetitivenessReport_2013- 14.pdf
Trình độ nền kinh tế: 3 mức
⚫ Nền kinh tế định hướng yếu tố cơ bản
thiên nhiên và lao động chưa qua chế biến
▪ factor-driven economy ▪ lợi thế cạnh tranh: xuất khẩu yếu tố giá trị thấp như tài nguyên
⚫ Nền kinh tế định hướng hiệu quả
2 1
▪ rất nhạy cảm :chu kỳ KT thế giới, giá hàng hóa, biến động tỷ giá
⚫ Nền kinh tế định hướng đổi mới
▪ Efficiency - Driven Economy ▪ Lợi thế cạnh tranh: sản phẩm và dịch vụ tiên tiến hơn rất hiệu quả (i) Đầu tư mạnh cơ sở hạ tầng hiệu quả; (ii) quản lý chính quyền thân thiện với doanh nghiệp; (iii) ưu đãi đầu tư mạnh; (iv) nâng cao kỹ năng; (v) tiếp cận tốt với nguồn vốn đầu tư nhằm cải thiện lớn về năng suất
▪ innovation-driven economy ▪ Lợi thế cạnh tranh: sản phẩm, dịch vụ mới và/hoặc độc đáo ▪ dựa trên công nghệ mới nhất và/hoặc quy trình sản xuất/mô
hình kinh doanh tinh vi nhất
▪ Khu vực dịch vụ có tỷ trọng cao trong nền kinh tế ▪ kiên cường trước những cú sốc từ bên ngoài
Mối quan hệ các cột trụ với nền kinh tế
3 1
Việt Nam
[WEF13] World Economic Forum (2013). The Global Competitiveness Report 2013–2014.
Nghị quyết 19/2014/NQ-CP ngày 18/3/2014 của Chính phủ về những nhiệm vụ, giải pháp chủ yếu cải thiện môi trường kinh doanh, nâng cao năng lực cạnh tranh quốc gia
Giới thiệu Khai phá quy trình
- Wil van der Aalst
▪
▪
▪
▪
▪
4 1
▪
ĐHCN Eindhoven (Eindhoven Univ. of Technology (TU/e)) Khởi xướng và duy trì phát triển khai phá quá trình http://wwwis.win.tue.nl/~wvdaalst/ Master's thesis “Specificatie en Simulatie met behulp van ExSpect” Đặc tả và mô phỏng bởi ExSpect, 1988 PhD thesis “Timed coloured Petri nets and their application to logistics”, 1992 Nhà khoa học Tin học ngoài Mỹ có chỉ số h-index cao thứ nhất: 112 (9/2015; 101: 9/2013, 94: 5/2013) http://www.cs.ucla.edu/~palsberg/h- number.html
-
Tổ chức nghề nghiệp về khai phá quy trình
▪
▪
▪
▪
▪
http://www.processmining.org/: Cho tài nguyên phong phú: các bài báo, luận án Tiến sỹ [Http] http://www.processmining.org/publications/phd bộ công cụ PRoM và các công cụ khác các tập dữ liệu nhật ký sự kiện: một phần từ hơn 100 tổ chức
July 12, 202 1
Mối quan hệ giữa một số khái niệm
5 1
-
Khái niệm và triết lý khai phá quy trình Khái niệm khai phá quy trình
▪
▪
Process Mining: chiết xuất thông tin có giá trị, liên quan đến quy trình từ các nhật ký ghi sự kiện, bổ sung vào các tiếp cận hiện có để quản lý quy trình tác nghiệp (Business Process Management : BPM). Kết hợp giữa khai phá dữ liệu và quản lý quy trình tác nghiệp
6 1
-
Triết lý “đường mòn” của khai phá quy trình
▪
▪
▪
▪
▪
▪
Đường mòn (desire line) / đường xã hội (the social trail) Là con đường được hình thành do sự xói mòn bởi bước chân của con người hoặc động vật Chiều rộng và độ xói mòn thể hiện độ thường xuyên sử dụng “Đường mòn là ngắn nhất/thuận tiện nhất giữa hai điểm Xói mòn càng cao Sử dụng càng thường xuyên Hành động trong kinh doanh hình thành đường mòn kinh doanh ~ nhật ký sự kiện phản ánh quy trình tốt/thuận tiện
[Aalst11] WMP Van der Aalst (2011). Process Mining: Discovery, Conformance
and Enhancement of Business Processes, Springer, 2011.
July 12, 202 1
Ví dụ triết lý đường mòn - Xây dựng lối đi trong ĐH Columbia
▪
▪
▪
Tác giả: Dwight Eisenhower, Chủ tịch ĐH Columbia (sau này là Tổng thống Mỹ đời thứ 34) Bài toán: xây lối đi tốt nhất nối các nhà trong khu trường Lời giải:
▪
▪
▪
Cho cỏ mọc giữa các tòa nhà và trì hoãn tạo vỉa hè Mọi người đi: Hình thành dần lối mòn giữa các nhà Xây vỉa hè theo các lối mòn đó
17
Cơ bản về Khai phá quy trình
-
Khái niệm
⚫
⚫
⚫
⚫
KPQT: phát hiện, theo dõi, cải thiện quy trình kinh doanh dựa trên trích xuất tri thức từ nhật ký sự kiện NKSK (event log) NKSK={trường hợp (case) “thể hiện” quy trình}: “xuất phát điểm của KPQT” Case: dãy có thứ từ các hành động (activity), hành động được “xác định tốt” NKSK = {hành vi quan sát được} {hành vi}
-
Cộng đồng KPQT
⚫
⚫
Quan tâm KPQT: Tuyên ngôn KPQT (Process Mining Manifesto) do the IEEE Task Force on Process Mining công bố 53 tổ chức, 77 chuyên gia KPQT (người dùng, cung cấp công cụ, tư vấn, phân tích, nghiên cứu): KPDL KPQT mô hình hóa BM (quy trình kinh doanh)
[Aalst13] Wil M. P. van der Aalst (2013). Decomposing Petri nets for process mining: A
generic approach. Distributed and Parallel Databases 31(4): 471-507
18
Triết lý “đường mòn” [Aalst11]
Khai phá quy trình: cầu nối khai phá dữ liệu với khoa học quy trình
19
Vai trò của khai phá quy trình
▪ Quản lý quy trình nghiệp vụ (tự động hóa): Vòng đời hở (pha chẩn đoán: Diagnosis) theo tiếp cận truyền thống (trái), vòng đời khép kín theo tiếp cận khai phá quy trình (phải)
[Mans11] Ronny Mans. Workflow Support for the Healthcare Domain. PhD Thesis,
Eindhoven University of Technology, 2011
20
Cycle DiagramContents Nhật ký sự kiện
Dữ liệu đầu vào cho khai phá quá trình là nhật ký sự kiện. Ngầm định
dữ liệu chuẩn: ▪ Một nhật ký sự kiện bao gồm nhiều trường hợp (cases). ▪ Một trường hợp chứa nhiều sự kiện (events) được sắp xếp theo trình tự. Một trường hợp là “một lần thi hành mô hình quá trình trong thực tiễn”
▪ Mỗi sự kiện chứa các thuộc tính (attributes).
21
Nhật ký sự kiện
2 2
⚫
ticket;
request;
e-decide;
f=reinititate
⚫
⚫
⚫
⚫
a=register request; b=examine thoroughly; c=examine casually;
g=pay
d=check
compensasion, và h=reject request
Dạng đơn giản: dãy hành động {, ,…}. là một “vết” (trace)
Tập bội (multi-set): mở rộng tập thông thường, một phần tử xuất
hiện nhiều lần: Gộp {112, 99,…}
Cho tập X: tập mọi tập bội trong X ký hiệu B(X)
Định nghĩa: Cho A tập hành động, một vết của A là A* là dãy
các hành động, Một LB(A*) là một nhật ký dự kiện (trên A)
[AD13] Wil M. P. van der Aalst, Boudewijn F. van Dongen (2013). Discovering Petri
Nets from Event Logs. T. Petri Nets and Other Models of Concurrency 7: 372-422.22
Nhật ký sự kiện: khía cạnh bổ sung
⚫
⚫
⚫
Ba khía cạnh bổ sung điển hình Tổ chức: Con người, đơn vị, tổ chức… Thời gian: Tem thời gian, thời gian thực hiện, thời gian chờ, … Tài nguyên: Chi phí.
⚫ ⚫ Quy trình chung: Phát hiện mô hình quy trình từ NKSK đơn
giản, tiến hành khai phá dữ liệu các khía cạnh bổ sung
[AD13] Wil M. P. van der Aalst, Boudewijn F. van Dongen (2013). Discovering Petri Nets from Event Logs. T. Petri Nets and Other Models of Concurrency 7: 372- 422.
23
Mô hình quá trình [3]
Cycle DiagramContents Mô hình quy trình
- Mô hình quy trình được biểu diễn bằng một ngôn ngữ mô
-
-
hình hóa. Có nhiều loại ngôn ngữ mô hình hóa khác nhau như: BPMN, BPEL, UML, Petri-net,… Petri-net là mô hình thường được sử dụng để mô hình hóa quy trình và có thể chuyển đổi sang các mô hình BPMN, PBEL, UML,…
24
Ví dụ mô hình quy trình bằng lưới Petri
Lưới Petri mô hình hóa quy trình giải quyết yêu cầu bồi thường từ khách hàng của một hãng hàng không
25
Các bài toán trong khai phá quá trình
Ba bài toán khai phá quy trình Cycle DiagramContents
a) Phát hiện b) Kiểm tra phù hợp c) Tăng cường
26
Phát hiện mô hình quy trình
⚫ Là bài toán thứ nhất trong khai phá quy trình
⚫ Input: Nhật ký sự kiện. ⚫ Output: Mô hình quy trình.
⚫ Bài toán thực hiện phát hiện mô hình quy trình dựa vào thông tin trong nhật ký sự kiện mà không sử dụng bất kỳ thông tin tiền nghiệm nào.
⚫ Mô hình quy trình được biểu diễn bằng một ngôn ngữ
mô hình hóa
⚫ Có nhiều loại ngôn ngữ mô hình hóa khác nhau (BPMN,
BPEL, UML, Petri-net,…)
⚫ Petri-net thường được sử dụng để mô hình hóa quy trình và có thể chuyển đổi sang các mô hình BPMN, PBEL, UML,… khác.
27
Phát hiện quy trình và biên dịch ngược
⚫ Biên dịch ngược
▪ Decompiling/Reverse Engineering ▪ Phiên bản chương trình đích → phiên bản chương trình nguồn ▪ Bài toán khó. Mất thông tin khi biên dịch ngược. ▪ Một số tài liệu liên quan. ⚫ Phát hiện quy trình
(ngôn ngữ mô hình hóa)
▪ Phiên bản mô hình quy trình trong thi hành → mô hình quy trình
hành chương trình
▪ “Lập lại sơ đồ khối” từ biên bản chạy chương trình đích ▪ Đầu vào: không là chương trình đích, là tập các trường hợp thi
▪ “tên lệnh” và giá trị các thanh ghi ? ▪ thi hành “một lệnh” không là một máy mà có thể nhiều người
[Wang10] W. Wang. Reverse engineering: technology of reinvention. CRC, 2010 [Kadavy11] David Kadavy. Design for Hackers: Reverse Engineering Beauty. Wiley,
2011
28
[Alazard13] Daniel Alazard. Reverse Engineering in Control Design. Wiley-ISTE, 2013 [Nolan12] Godfrey Nolan. Decompiling Android. Apress, 2012 [Dang14] Bruce Dang, Alexandre Gazet, Elias Bachaalany, Sebastien Josse. Practical Reverse Engineering x86, x64, ARM, Windows Kernel, Reversing Tools, and Obfuscation. Wiley, 2014
Tiếp cận hai giai đoạn
⚫ Mô hình hai giai đoạn+ K/phá khía cạnh bổ sung ▪ Tinh chế NKSK đầu vào→phát hiện mô hình→khía cạnh bổ sung ▪ Mô hình hai giai đoạn: Tinh chế NKSK đầu vào → phát hiện mô hình ▪ Trình bày: Phát hiện mô hình→Tinh chế NKSK đầu vào→KC BS [Bose12] R. P. Jagadeesh Chandra Bose. Process Mining in the Large: Preprocessing, Discovery, and Diagnostics. PhD Thesis, Eindhoven University of Technology, The Netherlands, 2012
29
Tiền xử lý NKSK: T/tượng hóa hoạt động
[Bose09] R. P. Jagadeesh Chandra Bose, Wil M. P. van der Aalst. Abstractions in
Process Mining: A Taxonomy of Patterns. BPM 2009: 159-175, 2009.
30
Tiền xử lý NKSK: Trôi khái niệm
⚫ Trôi khái niệm trong khai phá quy trình
▪ Trôi đột ngột (sudden): thay đổi lớn, trôi dần (gradual): tiếp cận nhập pha, trôi định kỳ (Recurring): theo mùa kinh doanh, trôi gia tăng (Incremental): thay đổi duy trì
[Bose14] R. P. Jagadeesh Chandra Bose, Wil M. P. van der Aalst, Indre Zliobaite, Mykola Pechenizkiy. Dealing With Concept Drifts in Process Mining. IEEE Trans. Neural Netw. Learning Syst. 25(1): 154-171, 2014.
[Martjushev15] J. Martjushev, R. P. Jagadeesh Chandra Bose, Wil M. P. van der Aalst. Change Point Detection and Dealing with Gradual and Multi-order Dynamics in 31 Process Mining. BIR 2015: 161-178.
31
Trực quan mô hình quy trình
khía cạnh trường hợp (case perspective,
Mở rộng mô hình khi bổ sung các khía cạnh: khía cạnh tổ chức (organizational perspective, “What are the organizational roles and which resources are performing “Which particular activities?”), characteristics of a case influence a particular decision?”) và khía cạnh thời gian (time perspective, “Where are the bottlenecks in my process?”)
[Aalst11] WMP Van der Aalst (2011). Process Mining: Discovery, Conformance and
Enhancement of Business Processes, Springer, 2011.
[Aalst12] Wil M. P. van der Aalst: Process Mining: Overview and Opportunities. ACM
Trans. Management Inf. Syst. 3(2): 7 (2012)
32
Kiểm tra phù hợp
BÀI TOÁN KIỂM TRA SỰ PHÙ HỢP
Cycle DiagramContents
❖ Input:
- Nhật ký sự kiện (Event Log) - Mô hình quy trình (Model)
Các độ đo phù hợp.
❖ Output: ❖ Ứng dụng:
• Xem xét chất lượng của một mô hình quy trình. • Để xác định những trường hợp chệch hướng
và hiểu chúng có hành vi chung gì.
• Để xác định các đoạn quy trình mà ở đó hầu
hết xảy ra lệch hướng.
• Cho mục đích kiểm toán, …
33
3. GIỚI THIỆU VỀ HỌC MÁY SUỐT ĐỜI
34
Nguồn tài liệu chính
⚫ Sách
edition). Morgan & Claypool Publishers, November 2018.
▪ [Thrun96] Sebastian Thrun. Explanation-Based Neural Network
Learning: A Lifelong Learning Approach. Springer US, 1996.
⚫ Bài trình bày
▪ [Chen18] Zhiyuan Chen and Bing Liu. Lifelong Machine Learning (2nd
Data Era. A IJCAI 2015 Tutorial. 130
▪ Zhiyuan Chen and Bing Liu. Lifelong Machine Learning in the Big
to Vietnamese Text Multi-label Classification. ACIIDS 2018
⚫ Trang Web
▪ Zhiyuan Chen, Estevam Hruschka, Bing Liu. Lifelong Machine Learning and Computer Reading the Web. A KDD-2016 Tutorial. 217 ▪ DS&KTLab: A New Lifelong Topic Modeling Method and Its Application
35
▪ https://www.cs.uic.edu/~liub/lifelong-learning.html. Zhiyuan Chen ▪ https://www.cs.uic.edu/~liub/lifelong-learning.html. Bing Liu ▪ http://lifelongml.org/. Website on lifelong machine learning.
Hình ảnh Trường thu – đông Quảng Bình
36
Hình ảnh Trường thu – đông Quảng Bình
37
Tại sao học máy suốt đời?
- Học máy truyền thống: hạn chế - Học máy suốt đời: hiện diện một cộng đồng - Một dự án về học máy suốt đời
38
Học máy truyền thống (ML1.0)
⚫ Thành công
▪ Học máy thống kê: nhiều thành công đáng ghi nhận
⚫ Hạn chế
▪ Học máy cô lập: xem xét một bài toán học máy ▪ Không thừa kế được ”kinh nghiệm” từ học trước đây ▪ Không thể đáp ứng “học tựa như con người” ▪ Yêu cầu tập ví dụ huấn luyện đủ lớn
⚫ Yêu cầu
▪ “học tựa như con người” ▪ Chỉ cần tập ví dụ rất nhỏ
39
Học suốt đời (ML2.0): một hành vi trí tuệ
⚫ Nghiên cứu trí tuệ tự nhiên luôn thời sự ⚫ Một số hành vi trí tuệ liên quan tới học ▪ Học từ kinh nghiệm và áp dụng tri thức từ kinh nghiệm. ▪ Giải quyết vấn đề thiếu thông tin quan trọng ▪ Xử lý và thao tác với “biểu tượng”
⚫ Học máy suốt đời
40
▪ Thế hệ học máy thứ hai (ML2.0) ▪ Học và sử dụng tri thức từ kinh nghiệm, đặc biệt các miền văn bản ▪ Giải quyết thách thức tập ví dụ huấn luyện lớn ▪ Vấn đề: Chọn tri thức đã học để giải quyết bài toán mới
Học suốt đời: một nguồn trí tuệ [Poole17]
⚫ Di truyền sinh học ▪ Tiến hóa của loài người ▪ Sống sót được trong nhiều môi trường sống khác nhau
⚫ Văn hóa
▪ Cung cấp ngôn ngữ ▪ Các công cụ hữu dụng, các khái niệm hữu dụng, sự thông thái
từ cha mẹ và giáo viên truyền tới con cái
⚫ Học suốt đời
▪ Con người học hỏi suốt đời ▪ Tích lũy tri thức và kỹ năng ▪ Học nhanh hơn và hiệu quả hơn
[Poole17] David L Poole, Alan K Mackworth. Artificial intelligence foundations of
computational agents (2nd edition). Cambridge University Press, 2017. http://artint.info/html/ArtInt_4.html
41
Xe tự lái: một hệ thống học suốt đời
thời; (ii) Chỉnh sửa chương trình và dữ liệu
▪ Hình mô tả hệ thống học của “xe tự lái” ▪ cảm biến quét xung quanh thông báo không ngừng tới hệ thống ▪ hệ thống học sử dụng dữ liệu (i) Hướng dẫn hành động lái xe hiện
https://www.darpa.mil/news-events/2017-03-16
42
Học suốt đời: hiện diện một cộng đồng
công bố về học máy suốt đời danh sách học giả học suốt đời dự án học suốt đời chính Các sự kiện học suốt đời thông báo và tin tức học suốt đời
http://lifelongml.org/
43
Học suốt đời: một cộng đồng
Bing Liu. Sentiment Analysis Mining Opinions Sentiments and Emotions. Cambridge University Press, 2015 (11 Mining Intentions)
http://lifelongml.org/research-groups/
44
Một thư xin tài liệu
45
Một chương trình nghiên cứu
⚫ Thông tin chung
Research Projects Agency: DARPA)
▪ Quản lý chương trình: Tiến sĩ Hava Siegelmann, ▪ https://www.darpa.mil/staff/dr-hava-siegelmann, http://dblp.uni-trier.de/pers/hd/s/Siegelmann: Hava_T= (J40, C44, i7). video
⚫ Mục tiêu kỹ thuật
▪ Cơ quan nghiên cứu Bộ Quốc phòng Mỹ (Defense Advanced
▪ Cơ chế học máy: học máy liên tục áp dụng kinh nghiệm quá khứ và thích ứng "bài học kinh nghiệm" với dữ liệu/tình huống mới, phát triển kỹ thuật giám sát hành vi hệ thống học máy, đặt phạm vi khả năng thích ứng, và can thiệp vào chức năng hệ thống khi cần. Lý thuyết mạng, thuật toán, phần mềm và kiến trúc máy tính. ▪ Cơ chế học sinh học: (i) hệ sinh thái học: di truyền từ thế hệ cha → con: di truyền toàn bộ, di truyền chỉ khả năng học, v.v.?; (ii) làm thích nghi áp dụng được tới hệ thống học máy.
https://www.darpa.mil/news-events/2017-03-16
46
Học máy truyền thống liên quan
- Học chuyển đổi - Học đa nhiệm theo lô - Học trực tuyến đơn nhiệm - Học tăng cường
47
Học truyền thống và học chuyển đổi
⚫ Học truyền thống và Học chuyển đổi
▪ Học truyền thống: (i) Cho bài toán/miền A: có dữ liệu có nhãn để dạy mô hình A, áp dụng mô hình tới dữ liệu chưa nhãn của A; (ii) Cho bài toán/miền B: cần đủ ví dụ mẫu cho B; (iii) Không liên hệ học A và B
▪ Học chuyển đổi: (i) Transfer learning/domain adaptation (thích ứng miền); (ii) Miền B: một/nhiều miền nguồn, nhiều dữ liệu có nhãn; Miền đích A: ví dụ mẫu ít/vắng; (iii) Liên kết học B tới A ; (iv): Giả thiết quan trọng: miền nguồn “tương tự” miền đích : tri thức miền B dùng cho học miền đích A
www.comp.nus.edu.sg/~leews/MLSS/Transfer1.pptx
48
Học chuyển đổi và học suốt đời
⚫ Kiểu truyền tri thức miền nguồn cho miền đích ▪ chuyển dịch “ví dụ có nhãn nguồn” → “ví dụ có nhãn đích”; NLP ▪ chuyển dịch “đặc trưng nguồn” → “đặc trưng đích” ▪ Học tương ứng cấu trúc Structural Correspondence Learning: SCL: ứng dụng văn bản, “dấu hiệu đặc trưng” cùng xuất hiện ở hai miền “đặc trưng then chốt”, ví dụ từ phổ biến ở cả hai miền
⚫ Phân biệt học suốt đời với học chuyển đổi ▪ Học chuyển đổi không học liên tục và không tích lũy tri thức ▪ Học chuyển đổi là một chiều ▪ Học suốt đời không đòi hỏi yêu cầu tương tự miền
▪ Học sâu (deep learning) trong học chuyển đổi.
Textual Entailment: Minh Quang Nhat Pham, Minh Le Nguyen, Akira Shimazu. An Empirical Study of Recognizing Textual Entailment in Japanese Text. CICLing (1) 2012: 438-449; Quang-Thuy Ha, Thi-Oanh Ha, Thi-Dung Nguyen, Thuy-Linh Nguyen Thi. Refining the Judgment Threshold to Improve Recognizing Textual Entailment Using Similarity. ICCCI (2) 2012: 335-344.
VietSentiWordNet: Quang-Thuy Ha, Tien-Thanh Vu, Huyen-Trang Pham, Cong-To Luu.An Upgrading Feature-Based Opinion Mining Model on Vietnamese Product Reviews. AMT 2011: 173-185.
49
Học đa nhiệm theo lô và học suốt đời
⚫ Giới thiệu
⚫ Giả thiết các bài toán có liên quan chặt
▪ multi-task learning/batch multi-task learning “theo lô” ▪ Định nghĩa: học nhiều bài toán 𝒯 = {1, 2, …, N} đồng thời, mỗi bài toán j có dữ liệu học Dj. Mục tiêu tối ưu hóa hiệu năng mọi bài toán
“tựa” trên một mô hình tổng quát
▪ Dữ liệu bài toán trong cùng một không gian, các mô hình bài toán
⚫ Phân biệt học suốt đời với học đa nhiệm theo lô
▪ Sử dụng chung tập đặc trưng
không sử dụng khái niệm học liên tục
▪ Cùng mục địch chia sẻ thông tin hỗ trợ việc học. ▪ Học đa nhiệm theo mô hình truyền thống: không tích lũy tri thức,
thức cho học về sau
50
▪ Học đa nhiệm trực tuyến: một kiểu học suốt đời do có giữ lại tri
Học trực tuyến đơn nhiệm& học suốt đời
⚫ Giới thiệu
▪ Online machine learning ▪ Định nghĩa: Điểm dữ liệu huấn luyện diễn ra tuần tự theo một thứ tự nhất định, khi điểm dữ liệu mới xuất hiện mô hình hiện tại được cập nhật để phù hợp tốt nhất
▪ Là một mô hình học theo ghi nhớ
⚫ Phân biệt học suốt đời với học trực tuyến
▪ Học trực tuyến: Thực hiện chỉ một bài toán theo thời gian, không lưu tri thức, không sử dụng tri thức từ trước. ▪ Học suốt đời: học một chuỗi bài toán khác nhau, lưu và
51
sử dụng tri thức hỗ trợ bài toán mới
Học tăng cường và học suốt đời
⚫ Giới thiệu
đánh giá lỗi” trong môi trường động. Mục đích:
▪ Reinforcement Learning: RL ▪ Định nghĩa: học cách hành động theo tiếp cận tương tác “thử và
▪ Thử và đánh giá lỗi trong mỗi bước tương tác: (i) nhận input chứa trạng thái môi trường hiện thời; (ii) Chọn một hành động trong tập hành động có thể → thay đổi môi trường, (iii) Tính lại giá trị trạng thái môi trường: thưởng hoặc phạt.
động để cực đại tổng thưởng trong thời gian dài.
⚫ Phân biệt học suốt đời với học tăng cường
▪ Học tăng cường:
▪ Học được quỹ đạo tối ưu hóa mục tiêu ánh xạ trạng thái → hành
52
❖ chi phạm vi một bài toán và ở một môi trường, ❖ không tích lũy và sử dụng tri thức.
Học máy suốt đời là gì?
- Thrun 1996 - Silver 2013 - Z. Chen và B. Liu 2014-2016
53
Học mạng nơ-ron giải thích EBNN [Thrun96]
⚫ EBNN:Explanation-based neural network learning ▪ Tích hợp học quy nạp và học phân tích. Mức cơ sở, mức meta EBNN. ▪ Học quy nạp: EBNN biên dịch tập hỗ trợ Y thành lý thuyết miền:
tri thức mức meta. Tập ràng buộc. Sử dụng tri thức kinh nghiệm.
54
▪ Học phân tích: Ví dụ học trong tập học X được giải thích và phân tích theo lý thuyết miền, lấy được thông tin dốc cho hàm đích: tri thức mức cơ sở. Thông tin độ dốc được kết hợp vào học mạng nơ-ron.
Lựa chọn tri thức kinh nghiệm
⚫ Bài toán học
▪ Học giám sát: Cho một ánh xạ F: I→O, tập ví dụ {
tập giả thuyết.
▪ Tồn tại một tập các tập giả thuyết đối với các bài toán học ▪ Học thiên vị (learning bias): Học hàm f* có sử dụng thiên vị từ các
55
▪ Ví dụ: các giả thuyết Ho, H1, H2, H3, H4 →H4 thiên vị tốt nhất ▪ Hi tập ví dụ học bài toán học Fi “tập hỗ trợ”
Khung học suốt đời [Silver13]
⚫ Định nghĩa hệ thống học máy suốt đời
56
▪ Học nhiều bài toán trong suốt vòng đời từ một hoặc nhiều miền ▪ Duy trì tri thức học được một cách hiệu suất và hiệu quả ▪ Sử dụng tri thức đó để học bài toán mới một cách hiệu suất và hiệu quả
Giải thích [Silver13]
⚫ Duy trì hiệu suất và hiệu quả
▪ Hiệu quả (i) Ngăn ngừa tiến cử /sử dụng tri thức lỗi; (ii) Lưu dài hạn giả thuyết đủ chính xác tổng quát hóa, (ii) Thêm giả thuyết không giảm độ chính xác mọi giả thuyết cũ/mới, (iv) Tích hợp/hợp nhất tri thức mới: tăng độ chính xác tri thức cũ
⚫ Học hiệu suất và hiệu quả
▪ Hiệu suất: về không gian bộ nhớ lưu giữ và thời gian tính toán.
⚫ Các thành phần chính
▪ Hiệu năng giả thuyết mới hiệu năng giả thuyết từ tập ví dụ học ▪ Dùng tri thức quá khứ cần ra mô hình bài toán mới chính xác hơn ▪ Lựa chọn tri thức liên quan nhất để thiên vị mô hình bài toán mới. ▪ Lựa chọn tri thức quá khứ nên giảm thời gian học
thức.
57
▪ Duy trì (hợp nhất) tri thức bài toán đã học ▪ Chuyển giao tri thức chọn lọc để học bài toán mới ▪ Hệ thống hóa tương tác hiệu suất và hiệu quả duy trì/chuyển giao tri
Hệ thống học suốt đời [Isele17]
[Isele17] David Isele, Mohammad Rostami, Eric Eaton. Using Task Descriptions in
Lifelong Machine Learning for Improved Performance and Zero-Shot Transfer. CoRR abs1710.03850 (2017)
58
Học máy suốt đời [Chen and Liu, 2016]
⚫ Định nghĩa học suốt đời
▪ Mục tiêu: Tối ưu hóa bài toán TN+1/Tối ưu hóa mọi bài toán T1, T2,
…, TN, TN+1.
⚫ Một số nhận xét
▪ Một quá trình học liên tục ▪ Tại thời điểm bất kỳ: (i) bộ học đã hoàn thành một chuỗi N bài toán/với tập dữ liệu học T1/D1, T2/D2, …, TN/DN: Ti thuộc 1/nhiều kiểu bài toán thuộc một miền hoặc nhiều miền; (ii) Gặp bài toán mới/hiện tại TN+1/DN+1, sử dụng tri thức quá khứ trong CS tri thức KB để học bài toán TN+1.
▪ Định nghĩa ở mức chung chung cần được diễn giải. ▪ Ba đặc trưng chính: học liên tục, tích lũy và duy trì tri thức trong KB → học một loạt bài toán, học có thể không dừng, học ngày càng thông thạo và học tốt hơn.
xuất thông tin, liên kết thực thể)
▪ Khái niệm “miền” (không gian đặc trưng) và “kiểu bài toán” (trích
59
▪ Bài toán mới xuất hiện đột ngột hoặc từng bước.
Tri thức mức cao [Chen and Liu, 2016]
⚫ Hai kiểu tri thức quá khứ
▪ Tri thức quá khứ phổ quát và tri thức chia sẻ được ▪ Tri thức toàn cục: Ngầm định một cấu trúc ẩn chia sẻ cho mọi bài toán. Cấu trúc ngầm định này được học, tận dụng bài toán mới
▪ Tri thức cục bộ: Không có ngầm định trên. Cần chọn mẩu tri thức theo nhu cầu bài toán hiện tại. Tối ưu hóa kết quả bài toán hiện thời dựa trên tri thức quá khứ
⚫ Hai loại bài toán
▪ Bài toán độc lập: Có khai thác tri thức quá khứ song các bài toán độc lập nhau. Hầu hết theo hướng bài toán độc lập
▪ Bài toán phụ thuộc: Các bài toán có sự phụ thuộc nhau
60
Khung học máy suốt đời [Chen and Liu, 2016]
⚫ Giới thiệu
▪ Có chuyển giao thông tin từ các bước
61
▪ Bốn thành phần chính: Cơ sở tri thức (Knowledge Base: KB), Bộ học dựa trên tri thức (Knowledge-Based Learner: KBL), Bộ quản lý bài toán (Task Manager: TM) và Đầu ra
Cơ sở tri thức
⚫ Giới thiệu chung
⚫ Kho thông tin quá khứ
▪ Cơ sở tri thức gồm có: Kho thông tin quá khứ (Past Information Store: PIS), Bộ khai phá siêu tri thức (Meta-Knowledge Miner: MKM), Kho siêu tri thức (Meta-Knowledge Store: MKS) và Bộ suy luận tri thức (Knowledge Reasoner: KR)
kết quả trung gian, (iii) mô hình/mẫu kết quả học được.
▪ Lưu thông tin học trong mỗi bài toán quá khứ: (i) dữ liệu gốc, (ii)
⚫ Bộ khai phá siêu tri thức
▪ Khai phá siêu tri thức từ PIS và MKS (siêu khai phá: meta-mining).
Tri thức kết quả được lưu vào MKS.
⚫ Kho siêu tri thức và Bộ suy luận tri thức
▪ Người dùng quyết định cần giữ lại gì để giúp việc học tương lai.
62
▪ MKS: Biểu diễn tri thức phù hợp ▪ KR: suy luận dựa trên tri thức MKS, thông tin PIS ra tri thức mới
Ba thành phần khác
⚫ Bộ học dựa trên tri thức
▪ Bộ học: Sử dụng tri thức khai phá được vào học bài toán mới.
⚫ Đầu ra
▪ Hai thành phần con: dùng tri thức quá khứ từ KB học bài toán mới ▪ Bộ khai phá tri thức bài toán (Task knowledge miner: TKM): dùng tri thức thô/thông tin từ KB để khai phá/xác định tri thức phù hợp bài toán hiện tại. Cần tri thức đặc tả bài toán và tri thức tổng quát hơn được khai phá từ KB
đề…
⚫ Bộ quản lý bài toán
▪ Kết quả học cho người dùng: mô hình dự báo/phân lớp, cụm chủ
bài toán và đề xuất bài toán học mới cho KBL
63
▪ nhận và quản lý các bài toán đi tới hệ thống và xử lý việc thay đổi
Mô hình chủ đề suốt đời
- Biểu diễn văn bản - Hai tiếp cận mô hình chủ đề suốt đời - Một tiếp cận mới
64
Các bước khai phá dữ liệu văn bản
⚫ Giải thích
pháp, v.v.)
▪ Nguồn văn bản: Nội bộ, Internet, kết hợp ▪ Chọn lọc tập dữ liệu miền bài toán: văn bản, trang web, nhận xét… ▪ Tiền xử lý dữ liệu (tách câu, tách từ, gán nhãn từ loại, phân tích cú
hướng ngữ nghĩa
▪ Lựa chọn đặc trưng, biểu diễn văn bản: phù hợp thuật toán, định
65
▪ Thực hiện thuật toán sinh mô hình kết quả ▪ Đánh giá: tốt đưa vào sử dụng
Lựa chọn từ trong biểu diễn văn bản
⚫ Loại bỏ từ dừng
➢ Những từ được coi là không mạng nghĩa ➢ Có sẵn trong ngôn ngữ
⚫ Đưa về từ gốc
➢ Các ngôn ngữ có biến dạng từ: Anh, Nga… ➢ Thay từ biến dạng về dạng gốc ⚫ Chon đặc trưng n-gram
➢ Các âm tiết liền nhau n-gram ➢ Uni-gram: chỉ chứa một âm tiết ➢ Bigram: chứa không quá 2 âm tiết ➢ Trigram: chứa không quá 3 âm tiết ➢ N-gram: Thường không quá 4 gram
➢ Một số đặc trưng
➢ Chính xác hơn về ngữ nghĩa ➢ Tăng số lượng đặc trưng ➢ Tăng độ phức tạp tính toán
66
Đặc trưng chủ đề ẩn
⚫ Đặc trưng chủ đề LSI
▪ LSI: Latent Semantic Indexing biểu diễn ngữ nghĩa ẩn
▪ Nâng mức ngữ nghĩa (trừu tượng) của đặc trưng ▪ Rút gọn tập đặc trưng, giảm số chiều không gian biểu diễn ▪ Không gian từ khóa không gian khái niệm (chủ đề).
▪ Phương pháp chuyển đổi
➢ Ma trận trọng số ma trận hạng nhỏ hơn ➢ Phép biến đổi : Từ khóa khái niệm. Thay thế biểu diễn. ➢ Hidden Topic Model
⚫ Đặc trưng “nhúng”
➢ Học không giám sát hình thái (morphology) từ ➢ W={w|wC: kho ngữ liệu}→V={v|vV: không gian ngữ nghĩa} ➢ Ba vấn đề: từ hiếm, từ khó hiểu “OOV”, phân bố từ “đuôi dài“ (long tail) → bùng nổ tham số; ví dụ, cỡ vector 300 từ, từ điển 10K từ → 3 triệu tham số.
67
Biểu diễn văn bản
⚫ Bài toán
➢ Input: Cho tập văn bản miền ứng dụng D = {dj }, tập đặc trưng được chọn biểu diễn văn bản V = {wi }, ma trân trọng số W = (wi,j) .
➢ Output: Tìm biểu diễn của các văn bản dj D.
⚫ Một số mô hình ➢ Mô hình Boolean ➢ Mô hình không gian vector ➢ Mô hình túi các từ (Mô hình xác suất) ➢ Các mô hình khác ⚫ Mô hình Boolean
➢ Tập các từ thuộc V xuất hiện trong văn bản
68
Biểu diễn không gian vector
⚫ Giới thiệu
➢ Ánh xạ tập tài liệu vào không gian vector n =|V| chiều. ➢ Mỗi tài liệu được ánh xạ thành 1 vector
di (wi1, wi2, …, win) ⚫ Độ đo tương tự nội dung văn bản ➢ Chuẩn hóa vector: đưa về độ dài 1
➢ Độ “tương tự nội dung” giữa hai văn bản độ tương tự
giữa hai vector
➢ Một số phương án sơ khai “các thành phần giống nhau”,
“nghịch đảo khoảng cách”, ..
➢ Phổ biến là tính độ đo cosin của góc giữa hai
vector: không yêu cầu chuẩn hóa
69
Mô hình chủ đề suốt đời [Chen&Liu 2016]
⚫ Miền bài toán
/ phân tích đánh giá
(semitiment analysis)
▪ Khai phá quan điểm (opinion mining)
▪ Học suốt đời “nhiều miền” đối tượng khác nhau: nhận xét điện thoại di động, máy ảnh, bộ phim, v.v. phát hiện “khía cạnh” “aspects”
⚫ Khung học máy suốt đời: Xem xét CSTT ▪ Tri thức quá khứ nào nên được lưu giữ lại và tích lũy? ▪ Những tri thức nào nên được sử dụng trong mô hình miền mới và
làm thế nào để khai phá những tri thức đó ?
▪ Mô hình chủ đề của Blei và cộng sự năm 2003
đối phó với tri thức có thể sai?
▪ Làm thế nào để áp dụng tri thức vào quá trình mô hình hóa để tạo
ra các chủ đề tốt hơn trong miền ứng dụng mới?
70
▪ Làm thế nào để đánh giá chất lượng của tri thức và làm thế nào để
Tri thức chia sẻ: Must-links & cannot-links
⚫ Ví dụ ba miền: vấn đề với chủ đề
▪ Ba miền cùng có chủ đề ẩn “giá cả” ▪ Xem xét bốn từ tốp đầu thuộc chủ đề “giá cả” ❖ Miền 1: giá cả, màu sắc, chi phí, cuộc sống ❖ Miền 2: chi phí, hình ảnh, giá cả, đắt tiền ❖ Miền 3: giá cả, tiền, khách hàng, đắt tiền ❖ “hình ảnh”, “màu sức”, v.v. không mang ý nghĩa “giá cả”
⚫ Ý tưởng
▪ Các cặp từ thuộc “đa số” miền (2) “tập phổ biến độ dài 2” ❖ Miền 1,2: {giá cả, chi phí} cho một cặp từ (giá cả, chi phí) ❖ Miền 2,3: {giá cả, đắt tiền} cho một cặp từ (giá cả, đắt tiền) ❖ Miền 1,3: {giá cả} không có cặp từ nào
▪ Cặp hai từ must-links nên ở cùng một chủ đề mới ▪ Tương tự: cặp hai từ tại đa số miền ở hai chủ đề khác biệt nhau “mẫu âm độ dài 2”: cannot-links không nên ở cùng một chủ đề mới
71
Sơ đồ LTM (Lifelong Topic Model)
⚫ Bài toán ▪ N bài
toán: Ti, Di (dữ liệu bài toán Ti), Topicsi (tập chủ đề từ tập Di): chủ đề trước. KB= {Topicsi, i=1, 2, … N}
khai
toán mới TN+1 với DN+1 xuất hiện (DN+1 lượng phù hợp). Tìm thác TopicsN+1 được tri thức từ KB.
⚫ Mô hình
▪ Bài
72
▪ Mẩu tri thức must-links dùng để tinh chỉnh TopicsN+1. Hình vẽ
LTM: Thuật toán chính
73
LTM: Thuật toán con tìm must-links
⚫ Giải thích: symmetrized Kullback-Leibler (KL) Divergence
▪ Dòng 2: p (chủ đề cũ): chọn chủ đề mới a gần nó nhất KL ▪ Dòng 3: Độ phân biệt KL (p,a) : thêm p vào tập chủ đề liên quan a ▪ Dòng 7: Tìm must-links với a và thêm vào KN+1.
74
LTM: Tinh chỉnh chủ đề mới
Simple Pólya Urn model (SPU)
⚫ Giải thích
▪ Must-links: Tri thức sẵn có để tinh chỉnh chủ đề mới trong lấy mẫu
Gibbs
75
▪ Sử dụng mô hình Pólya Urn đơn giản
Mô hình AMC:
⚫ Bài toán
bài
toán
▪ N bài toán: Ti, Di (dữ liệu Ti), Topicsi (tập chủ đề từ tập Di): chủ đề trước. KB= {Topicsi, i=1, 2, … N}
▪ Bài toán mới TN+1 với DN+1 xuất hiện (DN+1 Tìm nhỏ). lượng TopicsN+1 thác khai được tri thức từ KB.
⚫ Mô hình ▪ Mẩu tri
AMC: Automatically generated Must-links and Cannot-links
thức must- links và cannot-links dùng để tinh chỉnh TopicsN+1. Hình vẽ
76
ACM: Chương trình chính
⚫ Giải thích
77
▪ Khai phá must-links như LTM ▪ Chạy lấy mẫu Gibbs tạo tập chú đề ẩn không có cannot-links ▪ Lần lượt tìm cannot-links tinh chỉnh lại chủ đề hiện tại
AMC: Tinh chỉnh chủ đề mới
Multi- generalized Pólya Urn model (MGPU)
⚫ Giải thích
▪ Must-links: Tri thức sẵn có để tinh chỉnh chủ đề mới trong lấy mẫu
Gibbs
78
▪ Sử dụng mô hình Multi-generated Pólya Urn cho cannot-links
Một mô hình đề xuất [ACIIDS2018]
Quang-Thuy Ha, Thi-Cham Nguyen et al.
⚫ Giải thích
79
▪ Dựa trên AMC ▪ Thiên vị mức “miền dữ liệu”: chỉ lấy miền dữ liệu gần S* ▪ Định nghĩa độ gần nhau: mức chủ đề và mức miền ▪ Mức miền: tập từ vựng, tập từ tốp đầu, lượng chủ đề gần nhau ▪ Mức chủ đề: độ đo cosine cho hai túi từ có trọng số
Áp dụng phân lớp đa nhãn văn bản
Kiểm thử một mẫu cho kỳ vọng giả thuyết quần thể với phương sai chưa biết: kết quả tăng thực sự so với AMC
80
WordNet và mô hình chủ đề suốt đời
⚫ WordNet chung: Thành phần kho tri thức
[Chen16] ▪ Đề cập cơ sở tri thức KB khởi đầu: | WordNet ▪ Tiếp theo: chỉ đề cập tới KB khởi đầu
⚫ Vấn đề
▪ ? Sử dụng WordNet: tính đa nghĩa của từ, đồng nghĩa/nghịch
nghĩa có ngư cảnh các từ.
81
▪ Đồng nghĩa: mustlinks, nghịch nghĩa: Cannotlinks ▪ Vấn đề: “ngữ cảnh” đồng nghĩa/nghịch nghĩa ▪ Wordnet chung hay WordNet tự xây dựng ? ▪ Wordnet chung: sẵn có VietWordNet từ KC.01.02/06-10 ▪ Wordnet tự xây dựng: liên quan tới từng miền
Học sâu suốt đời: một chủ đề nghiên cứu
⚫ Các chủ đề nghiên cứu về học suốt đời
▪ Học suốt đời phân lớp và hồi quy (Lifelong Learning for
Classification and Regression)
thông tin cấu trúc (Lifelong Learning of
▪ Học suốt đời người máy (Lifelong Robot Learning) ▪ Học suốt đời
Structured Information)
82
▪ Học tăng cường suốt đời (Lifelong Reinforcement Learning) ▪ Học suốt đời với chuyển giao tri thức mức cao (Few-Shot Transfer in Lifelong Learning). David Isele. http://dblp.uni- trier.de/pers/hd/i/Isele:David . ACIIDS 2018? ▪ Học sâu suốt đời (Deep Lifelong Learning) ▪ Học suốt đời mô hình người dùng và cung cấp đám đông (Lifelong Learning for User Modeling and Crowdsourcing)
Học sâu: Nhận định của François Chollet
⚫ An Interview with François Chollet
https://research.google.com/pubs/105096.html
▪ François Chollet, ít thông tin cá nhân
https://www.linkedin.com/in/fchollet
https://www.kaggle.com/rankings
bố
nhiều
không
http://dblp.uni-
Công trier.de/pers/hd/c/Chollet:Fran=ccedil=ois ▪ Hạng Kaggle cao nhất đạt được: 17th toàn cầu ▪ AI và học sâu của Google ▪ Tác giả: (i) Keras: khung học sâu Python hàng đầu nguồn mở: Google Scholar Cited 1060, (ii) Sách "Deep Learning with Python“
▪ https://www.datacamp.com/community/blog/int
erview-francois-chollet
/deep-learning-python
▪ [Chollet18] François Chollet. Deep Learning
▪ https://www.datacamp.com/community/tutorials
with Python. Manning, 2018
83
Học sâu: Hạn chế [Chollet18] ⚫ Giới thiệu
⚫ Học sâu và hạn chế
▪ Hạn chế của học sâu ▪ Học sâu suốt đời: Một chủ đề nghiên cứu thời sự
sâu ánh xạ X → Y
▪ Học sâu “vô hạn” ứng dụng ▪ nhiều ứng dụng ngoài tầm học sâu dù có rất nhiều ví dụ mẫu ▪ X={mô tả sản phẩm phần mềm do một người quản lý viết} ▪ Y={mã nguồn đáp ứng mô tả do một đội viết} ▪ Cho 105 (106) cặp (x, y) XY. Không thể sinh một mô hình học
▪ Giải thích: học xâu = chuỗi các phép biến đổi hình học đơn giản và liên tục: X → Y (hai không gian vector) ngầm định dãy biến đổi liên tục từ X sang Y.
trình không thể biểu diễn bằng mô hình học sâu
▪ Chồng lấp mô hình chỉ giảm thiểu mà không giải quyết
▪ Một mô hình học sâu là một chương trình song hầu hết chương
https://blog.keras.io/the-limitations-of-deep-learning.html
84
Hạn chế học sâu: ví dụ 1
phân loại ảnh gấu trúc thành vượn
“Cậu bé đang cầm cây gậy bóng chày”
⚫ Rủi ro nhân cách hóa mô hình học máy
▪ anthropomorphizing ▪ Nhận dạng ảnh: chỉ một thay đổi nhỏ cho kết quả khác biệt ▪ Giải thích: mô hình học sâu không hiểu gì về đầu vào như con người ▪ Con người hiểu biết về hình ảnh, âm thanh, ngôn ngữ
[Chollet18] François Chollet. Deep Learning with Python. Manning, 2018
85
Hạn chế học sâu: Ảnh mờ trong gương
Trải nghiệm con người
Thế giới thực
Mô hình học máy
Tóm tắt khái niệm vào tâm trí người
Dữ liệu có nhãn minh hoạ khái niệm
Khớp với dữ liệu học
Không khớp với mô hình tâm trí người dẫn xuất
Không phải lúc nào cũng chuyển tốt tới thế giới thực
⚫ Lưu ý chuyên gia học máy
86
▪ Tránh rơi vào bẫy miền tin “mạng nơ-ron hiểu được bài toán cần làm” ▪ Thực hiện nhiệm vụ hẹp hơn so với mong muốn con người ▪ Dữ liệu khác ví dụ học: mạng nơ-ron phá vỡ một cách vô lý [Chollet18] François Chollet. Deep Learning with Python. Manning, 2018
Học sâu khác biệt với người học ⚫ Khái quát hóa cục bộ khái quát hóa tới cực
▪ Học sâu: biến dạng hình học đơn giản từ đầu vào tới đầu ra.
Khái quát hóa cục bộ (local generalization)
▪ “Con” người học: qua trải nghiệm bản thân thay vì được trình
diễn qua ví dụ học
huống hiện thời, dùng mô hình cho tương lai
▪ Năng lực cao > ánh xạ kích thích trực tiếp để đáp ứng trực tiếp ▪ Duy trì các mô hình phức tạp, tóm tắt các mô hình cho tình
▪ Khái quát hóa “cận biên” (extreme generalization)
[Chollet18] François Chollet. Deep Learning with Python. Manning, 2018
87
Tương lai học sâu: suy đoán [Chollet18]
⚫ Mô hình như là một chương trình máy tính
và trừu tượng hóa)
▪ Từ khái quát hóa cục bộ tới khái quát hóa cận biên (lập luận
▪ Hiện tại: thành phần học của hệ thống chỉ xảy ra ở mô đun chuyên dụng. Tương lai: hệ thống học đầy đủ, không có sự tham gia của con người
algorithmic primitives
geometric primitives
[Chollet18] François Chollet. Deep Learning with Python. Manning, 2018
88
Truyền ngược, phân biệt và học tự động
⚫ Vượt qua tầng lan truyền ngược, sự phân biệt
(phân biệt) song toàn bộ chương trình là không phân biệt
▪ “Chương trình” mô hình vẫn sử dụng chương trình con hình học
⚫ Học máy tự động
▪ Tương lai: học kiến trúc mô hình ▪ Tìm kiếm kiến trúc phù hợp dựa trên học tăng cường và học di
truyền
▪ Lan truyền ngược là cách thức không nên chọn ▪ Không phân biệt toàn bộ song phân biệt cục bộ
▪ Học kiến trúc mô hình đồng thời với trọng số mô hình ▪ Thay thế công việc của kỹ sư học máy → kỹ sư học máy hướng mô hình tới mục tiêu kinh doanh, mô hình tác động tới hệ sinh thái kỹ thuật số
[Chollet18] François Chollet. Deep Learning with Python. Manning, 2018
89
Học sâu suốt đời: tái sử dụng mô-đun
mức miền, được tổ chức vào thư viện
▪ Chương trình con thuật toán (Algorithmic subroutine): tri thức
▪ Chương trình con hình học (Geometric subroutine): tri thức mức
dữ liệu cụ thể liên quan tới thuật toán học sâu [Chollet18] François Chollet. Deep Learning with Python. Manning, 2018
90
Học sâu suốt đời ⚫ Nhận diện thực thể
▪ Lei Shu, Hu Xu, Bing Liu. Lifelong Learning CRF for Supervised Aspect Extraction. ACL (2) 2017:148-154. Học suốt đời nhận diện thực thể ▪ Lei Shu, Bing Liu, Hu Xu, Annice Kim. Lifelong-RL: Lifelong Relaxation Labeling for Separating Entities and Aspects in Opinion Targets. EMNLP 2016: 225-235. Học suốt đời nhận diện thực thể
▪ Chen Tessler, Shahar Givony, Tom Zahavy, Daniel J. Mankowitz, Shie Mannor. A Deep Hierarchical Approach to Lifelong Learning in Minecraft. AAAI 2017: 1553-1561. Học sâu dữ liệu ảnh
⚫ Học sâu suốt đời phân lớp đa nhãn
▪ Lei Shu, Hu Xu, Bing Liu. DOC: Deep Open Classification of Text
Documents. EMNLP 2017: 2911-2916. Học sâu
▪ Geli Fei, Shuai Wang, Bing Liu. Learning Cumulatively to Become More Knowledgeable. KDD 2016: 1565-1574. Phân lớp sâu suốt đời = học tích lũy + học sâu (trên)
▪ Quang-Thuy Ha, Thi-Ngan Pham, Van-Quang Nguyen, Thi-Cham Nguyen, Thi-Hong Vuong, Minh-Tuoi Tran and Tri-Thanh Nguyen. A New Lifelong Topic Modeling Method and Its Application to Vietnamese Text Multi-label Classification. ACIIDS 2018 (in press). Phân lớp đa nhãn dựa trên mô hình chủ đề suốt đời.
91
Một dự án học sâu suốt đời ⚫ Giới thiệu
▪ Do Eric Eaton chủ trì, được AFRL và DARPA tài trợ ▪ https://www.grasp.upenn.edu/projects/lifelong-deep-
learning ▪ Xem [Isele17]
92
Học sâu suốt đời
⚫ Một vài tham khảo khác
▪ David Isele. Thesis Proposal: Representations for Continuous Learning. the Thirty-First AAAI Conference on Artificial
Proceedings of Intelligence (AAAI-17). https://www.grasp.upenn.edu/people/david-isele https://www.grasp.upenn.edu/labs/lifelong-machine-learning
▪ Simon Stiebellehner, Jun Wang, Shuai Yuan. Learning Continuous User Representations through Hybrid Filtering with doc2vec. arXiv:1801.00215.
Improving Zero-Shot Transfer
▪ Andrei A. Rusu, Neil C. Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, Raia Hadsell. Progressive Neural Networks. CoRR abs/1606.04671, 2016 ▪ Irina Higgins, Arka Pal, Andrei A. Rusu, Loïc Matthey, Christopher Burgess, Alexander Pritzel, Matthew Botvinick, Charles Blundell, in Alexander Lerchner. DARLA: Reinforcement Learning. ICML 2017: 1480-1490
▪ James Kirkpatrick et al. Overcoming catastrophic forgetting in neural
networks. CoRR abs/1612.00796, 2016.
▪ v.v.
93
GIỚI THIỆU VỀ HỌC MÁY THẾ GIỚI MỞ
94
Tài liệu nghiên cứu ⚫ [Chen18] Zhiyuan Chen, Bing Liu. Lifelong Machine Learning (2nd edittion). Morgan & Claypool, 2018 ▪ CHAPTER 5. Open-World Learning ▪ [Bendale15] Abhijit Bendale and Terrance E Boult. Towards open world IEEE Conference on Computer Vision and Pattern
recognition. Recognition, pages 1893–1902, 2015.
▪ [Fei16] Geli Fei and Bing Liu. Breaking the closed world assumption in
text classification. NAACL-HLT, pages 506–514, 2016.
▪ [Fei16a] Geli Fei, Shuai Wang, Bing Liu. Learning Cumulatively to
Become More Knowledgeable. KDD 2016: 1565-1574.
▪ [Shu17] Lei Shu, Hu Xu, Bing Liu. DOC: Deep Open Classification of
Text Documents. EMNLP 2017: 2911-2916.
▪ Lei Shu, Hu Xu, Bing Liu. Unseen Class Discovery in Open-world
Classification. CoRR abs/1801.05609, 2018
knowledge
learning
engine
for
continuous
a ArXiv:1802.06024, 2018
95
▪ CHAPTER 8. Continuous Knowledge Learning in Chatbots ▪ [Mazumder18] Sahisnu Mazumder, Nianzu Ma, and Bing Liu. Towards chatbots.
Ví dụ minh họa 1: Người máy chào hỏi ⚫ Người máy chào đón khách hàng ở cửa ra-vào ▪ Với mỗi khách hàng quen: Có ảnh, tên khách hàng, thông tin
khác và mô hình đoán nhận khách hàng từ ảnh
▪ Một khách hàng tới cửa ra –vào. Người máy chụp ảnh, sử dụng
mô hình đoán nhận khách hàng để biết tên khách hàng.
⚫ Tiếp cận học máy thế giới đóng
hình phân lớp mới.
⚫ Tiếp cận học máy thế giới đóng
▪ Số lớp = số lượng khách hàng quen + k “lớp chưa biết” ▪ Khách quen: phát hiện lớp, chào hỏi theo tên ▪ Khách lạ: bổ sung dữ liệu về khách như chụp thêm ảnh nhận diện, đàm thoại với khách hàng hoặc người quản lý để biết tên và các thông tin khác về khách hàng. Chào hỏi theo tên. Xây dựng mô hình đoán nhận khách hàng theo ảnh.
96
▪ Số lớp = số lượng khách hàng quen + 01 “lớp chưa biết” ▪ Khách quen: phát hiện, chào hỏi theo tên ▪ Khách lạ: phân vào lớp chưa biết và đợi người quản lý nạp mô
Ví dụ minh họa 2: Chatbot với chủ đề mới ⚫ Đàm thoại chatbot
hình phân lớp từ ví dụ học liên quan tới mỗi chủ đề
▪ Khởi động một đàm thoại mới: Sử dụng các mô hình phân lớp
để nhận diện chủ đề của đàm thoại hiện thời
⚫ Tiếp cận thế giới đóng
▪ Chatbot đã nhận biết được một số chủ đề cho trước theo mô
lớp phát hiện chủ đề người đàm thoại nêu ra.
▪ Người đàm thoại nêu câu đàm thoại, dùng các mô hình phân
không tự nhiên
⚫ Tiếp cận thế giới mở
▪ Sử dụng cơ sở tri thức cho chủ đề chưa biết: suy luận tuy nhiên
thức, đàm thoại người dùng để thêm tri thức dữ kiện.
▪ Số lớp = số chủ đề đã biết + k lớp “khác đi” ▪ Câu đàm thoại thuộc chủ đề: tiếp tục trợ giúp ▪ Câu đàm thoại không thuộc chủ đề đã biết. Sử dụng Cơ sở tri
thoại bổ sung.
97
▪ Xây dựng mô hình phân lớp theo các chủ đề liên quan với đàm
Ví dụ minh họa 3: Xe tự lái trên đường
⚫ Xe tự lái
⚫ Chỉ có thể tiếp cận thế giới mở
▪ Muôn màu “vật” có thể gặp trên đường ▪ Có mô hình liên quan tới các kiểu đối tượng “đã biết” ▪ Xuất hiện không ngừng các đối tượng “chưa biết”
thông tin về đối tượng chưa biết
▪ Bài toán rất phức tạp ▪ Ghi nhận dữ liệu đối tượng chưa biết và tương tác để có thêm
⚫ Qua ba ví dụ
▪ Tương tác: (i) người giám sát, (2) khách hàng, (3) đa tác tử: kết nối với các xe đang vận hành “láng giềng” bổ sung tri thức về đối tượng chưa biết
98
▪ Nhận ra một “cái mới chưa biết” nào đõ xuất hiện ▪ Tự động học để hiểu về “cái mới chưa biết” đó
Học thế giới mở ⚫ Định nghĩa
1) Bộ học có một mô hình phân lớp đa lớp FN={f1, f2,..., fN} từ N tập dữ liệu lớp quá khứ DN= {D1, D2, …, DN} với các nhãn lớp tương ứng YN= {l1, l2, …, lN}. thể hiện mới x, FN hoặc gán nhãn li YN hoặc từ chối và đưa x vào tập chưa biết R.
R và thu thập dữ liệu học cho các lớp chưa biết
2) Hệ thống/người sử dụng xác định các lớp chưa biết ẩn C trong
lớp mới theo dữ liệu học. Bộ học cập nhật là (FN+k, DN+k, YN+k).
⚫ Học thế giới mở là một dạng học suốt đời
3) Giả sử có k lớp mới đã đủ dữ liệu học, bộ học học gia tăng k
đã biết và các lớp mới
▪ Cơ sở tri thức: mọi mô hình thuộc FN+k và mọi dữ liệu thuộc
DN+k.
▪ Bài toán TN+1: xây dựng bộ phân lớp mở đa lớp dựa trên các lớp
99
▪ 3) học gia tăng truyền thống (không từ chối thể hiện lớp chưa biết) dù có bổ sung lớp mới gia tăng mà không cần học lại toàn bộ mô hình
Học không gian tương tự theo tâm [Fei16] ⚫ Tư tưởng
▪ Học khái niệm mới của con người thông qua các khái niệm
tương tự đã biết
▪ Đã biết {“phim”, “đồ nội thất”, “bóng đá”} cần học khái niệm mới chưa biết “bóng rổ”. “Bóng rổ” tương tự “bóng đá” và rất khác biệt “phim” và “đồ nội thất”
▪ Hai bước (1) tìm kiếm tập SC các lớp đã biết tương tự lớp mới chưa biết lN+1, (2) học phân biệt tách lớp mới chưa biết lN+1 với các lớp đã biết tương tự trong SC
⚫ Giải pháp
▪ center-based similarity: tương tự theo tâm
100
▪ (1) Tìm SC: Chạy từng bộ phân lớp nhị phân “1-vs-rest” trong FN với mỗi xDN+1. Lớp “tương tự” với lớp “mới chưa biết” có một tỷ lệ đoán nhận các x DN+1 vượt qua một ngưỡng cho trước. ▪ (2) gồm hai nội dung: (i) xây dựng phân lớp nhị phân đoán nhận lớp N+1 với DN+1 tập ví dụ dương và SCDi là tập ví dụ âm (2) cập nhật các phân lớp thuộc SC với tập ví dụ dương đã biết còn tập ví dụ âm là tập ví dụ âm đã biết bổ sung thêm DN+1.
Thuật toán học gia tăng CBS khái quát
⚫ N
⚫ H
[Fei16] mô tả cụ thể thuật toán CL-cbsSVM với “tương tự theo tâm”
101
Đánh giá thuật toán học gia tăng CBS
⚫ Nhận biết một ví dụ là chưa biết
▪ Bộ học cập nhật FN+1= {f1, f2, …, fN, fN+1}, một thể hiện x, cần xác định x thuộc một lớp đã biết nào hoặc thuộc một lớp chưa biết. ▪ f1 là các bộ phân lớp nhị phân SVM “1-vs-còn lại” mà điểm đầu
ra SVM khó so sánh
toán [Platt99] (có sẵn trong LIBSVM)
⚫ Quyết định
▪ Chuyển điểm đầu ra SVM thành một xác suất P(li|x) theo thuật
102
▪ y* : nhãn quyết định cho x ▪ : ngưỡng quyết định, chọn =0.5 ▪ Co: “nhãn” lớp mới chưa biết.
