QuantLib › quantlib-dev

Longstaff-Schwartz method, SVD and OLS

Classic

List

Threaded

11 messages Options

Kakhkhor Abdijalilov

Longstaff-Schwartz method, SVD and OLS

It seems that LongstaffSchwartzPathPricer implementation may not deal
with basis collinearity properly.

SVD can deal with collinearity, but the cutoff threshold for small
singular values in LinearLeastSquaresRegression is n*QL_EPSILON (n is
matrix size).

Btw, the cutoff should be applied to the ratio of singular values, not
to the singular values directly. That is something we need to fix as
well.

The above cutoff threshold is OK for OLS purposes, but not for MC
(at least how it is implemented in QL). For OLS purposes we compute
coefficients by performing SVD of the design matrix and then use those
coefficients with the same design matrix to compute the projection of
the dependent variable. This way all singular values cancel out as
long as the cutoff was applied.

But LongstaffSchwartzPathPricer does compute projection (option
continuation values) from a new sample. It is like using the old
coefficients with a new design matrix. There is chance that singular
values of this new design matrix won't cancels out inverse singular
values of the old design matrix. Both design matrices have the same
statistical properties, so that singular values should be more or less
comparable, except very small ones. With typical sample sizes, SVD
cutoff threshold can be as small as 1.0E-012, which is much smaller
than statistical uncertainty of MC (inverse square root of sample
size). Small singular values will show up whenever there is a
collinearity in the basis system.

Fortunately, the problem is fixed if SVD cutoff (n*QL_EPSILON) is
replaced with something commensurable with MC tolerance. I want to
code and submit new LongstaffSchwartzPathPricer and
LinearLeastSquaresRegression classes, but would like to know others
think.

With best regards,
Kakhkhor Abdijalilov.

------------------------------------------------------------------------------
This SF.net Dev2Dev email is sponsored by:

Show off your parallel programming skills.
Enter the Intel(R) Threading Challenge 2010.
http://p.sf.net/sfu/intel-thread-sfd
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Kakhkhor Abdijalilov

Re: Longstaff-Schwartz method, SVD and OLS

My message didn't show up in Nabble forum. I am resending it just in
case it didn't go through.

On Wed, Sep 8, 2010 at 8:42 AM, Kakhkhor Abdijalilov
<[hidden email]> wrote:

> It seems that LongstaffSchwartzPathPricer implementation may not deal
> with basis collinearity properly.
>
> SVD can deal with collinearity, but the cutoff threshold for small
> singular values in LinearLeastSquaresRegression is n*QL_EPSILON (n is
> matrix size).
>
> Btw, the cutoff should be applied to the ratio of singular values, not
> to the singular values directly. That is something we need to fix as
> well.
>
> The above cutoff threshold is OK for OLS purposes, but not for MC
> (at least how it is implemented in QL). For OLS purposes we compute
> coefficients by performing SVD of the design matrix and then use those
> coefficients with the same design matrix to compute the projection of
> the dependent variable. This way all singular values cancel out as
> long as the cutoff was applied.
>
> But LongstaffSchwartzPathPricer does compute projection (option
> continuation values) from a new sample. It is like using the old
> coefficients with a new design matrix. There is chance that singular
> values of this new design matrix won't cancels out inverse singular
> values of the old design matrix. Both design matrices have the same
> statistical properties, so that singular values should be more or less
> comparable, except very small ones. With typical sample sizes, SVD
> cutoff threshold can be as small as 1.0E-012, which is much smaller
> than statistical uncertainty of MC (inverse square root of sample
> size). Small singular values will show up whenever there is a
> collinearity in the basis system.
>
> Fortunately, the problem is fixed if SVD cutoff (n*QL_EPSILON) is
> replaced with something commensurable with MC tolerance. I want to
> code and submit new LongstaffSchwartzPathPricer and
> LinearLeastSquaresRegression classes, but would like to know others
> think.
>
> With best regards,
> Kakhkhor Abdijalilov.

------------------------------------------------------------------------------
This SF.net Dev2Dev email is sponsored by:

Show off your parallel programming skills.
Enter the Intel(R) Threading Challenge 2010.
http://p.sf.net/sfu/intel-thread-sfd
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Klaus Spanderen-2

Re: Longstaff-Schwartz method, SVD and OLS

In reply to this post by Kakhkhor Abdijalilov

Hi

