LỜI CẨM Ơ N
Vui mừng khi hoàn thành 6ản Cuận văn, tôi kịiông quên công Cao to (ơn của (anfi đạo,
của các th ầ y cô g iá o , của g ia đìn h và 6ạn bè ấồng nghiệp.
T o i JQU g h i nhận và chân th à nh b iế t on các th ầ y cô g iá o đã quan tâm tẩ cíiứ c c h ỉ đạo

và tíiự c hà nh g iả n g dạ y íịíio ả cao Học tíiu ộ c íịíio a Công N g fiê j (Đ ạ i học Quốc g ia J {à N ộ i; (Đặc

b iệ t cảm ơn các th ầ y fvuxmg ẩẫn : T s. Luxrng c h i 94a i và T s. N g ô Quốc Tạo, n íiừ rig chuyên

g ia g ià u k in íi nghiêm & V iệ n Công nghệ T íiô n g tin , đã (fin fi íiư óng n ghiên cứu và tfie o c íõ ị c íiỉ

dẫ n từ ng bước; cảm 071 Ç S tfSTtyC J ỉổ Tủ (Bảo, V iệ n % Ịioa học và Công nghệ tiê n tiê n N íiậ t

(Bản, trong th ò i g ia n ngắn n g ủ i ở V iệ t N am củng đã nghe phầ n báo cáo tóm tắ t và cho những

ý kịển g ợ i mer qu ý 6áu. ^Tất cả những ngư ời th ầ y đó ng oà i việ c tậ n tu y truyề n th ụ kiến thức,

còn íả tấm gưong sáng về những đức tín h cần có tro n g nghiên cứu

^hoa fiọ c.
T ô i củng jç in chân th ành 6 iế t 071 íã n íi đạo trư ờ n g (Đ ại học S ư phạm ‘H à N ộ i, mà trự c

tiế p íằ (K jio a Toán—T ín Học, củng n hư g ia đình , bạn Sè đổng n ghiệp đã d à nh cho tô i nhiều ưu

ả i tro n g s u ố t quá trìn h học tậ p củng n hư tro n g th ò i g ia n thự c hiệ n ấề tà i.
T u y n hiê n, (ÍO bản th â n m ói b ắ t đầu trê n con đ ư ò tig nghiên cứu khoa Học đ ầy thách

thức, nên chắc chắn 6ản Cuận v ăn còn nhiề u th iế u s ót, 6 ấ t cập mà tô i chưa đủ k ịiả năng nfiâ n

tíiâ ỳ Hoặc í t n hiề u n hận th ấ y n íim ig chưa ấ ủ sức vư ợ t qua
.

thông tin, mơ ước đó mới đang dần trở thành hiện thực.
Chúng ta biết rằng, con người nhận thức được thế giới khách quan bằng các giác
quan và tư duy của mình. Hiện nay, chúng ta đã có nhiều thiết bị cảm nhận (sensor)
có khả năng thu nhận thông tin của môi hường xung quanh giống với chức năng
cua các giác quan con người. Đơn giản như một chiếc micro để có thể thu nhận âm
thanh cho đến những chiếc camera có khả năng thu nhận hình ảnh. vấn đề tiếp đó là
phải xử lý các thông tin thu được như thế nào.
Đối với con người thì quá trình xử lý thông tin là quá trình tư duy dựa trên cơ chế
hoạt động của bộ não. Đây là một quá trình rất phức tạp mà cho đến ngày nay,
chúng ta mới chỉ nắm bắt được một phần nhỏ cơ chế hoạt động của nó. Có lẽ sẽ
chăng bao giờ máy móc mới đạt tới khả năng tư duy của con người, nhưng trong sự
nồ lực từng bước của mình, các nhà khoa học đã phân tách các mảng thông tin ra
từng phần nhất định và xử lý riêng trong những khuôn khổ đó. Chính sự xử lý riêng
biệt này đã tạo ra được những thành công nhất định trong việc tạo ra những hệ
thống kỳ thuật có một số năng lực "tư duy" gần với con người.
Việc tạo ra các hệ thống có khả năng nhận định thông tin là một trong những hướng
nghiên cứu đã có những thành công. Trong các hệ thống này, từ một dạng thông tin
thu nhận được, hệ thống sẽ phân tách ra thành các mẫu thông tin riêng biệt, sau đó
biểu diễn các mẫu thông tin này, sắp xếp, phân loại chúng, và dùng những kỹ thuật
xu lý để nhận ra ý nghĩa của các thông tin đó. Đây chính là tư tưởng chủ đạo của bài
toán nhận dạnu mầu (Pattern Recognition). Phạm vi ứng dụng của lý thuyết nhận

J

Luận văn tôt nghiệp cao học
Lô Minh Hoàng Một phương pháp nhận dạng văn bán tiéng Việt «é*
dạng mẫu đã được áp dụng cho các lĩnh vực như: Nhận dạng tín hiệu, nhận dạng
tiếng nói, nhận dạng ảnh v.v
Nhận dạng anh có thể coi là công đoạn cuối cùng của quá trình xử lý ảnh. Rất nhiều
lý thuyết và kỹ thuật xử lý ảnh đã được phát triển với mục đích để nhận dạng tốt

• Trình bày cơ sở lý thuyết toán học cho vấn đề cần nghiên cứu
• Xây dụng các mô hình nhận dạng cấu trúc chữ Việt
• Xây dựng mô hình nhận dạng từ Tiếng Việt
• Xử lý văn bản và nhận dạng văn bản
• Ket quả cài đặt thử nghiệm
Luận văn tôi nghiệp cao học
Lê Minh Hoàng Một phương pháp nhặn dạng văn bán tiếng Việt «é*
Chương I:
TỎNG QUAN
I. MỤC ĐÍCH NGHIÊN cứu CỦA ĐÈ TÀI
Xử lý ảnh ngày nay đã trở thành một ngành khoa học lớn và có mặt ứong nhiều lĩnh
vực của cuộc sống. Điều này hoàn toàn có thể lý giải được từ một định nghĩa đơn
giản về ngành khoa học này: Xử lý ảnh là ngành khoa học nghiên cứu các quá
trình xử lý thông tin dạng hình ảnhịBí\ mà hình ảnh là một trong những dạng thông
tin phong phú nhất đối với chúng ta.
Bamera
Bcaner
Kensor
Hình 1: Phân cấp các hoạt dộng của quá trình xử lý ảnh số
Khử nhiễu
Hiệu chỉnh các
đặc tính của ảnh
Lưu trữ, hiển thị
và truyền dẫn
Nhận dạng
Luận văn tốt nghiệp cao học
Lê Minh Hoàng
Một phương pháp nhận dạng văn bàn tiếng Việt SP*
Khi quan sát một bức ảnh, ngoài sự cảtn nhận về kích thước và màu sắc thì các đối
tượng trong bức ảnh đó cũng mang lại những ý nghĩa nhận thức nào đó cho người

II.2. Khoảng cách mẫu và hàm phân biệt
Khoang cách là một công cụ tốt đế đánh giá các đối tượng có ở "gần nhau" hay
không. Khi khoang cách nhỏ hơn một ngưỡng nào đó thì có thể coi hai đối tượng là
đồng dạng với nhau, tức là được xếp vào cùng một lóp.
Hàm đo khoáng cách có thể coi là hàm đo mức tương tự. Trong trường hợp ta có
một số mẫu chuân đủ lớn đã được phân lớp một cách họp lý thì khi cần nhận dạng
một mẫu, ta chỉ cần tìm lóp chuẩn gần với mẫu đó nhất và xếp luôn mẫu đó vào lớp
này. Chính vì vậy hàm khoảng cách có ý nghĩa quyết định tới tính chính xác của
quá trình nhận dạng.
Với khái niệm khoảng cách Iĩiẫu, người ta xây dựng khái niệm hàm phân biệt: Hàm
phân biệt là một hàm có đối số là mẫu, dùng đế phân lớp mầu. Mỗi lớp có một hàm
phân biệt đặc trưng riêng và hàm này luôn cho giá trị "tốt" hơn đối với các mẫu
thuộc lớp của nó.
,

Luận văn tôt nghiệp cao học
Lê Minh Hoàng
Một phương pháp nhận dạng văn bản tiéng Việt «£*
11.3. Tiến trình nhận dạng ảnh
ảnh
Hình 2: Lưu dồ tiến trình nhận dạng ảnh
'r
Thu thập dữ liệu (Data Collection): Đây là công đoạn đầu tiên, quyết định
nhiều đến kết quả nhận dạng. Việc lựa chọn thiết bị thu nhận ảnh sẽ phụ thuộc
vào đặc tính của các đối tượng cần nhận dạng. Ví dụ, nếu đối tượng là chữ viết
thì kích cỡ của các chữ sẽ quyết định độ phân giải cần thiết cho camera hay máy
quét. Các thông số quan trọng ở bước này là độ phân giải, chất lượng màu, dung
lượng bộ nhớ và tốc độ thu nhận ảnh. Cuối cùng, ảnh phải được lưu trữ theo một
định dạng phù hợp với các bước xử lý sau này.
> Tiền xử lý (Preprocessing): Đẻ nâng cao khả năng nhận dạng chính xác, các

như nó duy trì và làm nổi bật được các nét đặc trưng của đối tượng mà những
đặc trưng đó sẽ giúp cho việc phân biệt được các lóp mẫu khác nhau, đồng thời
nó cũng miễn trừ được những biến đổi do các thiết bị thu nhận ảnh tạo ra.
> Phân lóp (Classification): Đây là bước quyết định trong quá ừinh nhận dạng.
Tất cả các bước xử lý trước đều nhằm mục đích cho việc phân lớp các mẫu một
cách thành công. Quá trình phân lóp có thể hiểu một cách đơn giản là quá trình
biến đối các số liệu định lượng ở đầu vào sang các số liệu định tính ở đầu ra .
Luận văn tốt nghiệp cao học
Lê Minh Hoàng
Một phương pháp nhận dạng văn bản tiéng Việt SP*
Đầu ra của bộ phân lớp có thể là sự chọn lựa rời rạc một lớp trong số các lóp đã
được định nghĩa trước. Cũng có thế là một dãy số biểu diễn các giá trị có thể
thừa nhận mẫu đó được hỉnh thành từ lớp tương ứng. Trong nhận dạng chữ,
thuật toán phân lớp chủ yếu được chia thành hai phương pháp chính, đó là
phương pháp thống kê (staticstical) và phương pháp cú pháp (syntactic). Bộ
phân lóp có thể gửi các thông tin hồi tiếp về bộ phân tách và bộ ữích chọn đặc
trưng đề hiệu chỉnh nhũng sai lệch của hai tiến trình này.
r- Hậu xử lý (Postprocessing): Có một số hệ thống nhận dạng mà kết quả nhận
dạng cần được xử lý tiếp đê thu được nhiều thông tin hữu ích hơn. Các đối
tượng đã được phân tách ra thành các mẫu để nhận dạng và quá trình phân lớp
đã gán được ý nghĩa cho các mẫu này, nhưng các đối tượng lại có những mối
quan hệ với nhau và những mối quan hệ này có thế mang những thông tin hữu
ích. Quá trình hậu xử lý có thể xem xét các mối quan hệ này để phát hiện ra các
lỗi của việc phân lóp và chữa lỗi này hoặc yêu cầu lại bộ phân lớp thực hiện một
số sửa đổi đề ưánh lỗi đó. Đối với hệ thống nhận dạng chữ viết thì bước hậu xử
lý chính là bước ghép nối các ký tự nhận dạng được thành các từ, các đoạn văn,
tái hiện lại văn bản, đồng thời kiểm tra chính tả, ngữ nghĩa từng tò trong văn
cảnh đê phát hiện ra lỗi nhận dạng.
II.4. Chữ viết trực tuyến và ngoại tuyến
Các dữ liệu viết tay thường được số hoá bằng cách quét văn bản hoặc bằng cách

Những sản phẩm nhận dạng chữ viết mang tính thương mại bắt đầu xuất hiện từ
những năm 1960. Một vài phương pháp nhận dạng đơn giản đã được đưa vào áp
dụng. Có thể kể ra một vài sản phẩm tiêu biểu là: IBM 1418, IBM 1428, IBM 1285,
IBM 1287 của IBM, Facom 6399A của Fujitsu và H-852 của Hitachi. Kỹ thuật chủ
yếu được sử dụng là phương pháp đối sánh mẫu.
Vào những năm 1970, phần mềm nhận dạng chữ viết có hiệu suất cao và giá rẻ
được Hitachi đưa ra thị trường gọi là H8959. Cũng trong thời kỳ này, những tiến bộ
Luận văn tốt nghiệp cao học
Lc Minh Hoàng
Một phương pháp nhận dạng văn bản tiéng Việt «é*
công nghệ cho phép chế tạo các máy quét laser giá rẻ và chất lượng cao, một số
phần mềm khác cũng được giới thiệu, được viết chủ yếu trên nền FORTRAN, sản
phẩm nâng cấp H8959 của Hitachi đã đạt tới độ chính xác 100% nếu được huấn
luyện bằng mẫu chừ của một người và thử nghiệm lại bằng chính chữ của người đó.
Những kỳ thuật phân tích cấu trúc đơn giản đã được tích hợp vào các hệ thống nhận
dạng thời kỳ này.
Tù giữa những năm 1970 đến những năm 1980, bắt đầu vào kỷ nguyên của PC, máy
tính giờ đây nhở hơn, nhanh hơn, và rẻ hơn. Những sản phẩm nhận dạng chữ viết
klìônt» ngừng được nàng cao chất lượng. Hệ thống ASPET/71 của ETL và Toshiba
và hệ thống IBM 1975 đã được thừa nhận và đưa vào sử dụng trong công tác văn
phòng. Tháng 9/1975, trung tâm thị trường lao động - Bộ lao động Nhật Bản quyết
định sử dụng hệ thống nhận dạng chữ viết Katakana trong tất cả các hệ thống bảo
hiêm của họ.
Tù những năm 1980 trở lại đây, với những cải tiến lớn trong công nghệ chế tạo
phần cứng máy tính, với những tiến bộ trong lĩnh vực xử lý thông tin, những bước
đột phá trong việc ứng dụng công nghệ tri thức, các hệ thống nhận dạng chữ viết
đang ngày một hướng tới sự hoàn thiện. Với sự đóng góp của nhiều ngành khoa
học, đặc biệt là Toán học và Khoa học máy tính, nhận dạng chừ viết tập trung
nghiên cứu phát triển nhằm mục tiêu nâng cao tính ốn định và tính linh hoạt, có khả
năng tự thích nghi với các dạng chừ viết khác lạ.

định này, người ta lấy một số điểm làm đặc trưng. Khi cần so sánh một mẫu cần
nhận dạng với một mẫu chuẩn, ta lấy dãy điểm đặc trưng trên mẫu chuẩn đối sánh
với dãy điểm cùng vị trí trên mẫu cần nhận dạng để xác định mức độ giống nhau
giữa hai mẫu và từ đó ra quyết định xem mẫu nhận dạng tương ứng với chữ cái nào.
Việc chọn dãy điếm đặc trưng như thế nào là tuỳ thuộc vào ngôn ngữ, không có quy
chuấn nào cụ thể. Nói chung không nên chọn dãy điểm đặc trưng là tất cả các điểm
trên khung. Ví dụ ta có khoảng 10 mẫu số "2" khá giống nhau thì dãy điếm đặc
trưng tốt nhất nên chọn là những vị trí có màu giống nhau trên cả 10 mẫu số 2 này.
b) Pỉiương pháp lưới.
Luận văn tôt nghiệp cao học
Lê Minh Hoàng
Một phương pháp nhận dạng văn bản tiếng Việt «é*
Một lưới ỏ vuông chuẩn được trùm lên đối tượng, số lượng điểm cắt của mỗi nan
lưới dọc và ngang với đối tượng sẽ là đặc trưng của đối tượng. Đồng thời số lượng ô
chứa một phần của đối tượng cũng được sử dụng làm đặc trưng của đối tượng. Mỗi
đường dọc và ngang của lưới sẽ được gán một trọng số nhất định.
Khi đó dựa vào các thông số và trọng số kể trên, ta có thể xây dựng được một hàm
đặc trưng cho đối tượng và việc đối sánh hai đối tượng được quy về đối sánh các
hàm đặc trung.
Với phương pháp này, việc chuẩn hoá đối tượng là rất quan trọng vì nó sẽ giúp cho
việc xác định kích thước của lưới chuân được sử dụng. Hơn thế độ nghiêng của đối
tượng cần nhận dạng cũng có ảnh hưởng rất lớn đến kết quả của phương pháp này.
Hình 4: Phương pháp lưới
c) Phương pháp cung
Có thể loại bỏ ảnh hưởng của độ nghiêng trong phương pháp lưới bằng cách thay
thế lưới ô vuông chuấn bằng lưới hình vành khăn: các nan lưới là các đường tròn
đồng tâm và các đường thẳng qua tâm. Có thể coi đây là phương pháp lưới ứong toạ
độ cực. Tâm cực là trọng tâm của đối tượng. Những vấn đề xác định đặc trưng còn
lại tương tự như phương pháp lưới.
Luận văn tỏt nghiệp cao học

lại hết sức khó khăn khi cài đặt.
Cách thứ hai, có thể áp dụng được trong trường hợp này dựa vào nhận xét: Neu bở
đi các đỉnh rẽ nhánh, đỉnh cắt và đỉnh treo thì mồi phần rời còn lại có thể vẽ chỉ
bằng một nét đơn. Khi đó những nét đơn này có thể mã hoá bằng xích hướng hay
còn gọi là mã Freeman. Các mã Freeman cùng với những điểm đặc trưng trong
phương pháp của Sherman sẽ được dùng đế đặc tả cấu trúc chữ
Hình 7: Ví dụ tồi tệ đối với cách phân tích cấu trúc của Sherman
;?iA HA NO* ;
Luận văn tốt nghiệp cao học
Lê Minh Hoàng
Một phương pháp nhặn dạng văn ban tiếng Việt
3
2
X3> 1
Freeman code: 3, 3, 2, 2, 1
6
7
8
Hình 8: Mã Freeman
b) Phương pháp phân tích hình học
Trong phương pháp này, mỗi đối tượng được đặt trong không gian Euclide 2 chiều
và được đặc ta bằng các khái niệm hình học cơ bản: đoạn thẳng, đường tròn, ellipse,
thậm chí cả các đường Bezier và B-Spline. Mỗi đối tượng hình học này được viết
phương trình toạ độ và được ưích ra một số đặc trưng như hướng, độ cong, điểm
uốn v.v Và những đặc trưng này được dùng làm tham số cho hàm phân biệt của
mồi lớp.
Cách tiếp cận này khá chặt chẽ về mặt lý thuyết, chẳng hạn có thế mô tả chữ o là
2 2 1
X V I ci
một hình ellipse có phương trình — + —T = 1 với — < — < 3. Nhưng vấn đề phân

tập hợp nhở các ký hiệu khó gây nên sự nhập nhằng (chẳng hạn như các chữ "Y" và
"N", "C" và "K", ) và cho phép một số sai sót nhất định. Thống kê các phiếu điều
tra là một ví dụ ứng dụng cho phương pháp sử dụng hình chiếu.
Luận văn tốt nghiệp cao học
Lê Minh Hoàng Một phương pháp nhận dạng văn bản tiéng Việt
Phương pháp sư dụng hình chiếu tức là sử dụng biểu đồ mật độ thay cho chừ.
Thông thường người ta sử dụng bốn loại biểu đồ mật độÍParkI995).
• Biêu đồ mật độ ngang (HRPCT): Là lược đồ xám ngang của chữ
• Biêu đồ mật độ dọc (VRPCT): Là lược đồ xám dọc của chữ
• Biểu đồ mật độ chiếu ngang dọc (HVRPCT)
• Biểu đồ mật độ chiếu chéo (DDRPCT)
Chi tiết về 4 phép chiếu này được trình bày trong hình 10:
\f
—

►
▼
s. ▼
vỷr
—►X
liX
\ỵ<

<►
— V
—► /1 k
/ í

mẫu chữ về việc nhận dạng các hình chiếu, còn việc nhận dạng như thế nào hoàn
toàn có thể sử dụng phương pháp đối sánh mẫu. Tuy nhiên để tận dụng được các ưu
điểm cua hình chiếu, người ta vẫn thường dùng phương pháp phân tích đường biên.
Trong công trinh nhận dạng bộ ký tự Hangul (Hàn Quốc), Hee-Seon Park và Seong-
Whan Lee đã inã hoá đường biên các hình chiếu dưới dạng mã Freeman và sừ dụng
mô hình Markov ẩn để nhận dạng đạt độ chính xác 96.7%, đây là một hiệu suất cao
trong nhận dạng chữ tượng hình.
IV. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN cứ u CỦA ĐÊ TÀI
Đề tài này trình bày phương pháp sử dụng mô hình Markov ẩn (Hidden Markov
Models - HMM) trong nhận dạng chừ viết tay hạn chế dựa theo cấu trúc biên cua
chữ. Tư tưởng chính là sử dụng các tiến trình ngẫu nhiên đề mô hình hoá quá trình
nhận dạng chữ viết bằng cách sử dụng xác suất để ưích chọn những đặc trưng cấu
trúc của đường biên. Đề tài nghiên cứu chuyên sâu vào các vấn đề:
• Đặc tả cấu trúc chữ: Phân tích các miền liên thông, biểu diễn đường biên theo
mã xích, phân lớp các mẫu huấn luyện
• Sử dụng HMM để loại bỏ nhiễu và trích chọn đặc trưng cấu trúc đường biên.
Phân tích tính hữu hiệu của phương pháp khi xử lý những thông tin không chắc
chắn hoặc không đầy đủ.
• Phương pháp nhận dạng từ Việt và các kỹ thuật xử lý văn bản.
Phạm vi nghiên cứu của đề tài là Tiếng Việt, vì vậy nội dung đề tài chỉ đề cập đến
các cách thức xử lý trong nhận dạng chữ và từ Tiếng Việt, những ký hiệu và từ
không phải tiếng Việt (Các bộ kí tự tượng hình, Sanskrit, Hy Lạp hay CnobeHufl )
không thuộc phạm vi nghiên cứu của đề tài.

J

Luận vãn tôt nghiệp cao học
Lc Mi nil Hoàng
Một phương pháp nhận dạng văn bản tiếng Việt «p»
Chương II:

thỉ ta nói quá trình Markov này là thuần nhất theo thời gian.
II. XÍCH MARKOV RỜI RẠC VÀ THUẦN NHẤT
■
Giả sử (Xn); n = 0, 1, 2, là xích Markov rời rạc và thuần nhất. Nói một cách chính
xác là: Giả su (Q, A, P) là không gian xác suất, x n: Q —»E là biến ngẫu nhiên nhận
giá trị trong tập không quá đếm được E. E là không gian trạng thái mà các phần tử
của nó có thể đánh số 1, 2, Khi đó tính Markov và tính thuần nhất của (Xn) có
nghĩa là:
Pij — P(Xn+Ị — J I x n — ì) — P(Xn+1 — J I Xo — l o , x n_! ln-lj Xn — l)
không phụ thuộc vào n.
Trong trường hợp này, ta dùng ký hiệu a,j thay cho Pij để đặc trưng riêng cho xích
Markov rời rạc và thuần nhất.
Chú ý rằng từ công thức xác suất đầy đủ, ta suy ra:
Vi, j e E : 0 < ay < 1 và =1
je E
Xác suất chuyến sau n bước được định nghĩa theo công thức:
ai/n) = P(Xn+m = j I x m = i) = P(Xn = j I Xo = i)
Đây là xác suất để hệ đang ở trạng thái i, sau n đơn vị thời gian (n bước) chuyển
sang trạng thái J. Rõ ràng a,j( 1} = ay. Ta quy ước:
(0) _ 1 Ẵ
• a,j = 1 nêu i = J
• aịJ(0) = 0 nếu i * j
Luận vãn tốt nghiệp cao học
Le Minh Hoàng <*ì* Một phương pháp nhận dạng văn bàn tiéng Việt «é*
*v24ss>“
l a sẽ chứng minh công thức sau: Vn = 0, 1,2,
,(n + l)
. 5
keE
(n)

vụ đám đông v.v. Tuy nhiên dưới đây ta chỉ xét tới một ví dụ quan trọng liên quan
tới việc xây dựng lý thuyết về mô hình Markov ẩn.
Trò chơi nhặt bóng (Urns and balls model|Rabmerl[Ponlzl): Có N cái bình đánh số 1,2,
N. Trong mỗi bình có chứa một số quả bóng, mỗi quả bóng có một trong M màu:
{V], VM}. Trò chơi diễn ra như sau: Người ta chọn ngẫu nhiên một bình, trong
bình đó chọn ngẫu nhiên một quả bóng, ghi nhận lại màu của quả bóng đó rồi trả lại
quà bóng vào bình. Sau T lần như vậy dãy màu ghi nhận được có dạng 0], 0 2,
Or
Gia sư 71 i là xác suất để bình thứ 1 được chọn đầu tiên, a¡j là xác suất tại thời điểm
t+1 chọn bình thứ j trong điều kiện tại thời điểm t đã chọn bình thứ i. a,j không phụ
thuộc vào t (nó chỉ phụ thuộc vào khoảng cách giữa hai bình chẳng hạn), và cuối
cùng ta biết được số bóng trong mỗi bình cũng như màu của các quả bóng đó, hay
rõ hơn, ta biết được bj(vk) là xác suất để chọn được quả bóng màu v k trong bình j.
Một trong những vấn đề đặt ra là cho trước một dãy màu o = (Oi, O2 , Or), hãy
tính xác suất để người chơi chọn được dãy màu đó.
Đê tính xác suất này, ta thử xét xem nếu dãy bình được chọn là Q = (qi, q2 , q-r)
thì xác suất nhận được dãy o = (Oi, 0 2, 0 T) là bao nhiêu. Dễ thấy rằng:
P (0|Ọ ) = bqi(0,).bq2(02)

bqT(0 T)
Ngoài ra, xác suất để chọn được dãy bình Q = (q]; q2,q-r) là:
P(Q) = ^qj-^q
\C\2
‘^2^3 ^T-lqT
Vậy xác suất để chọn được dãy bình ọ và dãy màu o là:
P(0, Q) = P(0 I Q).P(Q) = 7iqi.bqi(0i).aqiq2.bq2(02).aq2q3 aq.r iqT.bqT(0 T).

7

Luận văn tỏt nghiệp cao học