1. Homepage
  2. Programming
  3. CSCI-561 Foundations of Artificial Intelligence - Homework 3: Temporal Reasoning in Artificial Intelligence

CSCI-561 Foundations of Artificial Intelligence - Homework 3: Temporal Reasoning in Artificial Intelligence

Engage in a Conversation
USCCSCI-561CSCI561Foundations of Artificial IntelligenceTemporal ReasoningPythonPartially Observable Markov Decision Process

Overview CourseNana.COM

CSCI-561 - Fall 2023 - Foundations of Artificial Intelligence CourseNana.COM

Homework 3 CourseNana.COM

Due Time: Monday, November 20th, 2023, 23:59:59 PST CourseNana.COM

This homework explores the applications of Temporal Reasoning in Artificial Intelligence. In general, the solution for a temporal reasoning task involves taking a sequence of actions/observations on an Partially Observable Markov Decision Process (POMDP Environment) , applying a temporal-reasoning algorithm that you learned from this class, and returning the most probable sequence of the hidden states that the POMDP most-likely went through when experiencing the given sequence of actions/observations. CourseNana.COM

More specifically, this assignment provides you with two versions of temporal data: a base version involving the “Little Prince” Environment and an advanced version that revolves around speech recognition and text prediction. CourseNana.COM

Scenario 1 : Little Prince Model CourseNana.COM

The setup in this version is very similar to the “Little Prince” environment shown in Figure 1, presented in the lecture notes and in the optional reading textbook (ALFE). CourseNana.COM

Figure 1: The Little Prince POMDP (lecture 08-09 and 22). CourseNana.COM

You will be given a list of available percepts, actions and states and the corresponding initial state weightages, transition and observation weight values in that environment (More on the input structure will be covered in the sections below) .<rose, forward, none, ..., turn, rose, backward, volcano, ...> CourseNana.COM

Then, your program should return a sequence of hidden-states that this POMDP is most-likely going through (The following sequence is an example of the final state sequence that one might encounter): CourseNana.COM

<s3, s4, s2, s3, ...> CourseNana.COM

Figure 2: The inputs and outputs of a temporal-reasoning task (lecture 22). CourseNana.COM

More Details on solving this state sequence prediction problem can be found in the lecture slides. The input file format for this environment will be the same as the Speech Recognition environment. You will be given weight values instead of probabilities and the process of converting weights to probabilities is explained in detail in the following sections. CourseNana.COM

Scenario 2 : Simplified Speech Recognition CourseNana.COM

This scenario deals with a more sophisticated environment of speech recognition - without the hassle of going through audio signal processing. This model will primarily focus on resolving the ambiguity introduced by multiple plausible texts that could correspond to a single spoken utterance. For every word pronunciation, instead of dealing with audio signals, you will be given a set of phonemes which phonetically represent the word, and will produce a series of text fragments the same length as the sequence of phonemes. The following table provides some sample words and their phoneme / fragment mapping for better understanding. CourseNana.COM

Example Words CourseNana.COM

Phoneme Mapping CourseNana.COM

Fragment Mapping CourseNana.COM

W | AO1 | T | ER0 CourseNana.COM

w | a | t | er CourseNana.COM

Y | UW1 | M | AH0 | N CourseNana.COM

h|u|m|a|n CourseNana.COM

OW1 | SH | AH0 | N CourseNana.COM

o | c | ea | n CourseNana.COM

As evident in the table, there is a 1:1 correspondence with phoneme and fragment for a given word. For the word water, fragment “A” corresponds to the phoneme “AO1” and fragment “er” corresponds to “ER0”.
Because this project builds off prior work from the CMU Pronouncing Dictionary, we use a dialect of English known as
North American English, where e.g. human is pronounced with a “Y” sound at the start. CourseNana.COM

The ultimate goal of this environment is to find the best sequence of text fragments for a given sequence of phonemes. Formally, we will represent the process as a POMDP, with the text fragments corresponding to states and the phonemes corresponding to observations. For convenience, we will use a single null action “N”. This will ensure that we are using a Partially Observable Markov Decision Process instead of just a Partially Observable Markov Process. This will also allow you to re-use parsing code between the Little Prince environment and the Speech Recognition environment. CourseNana.COM

