Giới thiệu về chuỗi Markov với ví dụ - Chuỗi Markov với Python

Giới thiệu về Chuỗi Markov:

Bạn đã bao giờ tự hỏi Google xếp hạng các trang web như thế nào chưa? Nếu bạn đã thực hiện nghiên cứu của mình thì bạn phải biết rằng nó sử dụng Thuật toán xếp hạng trang dựa trên ý tưởng về chuỗi Markov. Bài viết Giới thiệu về chuỗi Markov này sẽ giúp bạn hiểu ý tưởng cơ bản đằng sau chuỗi Markov và cách chúng có thể được mô hình hóa như một giải pháp cho các vấn đề trong thế giới thực.

Đây là danh sách các chủ đề sẽ được đề cập trong blog này:

1. Chuỗi Markov là gì?
2. Tài sản Markov là gì?
3. Hiểu chuỗi Markov với một ví dụ
4. Ma trận chuyển tiếp là gì?
5. Chuỗi Markov bằng Python
6. Các ứng dụng chuỗi Markov

Để có kiến ​​thức chuyên sâu về Khoa học dữ liệu và Học máy bằng Python, bạn có thể đăng ký trực tiếp của Edureka với hỗ trợ 24/7 và quyền truy cập trọn đời.

Chuỗi Markov là gì?

Andrey Markov lần đầu tiên giới thiệu chuỗi Markov vào năm 1906. Ông giải thích chuỗi Markov là:

Một quá trình ngẫu nhiên có chứa các biến ngẫu nhiên, chuyển đổi từ trạng thái này sang trạng thái khác tùy thuộc vào các giả định nhất định và các quy tắc xác suất xác định.

Những ngẫu nhiên các biến chuyển đổi từ trạng thái này sang trạng thái khác, dựa trên một thuộc tính toán học quan trọng được gọi là Tài sản Markov.

Điều này đưa chúng ta đến câu hỏi:

Tài sản Markov là gì?

Thuộc tính thời gian rời rạc Markov tuyên bố rằng xác suất tính toán của một quá trình ngẫu nhiên chuyển sang trạng thái có thể tiếp theo chỉ phụ thuộc vào trạng thái và thời gian hiện tại và nó độc lập với chuỗi các trạng thái trước đó.

Thực tế là hành động / trạng thái có thể xảy ra tiếp theo của một quá trình ngẫu nhiên không phụ thuộc vào chuỗi các trạng thái trước đó, làm cho chuỗi Markov như một quá trình không có bộ nhớ mà chỉ phụ thuộc vào trạng thái / hành động hiện tại của một biến.

Hãy suy ra điều này một cách toán học:

Cho quá trình ngẫu nhiên là, {Xm, m = 0,1,2, ⋯}.

Quá trình này chỉ là một chuỗi Markov nếu,

Chuỗi Markov - Giới thiệu về Chuỗi Markov - Edureka

cho tất cả m, j, i, i0, i1, ⋯ im & trừ1

Đối với một số hữu hạn trạng thái, S = {0, 1, 2, ⋯, r}, đây được gọi là chuỗi Markov hữu hạn.

P (Xm + 1 = j | Xm = i) ở đây đại diện cho các xác suất chuyển đổi để chuyển từ trạng thái này sang trạng thái khác. Ở đây, chúng tôi giả định rằng xác suất chuyển đổi không phụ thuộc vào thời gian.

Có nghĩa là P (Xm + 1 = j | Xm = i) không phụ thuộc vào giá trị của ‘m’. Do đó, chúng tôi có thể tóm tắt,

Công thức chuỗi Markov - Giới thiệu về chuỗi Markov - Edureka

Vì vậy, phương trình này biểu diễn chuỗi Markov.

Bây giờ chúng ta hãy hiểu chuỗi Markov chính xác là gì với một ví dụ.

Ví dụ về chuỗi Markov

Trước khi tôi cung cấp cho bạn một ví dụ, hãy định nghĩa Mô hình Markov là gì:

Mô hình Markov là gì?

Mô hình Markov là một mô hình ngẫu nhiên mô hình hóa các biến ngẫu nhiên theo cách mà các biến tuân theo thuộc tính Markov.

Bây giờ, hãy hiểu cách Mô hình Markov hoạt động với một ví dụ đơn giản.

Như đã đề cập trước đó, chuỗi Markov được sử dụng trong các ứng dụng tạo văn bản và tự động hoàn thành. Đối với ví dụ này, chúng ta sẽ xem xét một câu ví dụ (ngẫu nhiên) và xem cách nó có thể được mô hình hóa bằng cách sử dụng chuỗi Markov.

