Markov zinciri basittir: Prensibe ayrıntılı olarak bakalım. Kelime tabanını genişletmek

Python programcılarının röportajlar sırasında sorduğu soruları bulmak için forumlarda geziniyordum ve çok harika bir soruyla karşılaştım. Ondan serbestçe alıntı yapacağım: "Benden n'inci dereceden Markov zincirine dayanan saçma bir jeneratör yazmamı istediler." “Ama henüz böyle bir jeneratörüm yok!” - bağırdım iç ses- “Acele et, yüceyi aç ve yaz!” - ısrarla devam etti. Aslında itaat etmem gerekiyordu.

Ve burada size bunu nasıl yaptığımı anlatacağım.

Jeneratörün tüm düşüncelerini Twitter ve web sitesinde ifade etmesine hemen karar verildi. Ana teknolojiler olarak Flask ve PostgreSQL'i seçtim. SQLAlchemy aracılığıyla birbirleriyle iletişim kuracaklar.

Yapı.

Bu yüzden. Aşağıdaki gibi modeller şöyle görünür:
class 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()) class UpperWords(db .Model): word = db.Column(db.String(40), index = Doğru, birincil_anahtar = Doğru, benzersiz = Doğru) def __repr__(self): return self.word class Phrases(db.Model): id = db .Column(db.Integer, Primary_key = True) created = db.Column(db.DateTime, default=datetime.datetime.now) tümce = db.Column(db.String(140), index = True) def __repr__(self ): return str(self.phrase)
Kaynak metin olarak popüler dizilerden altyazı alınmasına karar verildi. Srt sınıfı, bir bölüm için işlenmiş altyazılardaki tüm kelimelerin sıralı bir setini ve bu aynı kelimelerin benzersiz bir setini (tekrarlamalar olmadan) saklar. Bu, botun belirli altyazılarda bir ifadeyi aramasını kolaylaştıracaktır. İlk olarak altyazıların sözcük kümesinde sözcük kümesinin bulunup bulunmadığını kontrol edecek ve daha sonra bunların orada bulunup bulunmadığına bakacaktır. doğru sırayla.

Metindeki ifadenin ilk kelimesi ile başlayan rastgele bir kelimedir. büyük harfler. UpperWords bu tür kelimeleri saklamak için kullanılır. Kelimeler orada tekrar edilmeden aynı şekilde yazılmıştır.

Zaten oluşturulmuş tweet'leri depolamak için Phrases sınıfına ihtiyaç vardır.
Yapı son derece basittir.

.srt formatının altyazı ayrıştırıcısı ayrı bir add_srt.py modülünde bulunur. Burada olağanüstü bir şey yok ama ilgilenen varsa tüm kaynaklar GitHub'da.

Jeneratör.

Öncelikle tweetinizin ilk kelimesini seçmeniz gerekiyor. Daha önce de belirtildiği gibi bu, UpperWords modelinden herhangi bir kelime olacaktır. Seçimi fonksiyonda uygulanır:
def add_word(word_list, n): if not 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
Bu kelimenin seçimi doğrudan şu satırla uygulanır:

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

MySQL kullanıyorsanız func.random() yerine func.Rand() kullanmanız gerekir. Bu uygulamanın tek farkı budur; geri kalan her şey tamamen aynı şekilde çalışacaktır.

İlk kelime zaten oradaysa, fonksiyon zincirin uzunluğuna bakar ve buna bağlı olarak listemizi metindeki kaç kelimeyle karşılaştırmamız gerektiğini (n'inci dereceden zincir) seçer ve elde ederiz. sonraki kelime.

Ve get_word işlevindeki bir sonraki kelimeyi alıyoruz:
def get_word(word_list, n): sorgular = models.Srt.query.all() query_list = sorgulardaki sorgu için liste(): 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
Her şeyden önce, komut dosyası yüklenen tüm altyazıları çalıştırır ve kelime kümemizin belirli altyazıların sözcük kümesine dahil edilip edilmediğini kontrol eder. Daha sonra filtrelenen altyazıların metinleri tek bir listede birleştirilerek tüm cümlelerin eşleşmeleri aranır ve bu cümleleri takip eden kelimelerin konumları döndürülür. Her şey kör bir kelime seçimiyle bitiyor. Her şey hayattaki gibidir.
Kelimeler listeye bu şekilde eklenir. Tweetin kendisi bir işleve dönüştürülmüştür:
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() sonu, word_list[-1][-1] ".?!" içinde değilken: word_list.pop() " ".join(word_list) değerini döndürür
Çok basit; tweet 140 karakteri geçmemeli ve cümle sonu noktalama işaretiyle bitmelidir. Tüm. Jeneratör görevini yaptı.

Sitede sergileyin.

Views.py modülü sitedeki ekranı yönetir.
@app.route("/") def index(): return render_template("main/index.html")
Sadece şablonu görüntüler. Tüm tweet'ler js kullanılarak buradan çekilecektir.
@app.route("/page") def page(): page = int(request.args.get("page")) diff = int(request.args.get("difference")) limit = 20 kelime öbeği = models.Phrases.query.order_by(-models.Phrases.id).all() sayfalar = math.ceil(len(phrases)/float(limit)) count = len(phrases) ifadeler = ifadeler return json.dumps(( "phrases":phrases, "pages":sayfalar, "count":count), cls=controllers.AlchemyEncoder)
Belirli bir sayfadan tweetleri döndürür. Sonsuz kaydırma için bu gereklidir. Her şey oldukça sıradan. diff – güncelleme sırasında site yüklendikten sonra eklenen tweetlerin sayısı. Sayfanın tweet örnekleri bu miktarda kaydırılmalıdır.

Ve güncellemenin kendisi:
@app.route("/update") def update(): last_count = int(request.args.get("count")) ifadeler = models.Phrases.query.order_by(-models.Phrases.id).all( ) count = len(phrases) if count > last_count: ifadeler = ifadeler[:count-last_count] return json.dumps(("phrases":phrases, "count":count), cls=controllers.AlchemyEncoder) else: return json .dumps(("count":count))
İstemci tarafında ise her n saniyede bir aranır ve yeni eklenen tweetleri gerçek zamanlı olarak yükler. Tweet ekranımız bu şekilde çalışıyor. (İlgilenen olursa, controls.py'deki AlchemyEncoder sınıfına bakabilirsiniz, SQLAlchemy'den alınan tweet'leri serileştirmek için kullanılır)

Veritabanına tweet ekleme ve Twitter'a gönderme.

Twitter'da paylaşım yapmak için tweepy'yi kullandım. Çok kullanışlı pil, hemen çalışır.

Neye benziyor:
def twit(): cümle = 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)
Projenin kökündeki cron.py dosyasında bu fonksiyonu çağırdım ve tahmin edebileceğiniz gibi cron tarafından başlatılıyor. Her yarım saatte bir veritabanına ve Twitter'a yeni bir tweet ekleniyor.

Her şey işe yaradı!

Sonuç olarak.

Şu anda “Friends” ve “The Big Bang Theory” dizilerinin tüm altyazılarını indirdim. Şu ana kadar Markov zincirinin derecesini ikiye eşit olacak şekilde seçtim (altyazı tabanı arttıkça derece artacaktır). Nasıl çalıştığını görebilirsiniz

Bir nötron ağının Mario oynaması veya bir robotu kontrol etmesi için nasıl eğitileceği anlatıldı. Peki bir sinir ağı metin üretebilir mi? Markov zincirleri bu konuda yardımcı olabilir.

Bu nedenle Rusça Vikipedi'yi “seviyorum”, çünkü herhangi bir basit olgu/denklem/kural, özellikle matematikten gelenler, o kadar genel bir şekilde, o kadar akıllara durgunluk veren formüllerle hemen anlatılıyor ki, olmadan çözemezsiniz. yarım litre. Üstelik makalelerin yazarları, basit insan dilinde bir açıklama (en azından birkaç cümle) verme zahmetine girmiyor, hemen formüllere geçiyor.

Birisi Markov zincirlerinin ne olduğunu bilmek isterse, ilk çeviride şunu öğrenecektir:
“Markov zinciri, sonlu veya sayılabilir sayıda sonucu olan rastgele olaylar dizisidir; kabaca, sabit bir şimdiki zaman ile geleceğin geçmişten bağımsız olması özelliği ile karakterize edilir. Adını A. A. Markov'un (kıdemli) onuruna vermiştir. .”

Ve bu, Markov zincirlerinin temel fikrinin çok basit olmasına rağmen, bunu Wikipedia'dan matematik eğitimi olmadan anlamak imkansızdır.

Markov zincirleri sadece bir sistemin bir durumdan diğerine geçiş olasılıklarının bir açıklamasıdır. Tüm durumlar grafiğin köşeleriyle açıklanabilir. Örneğin, bu tür köşeler insan konumları olabilir: [yatma], [oturma], [ayakta durma], [yürüme]

Burada grafiğin yönlendirildiğini görüyorsunuz, bu da her durumdan diğerine geçmenin mümkün olmadığı anlamına geliyor. Mesela yatıyorsanız hemen yürümeniz mümkün değildir. Önce oturmanız, sonra ayağa kalkmanız ve ancak ondan sonra yürümeniz gerekir. Ama düşebilir ve herhangi bir pozisyonda uzanabilirsiniz))
Her bağlantının belirli bir olasılığı vardır. Yani örneğin ayakta dururken düşme olasılığı çok azdır; daha fazla ayakta durmak, yürümek veya oturmak çok daha olasıdır. Tüm olasılıkların toplamı 1'dir.

Diğer şeylerin yanı sıra Markov zincirleri olaylar oluşturmanıza olanak tanır. Öyle ya da böyle çoğu metin oluşturucu Markov zincirleri üzerine kuruludur.

Bir turta üreteci yazmaya çalışalım.

Turtalar

Turtalar kafiye, noktalama işareti, sayı veya büyük harf içermeyen dörtlüklerdir. Hece sayısı 9-8-9-8 olmalıdır.

Çoğu metin oluşturucu morfolojik analizörleri kullanır. Ama bunu kolaylaştıracağız. Şimdi kelimeleri hecelere ayıralım ve bir hecenin diğer heceden sonra gelme olasılığını hesaplayalım. Yani, grafiğin düğümleri heceler, kenarlar ve bunların ağırlıkları (birinciden sonraki ikinci hecenin sıklığı) olacaktır.
Daha sonra programa elli turta besleyeceğiz.

Örneğin “pri” hecesinden sonra şu heceler gelebilir (kenarlar ve ağırlıkları):
"chem" (1) "ho" (4) "me" (1) "du" (2) "chi" (4) "yatel" (4) "gitti" (5) "ku" (1) " " (9) "su"(1) "vych"(3) "mi"(1) "kos"(1) "ob"(1) "det"(2) "sürüş"(1) "uchi"(1 ) "mu"(1) "bi"(1) "tse"(1) "int"(2) "tom"(1) "ko"(1) "mil"(1) "nes"(1) " det"(1) "ama"(1) "vez"(1) "meth"(1) "veteriner"(1) "dia"(1) "sen"(1)

Şimdi tek yapmanız gereken rastgele bir hece almak (örneğin, "at"). Ondan sonra gelen tüm hecelerin toplamı 58'dir. Şimdi bu hecelerin sıklığını (sayısını) dikkate alarak bir sonraki heceyi almanız gerekir:

size_t nth = Rand() % sayım;

size_t hepsi = 0;

for (const auto &n: sonraki) (

Hepsi += n.sayım;

if (tümü >= n'inci)

n.word'ü döndür;

Böylece, ilk satırda 9 hece, ikincisinde - 8, sonra 9 ve 8 olacak şekilde satırlar oluştururuz:

Bir zamanlar çalar saatle ilgili bir şaka vardı
o sırada kaçırıldı
patronun burada evet
Onegin efektli kanepe

Şu ana kadar pek tutarlı bir metne benzemiyor. Varolmayan kelimelerle (“poku”) sıklıkla karşılaşılır. Artık anahtar olarak yalnızca bir hece var. Ancak tek heceye dayalı bir cümle kurmak zordur. Bir sonraki heceyi oluşturacağımız hece sayısını en az 3'e çıkaralım:

Zihne yetecek kadar asfalt
saat yedi bölü
masa çıkarıldı, kara kutu
büyüdü, intikam aldı, buldu
İşte az çok bir kişi tarafından yazıldığı yanılgısına düşülebilecek ilk pasta.
Metni daha anlamlı hale getirmek için morfolojik analizörleri kullanmanız gerekir; bu durumda düğümler heceler değil, kelimelerin meta açıklamaları olacaktır (örneğin, “fiil, çoğul, geçmiş zaman").

Bu tür programlar zaten daha “anlamlı” metinler yazmanıza olanak sağlıyor. Örneğin kök oluşturucu, bilimsel bir metin oluşturucu tarafından yazılan, incelenen ve hatta bilimsel bir dergide yayınlanan bir makaledir.

Bu makale şunları sağlar: genel fikir Markov süreç modellemesini kullanarak metinlerin nasıl oluşturulacağı hakkında. Özellikle Markov zincirlerini tanıtacağız ve pratik olarak Python'da küçük bir metin oluşturucu uygulayacağız.

Başlangıç olarak, neyle uğraştığımızı en azından kabaca anlamak için Wikipedia sayfasından gerekli ancak henüz çok net olmayan tanımları yazalım:

Markov süreci T T

Markov zinciri

Bütün bunlar ne anlama geliyor? Hadi çözelim.

Temel bilgiler

İlk örnek son derece basittir. Bir çocuk kitabındaki bir cümleyi kullanarak ustalaşacağız temel kavram Markov zincirleri ve ayrıca bizim bağlamımızda ne olduklarını tanımlayın gövde, bağlantılar, olasılık dağılımı ve histogramlar. Teklifin verilmesine rağmen İngilizce teorinin özünü kavramak kolay olacaktır.

Bu öneri çerçeve yani metnin gelecekte oluşturulacağı temel. Sekiz kelimeden oluşur, ancak yalnızca beş benzersiz kelime vardır - bu bağlantılar(Markovian'dan bahsediyoruz zincirler). Netlik sağlamak için her bağlantıyı kendi rengine boyayalım:

Ve metindeki her bağlantının oluşum sayısını yazıyoruz:

Yukarıdaki resimde bu kelimenin olduğunu görebilirsiniz. "balık" metinde diğer kelimelerin her birinden 4 kat daha sık geçiyor ( "Bir", "iki", "kırmızı", "mavi"). Yani kelimenin derlemimizde karşılaşma olasılığı "balık"Şekilde gösterilen diğer tüm kelimelerle karşılaşma ihtimaliniz 4 kat daha yüksektir. Matematik dilinde konuşursak, bir rastgele değişkenin dağılım yasasını belirleyebilir ve kelimelerden birinin metinde mevcut kelimeden sonra hangi olasılıkla görüneceğini hesaplayabiliriz. Olasılık şu şekilde hesaplanır: İhtiyacımız olan kelimenin derlemde geçme sayısını şuna bölmemiz gerekir: toplam sayı içindeki tüm kelimeler. Kelime için "balık" 8 kelimelik bir cümlede 4 kez geçtiği için bu olasılık %50'dir. Geriye kalan bağlantıların her biri için bu olasılık %12,5’tir (1/8).

Dağıtımı grafiksel olarak temsil edin rastgele değişkenler kullanarak mümkün histogramlar. İÇİNDE bu durumda, cümledeki bağlantıların her birinin görülme sıklığı açıkça görülebilir:

Yani metnimiz kelimelerden ve benzersiz bağlantılardan oluşuyor ve her bir bağlantının bir cümlede görünmesinin olasılık dağılımını histogram üzerinde gösterdik. İstatistiklerle uğraşmaya değmeyeceğini düşünüyorsanız okumaya devam edin. Ve belki de hayatınızı kurtaracaktır.

Tanımın özü

Şimdi metinlerimize her zaman ima edilen ancak günlük konuşmada dile getirilmeyen öğeleri - cümlenin başlangıcını ve sonunu - ekleyelim:

Her cümle bu görünmez “başlangıç” ve “son”u içerir; bunları dağıtımımıza bağlantılar olarak ekleyelim:

Yazının başında verilen tanıma dönelim:

Markov süreci - rastgele süreç, herhangi bir evrimden sonra evrimi değeri belirle zaman parametresi Tönceki evrime bağlı değildir TŞu andaki sürecin değerinin sabit olması şartıyla.

Markov zinciri - özel durum Markov süreci, durumlarının uzayı ayrık olduğunda (yani sayılabilirden fazla olmadığında).

Peki bu ne anlama geliyor? Kabaca söylemek gerekirse, sistemin bir sonraki andaki durumunun yalnızca o andaki durumuna bağlı olduğu bir süreci modelliyoruz. şimdiki an ve hiçbir şekilde önceki durumların tümüne bağlı değildir.

Önünüzde ne olduğunu hayal edin pencere yalnızca sistemin mevcut durumunu görüntüleyen (bizim durumumuzda bu bir kelimedir) ve yalnızca bu pencerede sunulan verilere dayanarak bir sonraki kelimenin ne olacağını belirlemeniz gerekir. Derlemimizde kelimeler aşağıdaki kalıba göre birbirini takip eder:

Böylece kelime çiftleri oluşur (cümlenin sonunun bile kendi çifti vardır - boş bir anlam):

Bu çiftleri ilk kelimeye göre gruplayalım. Her kelimenin, cümlemizin bağlamında kendi bağlantı kümesine sahip olduğunu göreceğiz. olabilmek onu takip et:

Bu bilgiyi başka bir şekilde sunalım - her bağlantı için, bu bağlantıdan sonra metinde görünebilecek tüm kelimelerin bir dizisini atadık:

Daha yakından bakalım. Her bağlantının kelimeler içerdiğini görüyoruz. olabilmek bir cümleyle arkasından gelin. Yukarıdaki diyagramı bir başkasına gösterseydik, o kişi büyük olasılıkla bizim şemamızı yeniden oluşturabilirdi. ilk teklif yani vücut.

Örnek. Kelimeyle başlayalım "Başlangıç". Daha sonra kelimeyi seçin "Bir", çünkü şemamıza göre bu, bir cümlenin başlangıcından sonra gelebilen tek kelimedir. Kelimenin Arkasında "Bir" ayrıca sadece bir kelime takip edebilir - "balık". Artık ara versiyondaki yeni teklif şuna benziyor "Bir balık". Dahası durum daha da karmaşıklaşıyor; "balık"%25 eşit olasılığa sahip kelimeler olabilir "iki", "kırmızı", "mavi" ve cümlenin sonu "Son". Bir sonraki kelimenin olduğunu varsayarsak "iki", yeniden yapılanma devam edecek. Ama bir bağlantı seçebiliriz "Son". Bu durumda, şemamıza göre, bütünceden çok farklı olan rastgele bir cümle oluşturulacaktır. "Bir balık".

Sadece simüle ettik Markov süreci- sonraki her kelimeyi yalnızca mevcut kelime hakkındaki bilgiye dayanarak tanımladı. Materyali tam olarak anlamak için, külliyatımızın içindeki öğeler arasındaki bağımlılıkları gösteren diyagramlar oluşturalım. Ovaller bağlantıları temsil eder. Oklar, oval içindeki kelimeyi takip edebilecek potansiyel bağlantılara yönlendirir. Her okun yanında, mevcut bağlantıdan sonra bir sonraki bağlantının görünme olasılığı bulunur:

Harika! öğrendik gerekli bilgiler devam etmek ve daha karmaşık modelleri analiz etmek.

Kelime tabanını genişletmek

Makalenin bu bölümünde öncekiyle aynı prensibe göre bir model oluşturacağız ancak açıklamalarda bazı adımları atlayacağız. Herhangi bir zorlukla karşılaşırsanız ilk bloktaki teoriye dönün.

Aynı yazardan dört alıntı daha alalım (İngilizce de olsa zararı olmaz):

"Bugün sen sen misin. Bu gerçekten daha doğrudur. Hayatta senden başka sen olan kimse yok."

« Var beyin kafanın içinde. Ayakkabının içinde ayakların var. Kendinizi seçtiğiniz herhangi bir yöne yönlendirebilirsiniz. Tek başınasın."

“Ne kadar çok okursanız, o kadar çok şey bileceksiniz.” Ne kadar çok öğrenirsen o kadar çok yere gidersin.”

"Sol düşün ve düşün doğru ve düşük düşün ve yüksek düşün. Ah, düşünüyor yapabilirsiniz denersen düşün.”

Derlemin karmaşıklığı arttı, ancak bizim durumumuzda bu yalnızca bir artı - artık metin oluşturucu daha anlamlı cümleler üretebilecek. Gerçek şu ki, herhangi bir dilde konuşmada diğerlerinden daha sık görülen kelimeler vardır (örneğin, "in" edatını "kriyojenik" kelimesinden çok daha sık kullanırız). Nasıl daha fazla kelime Bizim külliyatımızda (ve dolayısıyla aralarındaki bağımlılıklarda), oluşturucunun mevcut kelimeden sonra metinde hangi kelimenin görüneceği hakkında o kadar fazla bilgisi olur.

Bunu açıklamanın en kolay yolu program bakış açısındandır. Her bağlantı için onu takip edebilecek bir dizi kelime bulunduğunu biliyoruz. Ayrıca her kelime, metindeki geçiş sayısına göre de karakterize edilir. Tüm bu bilgileri tek bir yerde toplamanın bir yoluna ihtiyacımız var; Bu amaçla “(anahtar, değer)” çiftlerini saklayan bir sözlük en uygunudur. Sözlük anahtarı sistemin mevcut durumunu, yani gövdenin bağlantılarından birini (örneğin, "" aşağıdaki resimde); ve başka bir sözlük sözlük değerinde saklanacaktır. Yuvalanmış sözlükte anahtarlar, derlemin geçerli bağlantısından sonra metinde görünebilecek kelimeler olacaktır ( "düşünüyor" Ve "Daha" metinde sonra gelebilir "") ve değerler bu kelimelerin metinde bağlantımızdan sonraki görünme sayısıdır (kelime "düşünüyor" metinde kelimeden sonra görünür "" 1 kez, kelime "Daha" kelimeden sonra ""- 4 kez):

Yukarıdaki paragrafı tam olarak anladığınızdan emin olmak için birkaç kez tekrar okuyun. Bu durumda iç içe geçmiş sözlüğün aynı histogram olduğunu lütfen unutmayın; bu, bağlantıları ve bunların metinde diğer kelimelere göre görülme sıklığını izlememize yardımcı olur. Böyle bir kelime tabanının bile metinlerin doğru şekilde üretilmesi için çok küçük olduğu unutulmamalıdır. doğal dil- 20.000'den fazla kelime içermeli, daha da iyisi 100.000'den fazla, hatta daha iyisi 500.000'den fazla. Ama gelin şuna bir bakalım. kelime tabanı, bunu aldık.

Bu durumda Markov zinciri ilk örneğe benzer şekilde oluşturulmuştur - sonraki her kelime yalnızca mevcut kelime hakkındaki bilgilere dayanarak seçilir, diğer tüm kelimeler dikkate alınmaz. Ancak hangi kelimelerin diğerlerinden daha sık göründüğüne dair veri sözlüğündeki depolama sayesinde, seçim yaparken kabul edebiliriz. bilgilendirilmiş karar. Belirli bir örneğe bakalım:

Daha fazla:

Yani, eğer mevcut kelime kelime ise "Daha", ondan sonra %25 eşit olasılıkla kelimeler gelebilir "şeyler" Ve "yer" ve% 50 olasılıkla - kelime "O". Ancak olasılıkların tümü eşit olabilir:

Düşünmek:

Windows'la çalışma

Şu ana kadar sadece tek kelime büyüklüğündeki pencereleri değerlendirdik. Metin oluşturucunun daha fazla "doğrulanmış" cümle üretmesi için pencerenin boyutunu artırabilirsiniz. Bu, pencere ne kadar büyük olursa, nesil sırasında vücuttan sapmaların o kadar küçük olduğu anlamına gelir. Pencere boyutunun arttırılması Markov zincirinin daha fazlasına geçişine karşılık gelir. yüksek sipariş. Daha önce birinci dereceden bir devre kurmuştuk; bir pencere için iki kelime ikinci dereceden bir devre üretecek, üç kelime üçüncü dereceden bir devre üretecektir vb.

Pencere- bu içindeki veriler mevcut durum Karar vermek için kullanılan sistemler. Eğer eşleşirsek büyük pencere ve küçük bir veri kümesi varsa, büyük olasılıkla her seferinde aynı cümleyi alacağız. İlk örneğimizdeki kelime tabanını alalım ve pencereyi 2 boyutuna genişletelim:

Uzantı, artık her pencerenin sistemin bir sonraki durumu için yalnızca bir seçeneğe sahip olduğu anlamına geliyor; ne yaparsak yapalım, her zaman aynı cümleyi alacağız, bizim durumumuzun aynısı. Bu nedenle, pencerelerle denemeler yapmak ve metin oluşturucunun benzersiz içerik döndürmesi için en az 500.000 kelimelik bir kelime tabanı stoklayın.

Python'da Uygulama

Diktogram veri yapısı

Bir Diktogram (dict, Python'da yerleşik bir sözlük veri türüdür), bağlantılar ile bunların metinde bulunma sıklıkları arasındaki ilişkiyi, yani bunların dağılımını gösterecektir. Ancak aynı zamanda ihtiyacımız olan sözlük özelliğine de sahip olacak - programın yürütme süresi girdi verilerinin miktarına bağlı olmayacak, bu da etkili bir algoritma oluşturduğumuz anlamına geliyor.

Rastgele sınıfı içe aktar Dictogram(dict): def __init__(self, iterable=None): # Dağıtımımızı şu şekilde başlat: yeni nesne sınıf, # mevcut öğeleri ekleyin super(Dictogram, self).__init__() self.types = 0 # dağıtımdaki benzersiz anahtarların sayısı self.tokens = 0 # yinelenebilirse dağıtımdaki tüm kelimelerin toplam sayısı: self.update( yinelenebilir) def güncelleme (kendi kendine, yinelenebilir): # Dağılımı, yinelenebilir öğe için mevcut # yinelenebilir veri kümesindeki öğelerle güncelleyin: if item in self: self += 1 self.tokens += 1 else: self = 1 self. type += 1 self.tokens += 1 def count(self, item): # Öğenin sayaç değerini döndürür veya item in self içindeyse 0: return self return 0 def return_random_word(self): random_key = random.sample(self, 1) # Başka bir yol: # random .choice(histogram.keys()) return random_key def return_weighted_random_word(self): # 0 ile (n-1) arasında sözde rastgele bir sayı oluşturun, # burada n toplam sözcük sayısıdır random_int = random.randint(0, self.tokens-1 ) index = 0 anahtarların listesi = self.keys() # print "rastgele indeks:", range(0, self.types) içindeki i için random_int: indeks += self] # dizini yazdır if(index > rastgele_int): # anahtarların_listesini yazdır [i] anahtarların_listesini döndür[i]

Diktogram yapısının yapıcısına, yinelenebilecek herhangi bir nesne aktarılabilir. Bu nesnenin unsurları, Diktogramı başlatacak kelimeler, örneğin bir kitaptaki tüm kelimeler olacaktır. Bu durumda, elemanları sayarız, böylece herhangi birine erişmek için her seferinde veri setinin tamamını gözden geçirmek zorunda kalmazız.

Ayrıca rastgele bir kelime döndürmek için iki fonksiyon yaptık. İşlevlerden biri sözlükte rastgele bir anahtar seçer, diğeri ise her kelimenin metinde geçme sayısını dikkate alarak ihtiyacımız olan kelimeyi döndürür.

Markov zincir yapısı

histogramlardan içe aktar Diktogram def make_markov_model(veri): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Sadece mevcut bir dağıtıma ekleyin markov_model].update( ]) else: markov_model] = Dictogram() return markov_model

Yukarıdaki uygulamada pencereleri “(anahtar, değer)” çiftinde anahtar olarak ve dağıtımları da bu çiftteki değerler olarak saklayan bir sözlüğümüz var.

N'inci dereceden Markov zincir yapısı

histogramlardan içe aktar Diktogram def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Bir pencere oluştur window = tuple(data) # Eğer pencere içerideyse sözlüğe ekle markov_model: # Mevcut bir dağıtıma ekle markov_model.update() else: markov_model = Dictogram() return markov_model

Birinci dereceden Markov zincirine çok benzer, ancak bu durumda saklıyoruz konvoy sözlükteki “(anahtar, değer)” çiftindeki anahtar olarak. Tuple herhangi bir değişiklikten korunduğu için liste yerine bunu kullanıyoruz ve bu bizim için önemli - sonuçta sözlükteki anahtarlar değişmemeli.

Model ayrıştırma

Harika, sözlüğü hayata geçirdik. Peki şimdi mevcut duruma ve bir sonraki duruma atılan adıma göre nasıl içerik üretebiliriz? Modelimizi inceleyelim:

Histogramlardan içe aktar Diktogram koleksiyonlardan rastgele içe aktar import deque import re def created_random_start(model): # Herhangi bir tohum oluşturmak için satırın açıklamasını kaldırın: # return random.choice(model.keys()) # "Doğru" tohumu oluşturmak için şunu kullanın: aşağıdaki kod: # Doğru tohum sözcükleri, modelde "END" ise: tohum_kelime = "END" iken tohum_kelime == "END": tohum_kelime = model["END"].return_weighted_random_word( ) return tohum_kelimesi return random.choice(model.keys()) def created_random_sentence(uzunluk, markov_model): current_word = created_random_start(markov_model) cümle = for i in range(0, uzunluk): current_dictogram = markov_model random_weighted_word = current_dictogram.return_weighted_random_word() current_word = rastgele_ağırlıklı_kelime cümle.append(current_word) cümle = cümle.capitalize() return " ".join(sentence) + "."

dönüş cümlesi

Sırada ne var?

Markov zincirlerine dayalı bir metin oluşturucuyu nerede kullanabileceğinizi kendi başınıza düşünmeye çalışın. En önemli şeyin modeli nasıl ayrıştırdığınız ve üretime hangi özel kısıtlamaları koyduğunuz olduğunu unutmayın. Örneğin bu makalenin yazarı, tweet oluşturucuyu oluştururken geniş bir pencere kullandı, oluşturulan içeriği 140 karakterle sınırladı ve cümlelere başlamak için yalnızca "doğru" kelimeleri, yani cümlenin başlangıcını kullandı. korpus. Web yapımında ve SEO'da Markov zincirleri, kaynak metinlere dayalı sözde anlamlı metinler oluşturmak için kullanılır. Bu, belirtilen kapı aralıklarını damgalamak için kullanılır, içerik metni kütlesini ve benzer "siyah" hileleri yazmak için. Neyse ki arama motorları Markov zincirlerine dayalı olarak oluşturulan içerikleri etkili bir şekilde tanımlamayı ve bu tür akıllı insanları yasaklamayı öğrendi. Sana bu tür teknolojileri öğretmeyeceğim, bunun için özel boktan siteler var, ben sadece algoritmanın yazılım uygulamasıyla ilgileniyorum.

Markov zinciri, her birinde k'den yalnızca birinin yer aldığı bir dizi testtir. uyumsuz olaylar Ai'den tam grup. Aynı zamanda koşullu olasılık Ai olayının (s - 1)'inci denemede meydana gelmesi koşuluyla, Aj olayının s'inci denemede meydana gelmesinin pij(leri), önceki denemelerin sonuçlarına bağlı değildir.

Beynini uçurmak isteyenler okuyabilir matematiksel model. Açık insan dili Tüm bu formüller aşağıdakilere indirgenir. Kaynak metinde kelimeler tanımlanır ve hangi kelimelerin ardından geldiği sırası korunur. Daha sonra bu verilere dayanarak oluşturulur. yeni metin Kelimelerin rastgele seçildiği ancak aralarındaki bağlantıların korunduğu. Örnek olarak bir çocuk tekerlemesini ele alalım:

Orman yüzünden, dağlar yüzünden
Büyükbaba Egor geliyor:
kendimi bir atın üstünde,
ineğe binen karısı,
buzağılardaki çocuklar,
yavru keçilerin torunları.

Metni bağlantılara ve bağlantılara ayrıştıralım

[Orman, dağlar] nedeniyle
ormanlar [nedeniyle]
dağlar
[büyükbaba] geliyor
büyükbaba [Egor]
Egor [kendisi]
kendim
[at, inek, buzağılar, çocuklar] üzerinde
at [karısı]
karısı
inek [çocuklar]
çocuklar
buzağılar [torunlar]
torunlar

Bu listedeki bağlantılar temsil eder benzersiz kelimeler metinden ve köşeli parantezler bağlantılar listelenir - bu kelimeden sonra görünebilecek kelimelerin listesi.

Bağlantı listesinden metin oluşturulurken ilk yinelemede rastgele bir bağlantı seçilir, bağlantıları belirlenir, bağlantılar listesinden rastgele bir bağlantı seçilir ve yeni bağlantı olarak kabul edilir. Daha sonra eylem ulaşıncaya kadar tekrarlanır. doğru boyut metin. Sonuç örneğin şöyle bir şey olabilir:

Egor'un kendisi bir buzağının üzerinde, torunları bir atın üzerinde, karısı bir ineğin üzerinde, çocuklar bir ineğin üzerinde
Bu örnekte ortaya çıkan metin orijinal metinden çok az farklılık gösterir çünkü kaynakçok kısa. Birkaç kilobaytlık, hatta megabaytlık bir ilk sözlüğü alırsanız, hiçbir anlam ifade etmese de çıktı tamamen tutarlı bir metin olacaktır.

// Yenisinin oluşturulacağı kaynak metni okuyun
$str = file_get_contents("markov.txt");
// Sistem kodlamasını ayarlayın
setlocale(LC_ALL, "ru_RU.CP1251");
// Sayılar, harfler ve bazı noktalama işaretleri dışındaki karakterleri metinden kaldırın
$str = eregi_replace ("[^-a-zа-я0-9 !\?\.\,]" , " " , $str );
// Cümleleri bitirmeden önce boşlukları temizleyin
$str = eregi_replace (" (1,)([!\?\.\,])" , "\\1" , $str );
// Metni kelimelere böl
$tmp = preg_split ("/[[:space:]]+/is", $str );
// "Bağlantılar" dizisi
$kelimeler =Dizi();
// Bağlantıları doldur
for($i = 0 ; $i< count ($tmp ); $i ++) {
if ($tmp [ $i + 1 ]!= "" ) (
$kelimeler [ $tmp [ $i ]]= $tmp [ $i + 1 ];
$kelimeler = array_map("dizi_benzersiz", $kelimeler);
// Sıralamak ilk kelimeler cümlelerde
$başlangıç =Dizi();
foreach($words as $word => $bağlantılar ) (
if (ereg ("^[A-Z][a-Z]+" , $kelime )) (
$başlangıç = $kelime;
// Kaynak metne göre 100 cümle oluştur
için ($i = 0; $i< 100 ; $i ++) {
iken (doğru) (
$w = $başlangıç [ rand (0 ,(sayım ($başlangıç )- 1 ))];
if (ereg ("[\.!\?]$", $w )) ( devam et; )
$cümle = $w . " ";
// Cümledeki kelime sayısı
$cnt = 1;
// Teklif oluştur
while(doğru) (
$bağlantılar = $kelimeler [ $w ];
// Anahtar zinciri
$w = $kelimeler [ $w ][ rand (0 ,(count ($kelimeler [ $w ])- 1 ))];
$cümle .= $w . " ";
// Kelime cümlenin sonunda olsaydı
if (ereg ("[\.!\?]$", $w )) ( mola; )
$cnt++;
// Jeneratör bir döngüdeyse, çıkışı zorla
if ($cnt > 19 ) ( ara; )
// 5-20 kelime uzunluğundaki bir cümle başarılı sayılır
if ($cnt > 5 && $cnt< 20 ) { break; }
// Oluşturulan teklif
echo $cümle;

Her şeyin nasıl çalıştığına dair küçük bir açıklama. Öncelikle "markov.txt" dosyası yükleniyor, win-1251 kodlamasında olması gerekiyor. Daha sonra harfler ve bazı noktalama işaretleri dışında tüm karakterler kaldırılır ve ardından gereksiz boşluklar kesilir. Görünüşe göre metni temizle, daha sonra ikiye bölünür bireysel kelimeler. İşte bu, zincirde bireysel bağlantılarımız var. Artık kelimeler arasındaki bağlantıları yani hangi kelimelerin hangi kelimelerin arkasında yer alabileceğini belirlememiz gerekiyor. Bu, kaynak açısından en yoğun süreç olduğundan, büyük dosyalar konusunda sabırlı olmanız gerekecektir. Oluşturma sık sık gerekliyse, hızlı erişim sağlamak için bir veri tabanında bir dizi bağlantı ve bağlantı depolamak muhtemelen mantıklı olacaktır. Sonraki adım- cümlelerin başladığı kelimelerin belirlenmesi. Bu tür kelimelerin ilk harfinin büyük olması şartını kabul ettim, daha fazlasını yapabilirsiniz kesin tanım. Metin oluşturma yukarıda açıklanan algoritmaya göre gerçekleştirilir, ona döngüye karşı birkaç kontrol ekledim.

Markov zincirlerine ve yukarıdaki komut dosyasına dayanan bir metin oluşturucunun çalışan bir örneğini görebilirsiniz.