Results 1 to 10 of 10
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By Deveno

Math Help - Requesting help understanding an algorithm involving normalised vector

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    Malaysia
    Posts
    5

    Requesting help understanding an algorithm involving normalised vector

    Hi everyone,

    I am new here. I stumbled upon this forum while trying to figure out an algorithm that involves vector and normalised difference between the vector. The equation is given as

    Sr = 1 - ( || r1 - r2|| / || r1 + r2|| )

    A given example gives r1 and r2 as shown below.

    r1 = {1 2 3 4 5 6 0 3 3 0 0 0 1 1}
    r2 = {4 0 3 0 0 0 1 2 3 5 6 7 8 9}

    Sr = 0.2023

    It would be really great if anyone can explain or show me how to get the answer Sr = 0.2023. Thank you very much!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Requesting help understanding an algorithm involving normalised vector

    You get this result if you add and subtract the vectors component-wise (i.e., (x_1,\dots,x_n)+(y_1,\dots,y_n)=(x_1+y_1,\dots,x_n  +y_n)) and \|(x_1,\dots,x_n)\|=\sqrt{x_1^2+\dots+x_n^2}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2012
    From
    Malaysia
    Posts
    5

    Re: Requesting help understanding an algorithm involving normalised vector

    Thanks for the quick reply. I understand the first part that I should add and subtract the vector as give below.

    r1 - r2 = (x1 - y1, . . . , xn - yn)
    r1 + r2 = (x1 + y1, . . . , xn + yn)

    But, I am not sure understand the second part though. Is the equation below correct?

    ||r1 - r2|| = || sqrt{(x12 - y12)+ . . . + (xn2 - yn2)} ||
    ||r1 + r2|| = || sqrt{(x12 + y12)+ . . . + (xn2 + yn)} ||

    If that is correct, then I still cannot get the answer as 0.2023.
    Last edited by Eiko; December 13th 2012 at 06:27 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Requesting help understanding an algorithm involving normalised vector

    Quote Originally Posted by Eiko View Post
    But, I am not sure understand the second part though. Is the equation below correct?

    ||r1 - r2|| = || sqrt{(x12 - y12)+ . . . + (xn2 - yn2)} ||
    ||r1 + r2|| = || sqrt{(x12 + y12)+ . . . + (xn2 + yn)} ||
    No. To evaluate \|r_1-r_2\|, first find r=r_1-r_2 and then, if r=(x_1,\dots,x_n), find \|r\| according to the formula \|r\|=\sqrt{x_1^2+\dots+x_n^2}.

    Edit: Replaced \|r_1=r_2\| with \|r_1-r_2\|.
    Last edited by emakarov; December 14th 2012 at 12:23 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2012
    From
    Malaysia
    Posts
    5

    Re: Requesting help understanding an algorithm involving normalised vector

    Hi emakarov,

    I've tried that as well and the answers are still different from the given answer of 0.2023. It's difficult to explain the equation without being able to insert the proper symbols or insert images. But, basically I am trying to find

    1 - ( ||r1 - r2|| divide by ||r1 + r2|| ) for r1 and r2.

    It's actually an algorithm proposed to check for semantic similarity for sentences. If it would help explain my case, I posted a link to the paper. It's equation 8 on page 6.

    Link to paper: http://ants.iis.sinica.edu.tw/3BkMJ9...statistics.pdf

    Any help would really be great at this point.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Requesting help understanding an algorithm involving normalised vector

    First, I made a small correction to post #4.

    I'll post the output of the program that computes Sr.

    r₁
    Code:
    [1.; 2.; 3.; 4.; 5.; 6.; 0.; 3.; 3.; 0.; 0.; 0.; 1.; 1.]
    r₂
    Code:
    [4.; 0.; 3.; 0.; 0.; 0.; 1.; 2.; 3.; 5.; 6.; 7.; 8.; 9.]
    r₁ + r₂
    Code:
    [5.; 2.; 6.; 4.; 5.; 6.; 1.; 5.; 6.; 5.; 6.; 7.; 9.; 10.]
    r₁ - r₂
    Code:
    [-3.; 2.; 0.; 4.; 5.; 6.; -1.; 1.; 0.; -5.; -6.; -7.; -7.; -8.]
    Squares of elements of r₁ + r₂
    Code:
    [25.; 4.; 36.; 16.; 25.; 36.; 1.; 25.; 36.; 25.; 36.; 49.; 81.; 100.]
    Squares of elements of r₁ - r₂
    Code:
    [9.; 4.; 0.; 16.; 25.; 36.; 1.; 1.; 0.; 25.; 36.; 49.; 49.; 64.]
    Sum of squares of elements of r₁ + r₂ is 495

    Sum of squares of elements of r₁ - r₂ is 315

    ||r₁ + r₂|| = sqrt(495) = 22.248595461286989

    ||r₁ - r₂|| = sqrt(315) = 17.7482393492988493

    ||r₁ - r₂|| / ||r₁ + r₂|| = 0.79772403521746571

    1 - ||r₁ - r₂|| / ||r₁ + r₂|| = 0.20227596478253429
    Thanks from Eiko
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Requesting help understanding an algorithm involving normalised vector

    first we need to find r1 - r2 and r1 + r2.

    in your example, these are:

    r1 - r2 = (-3,2,0,4,5,6,-1,1,0,-5,-6,-7,-7,-8)

    r1 + r2 = (5,2,6,4,5,6,1,5,6,5,6,7,9,10)

    to find the norm, we dot these vectors with themselves (sum of squares) and then take the square root:

    (r1 - r2).(r1 - r2) = 9+4+0+16+25+36+1+1+0+25+36+49+49 = 315

    (r1 + r2).(r1 + r2) = 25+4+36+16+25+36+1+25+36+25+36+49+81+100 = 495

    √(315/495) ~ 0.79772403521746564185512620976512

    1 - √(315/495) ~ 0.20227596478253435814487379023488 to 4 decimal places this is 0.2023

    where you went wrong on ||r1 - r2|| is its not √(Σi(xi2 - yi2) but rather √(Σi(xi-yi)2)

    that is a sum of the squares of the differences, not a sum of the differences of the squares, and similarly for ||r1 + r2||

    (and darn it, yvgeny, no fair using a program when i have to do this stuff by hand!)
    Thanks from Eiko
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Requesting help understanding an algorithm involving normalised vector

    Quote Originally Posted by Deveno View Post
    (and darn it, yvgeny, no fair using a program when i have to do this stuff by hand!)
    Thanks for providing 15 additional decimal digits
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Dec 2012
    From
    Malaysia
    Posts
    5

    Re: Requesting help understanding an algorithm involving normalised vector

    Wow thanks a lot to the both of you. I was never good with Math but I never thought that there's still someone out there that would help me out here.

    Oh by the way, do you mind telling me what program did you use for this? Can the program be used to calculate other algorithms as well?
    Last edited by Eiko; December 14th 2012 at 01:50 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

    Re: Requesting help understanding an algorithm involving normalised vector

    Quote Originally Posted by Eiko View Post
    Oh by the way, do you mind telling me what program did you use for this? Can the program be used to calculate other algorithms as well?
    I used OCaml programming language. The expression that computes Sr is

    Code:
    1. -. sqrt (fold_right (+.) (map sqr (map2 (-.) r1 r2)) 0.) /. sqrt (fold_right (+.) (map sqr (map2 (+.) r1 r2)) 0.);;
    where r1 and r2 are lists of floats.

    But this can be easily written in any decent programming language. It is also possible to use computational software like MATLAB and Octave, but I personally don't know them.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Normalised Mantissa
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: November 18th 2011, 10:07 AM
  2. Problems understanding The Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 13th 2010, 09:12 PM
  3. Replies: 6
    Last Post: March 31st 2009, 05:44 PM
  4. Replies: 1
    Last Post: January 28th 2009, 04:56 PM
  5. Need urgent help understanding vector
    Posted in the Calculus Forum
    Replies: 5
    Last Post: April 25th 2008, 05:53 AM

Search Tags


/mathhelpforum @mathhelpforum