Need help in writing Exercise 11

Course Q&A Natural Language Processing NLP with Probabilistic Models
1

I am not able to understand what to fill in place of none for min_edit_distance function.

2

Hi, @Himanshu_Ahuja

Do you not understand a particular part of the min_edit_distance function or would you want to get hints / explanations from the start?

3

from the start please.

4

Well, first we calculate m - what is the length of the sourse (e.g. 5)
next we calculate n - what is the length of the target string (e.g. 4)

Next we initialize D - the matrix, that we intend to fill. It accounts for the start “#”, so it has one extra row and one extra column (e.g. 6x5). For now it is filled with zeroes.

Now comes the first question:
“# Fill in column 0, from row 1 to row m, both inclusive”
what it asks you to generate numbers 1,2,3…m (e.g. [1,2,3,4,5])
You would use range function for that and what arguments would you pass for it to get the result?

5

image

So I have achieved this by the loop and added insert cost in columns and delete cost in rows.

6

Everything is correct by now.
Next you get into the for loops. Do you have correct ranges?

7

Now I am facing difficulty to process the nested loop.

Loop through row 1 to row m, both inclusive

for row in range(1,m+1):
    
    # Loop through column 1 to column n, both inclusive
    for col in range(1,n+1):
        
        # Intialize r_cost to the 'replace' cost that is passed into this function
        r_cost = None
        
        # Check to see if source character at the previous row
        # matches the target character at the previous column, 
        if None: # Replace None with a proper comparison
            # Update the replacement cost to 0 if source and target are the same
            r_cost = None
            
        # Update the cost at row, col based on previous entries in the cost matrix
        # Refer to the equation calculate for D[i,j] (the minimum of three calculated costs)
        D[row,col] = None
        
# Set the minimum edit distance with the cost found at row m, column n 
med = None

### END CODE HERE ###
return D, med
8

Pay attention that both columns’ and rows’ ranges should be inclusive. Now your ranges are not correct for the nested loops

9

Yes I have corrected that.

10

I have updated this far.

11

Next you have to initialize (provide value) to r_cost variable, which should get the value of the min_edit_distance function rep_cost argument’s value.

This will get us the reference how big is replacement cost.

Next the if statement will check if previous row has the same value as as the previous column and if so we reset r_cost to 0.

12

Yes you have it correct now. But please remove the solution code because it is against the rules

13

Now is the tricky part - you need to get the minimum of three values, like in
image
except that you now have the r_cost and you don’t need an if statement.

14

Okay understood.

How should I calculate this part. And was if condition which I applied correct?
D[row,col] = None

15

Okay let me try this part.

16

D[row,col] = min(D[row-1,col]+del_cost,D[row,col-1]+ ins_cost,D[row-1,col-1]+r_cost)

is this line correct?

And what about calculating med value

17

Yes, this is correct.

The med value is straight forward - just check what value does matrix D has at row m and column n

18

Thank you for your Guidance. I completed the assignment. Now I understand the whole process.

19

Nice job! No problem

Cheers

1 Like
21

This was helpful for me as well! Thank You :grinning: