Chuỗi Markov rất đơn giản: chúng ta hãy xem xét nguyên tắc một cách chi tiết. Mở rộng cơ sở từ vựng

Tôi đang duyệt các diễn đàn để tìm kiếm những câu hỏi mà các lập trình viên Python được hỏi trong các cuộc phỏng vấn và tình cờ thấy một câu hỏi rất tuyệt vời. Tôi sẽ thoải mái trích dẫn anh ấy: “Họ yêu cầu tôi viết một trình tạo vô nghĩa dựa trên chuỗi Markov bậc n.” “Nhưng tôi chưa có máy phát điện như vậy!” - tôi hét lên giọng nói bên trong- “Nhanh lên, mở sublime ra và viết đi!” - anh kiên trì nói tiếp. Thôi, tôi đành phải vâng lời.

Và ở đây tôi sẽ cho bạn biết tôi đã làm được điều đó như thế nào.

Người ta ngay lập tức quyết định rằng người tạo ra sẽ bày tỏ mọi suy nghĩ của mình trên Twitter và trang web của mình. Tôi đã chọn Flask và PostgreSQL làm công nghệ chính. Họ sẽ liên lạc với nhau thông qua SQLAlchemy.

Kết cấu.

Vì thế. Như sau mô hình trông giống như:
lớp Srt(db.Model): id = db.Column(db.Integer, Primary_key = True) set_of_words = db.Column(db.Text()) list_of_words = db.Column(db.Text()) lớp UpperWords(db .Model): word = db.Column(db.String(40), index = True, Primary_key = True, Unique = True) def __repr__(self): return self.word class Cụm từ(db.Model): id = db .Column(db.Integer, Primary_key = True) đã tạo = db.Column(db.DateTime, default=datetime.datetime.now) cụm từ = db.Column(db.String(140), index = True) def __repr__(self ): trả về str(self.phrase)
Người ta quyết định lấy phụ đề từ các bộ phim truyền hình nổi tiếng làm văn bản nguồn. Lớp Srt lưu trữ một tập hợp có thứ tự tất cả các từ trong phụ đề đã xử lý cho một tập và một tập hợp duy nhất gồm các từ tương tự (không lặp lại). Điều này sẽ giúp bot tìm kiếm cụm từ trong phụ đề cụ thể dễ dàng hơn. Đầu tiên nó sẽ kiểm tra xem tập hợp từ có nằm trong tập hợp từ của phụ đề hay không, sau đó xem liệu chúng có nằm trong đó hay không. theo đúng thứ tự.

Từ đầu tiên của cụm từ trong văn bản là một từ ngẫu nhiên bắt đầu bằng chữ in hoa. UpperWords được sử dụng để lưu trữ những từ như vậy. Các từ được viết ở đó theo cùng một cách mà không lặp lại.

Chà, lớp Cụm từ là cần thiết để lưu trữ các tweet đã được tạo.
Cấu trúc rất đơn giản.

Trình phân tích cú pháp phụ đề ở định dạng .srt được bao gồm trong một mô-đun riêng add_srt.py. Không có gì đặc biệt ở đó cả, nhưng nếu có ai quan tâm thì tất cả các nguồn đều có trên GitHub.

Máy phát điện.

Đầu tiên, bạn cần chọn từ đầu tiên cho dòng tweet của mình. Như đã đề cập trước đó, đây sẽ là bất kỳ từ nào trong mô hình UpperWords. Lựa chọn của nó được thực hiện trong chức năng:
def add_word(word_list, n): nếu không phải word_list: word = db.session.query(models.UpperWords).order_by(func.random()).first().word #postgre elif len(word_list)<= n: word = get_word(word_list, len(word_list)) else: word = get_word(word_list, n) if word: word_list.append(word) return True else: return False
Việc lựa chọn từ này được thực hiện trực tiếp bởi dòng:

Word = db.session.query(models.UpperWords).order_by(func.random()).first().word

Nếu bạn đang sử dụng MySQL thì bạn cần sử dụng func.rand() thay vì func.random(). Đây là điểm khác biệt duy nhất trong cách triển khai này; mọi thứ khác sẽ hoạt động hoàn toàn giống nhau.

Nếu từ đầu tiên đã có sẵn, hàm sẽ xem xét độ dài của chuỗi và tùy thuộc vào điều này, chọn số lượng từ trong văn bản mà chúng ta cần để so sánh danh sách của mình (chuỗi thứ n) và nhận được từ tiếp theo.

Và chúng ta nhận được từ tiếp theo trong hàm get_word:
def get_word(word_list, n): query = models.Srt.query.all() query_list = list() cho truy vấn trong truy vấn: if set(word_list)<= set(query.set_of_words.split()): query_list.append(query.list_of_words.split()) if query_list: text = list() for lst in query_list: text.extend(lst) indexies = ) if text == word_list] word = text return word else: return False
Trước hết, tập lệnh chạy qua tất cả các phụ đề đã tải và kiểm tra xem tập hợp từ của chúng tôi có nằm trong tập hợp các từ của phụ đề cụ thể hay không. Sau đó, văn bản của phụ đề đã được lọc sẽ được kết hợp thành một danh sách và các kết quả khớp với toàn bộ cụm từ sẽ được tìm kiếm và vị trí của các từ theo sau các cụm từ này sẽ được trả về. Tất cả đều kết thúc bằng sự lựa chọn từ ngữ mù quáng. Mọi thứ đều giống như trong cuộc sống.
Đây là cách các từ được thêm vào danh sách. Bản thân tweet được tập hợp thành một chức năng:
def get_twit(): word_list = list() n = N while len(" ".join(word_list))<140: if not add_word(word_list, n): break if len(" ".join(word_list))>140: word_list.pop() ngắt trong khi word_list[-1][-1] không có trong ".?!": word_list.pop() return " ".join(word_list)
Rất đơn giản - tweet không được vượt quá 140 ký tự và kết thúc bằng dấu chấm câu kết thúc câu. Tất cả. Máy phát điện đã hoàn thành công việc của nó.

Hiển thị trên trang web.

Mô-đun view.py xử lý việc hiển thị trên trang web.
@app.route("/") def index(): return render_template("main/index.html")
Nó chỉ đơn giản là hiển thị mẫu. Tất cả các tweet sẽ được lấy từ nó bằng js.
@app.route("/page") def page(): page = int(request.args.get("page")) diff = int(request.args.get("difference")) limit = 20 cụm từ = models.Phrases.query.order_by(-models.Phrases.id).all() pages = math.ceil(len(phrases)/float(limit)) count = len(phrases)phrases = cụm từ return json.dumps(( "cụm từ":cụm từ, "trang":trang, "đếm":đếm), cls=controllers.AlchemyEncoding)
Trả về tweet từ một trang cụ thể. Điều này là cần thiết để cuộn vô hạn. Mọi thứ đều khá bình thường. khác biệt – số lượng tweet được thêm sau khi trang web được tải trong quá trình cập nhật. Mẫu tweet cho trang sẽ được thay đổi theo số lượng này.

Và bản cập nhật chính nó:
@app.route("/update") def update(): Last_count = int(request.args.get("count"))phrase = models.Phrases.query.order_by(-models.Phrases.id).all( ) count = len(cụm từ) nếu đếm > Last_count: cụm từ = cụm từ[:count-last_count] return json.dumps(("phrases":phrases, "count":count), cls=controllers.AlchemyEncoding) else: return json .dumps(("count":count))
Về phía khách hàng, nó được gọi cứ sau n giây và tải các tweet mới được thêm vào trong thời gian thực. Đây là cách hiển thị tweet của chúng tôi hoạt động. (Nếu ai quan tâm, bạn có thể xem lớp AlchemyEncode trong Controllers.py, nó được sử dụng để tuần tự hóa các tweet nhận được từ SQLAlchemy)

Thêm tweet vào cơ sở dữ liệu và đăng lên Twitter.

Tôi đã sử dụng tweepy để đăng lên Twitter. Pin rất tiện lợi, khởi động ngay.

Nó trông như thế nào:
def twit(): cụm từ = get_twit() twited = models.Phrases(phrase=phrase) db.session.add(twited) db.session.commit() auth = tweepy.OAuthHandler(CONSUMER_KEY, CONSUMER_SECRET) auth.set_access_token(ACCESS_TOKEN , ACCESS_TOKEN_SECRET) api = tweepy.API(auth) api.update_status(status=phrase)
Tôi đã gọi hàm này trong cron.py trong thư mục gốc của dự án và như bạn có thể đoán, nó được khởi chạy bởi cron. Cứ nửa giờ lại có một tweet mới được thêm vào cơ sở dữ liệu và Twitter.

Mọi thứ đã hoạt động!

Tóm lại.

Hiện tại tôi đã tải xuống tất cả phụ đề cho loạt phim “Những người bạn” và “Lý thuyết vụ nổ lớn”. Cho đến nay tôi đã chọn cấp độ của chuỗi Markov bằng hai (khi cơ sở phụ đề tăng lên, cấp độ sẽ tăng lên). Bạn có thể thấy nó hoạt động như thế nào trong

Nó được mô tả cách huấn luyện mạng neutron để nó chơi Mario hoặc điều khiển robot. Nhưng mạng lưới thần kinh có thể tạo ra văn bản không? Chuỗi Markov có thể giúp với điều này.

Đây là lý do tại sao tôi “yêu thích” Wikipedia tiếng Nga, bởi vì bất kỳ hiện tượng/phương trình/quy tắc đơn giản nào, đặc biệt là từ toán học, đều được mô tả ngay lập tức một cách tổng quát, với những công thức khó hiểu đến mức bạn không thể hình dung ra được nếu không có nó. nửa lít. Hơn nữa, các tác giả của bài viết không thèm mô tả (ít nhất một vài câu) bằng ngôn ngữ đơn giản của con người mà chuyển ngay sang các công thức.

Nếu ai đó muốn biết chuỗi Markov là gì thì trong bản dịch đầu tiên người đó sẽ tìm ra rằng:
“Chuỗi Markov là một chuỗi các sự kiện ngẫu nhiên với số lượng kết quả hữu hạn hoặc đếm được, được đặc trưng bởi đặc tính, nói một cách lỏng lẻo, với hiện tại cố định, tương lai độc lập với quá khứ. Được đặt tên để vinh danh A. A. Markov (cấp cao). .”

Và điều này mặc dù thực tế là ý tưởng cơ bản về chuỗi Markov rất đơn giản, nhưng đơn giản là không thể hiểu được điều này từ Wikipedia nếu không được đào tạo về toán học.