As part of the input, you will be provided with a dataset containing a list of fragment to phoneme pairs, along with a weight value for each pair. You will also be given fragment-to-fragment transition pairs with their weight values. The following example explains the procedure to compute the probability tables in more detail. These weights correspond to un-normalized total probabilities P(o, s) and P(s, s’) (using the null action “N”), which were computed by counting (observation, state) and (state, state) pairs from a set of approximately 300k Wikipedia articles. Note that you will need to normalize these weights into the appropriate probability distributions P(o | s) and P(s’ | s, N). CourseNana.COM

Consider the following dataset:
Fragment to Phoneme Mapping Fragment to Fragment Transition Mapping
CourseNana.COM

Fragment CourseNana.COM

Phoneme CourseNana.COM

Fragment CourseNana.COM

Fragment CourseNana.COM

Construction of Probability Tables : CourseNana.COM

Initial State Probability: Computing the initial state / prior state distribution only involves dividing each weight in the state probability table by the total weight in the table.
Given a state table as follows:
CourseNana.COM

The initial probability P(s) is: CourseNana.COM

State Transition Probability: This can be determined by looking at the weights of the transitions from one fragment to another and calculating the probability through normalization for each (state, action) pair. This produces P(s|s,a). In this example, there is only a single valid action, so we don’t show it in the table. CourseNana.COM

The state transition probability for the sample dataset would be: CourseNana.COM

Appearance Probabilities: This can be inferred from the fragment-phoneme pairs through normalization over all weights for a given state, producing the conditional distribution P(o|s). The appearance probability for the above example would be as follows: CourseNana.COM

Note how the row for state “s” sums to 1 over the different possible observations / phonemes “S” and “Z”. CourseNana.COM

Your algorithm will be tested on a list of phonemes for which it should provide the most probable sequence of fragments. CourseNana.COM

Input / Output Format CourseNana.COM

As mentioned in the problem statement above, there will be two types of input to indicate two modes / stages : Little Prince environment and Simplified Speech Recognition. CourseNana.COM

In both cases, you will be given a set of input files, containing the table of weights described above. You will need to parse and normalize these tables into the appropriate conditional probabilities. weight. Then, each file contains a sequence of entries, where states, observations, and actions are wrapped in double quotes, and the weights are specified as integers. At the end of the file, there will be one final newline. CourseNana.COM

There are three weight table files: CourseNana.COM

The first of these files contains weights for every state, and describes the prior probability of each state P(s). (The default weight value is present in this file just to ensure format consistency across all weight files - this will not be required to be used, as all states will be present in the state weights file) CourseNana.COM

state_weights.txt: CourseNana.COM

The second of these files contains weights for (state, action, state) triples, and describes the probability of state transitions P(s, a, s). Triples not specified in the table should be given the weight default weight specified on the second line. Note that you will need to normalize these weights into the appropriate probability distribution P(s’ | a, s). CourseNana.COM

state_action_state_weights.txt: CourseNana.COM

The third of these files contains weights for every (state, observation) pair, and describes the probability of each state observation pair P(s, o). Pairs not specified in the table should be given the default weight specified on the second line. Note that you will need to normalize these weights into the appropriate probability distribution P(o | s). CourseNana.COM

state_observation_weights.txt: CourseNana.COM

state_weights
<number of states> <default weight> “state1” <weight of state1> “state2” <weight of state2>
etc...
CourseNana.COM

state_action_state_weights
<number of triples in file> <number of unique states> <number of unique actions> <default weight>
“state1” “action1” “next state1” <weight of (state1, action1, next state1)> “state2” “action2” “next state2” <weight of (state2, action2, next state2)> etc...
CourseNana.COM

state_observation_weights
<number of pairs in file> <number of unique states> <number of unique observations> <default weight>
“state1” “observation1” <weight of (state1, observation1)>
“state2” “observation2” <weight of (state1, observation1)>
etc...
CourseNana.COM