On Wednesday 08 September 2010 15:42:04 Kakhkhor Abdijalilov wrote:
> SVD can deal with collinearity, but the cutoff threshold for small
> singular values in LinearLeastSquaresRegression is n*QL_EPSILON (n is
> matrix size).
>
> Btw, the cutoff should be applied to the ratio of singular values, not
> to the singular values directly. That is something we need to fix as
> well.

correct. What do you think about the following bug-fix for OLS purposes

change line 116 of linearleastsquaresregression.hpp towards

const Real threshold
= n*QL_EPSILON*(*std::max_element(w.begin(), w.end()));

best regards
Klaus

------------------------------------------------------------------------------
Nokia and AT&T present the 2010 Calling All Innovators-North America contest
Create new apps & games for the Nokia N8 for consumers in U.S. and Canada
$10 million total in prizes - $4M cash, 500 devices, nearly $6M in marketing
Develop with Nokia Qt SDK, Web Runtime, or Java and Publish to Ovi Store
http://p.sf.net/sfu/nokia-dev2dev
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Kakhkhor Abdijalilov

Re: Longstaff-Schwartz method, SVD and OLS

Let's use numerical rank as cutoff. Only first SVD::rank() singular
values are used, the rest are dropped. We could replace the loop at
line 118 with this one:

for (i=0; i<svd.rank(); ++i) {
const Real u = std::inner_product(U.column_begin(i),
U.column_end(i),
y.begin(), 0.0)/w[i];

for (Size j=0; j<m; ++j) {
a_[j] +=u*V[j][i];
err_[j]+=V[j][i]*V[j][i]/(w[i]*w[i]);
}
}

There is a deeper issue with 2 pass approach (reusing coefficients
from pass 1 in pass 2). It is not critical for equity pricing. I am
looking into the problem right now and planning to write a working
sometime soon.

Regards,
Kakhkhor Abdijalilov.

------------------------------------------------------------------------------
Nokia and AT&T present the 2010 Calling All Innovators-North America contest
Create new apps & games for the Nokia N8 for consumers in U.S. and Canada
$10 million total in prizes - $4M cash, 500 devices, nearly $6M in marketing
Develop with Nokia Qt SDK, Web Runtime, or Java and Publish to Ovi Store
http://p.sf.net/sfu/nokia-dev2dev
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Kakhkhor Abdijalilov

Re: Longstaff-Schwartz method, SVD and OLS

Do you mean SVD::s_? Yes, it should be ordered.

Regards,
Kakhkhor Abdijalilov.

------------------------------------------------------------------------------
Nokia and AT&T present the 2010 Calling All Innovators-North America contest
Create new apps & games for the Nokia N8 for consumers in U.S. and Canada
$10 million total in prizes - $4M cash, 500 devices, nearly $6M in marketing
Develop with Nokia Qt SDK, Web Runtime, or Java and Publish to Ovi Store
http://p.sf.net/sfu/nokia-dev2dev
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Klaus Spanderen-2

Re: Longstaff-Schwartz method, SVD and OLS

Hi

I'm asking because for your patch it is crucial, that SVD::s_ is ordered.

regards
Klaus

On Friday 29 October 2010 20:26:10 Kakhkhor Abdijalilov wrote:

> Do you mean SVD::s_? Yes, it should be ordered.
>
> Regards,
> Kakhkhor Abdijalilov.
>
> ---------------------------------------------------------------------------
>--- Nokia and AT&T present the 2010 Calling All Innovators-North America
> contest Create new apps & games for the Nokia N8 for consumers in U.S. and
> Canada $10 million total in prizes - $4M cash, 500 devices, nearly $6M in
> marketing Develop with Nokia Qt SDK, Web Runtime, or Java and Publish to
> Ovi Store http://p.sf.net/sfu/nokia-dev2dev
> _______________________________________________
> QuantLib-dev mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/quantlib-dev

------------------------------------------------------------------------------
Nokia and AT&T present the 2010 Calling All Innovators-North America contest
Create new apps & games for the Nokia N8 for consumers in U.S. and Canada
$10 million total in prizes - $4M cash, 500 devices, nearly $6M in marketing
Develop with Nokia Qt SDK, Web Runtime, or Java and Publish to Ovi Store
http://p.sf.net/sfu/nokia-dev2dev
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Kakhkhor Abdijalilov

Re: Longstaff-Schwartz method, SVD and OLS

I am 99% sure. In simple tests they are ordered. From reading the code
I have an impression, that the singular values are indeed ordered.

Regards,
Kakhkhor Abdijalilov.

