Text generation with nth order Markov chain models trained on reddit data
The probability \(P(\ word_{m}\ \mid\ word_{m-1}\ \land\ word_{m-2}\ \land\ \cdots\ \land\ word_{m-n}\ )\), where \(n\) is the order of the model, is proportional to the relative occurrences of such sequence of words in the training dataset.
SUBREDDITS = ("askreddit", "explainlikeimfive", "dankmemes")class RedditMarkovChain:def__init__(self, subreddit, order=1, sentence_limit=1000, begin_str="*BEGIN*", end_str="*END*", cycle_str="*CYCLE*", train_split=(0.9), test_split=None):self.__subreddit = subredditself.__order = order# first order: word1 -> word2# second order: (word1, word2) -> word3# ...self.__sentence_limit = sentence_limitself.__begin_str = begin_strself.__end_str = end_strself.__cycle_str = cycle_strself.__train_split = train_splitself.__test_split = (test_split if test_split isnotNoneelse (1.0- train_split))self.__sentences =self.mine_subreddit( subreddit=reddit.subreddit(self.subreddit), sentence_limit=self.sentence_limit)self.model =self.__build_model()def __build_model(self):"""Build a markov chain model from extracted sentences""" model = defaultdict(lambda: defaultdict(lambda: 0))for sentence inself.train_sentences: words = ([self.begin_str] +self.__split_sentence(sentence) + [self.end_str])for i inrange(1, len(words)):for j inrange(i-1, i-self.order-1, -1):if j <0:break key =self.__convert_to_key(words[j:i]) model[key][words[i]] +=1return modeldef __convert_to_key(self, values):"""Pads with None values to until the length is equal to the order"""assertlen(values) <=self.orderreturntuple([None]*(self.order -len(values)) + values)def __get_longest_key(self, l, keys):"""Returns the longest subkey that exist in the model, or the full key if no subkey was found"""for i inrange(len(l)-1): key =tuple(l[i:])if key in keys:return key# if no existing key was found, return the full key, so the defaultdict# creates an entry for it with a count value of zeroreturntuple(l)def __split_sentence(self, sentence):"""Split sentences into words"""return re.findall(r"((?:[\w']+)|(?:[,!.?]))", sentence)def __get_prob(self, key, word):"""Get single probability from word counts"""return (0if word notinself.model[key]elseself.model[key][word]/sum(self.model[key].values()))def __get_all_probs(self, key):"""Get all probabilities from word counts""" n =sum(self.model[key].values())return [v/n for v inself.model[key].values()]def generate(self, method="sample"):"""Generate text using the created markov chain model method: expected: choose most likely words, infinite cycles are possible random: choose words uniformly sample: choose words based on the modeled probabilities """ sentence = [] word =self.begin_str key =self.__convert_to_key([word])if method =="expected": used =set()whileTrue:if method =="expected": word =max(self.model[key].items(), key=lambda x: x[1])[0]elif method =="random": word = random.choice(tuple(self.model[key].items()))[0]elif method =="sample": words =tuple(self.model[key].keys()) probs =self.__get_all_probs(key) word = np.random.choice(words, p=probs)if word ==self.end_str:break sentence.append(word) key =self.__convert_to_key(sentence[-self.order:])if method =="expected":if key in used: sentence.append(f"{self.cycle_str}")break used.add(key)return (" ".join(sentence).replace(" .", ".") .replace(" ?", "?") .replace(" !", "!") .replace(" ,", ","))def classify(self, sentence):"""Deduce the most likely source of a sentence""" p =1 words = ([self.begin_str] +self.__split_sentence(sentence) + [self.end_str])for i inrange(1, len(words)): key =self.__get_longest_key(self.__convert_to_key(words[max(0, i-self.order):i]),self.model.keys()) p *=self.__get_prob(key, words[i])return p@staticmethoddef mine_subreddit(subreddit, sentence_limit):"""Extract clean sentences from submissions and comments"""# re that matches clean sentences matcher = re.compile(r"(?:[.!?]|^)[A-Z][\w', ]+[.!?](?=[A-Z]|$)") sentences = []with tqdm.tqdm(total=sentence_limit) as pbar:for submission in subreddit.hot(limit=None): sentences += matcher.findall(submission.title) sentences += matcher.findall(submission.selftext) submission.comment_sort ="best" comments = [ comment.body for comment in submission.comments.list()ifnotisinstance(comment, praw.models.MoreComments)]for comment in comments: sentences += matcher.findall(comment)iflen(sentences) >= sentence_limit: random.shuffle(sentences) pbar.update(sentence_limit - pbar.n)breakelse: pbar.update(len(sentences) - pbar.n)return [sentence.lstrip(".!? ") .replace("won't", "will not") .replace("n't", " not") .replace("'m", " am") .replace("'re", " are")for sentence in sentences[:sentence_limit]]@propertydef subreddit(self):returnself.__subreddit@propertydef sentences(self):returnself.__sentences@propertydef order(self):returnself.__order@propertydef sentence_limit(self):returnself.__sentence_limit@propertydef begin_str(self):returnself.__begin_str@propertydef end_str(self):returnself.__end_str@propertydef cycle_str(self):returnself.__cycle_str@propertydef train_split(self):returnself.__train_split@propertydef test_split(self):returnself.__test_split@propertydef train_sentences(self):returnself.sentences[:int(len(self.sentences)*self.train_split)]@propertydef test_sentences(self):returnself.sentences[int(len(self.sentences)*self.train_split):]
Demo
Construct markov chains for each specified subreddit
chains = {subreddit: RedditMarkovChain(subreddit, order=2, sentence_limit=1000)for subreddit in SUBREDDITS}
for subreddit, chain in chains.items():print(f"{subreddit}: {chain.generate('expected')}")
askreddit: I was at a young age.
explainlikeimfive: The problem with strictly widening a base, while maintaining perpendicular wheels, is there really any point?
dankmemes: I am not a arest' of the movie.
Generating new text
dict_data = defaultdict(lambda: [])for subreddit, chain in chains.items():for _ inrange(5): sentence = chain.generate() dict_data["sentence"].append(sentence) dict_data["model"].append(subreddit)for k, v in chains.items(): p = v.classify(sentence) dict_data[f"P({k})"].append(p)display(pd.DataFrame(dict_data))
sentence
model
P(askreddit)
P(explainlikeimfive)
P(dankmemes)
0
And it was great to see us do better in the neck.
askreddit
3.283425e-07
0.000000e+00
0.000000
1
Yep.
askreddit
3.333333e-03
0.000000e+00
0.002222
2
They have the Democrats would control the Senate, and it would cost the city less money to simply buy Norman and his mum a house far far away than to keep his mouth shut about the actual state of being in love.
askreddit
6.977041e-11
0.000000e+00
0.000000
3
Mitch's interests are focused on my own spit I want that put in my own car.
askreddit
1.102293e-06
0.000000e+00
0.000000
4
Congrats, onward with your journey.
askreddit
5.555556e-04
0.000000e+00
0.000000
5
A great example of this lap the runners will be separated by the stagger so there are parts of the lower body are some of these things.
explainlikeimfive
0.000000e+00
7.419278e-10
0.000000
6
Thanks for powerfully refuting your own horrible idea.
explainlikeimfive
0.000000e+00
1.111111e-03
0.000000
7
The answer is not really explain it well, but also a matter of how anything floats is that you can try this easily.
explainlikeimfive
0.000000e+00
1.627817e-11
0.000000
8
PC games are made to run properly on your system, kidneys and digestion.
explainlikeimfive
0.000000e+00
2.314815e-05
0.000000
9
Enough slack that it will interfere with the clock and yourself.
explainlikeimfive
0.000000e+00
1.736111e-06
0.000000
10
Im a minor and seeing those girls in those provocative positions and clothing isnt ok.
dankmemes
0.000000e+00
0.000000e+00
0.001111
11
What I said, with utter confidence, that it'd become a square.
dankmemes
0.000000e+00
0.000000e+00
0.000139
12
How.
dankmemes
0.000000e+00
0.000000e+00
0.001111
13
The cum accelerates.
dankmemes
0.000000e+00
0.000000e+00
0.005556
14
Well played.
dankmemes
0.000000e+00
0.000000e+00
0.001111
Classifying real text
Classifying isnβt exactly ideal this way, as probabilities turn zero when an unprecedented word connection is met. Check out multinomial naive Bayes for a simple text classifier.
dict_data = defaultdict(lambda: [])for subreddit, chain in chains.items():for sentence in chain.test_sentences[:5]: dict_data["sentence"].append(sentence) dict_data["source"].append(subreddit)for k, v in chains.items(): p = v.classify(sentence) dict_data[f"P({k})"].append(p)display(pd.DataFrame(dict_data))
sentence
source
P(askreddit)
P(explainlikeimfive)
P(dankmemes)
0
Sixth grade end of year trip, we were at a ropes course park where you'd rock climb and walked across tall catwalks and the like.
askreddit
0.000000
0.0
0.000000
1
Our reality is a fiction created by a higher civilization of higher beings who wrote a story and transformed it into a reality and every move, breath, even blink, is already programmed.
askreddit
0.000000
0.0
0.000000
2
Mitch is really old.
askreddit
0.000000
0.0
0.000000
3
Choking to death alone is honestly my biggest fear.
askreddit
0.000000
0.0
0.000000
4
The logic was similar for us, yes.
askreddit
0.000000
0.0
0.000000
5
On my PC, just the BIOS takes longer than that.
explainlikeimfive
0.000000
0.0
0.000000
6
No, only 4 left and 5 right.
explainlikeimfive
0.000000
0.0
0.000000
7
HAHA.
explainlikeimfive
0.000000
0.0
0.000000
8
Why is it that being slapped in the face will make you cry, stubing your toe makes you inhale rendering you speechless and being burnt by hot water will make you growl or scream?
explainlikeimfive
0.000000
0.0
0.000000
9
Kernel API is for abstracting away the nasty parts of communicating with the operating system.