Lastly, you will receive a file containing the sequence of (observation, action) pairs, on which you should run the Viterbi algorithm. CourseNana.COM

observation_actions.txt: CourseNana.COM

Your code will be expected to produce a file containing the predicted state sequence. CourseNana.COM

states.txt: CourseNana.COM

Sample Test Case CourseNana.COM

The following sample test case corresponds to the Little Prince Environment (The format matches that used for Simplified Speech Recognition Environment) CourseNana.COM

Little Prince Environment Test case: CourseNana.COM

state_weights.txt state_observation_weights.txt CourseNana.COM

observation_actions <number of pairs in file> “observation1” “action1” “observation2” “action2” etc... CourseNana.COM

states
<length of state sequence> “state1”
“state2”
CourseNana.COM

"S0" "Apple" 2 "S1" "Volcano" 5 "S1" "Grass" 5 "S1" "Apple" 2 "S2" "Volcano" 3 "S2" "Grass" 5 "S2" "Apple" 2 CourseNana.COM

state_weights 30
"S0" 2
"S1" 5
CourseNana.COM

"S2" 5 CourseNana.COM

state_action_state_weights.txt CourseNana.COM

state_action_state_weights 27 3 3 0
"S0" "Forward" "S0" 3 "S0" "Forward" "S1" 3 "S0" "Forward" "S2" 2 "S1" "Forward" "S0" 4 "S1" "Forward" "S1" 5 "S1" "Forward" "S2" 1 "S2" "Forward" "S0" 1 "S2" "Forward" "S1" 5 "S2" "Forward" "S2" 4 "S0" "Backward" "S0" 5 "S0" "Backward" "S1" 5 "S0" "Backward" "S2" 5 "S1" "Backward" "S0" 3 "S1" "Backward" "S1" 4 "S1" "Backward" "S2" 1 "S2" "Backward" "S0" 2 "S2" "Backward" "S1" 3 "S2" "Backward" "S2" 3 "S0" "Turnaround" "S0" 5 "S0" "Turnaround" "S1" 3 "S0" "Turnaround" "S2" 5 "S1" "Turnaround" "S0" 3 "S1" "Turnaround" "S1" 4 "S1" "Turnaround" "S2" 2 "S2" "Turnaround" "S0" 1 "S2" "Turnaround" "S1" 2 "S2" "Turnaround" "S2" 2
CourseNana.COM

observation_actions.txt CourseNana.COM

Output: CourseNana.COM

states.txt CourseNana.COM

observation_actions 4
"Apple" "Turnaround" "Apple" "Backward" "Apple" "Forward" "Volcano"
CourseNana.COM

states 4 "S2" "S2" "S2" "S1" CourseNana.COM

Input Constraints & Time Limits Little Prince Environment: CourseNana.COM

Maximum Number of States in the Environment CourseNana.COM

10 states CourseNana.COM

Maximum Number of Percepts in the Environment CourseNana.COM

10 percepts CourseNana.COM

Number of Actions Possible in the Environment (Fixed) CourseNana.COM

3 (“Forward”, “Backward”, “Turnaround”) CourseNana.COM

Maximum Length of Observation Action Sequence CourseNana.COM

Time Limit allowed per test case CourseNana.COM

1 second CourseNana.COM

Number of test cases CourseNana.COM

20 ( 5 Preliminary and 15 hidden) CourseNana.COM

Simplified Speech Recognition Environment: CourseNana.COM

Maximum Number of States in the Environment CourseNana.COM

Maximum Number of Observations in the Environment CourseNana.COM

Number of Actions Possible in the Environment (Fixed) CourseNana.COM

“N” ( Indicates Null Action, Refer Scenario Description ) CourseNana.COM

Maximum Length of Observation Action Sequence CourseNana.COM

100 steps CourseNana.COM

Time Limit allowed per test case CourseNana.COM

1 minute CourseNana.COM

Number of test cases CourseNana.COM

30 ( 5 Preliminary and 25 hidden) CourseNana.COM

Grading Criteria CourseNana.COM

There will be 50 test cases in total : 20 cases with the Little Prince environment and 30 cases with Speech Recognition. Each test case is worth 2 points. On clicking the submit button in Vocareum, Your solution will be run on preliminary test cases. Your code will be evaluated on the hidden test cases after the assignment deadline. CourseNana.COM

The performance of your program will be computed automatically by comparing your output sequence with the most-likely known sequence, and the matching percentage will determine the grade of your submissions.More specifically, the probability of the hidden state sequence that your solution has generated (p1), will be compared with the probability of the hidden state sequence proposed by TA agent (p2) and p1/ p2 will be used as the final score for each test case. CourseNana.COM

Score for a single test case = 2 * Probability of student’s state sequence Probability of TA agent’s state sequence CourseNana.COM

Final Score = Sum of scores across all test cases
NOTE : The Max Score for a single test case will be capped at 2 points.
CourseNana.COM

The probability of the state sequence will be calculated based on the joint probability of the state sequence, along with the action sequence and the observation sequence. CourseNana.COM

In the following example [used for calculation purposes only], the score will be calculated as follows: CourseNana.COM

States List = [S0, S1, S2], Actions Set= [N], Observations set= [A, B] Initial State Probability CourseNana.COM

Appearance Probability CourseNana.COM

Transition Probability CourseNana.COM

Observation Action Sequence = [A, <N>, B,<N>, B] CourseNana.COM

If the student’s predicted state sequence is [S0, S1, S1], then
Student’s Probability =
π(𝑆0)*P(A|S0)*P(S1|S0,<N>)*P(B|S1)*P(S1|S1,<N>)*P(B|S1) CourseNana.COM

= 0.5*0.9*0.3*0.8*0.1*0.8 = 0.00864 CourseNana.COM

If the TA’s predicted state sequence is [S0, S1, S0], then
TA’s Probability =
π(𝑆0)*P(A|S0)*P(S1|S0,<N>)*P(B|S1)*P(S0|S1,<N>)*P(B|S0) CourseNana.COM

= 0.5 * 0.9 * 0.3 *0.8 * 0.9 * 0.1 = 0.00972 CourseNana.COM

Your Score for this test case = 2 * 0.00864 / 0.00972 = 1.778 CourseNana.COM

Get in Touch with Our Experts

QQ QQ
Wechat WeChat
Whatsapp Whatsapp
USC代写,CSCI-561代写,CSCI561代写,Foundations of Artificial Intelligence代写,Temporal Reasoning代写,Python代写,Partially Observable Markov Decision Process代写,USC代编,CSCI-561代编,CSCI561代编,Foundations of Artificial Intelligence代编,Temporal Reasoning代编,Python代编,Partially Observable Markov Decision Process代编,USC代考,CSCI-561代考,CSCI561代考,Foundations of Artificial Intelligence代考,Temporal Reasoning代考,Python代考,Partially Observable Markov Decision Process代考,USChelp,CSCI-561help,CSCI561help,Foundations of Artificial Intelligencehelp,Temporal Reasoninghelp,Pythonhelp,Partially Observable Markov Decision Processhelp,USC作业代写,CSCI-561作业代写,CSCI561作业代写,Foundations of Artificial Intelligence作业代写,Temporal Reasoning作业代写,Python作业代写,Partially Observable Markov Decision Process作业代写,USC编程代写,CSCI-561编程代写,CSCI561编程代写,Foundations of Artificial Intelligence编程代写,Temporal Reasoning编程代写,Python编程代写,Partially Observable Markov Decision Process编程代写,USCprogramming help,CSCI-561programming help,CSCI561programming help,Foundations of Artificial Intelligenceprogramming help,Temporal Reasoningprogramming help,Pythonprogramming help,Partially Observable Markov Decision Processprogramming help,USCassignment help,CSCI-561assignment help,CSCI561assignment help,Foundations of Artificial Intelligenceassignment help,Temporal Reasoningassignment help,Pythonassignment help,Partially Observable Markov Decision Processassignment help,USCsolution,CSCI-561solution,CSCI561solution,Foundations of Artificial Intelligencesolution,Temporal Reasoningsolution,Pythonsolution,Partially Observable Markov Decision Processsolution,