------------------------------------------------------------------------------
Nokia and AT&T present the 2010 Calling All Innovators-North America contest
Create new apps & games for the Nokia N8 for consumers in U.S. and Canada
$10 million total in prizes - $4M cash, 500 devices, nearly $6M in marketing
Develop with Nokia Qt SDK, Web Runtime, or Java and Publish to Ovi Store
http://p.sf.net/sfu/nokia-dev2dev
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Klaus Spanderen-2

Re: Longstaff-Schwartz method, SVD and OLS

Hi

you are right, following the TNT/Jama docu the vector SVD::s_ is ordered. I've
checked the patch, thanks!

best regards
Klaus

On Tuesday 02 November 2010 19:56:53 Kakhkhor Abdijalilov wrote:

> I am 99% sure. In simple tests they are ordered. From reading the code
> I have an impression, that the singular values are indeed ordered.
>
> Regards,
> Kakhkhor Abdijalilov.
>
> ---------------------------------------------------------------------------
>--- Nokia and AT&T present the 2010 Calling All Innovators-North America
> contest Create new apps & games for the Nokia N8 for consumers in U.S. and
> Canada $10 million total in prizes - $4M cash, 500 devices, nearly $6M in
> marketing Develop with Nokia Qt SDK, Web Runtime, or Java and Publish to
> Ovi Store http://p.sf.net/sfu/nokia-dev2dev
> _______________________________________________
> QuantLib-dev mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Klaus Spanderen-2

Re: Longstaff-Schwartz method, SVD and OLS

In reply to this post by Kakhkhor Abdijalilov

Hi

you are right, following the TNT/Jama docu the vector SVD::s_ is ordered. I've
checked in the patch, thanks!

best regards
Klaus

On Tuesday 02 November 2010 19:56:53 Kakhkhor Abdijalilov wrote:

Kakhkhor Abdijalilov

Re: Longstaff-Schwartz method, SVD and OLS

Hi. Similar problem in SVD::solveFor. It uses all singular values to
compute matrix pseudo-inverse. Insignificant singular values should be
dropped. Quick fix:

Disposable<Array> SVD::solveFor(const Array& b) const{
Matrix W(n_, n_, 0.0);
Size numericalRank = this->rank();
for (Size i=0; i<numericalRank; i++)
W[i][i] = 1./s_[i];

Matrix inverse = V()* W * transpose(U());
Array result = inverse * b;
return result;
}

Also, in SVD::rank implementation we could replace
Real eps = std::pow(2.0,-52.0);
with
Real eps = QL_EPSILON.

Regards,
Kakhkhor Abdijalilov.

------------------------------------------------------------------------------
Achieve Improved Network Security with IP and DNS Reputation.
Defend against bad network traffic, including botnets, malware,
phishing sites, and compromised hosts - saving your company time,
money, and embarrassment. Learn More!
http://p.sf.net/sfu/hpdev2dev-nov
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Klaus Spanderen-2

Re: Longstaff-Schwartz method, SVD and OLS

Hi

it's in SVN. Thanks.

On Wednesday 03 November 2010 00:44:06 Kakhkhor Abdijalilov wrote:

> Hi. Similar problem in SVD::solveFor. It uses all singular values to
> compute matrix pseudo-inverse. Insignificant singular values should be
> dropped. Quick fix:
>
>
> Disposable<Array> SVD::solveFor(const Array& b) const{
> Matrix W(n_, n_, 0.0);
> Size numericalRank = this->rank();
> for (Size i=0; i<numericalRank; i++)
> W[i][i] = 1./s_[i];
>
> Matrix inverse = V()* W * transpose(U());
> Array result = inverse * b;
> return result;
> }
>
>
>
> Also, in SVD::rank implementation we could replace
> Real eps = std::pow(2.0,-52.0);
> with
> Real eps = QL_EPSILON.
>
>
> Regards,
> Kakhkhor Abdijalilov.
>
> ---------------------------------------------------------------------------
>--- Achieve Improved Network Security with IP and DNS Reputation.
> Defend against bad network traffic, including botnets, malware,
> phishing sites, and compromised hosts - saving your company time,
> money, and embarrassment. Learn More!
> http://p.sf.net/sfu/hpdev2dev-nov
> _______________________________________________
> QuantLib-dev mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/quantlib-dev

------------------------------------------------------------------------------
The Next 800 Companies to Lead America's Growth: New Video Whitepaper
David G. Thomson, author of the best-selling book "Blueprint to a
Billion" shares his insights and actions to help propel your
business during the next growth cycle. Listen Now!
http://p.sf.net/sfu/SAP-dev2dev
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev