Markov zinciri basittir: Prensibe ayrıntılı olarak bakalım. Veritabanına tweet ekleme ve Twitter'da yayınlama

Bir nötron ağının Mario oynaması veya bir robotu kontrol etmesi için nasıl eğitileceği anlatıldı. Ama yapabilir sinir ağı metin oluştur? Markov zincirleri bu konuda yardımcı olabilir.

İşte bu yüzden 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 bir açıklama (en azından birkaç cümle) verme zahmetine girmiyorlar. insan dili ve doğrudan formüllere gidin.

Birisi Markov zincirlerinin ne olduğunu bilmek isterse, ilk çeviride şunu bulacaktır:
"Markov zinciri bir dizidir rastgele olaylar Sonlu veya sayılabilir sayıda sonuçları olan, genel anlamda sabit bir şimdi ile geleceğin geçmişten bağımsız olduğu özelliği ile karakterize edilen. A. A. Markov'un (kıdemli) onuruna verilmiş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. Örneğin yatıyorsanız hemen yürümeniz imkansızdır. Ö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ı olmadan dörtlükler büyük harfler. 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 “at” 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örler 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 tanı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.

Markov zinciri, her bir sonraki olayın bir öncekine bağlı olduğu bir olaylar dizisidir. Bu yazımızda bu kavramı daha detaylı inceleyeceğiz.

Markov zinciri, rastgele olayları modellemenin yaygın ve oldukça basit bir yoludur. Çoğunda kullanılır farklı alanlar metin üretiminden finansal modellemeye kadar. En çok ünlü örnek SubredditSimulator'dur. İÇİNDE bu durumda Markov zinciri, alt dizi boyunca içerik oluşturmayı otomatikleştirmek için kullanılır.

Markov zinciri herhangi bir istatistiksel veya matematiksel kavram kullanılmadan uygulanabildiği için açık ve kullanımı kolaydır. Markov zinciri olasılıksal modellemeyi ve veri bilimini öğrenmek için idealdir.

Senaryo

Sadece iki tane olduğunu hayal et hava koşulları: Güneşli veya bulutlu olabilir. Hava durumunu her zaman doğru bir şekilde belirleyebilirsiniz. şimdiki an. Açık veya bulutlu olması garanti edilir.

Artık yarının hava durumunu nasıl tahmin edeceğinizi öğrenmek istiyorsunuz. Sezgisel olarak havanın bir günde dramatik bir şekilde değişemeyeceğini anlıyorsunuz. Bu birçok faktörden etkilenir. Yarının hava durumu doğrudan şu andaki hava durumuna vb. bağlıdır. Dolayısıyla, hava durumunu tahmin etmek için birkaç yıl boyunca veri toplarsınız ve bulutlu bir günün ardından güneşli bir günün olasılığının 0,25 olduğu sonucuna varırsınız. Yalnızca iki olası hava koşuluna sahip olduğumuz için arka arkaya iki bulutlu günün olasılığını 0,75 olarak varsaymak mantıklıdır.

Artık mevcut hava durumuna göre hava durumunu birkaç gün önceden tahmin edebilirsiniz.

Bu örnek gösteriyor anahtar kavramlar Markov zincirleri. Bir Markov zinciri, bir olasılık dağılımı tarafından belirlenen ve Markov özelliğini karşılayan bir dizi geçişten oluşur.

Örnekte olasılık dağılımının yalnızca geçişlere bağlı olduğunu lütfen unutmayın. şimdiki gün bir sonrakine. Bu benzersiz özellik Markov süreci - bunu hafızayı kullanmadan yapar. Tipik olarak bu yaklaşım herhangi bir eğilimin gözlemlendiği bir dizi oluşturamaz. Örneğin Markov zinciri, bir kelimenin kullanım sıklığına göre yazma stilini simüle edebilirken, bir kelimenin kullanım sıklığına göre metinler oluşturamaz. derin anlam yalnızca büyük metinlerle çalışabildiği için. Bu nedenle Markov zinciri bağlama bağlı içerik üretemez.

Modeli

Biçimsel olarak Markov zinciri olasılıksal bir otomattır. Geçiş olasılığı dağılımı genellikle bir matris olarak temsil edilir. Bir Markov zincirinde N varsa olası durumlar ise, matris N x N formunda olacaktır; burada (I, J) girişi, I durumundan J durumuna geçiş olasılığı olacaktır. Ek olarak, böyle bir matris stokastik olmalıdır, yani satırlar veya sütunların toplamı bir olmalıdır. Böyle bir matriste her satır kendi olasılık dağılımına sahip olacaktır.

Durumları daire şeklinde ve kenarları geçiş şeklinde olan bir Markov zincirinin genel görünümü.

Üç olası duruma sahip örnek bir geçiş matrisi.

Markov zinciri var başlangıç vektörü N x 1 matrisi olarak temsil edilen durumlar, N olası durumların her birinde başlangıcın olasılık dağılımlarını tanımlar. Giriş I, zincirin I durumunda başlama olasılığını açıklar.

Bu iki yapı Markov zincirini temsil etmek için oldukça yeterlidir.

Bir durumdan diğerine geçiş olasılığının nasıl elde edileceğini zaten tartıştık, peki ya bu olasılığı birkaç adımda elde etmeye ne dersiniz? Bunu yapabilmek için M adımlarında I durumundan J durumuna geçiş olasılığını belirlememiz gerekir. Aslında çok basit. Geçiş matrisi P, P'nin M gücüne yükseltilmesiyle (I, J) hesaplanarak belirlenebilir. Küçük M değerleri için bu, tekrarlanan çarpma kullanılarak manuel olarak yapılabilir. Ama için büyük değerler Eğer aşina iseniz M doğrusal cebir, Daha verimli bir şekilde Bir matrisi bir kuvvete yükseltmek ilk önce o matrisi köşegenleştirecektir.

Markov zinciri: sonuç

Artık Markov zincirinin ne olduğunu bildiğinize göre onu programlama dillerinden birinde kolayca uygulayabilirsiniz. Basit zincirler Markov daha fazla çalışmanın temelidir karmaşık yöntemler modelleme.

Python programcılarına röportajlar sırasında sorulan 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)
Gibi kaynak metinler 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ş tweetleri 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)
Bu fonksiyona çağrıyı projenin kökündeki cron.py dosyasına yerleştirdim 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 de artacaktır). Nasıl çalıştığını görebilirsiniz

Web yapımında ve SEO'da Markov zincirleri, kaynak metinlere dayalı sözde anlamlı metinler oluşturmak için kullanılır. Bu, verilen anahtar kelimelerle kapı aralıklarını damgalamak, içerik metni yazmak ve benzeri "kara" hileler için kullanılır. 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.

Bir Markov zinciri, her birinde tüm gruptan k uyumsuz olay Ai'den yalnızca birinin göründüğü bir denemeler dizisidir. Bu durumda, Ai olayının (s - 1)'inci denemede meydana gelmesi koşuluyla, Aj olayının s'inci denemede meydana gelmesine ilişkin koşullu olasılık pij(s), önceki denemelerin sonuçlarına bağlı değildir.

Beynini havaya uçurmak isteyenler matematiksel modeli okuyabilirler. İnsan dilinde tüm bu formüller aşağıdakilere indirgenir. Kaynak metin, kelimeleri tanımlar ve hangi kelimelerin ardından geldiği sırasını korur. Daha sonra bu verilere dayanarak kelimelerin rastgele seçildiği ancak aralarındaki bağlantıların korunduğu yeni bir metin oluşturulur. Ö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 metindeki benzersiz kelimeleri temsil eder ve köşeli parantez içindeki bağlantılar, o kelimeden sonra görünebilecek kelimelerin listesi olan bağlantılardır.

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 istenilen metin boyutuna ulaşılıncaya kadar işlem tekrarlanır. 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, orijinal metin çok kısa olduğundan, ortaya çıkan metin orijinal metinden çok az farklılık gösterir. 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);
// Cümlelerdeki ilk kelimelerin dizisi
$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ığı kelimeleri belirlemek. 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.

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 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şuyor ama aynı zamanda benzersiz kelimeler sadece beş tanesi 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. Bu durumda cümledeki her bağlantının görülme sıklığı açıkça görülmektedir:

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 ve hiçbir şekilde önceki durumların tümüne bağlı olmadığı bir süreci modelliyoruz.

Ö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 kendi cümlemiz 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 peşinden 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 diğer kelimelere göre bunların metinde görünme 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 kelime içermeli. Ama elimizdeki kelime tabanına bir bakalım.

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 stok yapın kelime tabanı 500.000 kelimeden.

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 elemanları 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 öğeleri, Diktogramı başlatacak kelimeler, örneğin bir kitaptaki tüm kelimeler olacaktır. Bu durumda, öğeleri sayarız, böylece herhangi birine erişmek için her seferinde tüm veri setini gözden geçirmemize gerek kalmaz.

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, dağıtımları ise 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 ilk kelimeler- bunlar derlemdeki cümlelerin başlangıcı olanlardır, eğer modelde "END" ise: tohum_kelime = "END" iken tohum_kelime == "END": tohum_kelime = model["END"].return_weighted_random_word() return tohum_kelime dönüş rastgele. seçim(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 = random_weighted_word cümle.append (current_word) cümle = cümle.capitalize() return " ".join(sentence) + "."

dönüş cümlesi

Sırada ne var?