quá mức trong học máy là gì

Ví dụ về chuỗi Markov - Giới thiệu về Chuỗi Markov - Edureka

Câu trên là ví dụ của chúng tôi, tôi biết nó không có ý nghĩa gì (không nhất thiết phải như vậy), đó là một câu chứa các từ ngẫu nhiên, trong đó:

1. Chìa khóa biểu thị các từ duy nhất trong câu, tức là 5 phím (một, hai, mưa đá, hạnh phúc, edureka)

2. Token biểu thị tổng số từ, tức là 8 mã thông báo.

Tiếp tục, chúng ta cần hiểu tần suất xuất hiện của những từ này, sơ đồ dưới đây cho thấy mỗi từ cùng với một số biểu thị tần suất xuất hiện của từ đó.

Các phím và tần suất - Giới thiệu về chuỗi Markov - Edureka

Vì vậy, cột bên trái ở đây biểu thị các phím và cột bên phải biểu thị các tần số.

Từ bảng trên, chúng ta có thể kết luận rằng khóa ‘edureka’ có giá trị gấp 4 lần so với bất kỳ khóa nào khác. Điều quan trọng là suy ra thông tin như vậy vì nó có thể giúp chúng ta dự đoán từ nào có thể xảy ra tại một thời điểm cụ thể. Nếu tôi đoán từ tiếp theo trong câu ví dụ, tôi sẽ chọn từ ‘edureka’ vì nó có xác suất xuất hiện cao nhất.

Nói về xác suất, một thước đo khác mà bạn phải biết là các phân phối có trọng số.

Trong trường hợp của chúng tôi, phân phối có trọng số cho ‘edureka’ là 50% (4/8) vì tần suất của nó là 4, trong tổng số 8 mã thông báo. Các phím còn lại (một, hai, mưa đá, hạnh phúc) đều có cơ hội xảy ra 1/8 (& asymp 13%).

Bây giờ chúng ta đã hiểu về phân bố trọng số và ý tưởng về cách các từ cụ thể xảy ra thường xuyên hơn những từ khác, chúng ta có thể tiếp tục với phần tiếp theo.

Hiểu về chuỗi Markov - Giới thiệu về Chuỗi Markov - Edureka

Trong hình trên, tôi đã thêm hai từ bổ sung biểu thị phần đầu và phần cuối của câu, bạn sẽ hiểu tại sao tôi lại làm như vậy trong phần bên dưới.

Bây giờ, hãy chỉ định tần suất cho các phím này:

Các khóa và tần suất cập nhật - Giới thiệu về Chuỗi Markov - Edureka

Bây giờ, hãy tạo một mô hình Markov. Như đã đề cập trước đó, mô hình Markov được sử dụng để mô hình hóa các biến ngẫu nhiên tại một trạng thái cụ thể theo cách mà trạng thái tương lai của các biến này chỉ phụ thuộc vào trạng thái hiện tại chứ không phải trạng thái trong quá khứ của chúng.

Vì vậy, về cơ bản trong một mô hình Markov, để dự đoán trạng thái tiếp theo, chúng ta chỉ phải xem xét trạng thái hiện tại.

Trong sơ đồ bên dưới, bạn có thể thấy cách mỗi mã thông báo trong câu của chúng tôi dẫn đến một mã khác. Điều này cho thấy rằng trạng thái tương lai (mã thông báo tiếp theo) dựa trên trạng thái hiện tại (mã thông báo hiện tại). Vì vậy, đây là quy tắc cơ bản nhất trong Mô hình Markov.

Biểu đồ dưới đây cho thấy rằng có các cặp mã thông báo trong đó mỗi mã thông báo trong cặp này dẫn đến mã khác trong cùng một cặp.

Markov Chain Pairs - Giới thiệu về Markov Chain - Edureka

Trong sơ đồ bên dưới, tôi đã tạo một biểu diễn cấu trúc cho thấy mỗi khóa với một loạt các mã thông báo có thể có tiếp theo mà nó có thể ghép nối.

Một loạt các cặp chuỗi Markov - Giới thiệu về chuỗi Markov - Edureka

Để tóm tắt ví dụ này, hãy xem xét một tình huống trong đó bạn sẽ phải tạo một câu bằng cách sử dụng mảng khóa và mã thông báo mà chúng ta đã thấy trong ví dụ trên. Trước khi xem qua ví dụ này, một điểm quan trọng khác là chúng ta cần chỉ định hai biện pháp ban đầu:

