The goal of the assignment is to implement beam search algorithm. You need to extract a directed weighted graph from a corpus and perform beam search on this graph to generate the sentence with highest probability.Coding in python
Task 1: Extract graph from a set of sentences.
In this task, you will work on ExtractGraph.py.
The sentence dataset locates in assign1_sentences.txt. Each line of file is one sentence, starting with , and end with . Punctuations include only , and .. It is easy to obtain the words simply by splitting the sentence with white space. Please keep the original lowercase and uppercase.
Your codes will extract a directed weighted graph from this dataset in the ExtractGraph initialization step. Each node represents a word; each edge connecting a head word and a tail word means the tail word is the next word of the head word; the edge weight is the probability of next word appearing after head word.
Also, you need to implement getProb(), which can read the graph and return the probability of next word appearing after head word.
Task 2: Implement Beam Search on the graph to generate the sentences of max probability.
In this task, you will work on BeamSearch.py.
You need to implement beamSearch()
Pre_words is the existing words in the sentence, and you will need to predict next and following words to finish the sentence.
beamK is width of beam.
maxToken is the maximum words of a valid sentence, including the pre_words.
Searched/generated sentence with its probability should be returned in form of StringDouble.
Search termination:
appears in the generated sentence. is the end of a sentence.- The count of words in the sentence is bigger than maxToken.
Existing online resources of Beam Search: https://geekyisawesome.blogspot.com/2016/10/using-beam-search-to-generate-most.html
The Extractgraph.py and BeamSearch.py code along with main snippet is attached here.
EXTRACT GRAPH.PY
BEAMSEARCH.PY
Supporting files for those two are String double.py and Assignment1Main.py
Assignment1Main.py
assign1_sentence dataset is a text file with so many sentences like this
It would be great if someone can come up with the solution.
Thanks a lot in advance.
1 2 class ExtractGraph: # key is head word; value stores next word and corresponding probability. graph = { } 6sentences_add"data assigni_sentences.txt 8 def init(self): # Extract the directed weighted graph, and save to (headword, (tail-word, probability}} return 10 12 13 14 15 16 17 def getProb (self, head word, tail word): return 0.0 import StringDouble 2 import ExtractGraph 3 4 Eclass BeamSearch: 6 graph 8 def_init__(self, input_graph) self.graph return input.-graph = 10 12 13 14 15 16 def beamsearch (self, pre-words, beamK, maxtoken): sentence probability = 0.0 return StringDouble.stringDouble (sentence, probability) class stringDouble string score = 0.0 def init (self, a, b): self,string a self.scoreb import ExtractGraph import BeamSearch # Extract graph from as signi-sentences, txt. graph-ExtractGraph . ExtractGraph() Test extraction correctness. head word -"
print ("The probability of \"" + tail word t "\" appearing after \"" head word "is "+ str (graph.qetProb (head word, tail word) head word"planned" tail word = "economy" print ("The probability of \"" tail word "\" appearing atter \""head word "\is "+ str (graph.getProb (head word, tail word))) head word".'" tail word - "" print("The probability of \" + tail_word "\" appearing after + head word "\" is " + str (graph.getProb (head word, tail word))) # Find the sentence with highest probability. beam search Beamsearch.Bc amsearch (graph) sentence prob-beam search. beamSearch (" Israel and Jordan signed the peace", 10, 40) print(str (sentence prob.score)"t" sentence prob.string) sentence probbeam search.beamSearch ( It is", 10, 15) print(str (sentence _prob.score)"t" sentence_prob.string) assign1 sentence Notepac File Edit Format View Hel ks> Secretary of State Warren Christopher came to Jordan time and again to meet with King Hussein during his more than a dozen of shuttle visits to the regio The Clinton Administration also voiced its full support, without reservation, to the kingdom to defend its security immediately after Iraqi former Indu Save As.. pasctrl sar, King Hussein, Crown Prince Hassan and Prime Minister Sharif Zeid Ben Shaker as well as other senior Jordanian officials traveled to L
It also signed a number of agreements with Israel, expanding peace to economic cooperation s Saudi Ambassador to Jordan Abdullah sudari arrived in Amman last month and took his post five years after Saudi Arabia recalled its ambassador in Amman s> Kuwait , invaded by Iraq in 1998 has not formally announced its normalization with Jordan , but has been moving closer to it . The latest violence took place today in southern Egypt where three policemen were slightly injured by unidentified gunmen in southern Egypt The car , carrying license plates of the New Valley Security Directorate , was on its way to Cairo when being attacked , according to MENA . The security forces launched an operation trying to arrest the gunmen . (5> It was on the second consecutive day that such a militant attack took place in Minya
On Sunday, unidentified assailants killed two policemen and one civilian as they opened fire at a traffic police patrol car on a road west of Abu Korkas s Four other policemen and as many civilians , including a young girl , were injured during the attack . s> Egypt has been haunted by terrorist attacks , especially in the south , since 1992 . Most of these attacks were believed to have been carried out by Islamic militants who seek to topple toppling the secular government and replacing it wit Bami is also the Chadian Minister of Communication. The report quoted President Negasso as saying during the meeting that the two countries should foster a common stand on regional, continental and intern The driver of the truck was arrested and the cause of the accident is under investigation , the police said . Tanzania began preparations for the transition five years ago . And afterwards in April 1991, the then President Ali Hassan Mwinyi appointed a presidential commission, which invited Tanzanians to air opinions on a f s> Then CCM adopted amendments to the party constitution . The National Assembly or parliament followed suit, making corresponding changes in the constitution . After independence in the 1960s, Nyerere led the country in a struggle to safeguard the national interests and create a society of equality, freedom , Also present at the opening ceremony are Hainan Province governor Ruan Chongwu, director of the National Tourism Administration He Guangwei, and secret Lipman also commented that there is no better place than Hannan to l aunch the year of vacationing and leisure . leisure Hainan will host a series of activities , including the 1996 Hainan International Exhibi According to Israel Radio, King Hussein is scheduled to inaugurate an emergency unit, named after late Israeli Prime Minister Yitzhak Rabin, in the Ih ajor destination for ar of vacationin > He will later be flied by helicopter to Bet Gabriel on the s> Israel and Jordan signed the peace treaty on October 1994 marking the end of 46 years of state of war and the start of the process of normalization bet Following the signing of the peace treaty , the two countries established diplomatic relations and exchanged ambassadors . It was reported that King Hussein had paid several secret visits to Israel and held talks with Israeli leader even before the two countries signed the pe One month later, came the Abuja Peace Accord . of Galilee end a ceremony honoring Israeli and Jordanian peace neg otiators who helpe 1 2 class ExtractGraph: # key is head word; value stores next word and corresponding probability. graph = { } 6sentences_add"data assigni_sentences.txt 8 def init(self): # Extract the directed weighted graph, and save to (headword, (tail-word, probability}} return 10 12 13 14 15 16 17 def getProb (self, head word, tail word): return 0.0 import StringDouble 2 import ExtractGraph 3 4 Eclass BeamSearch: 6 graph 8 def_init__(self, input_graph) self.graph return input.-graph = 10 12 13 14 15 16 def beamsearch (self, pre-words, beamK, maxtoken): sentence probability = 0.0 return StringDouble.stringDouble (sentence, probability) class stringDouble string score = 0.0 def init (self, a, b): self,string a self.scoreb import ExtractGraph import BeamSearch # Extract graph from as signi-sentences, txt. graph-ExtractGraph . ExtractGraph() Test extraction correctness. head word -" print ("The probability of \"" + tail word t "\" appearing after \"" head word "is "+ str (graph.qetProb (head word, tail word) head word"planned" tail word = "economy" print ("The probability of \"" tail word "\" appearing atter \""head word "\is "+ str (graph.getProb (head word, tail word))) head word".'" tail word - "" print("The probability of \" + tail_word "\" appearing after + head word "\" is " + str (graph.getProb (head word, tail word))) # Find the sentence with highest probability. beam search Beamsearch.Bc amsearch (graph) sentence prob-beam search. beamSearch (" Israel and Jordan signed the peace", 10, 40) print(str (sentence prob.score)"t" sentence prob.string) sentence probbeam search.beamSearch ( It is", 10, 15) print(str (sentence _prob.score)"t" sentence_prob.string) assign1 sentence Notepac File Edit Format View Hel ks> Secretary of State Warren Christopher came to Jordan time and again to meet with King Hussein during his more than a dozen of shuttle visits to the regio The Clinton Administration also voiced its full support, without reservation, to the kingdom to defend its security immediately after Iraqi former Indu Save As.. pasctrl sar, King Hussein, Crown Prince Hassan and Prime Minister Sharif Zeid Ben Shaker as well as other senior Jordanian officials traveled to L It also signed a number of agreements with Israel, expanding peace to economic cooperation s Saudi Ambassador to Jordan Abdullah sudari arrived in Amman last month and took his post five years after Saudi Arabia recalled its ambassador in Amman s> Kuwait , invaded by Iraq in 1998 has not formally announced its normalization with Jordan , but has been moving closer to it . The latest violence took place today in southern Egypt where three policemen were slightly injured by unidentified gunmen in southern Egypt The car , carrying license plates of the New Valley Security Directorate , was on its way to Cairo when being attacked , according to MENA . The security forces launched an operation trying to arrest the gunmen . (5> It was on the second consecutive day that such a militant attack took place in Minya On Sunday, unidentified assailants killed two policemen and one civilian as they opened fire at a traffic police patrol car on a road west of Abu Korkas s Four other policemen and as many civilians , including a young girl , were injured during the attack . s> Egypt has been haunted by terrorist attacks , especially in the south , since 1992 . Most of these attacks were believed to have been carried out by Islamic militants who seek to topple toppling the secular government and replacing it wit Bami is also the Chadian Minister of Communication. The report quoted President Negasso as saying during the meeting that the two countries should foster a common stand on regional, continental and intern The driver of the truck was arrested and the cause of the accident is under investigation , the police said . Tanzania began preparations for the transition five years ago . And afterwards in April 1991, the then President Ali Hassan Mwinyi appointed a presidential commission, which invited Tanzanians to air opinions on a f s> Then CCM adopted amendments to the party constitution . The National Assembly or parliament followed suit, making corresponding changes in the constitution . After independence in the 1960s, Nyerere led the country in a struggle to safeguard the national interests and create a society of equality, freedom , Also present at the opening ceremony are Hainan Province governor Ruan Chongwu, director of the National Tourism Administration He Guangwei, and secret Lipman also commented that there is no better place than Hannan to l aunch the year of vacationing and leisure . leisure Hainan will host a series of activities , including the 1996 Hainan International Exhibi According to Israel Radio, King Hussein is scheduled to inaugurate an emergency unit, named after late Israeli Prime Minister Yitzhak Rabin, in the Ih ajor destination for ar of vacationin > He will later be flied by helicopter to Bet Gabriel on the s> Israel and Jordan signed the peace treaty on October 1994 marking the end of 46 years of state of war and the start of the process of normalization bet Following the signing of the peace treaty , the two countries established diplomatic relations and exchanged ambassadors . It was reported that King Hussein had paid several secret visits to Israel and held talks with Israeli leader even before the two countries signed the pe One month later, came the Abuja Peace Accord . of Galilee end a ceremony honoring Israeli and Jordanian peace neg otiators who helpe