Chuỗi Markov chỉ là sự mô tả xác suất của một hệ thống chuyển từ trạng thái này sang trạng thái khác. Tất cả các trạng thái có thể được mô tả bằng các đỉnh của đồ thị. Ví dụ: các đỉnh như vậy có thể là vị trí của con người: [nằm], [ngồi], [đứng], [đi]

Ở đây bạn có thể thấy rằng đồ thị có hướng, có nghĩa là không thể đi từ trạng thái này sang trạng thái khác. Ví dụ, nếu bạn đang nằm thì không thể đi lại được ngay. Trước tiên bạn phải ngồi xuống, sau đó đứng lên và chỉ sau đó mới đi bộ. Nhưng bạn có thể ngã và nằm xuống từ bất kỳ vị trí nào))
Mỗi kết nối đều có một xác suất nhất định. Vì vậy, ví dụ, khả năng bị ngã từ tư thế đứng là rất nhỏ; khả năng đứng xa hơn, đi bộ hoặc ngồi xuống là rất nhỏ; Tổng của tất cả các xác suất là 1.

Trong số những thứ khác, chuỗi Markov cho phép bạn tạo sự kiện. Bằng cách này hay cách khác, hầu hết các trình tạo văn bản đều được xây dựng trên chuỗi Markov.

Hãy thử viết một trình tạo bánh nướng.

bánh nướng

Bánh nướng là những câu thơ không có vần, dấu câu, số hoặc chữ in hoa. Số lượng âm tiết phải là 9-8-9-8.

Hầu hết các trình tạo văn bản đều sử dụng máy phân tích hình thái. Nhưng chúng tôi sẽ làm cho nó dễ dàng hơn. Chúng ta hãy chia các từ thành các âm tiết và tính xác suất để một âm tiết đứng sau một âm tiết khác. Nghĩa là, các nút của biểu đồ sẽ là các âm tiết, các cạnh và trọng số của chúng - tần số của âm tiết thứ hai theo sau âm tiết đầu tiên.
Tiếp theo, chúng ta sẽ cung cấp cho chương trình 50 chiếc bánh.

Ví dụ: sau âm tiết “at” có thể có các âm tiết sau (các cạnh và trọng lượng của chúng):
"chem" (1) "ho" (4) "tôi" (1) "du" (2) "chi" (4) "yatel" (4) "đã đi" (5) "ku" (1) " " (9) "su"(1) "vych"(3) "mi"(1) "kos"(1) "ob"(1) "det"(2) "drive"(1) "uchi"(1 ) "mu"(1) "bi"(1) "tse"(1) "int"(2) "tom"(1) "ko"(1) "shaft"(1) "nes"(1) " det"(1) "nhưng"(1) "vez"(1) "meth"(1) "vet"(1) "dia"(1) "bạn"(1)

Bây giờ tất cả những gì bạn cần làm là lấy một âm tiết ngẫu nhiên (ví dụ: "at"). Tổng của tất cả các âm tiết theo sau nó là 58. Bây giờ bạn cần lấy âm tiết tiếp theo, có tính đến tần số (số) của các âm tiết này:

size_t nth = rand() % số lượng;

size_t tất cả = 0;

for (const auto &n: next) (

Tất cả += n.count;

nếu (tất cả >= thứ n)

return n.word;

Do đó, ta tạo dòng sao cho dòng đầu tiên có 9 âm tiết, dòng thứ hai - 8, rồi 9 và 8, ta được:

Ngày xửa ngày xưa có một câu chuyện cười về chiếc đồng hồ báo thức
anh ấy đã bị bắt cóc trong khi đó
sếp của bạn đang ở đây vâng
Sofa hiệu ứng Onegin

Cho đến nay nó không giống như một văn bản đặc biệt mạch lạc. Những từ không tồn tại (“poku”) thường gặp phải. Bây giờ chỉ có một âm tiết làm chìa khóa. Nhưng thật khó để xây dựng một câu dựa trên một âm tiết. Hãy tăng số lượng âm tiết trên cơ sở đó chúng ta sẽ tạo ra âm tiết tiếp theo lên ít nhất 3:

Đủ nhựa đường cho tâm trí
bây giờ là bảy giờ chia cho
cái bàn được lấy ra, chiếc hộp đen được
anh lớn lên, trả thù, tìm thấy
Đây là chiếc bánh đầu tiên ít nhiều có thể bị nhầm lẫn là do một người viết.
Để làm cho văn bản có ý nghĩa hơn, bạn cần sử dụng máy phân tích hình thái, khi đó các nút sẽ không phải là âm tiết mà là các mô tả meta của các từ (ví dụ: “động từ, số nhiều, thì quá khứ").

Những chương trình như vậy đã cho phép bạn viết nhiều văn bản “có ý nghĩa” hơn. Ví dụ: rooter là một bài báo được viết bởi một trình tạo văn bản khoa học, đã được xem xét và thậm chí được xuất bản trên một tạp chí khoa học.

Bài viết này cung cấp cho ý tưởng chung về cách tạo văn bản bằng mô hình hóa quy trình Markov. Đặc biệt, chúng tôi sẽ giới thiệu chuỗi Markov và trên thực tế, chúng tôi sẽ triển khai một trình tạo văn bản nhỏ bằng Python.

Để bắt đầu, chúng ta hãy viết ra những định nghĩa cần thiết, nhưng chưa rõ ràng lắm, từ trang Wikipedia để ít nhất hiểu đại khái những gì chúng ta đang giải quyết:

quá trình Markov t t

Chuỗi Markov

Tất cả điều này có nghĩa là gì? Hãy tìm ra nó.

Khái niệm cơ bản

Ví dụ đầu tiên cực kỳ đơn giản. Sử dụng một câu trong sách thiếu nhi, chúng ta sẽ nắm vững khái niệm cơ bản Chuỗi Markov và cũng xác định chúng là gì trong bối cảnh của chúng ta nội dung, liên kết, phân phối xác suất và biểu đồ. Mặc dù đề xuất được đưa ra vào ngày Tiếng Anh, bản chất của lý thuyết sẽ dễ dàng được nắm bắt.

Đề xuất này là khung, tức là cơ sở mà văn bản sẽ được tạo ra trong tương lai. Nó bao gồm tám từ, nhưng chỉ có năm từ duy nhất - đây là liên kết(chúng ta đang nói về Markovian dây chuyền). Để rõ ràng, hãy tô màu từng liên kết bằng màu riêng của nó:

Và chúng tôi ghi lại số lần xuất hiện của từng liên kết trong văn bản:

Trong hình trên bạn có thể thấy từ đó "cá" xuất hiện trong văn bản thường xuyên hơn 4 lần so với các từ còn lại ( "Một", "hai", "đỏ", "xanh"). Nghĩa là, xác suất gặp từ đó trong kho ngữ liệu của chúng ta "cá" Cao hơn 4 lần so với xác suất gặp từng từ khác trong hình. Nói bằng ngôn ngữ toán học, chúng ta có thể xác định quy luật phân phối của một biến ngẫu nhiên và tính toán xác suất một trong các từ sẽ xuất hiện trong văn bản sau từ hiện tại. Xác suất được tính như sau: chúng ta cần chia số lần xuất hiện của từ chúng ta cần trong kho văn bản cho tổng số tất cả các từ trong đó. Đối với từ "cá" xác suất này là 50% vì nó xuất hiện 4 lần trong một câu 8 từ. Đối với mỗi liên kết còn lại, xác suất này là 12,5% (1/8).

Biểu diễn bằng đồ họa sự phân bố biến ngẫu nhiên có thể sử dụng biểu đồ. TRONG trong trường hợp này, tần suất xuất hiện của từng liên kết trong câu có thể thấy rõ:

Vì vậy, văn bản của chúng tôi bao gồm các từ và các liên kết duy nhất, đồng thời chúng tôi hiển thị phân bố xác suất về sự xuất hiện của từng liên kết trong một câu trên biểu đồ. Nếu bạn nghĩ rằng việc thống kê không đáng bận tâm, hãy đọc tiếp. Và có lẽ nó sẽ cứu mạng bạn.

Bản chất của định nghĩa

Bây giờ, hãy thêm vào các thành phần văn bản luôn được ngụ ý nhưng không được phát âm trong lời nói hàng ngày - phần đầu và phần cuối của câu:

Bất kỳ câu nào đều chứa những phần “bắt đầu” và “kết thúc” vô hình này; hãy thêm chúng dưới dạng liên kết đến bản phân phối của chúng tôi:

Hãy quay lại định nghĩa được đưa ra ở đầu bài:

quá trình Markov - quá trình ngẫu nhiên, sự tiến hóa của nó sau bất kỳ đặt giá trị tham số thời gian t không phụ thuộc vào sự tiến hóa trước đó t, miễn là giá trị của quá trình tại thời điểm này là cố định.

Chuỗi Markov - trường hợp đặc biệt Quá trình Markov, khi không gian các trạng thái của nó là rời rạc (nghĩa là không quá số lượng có thể đếm được).

Vậy điều này có nghĩa là gì? Nói một cách đại khái, chúng ta đang mô hình hóa một quá trình trong đó trạng thái của hệ thống tại thời điểm tiếp theo chỉ phụ thuộc vào trạng thái của nó tại thời điểm đó. thời điểm hiện tại và không phụ thuộc vào tất cả các trạng thái trước đó.

Hãy tưởng tượng những gì ở phía trước của bạn cửa sổ, chỉ hiển thị trạng thái hiện tại của hệ thống (trong trường hợp của chúng tôi, đó là một từ) và bạn cần xác định từ tiếp theo sẽ chỉ dựa trên dữ liệu được trình bày trong cửa sổ này. Trong kho văn bản của chúng ta, các từ nối tiếp nhau theo mẫu sau:

Như vậy, các cặp từ được hình thành (ngay cả cuối câu cũng có cặp từ riêng - nghĩa trống):

Hãy nhóm các cặp này theo từ đầu tiên. Chúng ta sẽ thấy rằng mỗi từ có một tập hợp các liên kết riêng, trong ngữ cảnh của câu chúng ta Có thểđi theo anh:

Hãy trình bày thông tin này theo cách khác - đối với mỗi liên kết, chúng tôi chỉ định một mảng gồm tất cả các từ có thể xuất hiện trong văn bản sau liên kết này:

Chúng ta hãy xem xét kỹ hơn. Chúng tôi thấy rằng mỗi liên kết có những từ Có thể theo sau nó trong câu. Nếu chúng ta cho người khác xem sơ đồ trên, người đó có thể tái tạo lại đề nghị ban đầu, tức là cơ thể.

Ví dụ. Hãy bắt đầu với từ "Bắt đầu". Tiếp theo chọn từ "Một", vì theo sơ đồ của chúng tôi, đây là từ duy nhất có thể theo sau đầu câu. Đằng sau lời nói "Một" cũng chỉ có thể theo sau một từ - "cá". Bây giờ đề xuất mới trong phiên bản trung gian trông giống như "Một con cá". Hơn nữa, tình hình trở nên phức tạp hơn - vì "cá" có thể có những từ có xác suất bằng 25% "hai", "đỏ", "xanh" và cuối câu "Kết thúc". Nếu chúng ta giả định rằng từ tiếp theo là "hai", việc tái thiết sẽ tiếp tục. Nhưng chúng ta có thể chọn một liên kết "Kết thúc". Trong trường hợp này, dựa trên sơ đồ của chúng tôi, một câu sẽ được tạo ngẫu nhiên rất khác với kho ngữ liệu - "Một con cá".

Chúng tôi vừa mô phỏng quá trình Markov- chỉ xác định từng từ tiếp theo trên cơ sở kiến thức về từ hiện tại. Để hiểu đầy đủ tài liệu, hãy xây dựng sơ đồ hiển thị sự phụ thuộc giữa các thành phần bên trong kho văn bản của chúng ta. Các hình bầu dục đại diện cho các liên kết. Các mũi tên dẫn đến các liên kết tiềm năng có thể theo sau từ trong hình bầu dục. Bên cạnh mỗi mũi tên là xác suất mà liên kết tiếp theo sẽ xuất hiện sau liên kết hiện tại:

Tuyệt vời! Chúng tôi đã học được thông tin cần thiếtđể tiếp tục và phân tích các mô hình phức tạp hơn.

Mở rộng cơ sở từ vựng

Trong phần này của bài viết chúng ta sẽ xây dựng một mô hình theo nguyên tắc tương tự như trước, tuy nhiên trong phần mô tả chúng ta sẽ bỏ qua một số bước. Nếu gặp khó khăn hãy quay lại phần lý thuyết ở khối đầu tiên.

Hãy lấy thêm bốn câu trích dẫn của cùng một tác giả (cũng bằng tiếng Anh, điều đó sẽ không làm chúng ta tổn thương):

“Hôm nay cậu Bạn có phải. Điều đó còn đúng hơn cả sự thật. Không có ai còn sống là bạn hơn bạn.

« bạn có não trong đầu bạn. Bạn có đôi chân trong đôi giày của bạn. Bạn có thể tự mình điều khiển theo bất kỳ hướng nào bạn chọn. Bạn đang ở một mình."

“Bạn càng đọc nhiều, bạn sẽ càng biết nhiều điều.” Bạn càng học được nhiều, bạn sẽ càng đi được nhiều nơi.”

“Nghĩ trái và suy nghĩđúng và nghĩ thấp và nghĩ cao. Ồ, những suy nghĩ bạn có thể hãy suy nghĩ nếu bạn cố gắng.”

Độ phức tạp của kho văn bản đã tăng lên, nhưng trong trường hợp của chúng tôi, đây chỉ là một điểm cộng - giờ đây trình tạo văn bản sẽ có thể tạo ra các câu có ý nghĩa hơn. Thực tế là trong bất kỳ ngôn ngữ nào cũng có những từ xuất hiện trong lời nói thường xuyên hơn những từ khác (ví dụ: chúng ta sử dụng giới từ “in” thường xuyên hơn nhiều so với từ “cryogenic”). Làm sao nhiều từ hơn trong kho văn bản của chúng tôi (và do đó có sự phụ thuộc giữa chúng), trình tạo càng có nhiều thông tin về từ nào có nhiều khả năng xuất hiện trong văn bản sau từ hiện tại.

Cách dễ nhất để giải thích điều này là từ quan điểm chương trình. Chúng tôi biết rằng đối với mỗi liên kết có một tập hợp các từ có thể theo sau nó. Ngoài ra, mỗi từ còn được đặc trưng bởi số lần xuất hiện của nó trong văn bản. Chúng tôi cần một số cách để nắm bắt tất cả thông tin này ở một nơi; Với mục đích này, một từ điển lưu trữ các cặp “(khóa, giá trị)” là phù hợp nhất. Khóa từ điển sẽ ghi lại trạng thái hiện tại của hệ thống, tức là một trong các liên kết của phần thân (ví dụ: "cái" trong hình dưới đây); và một từ điển khác sẽ được lưu trữ trong giá trị từ điển. Trong từ điển lồng nhau, các khóa sẽ là những từ có thể xuất hiện trong văn bản sau liên kết hiện tại của kho văn bản ( "nghĩ" Và "hơn" có thể theo sau trong văn bản "cái") và các giá trị là số lần xuất hiện của các từ này trong văn bản sau liên kết của chúng ta (từ "nghĩ" xuất hiện trong văn bản sau từ "cái" 1 lần, lời nói "hơn" sau từ "cái"- 4 lần):

Đọc lại đoạn văn trên nhiều lần để đảm bảo bạn hiểu chính xác. Xin lưu ý rằng từ điển lồng nhau trong trường hợp này có cùng biểu đồ; nó giúp chúng tôi theo dõi các liên kết và tần suất xuất hiện của chúng trong văn bản so với các từ khác. Cần lưu ý rằng ngay cả nền tảng từ vựng như vậy cũng rất nhỏ để tạo ra các văn bản phù hợp trong ngôn ngữ tự nhiên- nó phải chứa hơn 20.000 từ, hoặc tốt hơn nữa là hơn 100.000 và thậm chí tốt hơn là hơn 500.000. Nhưng hãy xem xét điều đó. cơ sở từ vựng, mà chúng tôi đã nhận được.

Chuỗi Markov trong trường hợp này được xây dựng tương tự như ví dụ đầu tiên - mỗi từ tiếp theo chỉ được chọn dựa trên kiến thức về từ hiện tại, tất cả các từ khác không được tính đến. Nhưng nhờ việc lưu trữ trong từ điển dữ liệu về từ nào xuất hiện thường xuyên hơn những từ khác nên chúng ta có thể chấp nhận khi lựa chọn. quyết định sáng suốt. Hãy xem một ví dụ cụ thể:

Hơn:

Nghĩa là, nếu từ hiện tại là từ "hơn", sau nó có thể có những từ có xác suất bằng 25% "đồ đạc" Và "địa điểm", và với xác suất 50% - từ "cái đó". Nhưng các xác suất đều có thể bằng nhau:

Nghĩ:

Làm việc với Windows

Cho đến nay, chúng ta mới chỉ coi cửa sổ có kích thước bằng một từ. Bạn có thể tăng kích thước cửa sổ để trình tạo văn bản tạo ra nhiều câu “đã được xác minh” hơn. Điều này có nghĩa là cửa sổ càng lớn thì độ lệch so với cơ thể trong quá trình tạo ra càng nhỏ. Việc tăng kích thước cửa sổ tương ứng với sự chuyển đổi của chuỗi Markov sang nhiều hơn nữa. trật tự cao. Trước đây, chúng ta đã xây dựng mạch bậc một; đối với một cửa sổ, hai từ sẽ tạo ra mạch bậc hai, ba từ sẽ tạo ra mạch bậc ba, v.v.

Cửa sổ- đây là dữ liệu trong trạng thái hiện tại các hệ thống được sử dụng để đưa ra quyết định. Nếu chúng ta hợp nhau cửa sổ lớn và một tập hợp dữ liệu nhỏ, thì rất có thể lần nào chúng ta cũng sẽ nhận được cùng một ưu đãi. Hãy lấy cơ sở từ vựng từ ví dụ đầu tiên của chúng tôi và mở rộng cửa sổ lên kích thước 2:

Tiện ích mở rộng có nghĩa là mỗi cửa sổ hiện chỉ có một tùy chọn cho trạng thái tiếp theo của hệ thống - bất kể chúng ta làm gì, chúng ta sẽ luôn nhận được cùng một câu, giống hệt với trường hợp của chúng ta. Do đó, để thử nghiệm với windows và để trình tạo văn bản trả về nội dung độc đáo, hãy tích trữ nền tảng từ vựng ít nhất 500.000 từ.

Triển khai bằng Python

Cấu trúc dữ liệu Dictogram

Một Dictogram (dict là kiểu dữ liệu từ điển có sẵn trong Python) sẽ hiển thị mối quan hệ giữa các liên kết và tần suất xuất hiện của chúng trong văn bản, tức là sự phân bố của chúng. Nhưng đồng thời, nó sẽ có thuộc tính từ điển mà chúng ta cần - thời gian thực hiện của chương trình sẽ không phụ thuộc vào lượng dữ liệu đầu vào, nghĩa là chúng ta đang tạo ra một thuật toán hiệu quả.

Nhập lớp ngẫu nhiên Dictogram(dict): def __init__(self, iterable=None): # Khởi tạo phân phối của chúng tôi dưới dạng đối tượng mới class, # thêm các phần tử hiện có super(Dictogram, self).__init__() self.types = 0 # số lượng khóa duy nhất trong bản phân phối self.tokens = 0 # tổng số tất cả các từ trong bản phân phối nếu có thể lặp lại: self.update( iterable) def update (self, iterable): # Cập nhật phân phối với các phần tử từ tập dữ liệu # iterable hiện có cho mục trong iterable: if item in self: self += 1 self.tokens += 1 else: self = 1 self. loại += 1 self.tokens += 1 def count(self, item): # Trả về giá trị bộ đếm của mục hoặc 0 nếu mục trong self: return self return 0 def return_random_word(self): Random_key = Random.sample(self, 1) # Cách khác: # ngẫu nhiên .choice(histogram.keys()) return Random_key def return_weighted_random_word(self): # Tạo một số giả ngẫu nhiên trong khoảng từ 0 đến (n-1), # trong đó n là tổng số từ Random_int = Random.Randint(0, self.tokens-1 ) index = 0 list_of_keys = self.keys() # print "chỉ mục ngẫu nhiên:", Random_int cho i trong phạm vi (0, self.types): chỉ mục += self] # in chỉ mục if(index > Random_int): # print list_of_keys [i] trả về list_of_keys[i]

Hàm tạo của cấu trúc Dictogram có thể được truyền vào bất kỳ đối tượng nào có thể được lặp lại. Các phần tử của đối tượng này sẽ là các từ để khởi tạo Dictogram, ví dụ như tất cả các từ trong một cuốn sách. Trong trường hợp này, chúng tôi đếm các phần tử để truy cập bất kỳ phần tử nào trong số chúng, chúng tôi không cần phải xem qua toàn bộ tập dữ liệu mỗi lần.

Chúng tôi cũng đã thực hiện hai hàm để trả về một từ ngẫu nhiên. Một hàm chọn một khóa ngẫu nhiên trong từ điển và hàm kia, tính đến số lần xuất hiện của mỗi từ trong văn bản, sẽ trả về từ chúng ta cần.

Cấu trúc chuỗi Markov

từ biểu đồ nhập Dictogram def make_markov_model(data): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Chỉ cần thêm vào phân phối hiện có markov_model].update( ]) khác: markov_model] = Dictogram() trả về markov_model

Trong cách triển khai ở trên, chúng ta có một từ điển lưu trữ windows dưới dạng khóa trong cặp “(khóa, giá trị)” và phân phối dưới dạng giá trị trong cặp đó.

Cấu trúc chuỗi Markov bậc N

from histograms import Dictogram def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Tạo một cửa sổ window = tuple(data) # Thêm vào từ điển nếu window in markov_model: # Đính kèm vào phân phối hiện có markov_model.update() else: markov_model = Dictogram() trả về markov_model

Rất giống với chuỗi Markov bậc nhất, nhưng trong trường hợp này chúng ta lưu trữ đoàn xe hộ tống làm khóa trong cặp “(khóa, giá trị)” trong từ điển. Chúng tôi sử dụng nó thay vì danh sách, vì bộ dữ liệu được bảo vệ khỏi mọi thay đổi và điều này rất quan trọng đối với chúng tôi - xét cho cùng, các khóa trong từ điển không được thay đổi.

Phân tích mô hình

Tuyệt vời, chúng tôi đã triển khai từ điển. Nhưng làm thế nào bây giờ chúng ta có thể tạo nội dung dựa trên trạng thái hiện tại và bước chuyển sang trạng thái tiếp theo? Hãy đi qua mô hình của chúng tôi:

From histograms import Dictogram import ngẫu nhiên từ các bộ sưu tập import deque import re def generate_random_start(model): # Để tạo bất kỳ từ bắt đầu nào, hãy bỏ ghi chú dòng: # return Random.choice(model.keys()) # Để tạo từ bắt đầu "chính xác" , hãy sử dụng mã bên dưới: # Các từ gốc chính xác là những từ bắt đầu câu trong kho văn bản nếu "END" trong mô hình: Seed_word = "END" while Seed_word == "END": Seed_word = model["END"]. return_weighted_random_word() trả vềseed_word trả về ngẫu nhiên.choice(model.keys()) def generate_random_sentence(length, markov_model): current_word = generate_random_start(markov_model) câu = cho i trong phạm vi (0, độ dài): current_dictogram = markov_model Random_weighted_word = current_dictogram.return_weighted_random_word () current_word = Random_weighted_word câu.append(current_word) câu = câu.capitalize() return " ".join(sentence) + "."

câu trả lời

Tiếp theo là gì?

Hãy thử nghĩ xem bạn có thể tự mình sử dụng trình tạo văn bản dựa trên chuỗi Markov ở đâu. Đừng quên rằng điều quan trọng nhất là cách bạn phân tích mô hình và những hạn chế đặc biệt mà bạn đặt ra khi tạo. Ví dụ, tác giả của bài viết này, khi tạo trình tạo tweet, đã sử dụng một cửa sổ lớn, giới hạn nội dung được tạo ở 140 ký tự và chỉ sử dụng các từ “đúng” để bắt đầu câu, tức là những từ bắt đầu câu trong tử thi. Trong xây dựng web và SEO, chuỗi Markov được sử dụng để tạo ra các văn bản giả có ý nghĩa dựa trên văn bản nguồn. Điều này được sử dụng để dập các ô cửa với quy định, để gõ nội dung văn bản hàng loạt và các thủ thuật “đen” tương tự. May mắn thay, các công cụ tìm kiếm đã học cách xác định một cách hiệu quả nội dung được tạo dựa trên chuỗi Markov và cấm những người thông minh như vậy. Tôi sẽ không dạy bạn những công nghệ như vậy, có những trang web đặc biệt tồi tệ dành cho việc này, tôi chỉ quan tâm đến việc triển khai phần mềm của thuật toán.

Chuỗi Markov là một chuỗi các phép thử trong đó mỗi phép thử chỉ xuất hiện một trong số k. sự kiện không tương thích Ai từ nhóm đầy đủ. Đồng thời xác suất có điều kiện pij(s) về thực tế là sự kiện Aj xảy ra trong phép thử thứ s, với điều kiện là sự kiện Ai xảy ra trong phép thử thứ (s - 1), không phụ thuộc vào kết quả của các phép thử trước đó.

Những ai muốn nổ tung có thể đọc về mô hình toán học. TRÊN ngôn ngữ con người Tất cả những công thức này rút gọn lại như sau. Trong văn bản nguồn, các từ được xác định và trình tự các từ theo sau được duy trì. Sau đó, dựa trên dữ liệu này, nó được tạo ra văn bản mới, trong đó các từ được chọn ngẫu nhiên nhưng mối liên hệ giữa chúng vẫn được giữ nguyên. Hãy lấy một bài đồng dao làm ví dụ:

Vì rừng, vì núi
Ông nội Egor đang đến:
bản thân tôi đang cưỡi ngựa,
vợ cưỡi bò,
trẻ em trên bắp chân,
cháu trên dê con.

Hãy phân tích văn bản thành các liên kết và liên kết

Vì [rừng, núi]
rừng [do]
núi [cưỡi]
[ông] đang đến
ông nội [Egor]
Egor [chính mình]
bản thân tôi [trên]
trên [ngựa, bò, bê, trẻ em]
ngựa [vợ]
vợ [trên]
bò [trẻ em]
trẻ em [trên]
bê [cháu]
cháu [trên]

Các liên kết trong danh sách này đại diện từ độc đáo từ văn bản và trong dấu ngoặc vuông các kết nối được liệt kê - danh sách các từ có thể xuất hiện sau từ này.

Khi tạo văn bản từ danh sách liên kết, ở lần lặp đầu tiên, một liên kết ngẫu nhiên được chọn, các kết nối của nó được xác định, một liên kết ngẫu nhiên được chọn từ danh sách liên kết và được chấp nhận làm liên kết mới. Sau đó hành động được lặp lại cho đến khi đạt đúng kích cỡ chữ. Ví dụ: kết quả có thể giống như thế này:

Bản thân Egor cưỡi bê, cháu cưỡi ngựa, vợ cưỡi bò, con cưỡi bò
Trong ví dụ này, văn bản thu được sẽ khác một chút so với văn bản gốc, vì nguồn rất ngắn. Nếu bạn lấy một từ điển ban đầu có dung lượng vài kilobyte hoặc thậm chí megabyte, thì đầu ra sẽ là một văn bản hoàn toàn mạch lạc, mặc dù nó không có ý nghĩa gì.

// Đọc văn bản nguồn trên cơ sở đó một văn bản mới sẽ được tạo
$str = file_get_contents("markov.txt");
// Đặt mã hóa hệ thống
setlocale(LC_ALL, "ru_RU.CP1251");
// Xóa ký tự khỏi văn bản ngoại trừ số, chữ cái và một số dấu chấm câu
$str = eregi_replace ("[^-a-zа-я0-9 !\?\.\,]" , " " , $str );
// Dọn dẹp khoảng trắng trước khi kết thúc câu
$str = eregi_replace (" (1,)([!\?\.\,])" , "\\1" , $str );
// Chia văn bản thành các từ
$tmp = preg_split ("/[[:space:]]+/is" , $str );
// Mảng "liên kết"
$words =Array();
// Điền vào các liên kết
cho($i = 0 ; $i< count ($tmp ); $i ++) {
if ($tmp [ $i + 1 ]!= "" ) (
$words [ $tmp [ $i ]]= $tmp [ $i + 1 ];
$words = array_map("array_unique" , $words );
// Mảng từ đầu tiên trong câu
$start =Array();
foreach($words as $word => $links ) (
if (ereg ("^[A-Z][a-Z]+" , $word )) (
$start = $word ;
// Tạo 100 câu dựa trên văn bản nguồn
với ($i = 0 ; $i< 100 ; $i ++) {
trong khi (đúng) (
$w = $start [ rand (0 ,(đếm ($start )- 1 ))];
if (ereg ("[\.!\?]$" , $w )) ( continue; )
$câu = $w . " " ;
// Số từ trong câu
$cnt = 1 ;
// Tạo ưu đãi
trong khi (đúng) (
$links = $words [ $w ];
// Chuyển đổi chuỗi
$w = $words [ $w ][ rand (0 ,(đếm ($words [ $w ])- 1 ))];
$câu .= $w . " " ;
// Nếu từ đó ở cuối câu
if (ereg ("[\.!\?]$" , $w )) ( break; )
$cnt++;
// Nếu trình tạo ở trong vòng lặp thì buộc thoát
if ($cnt > 19 ) ( break; )
// Một câu có độ dài từ 5-20 từ được coi là thành công
nếu ($cnt > 5 && $cnt< 20 ) { break; }
// Ưu đãi được tạo
tiếng vang $ câu ;

Một lời giải thích nhỏ về cách tất cả hoạt động. Đầu tiên, tệp "markov.txt" được tải, nó phải ở dạng mã hóa win-1251. Sau đó, tất cả các ký tự sẽ bị xóa khỏi nó, ngoại trừ các chữ cái và một số dấu chấm câu, đồng thời các khoảng trắng không cần thiết sẽ bị cắt bỏ. Hóa ra văn bản rõ ràng, sau đó được chia thành từ riêng lẻ. Thế là xong, chúng ta có những mắt xích riêng lẻ trong chuỗi. Bây giờ chúng ta cần xác định mối liên hệ giữa các từ, tức là từ nào có thể nằm sau từ nào. Đây là quá trình tiêu tốn nhiều tài nguyên nhất, vì vậy bạn sẽ phải kiên nhẫn với các tệp lớn. Nếu việc tạo được yêu cầu thường xuyên thì có lẽ nên lưu trữ một loạt các liên kết và liên kết trong một số cơ sở dữ liệu để có thể truy cập nhanh vào nó. Bước tiếp theo- xác định các từ bắt đầu câu. Tôi chấp nhận điều kiện là chữ cái đầu tiên của những từ đó phải viết hoa, bạn có thể làm nhiều hơn định nghĩa chính xác. Việc tạo văn bản được thực hiện theo thuật toán được mô tả ở trên, tôi vừa thêm một số kiểm tra chống lặp lại nó.

Bạn có thể xem ví dụ hoạt động của trình tạo văn bản dựa trên chuỗi Markov và tập lệnh trên