1. Phân phối xác suất ban đầu (tức là trạng thái bắt đầu tại thời điểm = 0, (khóa ‘Bắt đầu’))

2. Xác suất chuyển từ trạng thái này sang trạng thái khác (trong trường hợp này là xác suất chuyển từ mã thông báo này sang mã thông báo khác)

Chúng tôi đã xác định phân phối có trọng số ngay từ đầu, vì vậy chúng tôi có các xác suất và trạng thái ban đầu, bây giờ hãy tiếp tục với ví dụ.

• Vì vậy, để bắt đầu với mã thông báo ban đầu là [Bắt đầu]

• Tiếp theo, chúng tôi chỉ có một mã thông báo có thể có, tức là [một]

• Hiện tại, câu chỉ có một từ, tức là 'một'

• Từ mã thông báo này, mã thông báo có thể tiếp theo là [edureka]

• Câu được cập nhật thành 'one edureka'

• Từ [edureka] chúng ta có thể chuyển sang bất kỳ mã thông báo nào sau đây [hai, mưa đá, hạnh phúc, kết thúc]

• Có 25% khả năng 'hai' được chọn, điều này có thể dẫn đến việc tạo thành câu gốc (một edureka hai edureka hail edureka happy edureka). Tuy nhiên, nếu chọn 'end' thì quá trình sẽ dừng lại và cuối cùng chúng ta sẽ tạo ra một câu mới, tức là 'one edureka'.

Hãy tự vỗ về mình vì bạn vừa tạo Mô hình Markov và chạy một trường hợp thử nghiệm thông qua nó. Để tóm tắt lại ví dụ trên, về cơ bản chúng ta đã sử dụng trạng thái hiện tại (present word) để xác định trạng thái tiếp theo (next word). Và đó chính xác là quy trình Markov.

cấu trúc dữ liệu trong java là gì

Nó là một quá trình ngẫu nhiên trong đó các biến ngẫu nhiên chuyển từ trạng thái này sang trạng thái khác theo cách mà trạng thái tương lai của một biến chỉ phụ thuộc vào trạng thái hiện tại.

Hãy chuyển sang bước tiếp theo và vẽ ra Mô hình Markov cho ví dụ này.

Sơ đồ chuyển đổi trạng thái - Giới thiệu về chuỗi Markov - Edureka

Hình trên được gọi là Sơ đồ chuyển đổi trạng thái. Chúng ta sẽ nói thêm về điều này trong phần bên dưới, bây giờ chỉ cần nhớ rằng biểu đồ này cho thấy sự chuyển đổi và xác suất từ ​​trạng thái này sang trạng thái khác.

Lưu ý rằng mỗi hình bầu dục trong hình đại diện cho một phím và các mũi tên hướng về các phím có thể theo sau nó. Ngoài ra, trọng số trên các mũi tên biểu thị xác suất hoặc phân phối có trọng số của việc chuyển đổi từ / sang các trạng thái tương ứng.

Đó là tất cả về cách thức hoạt động của Mô hình Markov. Bây giờ chúng ta hãy cố gắng hiểu một số thuật ngữ quan trọng trong Quy trình Markov.

Ma trận xác suất chuyển đổi là gì?

Trong phần trên, chúng ta đã thảo luận về hoạt động của Mô hình Markov với một ví dụ đơn giản, bây giờ chúng ta hãy hiểu các thuật ngữ toán học trong Quy trình Markov.

Trong Quy trình Markov, chúng tôi sử dụng ma trận để biểu diễn các xác suất chuyển đổi từ trạng thái này sang trạng thái khác. Ma trận này được gọi là ma trận chuyển đổi hay ma trận xác suất. Nó thường được ký hiệu là P.

Ma trận chuyển đổi - Giới thiệu về chuỗi Markov - Edureka

Lưu ý, pij & ge0 và ‘i’ cho tất cả các giá trị là,

Công thức ma trận chuyển đổi - Giới thiệu về chuỗi Markov - Edureka

Hãy để tôi giải thích điều này. Giả sử rằng trạng thái hiện tại của chúng ta là ‘i’, trạng thái tiếp theo hoặc sắp tới phải là một trong những trạng thái tiềm năng. Do đó, trong khi lấy tổng tất cả các giá trị của k, chúng ta phải nhận được một.

Sơ đồ chuyển đổi trạng thái là gì?

Mô hình Markov được biểu diễn bằng Sơ đồ chuyển đổi trạng thái. Biểu đồ cho thấy sự chuyển đổi giữa các trạng thái khác nhau trong Chuỗi Markov. Hãy cùng tìm hiểu ma trận chuyển tiếp và ma trận chuyển đổi trạng thái với một ví dụ.

Ví dụ về ma trận chuyển đổi

Hãy xem xét một chuỗi Markov với ba trạng thái 1, 2 và 3 và các xác suất sau:

Ví dụ về ma trận chuyển đổi - Giới thiệu về chuỗi Markov - Edureka

Ví dụ về sơ đồ chuyển đổi trạng thái - Giới thiệu về chuỗi Markov - Edureka

Biểu đồ trên đại diện cho biểu đồ chuyển đổi trạng thái cho chuỗi Markov. Ở đây, 1,2 và 3 là ba trạng thái có thể xảy ra, và các mũi tên chỉ từ trạng thái này sang trạng thái khác thể hiện xác suất chuyển đổi pij. Khi, pij = 0, có nghĩa là không có sự chuyển đổi giữa trạng thái ‘i’ và trạng thái ‘j’.

Bây giờ chúng tôi biết toán học và logic đằng sau chuỗi Markov, hãy chạy một bản demo đơn giản và hiểu nơi có thể sử dụng chuỗi Markov.

Chuỗi Markov bằng Python

Để chạy bản trình diễn này, tôi sẽ sử dụng Python, vì vậy nếu bạn không biết Python, bạn có thể xem qua các blog sau:

2. Cách học Python 3 từ Scratch - Hướng dẫn cho người mới bắt đầu

Bây giờ hãy bắt đầu với việc viết mã!

Trình tạo văn bản chuỗi Markov

Báo cáo vấn đề: Để áp dụng Thuộc tính Markov và tạo Mô hình Markov có thể tạo mô phỏng văn bản bằng cách nghiên cứu tập dữ liệu lời nói của Donald Trump.

Mô tả Tập dữ liệu: Tệp văn bản chứa danh sách các bài phát biểu của Donald Trump vào năm 2016.

Hợp lý: Áp dụng Thuộc tính Markov để tạo bài phát biểu của Donald Trump bằng cách xem xét từng từ được sử dụng trong bài phát biểu và đối với mỗi từ, hãy tạo một từ điển các từ được sử dụng tiếp theo.

Bước 1: Nhập các gói cần thiết

nhập numpy dưới dạng np

Bước 2: Đọc tập dữ liệu

trump = open ('C: //Users//NeelTemp//Desktop//demos//spearies.txt', encoding = 'utf8'). read () #display in dữ liệu (trump) PHÁT ÂM 1 ... Cảm ơn bạn rất nhiều. Thật tuyệt. Anh ấy không phải là một chàng trai tuyệt vời. Anh ta không nhận được một báo chí công bằng, anh ta không nhận được nó. Nó chỉ là không công bằng. Và tôi phải nói với bạn rằng tôi đang ở đây, và rất mạnh mẽ ở đây, bởi vì tôi rất tôn trọng Steve King và cũng có sự tôn trọng lớn đối với Citizens United, David và tất cả mọi người, và vô cùng giống Tea Party. Ngoài ra, cả người dân Iowa. Họ có điểm chung. Những người làm việc chăm chỉ....

Bước 3: Tách tập dữ liệu thành các từ riêng lẻ

corpus = trump.split () # Hiển thị bản in ngữ liệu (corpus) 'mạnh mẽ,', 'nhưng', 'không phải', 'quyền lực', 'như', 'chúng tôi.', 'Iran', 'có', ' hạt giống ',' khủng bố ', ...

Tiếp theo, tạo một hàm tạo các cặp từ khác nhau trong bài phát biểu. Để tiết kiệm dung lượng, chúng tôi sẽ sử dụng đối tượng máy phát điện.

Bước 4: Tạo các cặp phím và các từ tiếp theo

def make_pairs (corpus): for i in range (len (corpus) - 1): output (corpus [i], corpus [i + 1]) pair = make_pairs (corpus)

Tiếp theo, hãy khởi tạo một từ điển trống để lưu trữ các cặp từ.

Trong trường hợp từ đầu tiên trong cặp đã là một khóa trong từ điển, chỉ cần thêm từ tiềm năng tiếp theo vào danh sách các từ theo sau từ đó. Nhưng nếu từ không phải là khóa, thì hãy tạo một mục mới trong từ điển và gán khóa bằng từ đầu tiên trong cặp.

Bước 5: Thêm từ điển

word_dict = {} cho word_1, word_2 theo cặp: if word_1 trong word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Tiếp theo, chúng tôi chọn ngẫu nhiên một từ từ kho ngữ liệu, từ đó sẽ bắt đầu chuỗi Markov.

Bước 6: Xây dựng mô hình Markov

#randomly chọn từ đầu tiên first_word = np.random.choice (corpus) # Chọn từ đầu tiên làm từ viết hoa để từ đã chọn không được lấy giữa một câu trong khi first_word.islower (): # Bắt đầu chuỗi từ chuỗi từ đã chọn = [first_word] # Khởi tạo số lượng từ được kích thích n_words = 20

Sau từ đầu tiên, mỗi từ trong chuỗi được lấy mẫu ngẫu nhiên từ danh sách các từ đã theo sau từ cụ thể đó trong các bài phát biểu trực tiếp của Trump. Điều này được hiển thị trong đoạn mã dưới đây:

cho tôi trong phạm vi (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Bước 7: Dự đoán

Cuối cùng, hãy hiển thị văn bản được kích thích.

#Join trả về chuỗi dưới dạng chuỗi in ('' .join (chuỗi)) Số lượng người đáng kinh ngạc. Và Hillary Clinton, có con người của chúng tôi, và công việc tuyệt vời như vậy. Và chúng tôi sẽ không đánh bại Obama

Vì vậy, đây là văn bản được tạo mà tôi nhận được khi xem xét bài phát biểu của Trump. Nó có thể không có nhiều ý nghĩa nhưng nó đủ tốt để giúp bạn hiểu cách chuỗi Markov có thể được sử dụng để tự động tạo văn bản.

Bây giờ chúng ta hãy xem xét một số ứng dụng khác của chuỗi Markov và cách chúng được sử dụng để giải quyết các vấn đề trong thế giới thực.

Các ứng dụng chuỗi Markov

Dưới đây là danh sách các ứng dụng trong thế giới thực của chuỗi Markov:

1. Xếp hạng Trang của Google: Toàn bộ trang web có thể được coi như một mô hình Markov, trong đó mọi trang web có thể là một trạng thái và các liên kết hoặc tham chiếu giữa các trang này có thể được coi là chuyển đổi có xác suất. Vì vậy, về cơ bản, bất kể bạn bắt đầu lướt trang web nào, cơ hội truy cập vào một trang web nhất định, chẳng hạn, X là một xác suất cố định.

2. Nhập dự đoán từ: Chuỗi Markov được biết là được sử dụng để dự đoán các từ sắp tới. Chúng cũng có thể được sử dụng trong tự động hoàn thành và đề xuất.

3. Mô phỏng Subreddit: Chắc chắn bạn đã xem qua Reddit và có tương tác trên một trong các chuỗi hoặc tín dụng phụ của họ. Reddit sử dụng trình giả lập subreddit tiêu thụ một lượng lớn dữ liệu chứa tất cả các nhận xét và thảo luận được tổ chức trên các nhóm của họ. Bằng cách sử dụng chuỗi Markov, trình mô phỏng tạo ra xác suất từ ​​thành chữ, để tạo nhận xét và chủ đề.

4. Trình tạo văn bản: Chuỗi Markov được sử dụng phổ biến nhất để tạo ra các văn bản giả hoặc tạo ra các bài luận lớn và biên soạn các bài phát biểu. Nó cũng được sử dụng trong các trình tạo tên mà bạn thấy trên web.

Giờ bạn đã biết cách giải quyết một vấn đề trong thế giới thực bằng cách sử dụng Markov Chains, tôi chắc chắn rằng bạn muốn tìm hiểu thêm. Dưới đây là danh sách các blog sẽ giúp bạn bắt đầu với các khái niệm thống kê khác:

Với điều này, chúng ta sẽ đến phần cuối của blog Giới thiệu về Chuỗi Markov này. Nếu bạn có bất kỳ câu hỏi nào liên quan đến chủ đề này, vui lòng để lại bình luận bên dưới và chúng tôi sẽ liên hệ lại với bạn.

Hãy theo dõi để biết thêm blog về các công nghệ thịnh hành.

Nếu bạn đang tìm kiếm chương trình đào tạo có cấu trúc trực tuyến về Khoa học dữ liệu, hãy edureka! có một quản lý đặc biệt chương trình giúp bạn có kiến ​​thức chuyên môn về Thống kê, Đánh giá dữ liệu, Phân tích Dữ liệu Khám phá, Các thuật toán Máy học như K-Means Clustering, Quyết định Cây, Rừng ngẫu nhiên, Naive Bayes. Bạn cũng sẽ tìm hiểu các khái niệm về Chuỗi thời gian, Khai thác văn bản và giới thiệu về Học sâu. Các đợt mới cho khóa học này sắp bắt đầu !!