You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by "Lance Norskog (JIRA)" <ji...@apache.org> on 2011/04/07 05:58:05 UTC
[jira] [Created] (MAHOUT-653) Approximations to standard functions
Approximations to standard functions
------------------------------------
Key: MAHOUT-653
URL: https://issues.apache.org/jira/browse/MAHOUT-653
Project: Mahout
Issue Type: New Feature
Reporter: Lance Norskog
These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
log() and exp() stolen from:
[http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
pow() stolen from:
[http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
Re: [jira] [Updated] (MAHOUT-653) Approximations to standard functions
Posted by Lance Norskog <go...@gmail.com>.
Ted- No, please, tell us what you really think. Don't hold back.
What are legitimate data sets for doing these measurements? If I
wanted to do a survey of what distances are useful for what datasets,
what base material would I use?
[jira] [Updated] (MAHOUT-653) Approximations to standard functions
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Lance Norskog updated MAHOUT-653:
---------------------------------
Attachment: Approximations.java
Scrubbed.
The approximations are accurate either above or below 1.0. Exceptions added to prevent inaccurate use.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: Approximations.java, MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13016766#comment-13016766 ]
Sean Owen commented on MAHOUT-653:
----------------------------------
I think the Approximations are useful to have this in the code, sure.
These DistanceMeasures are used by passing their class name to a job -- that is, they have to have a no-arg constructor. So I think MinkowskiDistanceMeasure needs to retain a default no-arg constructor that selects Math.pow() rather than the approximation. (I might call the param "fastApproximation" but that's a matter of taste.)
My first question is whether this may get used in any situation where the accuracy is a problem. I don't see any at the moment. Distance is used as an indicator of closeness and doesn't necessarily need exact answers.
In theory, a less exact answer means very slightly less accurate clustering results. I worry whether the approximations become very off at very large or small values, which you might encounter in clustering situations. I don't know, open question.
And then the question is comparing that to the speedup -- how much time is spent in this versus I/O, since I'm thinking these come up in the context of Hadoop jobs.
Open questions, anyone know more?
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Ted Dunning (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13037122#comment-13037122 ]
Ted Dunning commented on MAHOUT-653:
------------------------------------
I don't see that these are necessary or even terribly high impact.
Can we close this?
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: Approximations.java, MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Ted Dunning (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13018039#comment-13018039 ]
Ted Dunning commented on MAHOUT-653:
------------------------------------
The comment and the test are inconsistent:
{code}
if (exponent > 2.0)
throw new Exception("Approximations.pow(n) only valid where n < 1");
{code}
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: Approximations.java, MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-653) Approximations to standard functions
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Lance Norskog updated MAHOUT-653:
---------------------------------
Attachment: MAHOUT-653.patch
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13016677#comment-13016677 ]
Lance Norskog commented on MAHOUT-653:
--------------------------------------
Use case: L1/L2 distances are not useful with very high dimensions. Fractional L is more useful, and thus we need a fast but inaccurate pow() implementation.
Citations:
[http://arnetminer.org/viewpub.do?pid=303924]
[http://portal.acm.org/citation.cfm?id=656414]
Postscript version:
[Postscript|http://www.charuaggarwal.net/surprise.ps]
I found a PDF somewhere, but it is owned by the ACM.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-653) Approximations to standard functions
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Lance Norskog updated MAHOUT-653:
---------------------------------
Attachment: MAHOUT-653.patch
This includes an implementation of MinkowskiDistanceMeasure that makes approximations optional.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (MAHOUT-653) Approximations to standard functions
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen resolved MAHOUT-653.
------------------------------
Resolution: Won't Fix
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: Approximations.java, MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Sean Owen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13017116#comment-13017116 ]
Sean Owen commented on MAHOUT-653:
----------------------------------
This is used wherever jobs take in a DistanceMeasure class name and instantiate it by reflection. Look at KmeansClusterMapper for instance. A setter could be fine, but then there's not a way to feed a fast-approximation version into any of the code that would use it. It needs a subclass... which feels ugly indeed.
I would remove the log method if it's not used and is too approximate.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13017107#comment-13017107 ]
Lance Norskog commented on MAHOUT-653:
--------------------------------------
No-arg constructor: where is this used and does it need a setter for exact/approximate?
log approximation: yes, this needs 'here be dragons' comments.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13037213#comment-13037213 ]
Lance Norskog commented on MAHOUT-653:
--------------------------------------
bq. Can we close this?
Ok.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: Approximations.java, MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13018173#comment-13018173 ]
Lance Norskog commented on MAHOUT-653:
--------------------------------------
This is a usability trick: coders will try to stay on "the good side" of 1.0 but may stray over the line a bit. Adding "slop barriers" allows that code to keep working, while still complaining when the coder completely blows it.
The approximations are about 3% wrong at 1.0 and drive towards exact as n moves away from 1.0. They are 4-5% wrong at the "slop barriers".
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: Approximations.java, MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Ted Dunning (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13017750#comment-13017750 ]
Ted Dunning commented on MAHOUT-653:
------------------------------------
I read the Aggrawal, Hinneburg and Keim paper in a bit more detail and performed numerical experiments that avoided the issues I had with their paper.
I have gone from unconfident in their results to disagreeing with their work. I think that they are totally off-base.
Fractional dimension norms may be useful in some situations, but this paper really doesn't say anything useful on the topic. They also are saying
nothing useful about regularization whatsoever.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MAHOUT-653) Approximations to
standard functions
Posted by "Lance Norskog (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13016677#comment-13016677 ]
Lance Norskog edited comment on MAHOUT-653 at 4/7/11 4:17 AM:
--------------------------------------------------------------
Use case: L1/L2 distances are not useful with very high dimensions. Fractional L is more useful, and thus we need a fast but inaccurate pow() implementation. pow() is around 3% off on average, and 20-40x faster than Math.pow().
Citations:
[http://arnetminer.org/viewpub.do?pid=303924]
[http://portal.acm.org/citation.cfm?id=656414]
Postscript version:
[Postscript|http://www.charuaggarwal.net/surprise.ps]
I found a PDF somewhere, but it is owned by the ACM.
was (Author: lancenorskog):
Use case: L1/L2 distances are not useful with very high dimensions. Fractional L is more useful, and thus we need a fast but inaccurate pow() implementation.
Citations:
[http://arnetminer.org/viewpub.do?pid=303924]
[http://portal.acm.org/citation.cfm?id=656414]
Postscript version:
[Postscript|http://www.charuaggarwal.net/surprise.ps]
I found a PDF somewhere, but it is owned by the ACM.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Ted Dunning (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13017093#comment-13017093 ]
Ted Dunning commented on MAHOUT-653:
------------------------------------
Are these really enough faster to matter? Do we have any code that is CPU bound on distance computations
rather than I/O bound? I expect (but do not know) not.
Also, the fractional dimension L measures are pretty controversial. L_1 does a fantastic job of
sparsification without sacrificing convergence properties. I know that both Google and Yahoo use
L_1 regularization for on-line SGD based learners.
The IBM paper provided has some serious issues (at first glance). In particular, they use a theoretical
figure of merit that is based on contrast for a particular distribution of points. Unfortunately, the
choice of distribution that they used almost always involves distributions that are substantially not
invariant under rotation. Since they are proving bounds over all possible distributions, this choice
of an almost always pathological case gives bounds that are dominated by the pathological case. Most of
the time, these distributions will have points that are highly oriented on the axes, which may or may not be
realistic. Data that has this property is trivially advantageous to metrics L_k for fractional values of k.
Given this issue with the basic premises and the well-known issues of convergence, I would recommend that
folks be pretty cautious with these results.
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-653) Approximations to standard
functions
Posted by "Ted Dunning (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-653?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13017104#comment-13017104 ]
Ted Dunning commented on MAHOUT-653:
------------------------------------
Small values of x give egregious errors in the log approximation here. At 0.001, the absolute error is 1.5
> Approximations to standard functions
> ------------------------------------
>
> Key: MAHOUT-653
> URL: https://issues.apache.org/jira/browse/MAHOUT-653
> Project: Mahout
> Issue Type: New Feature
> Reporter: Lance Norskog
> Attachments: MAHOUT-653.patch, MAHOUT-653.patch
>
>
> These give approximate versions of pow(value, exponent), exp(value), and natural log(value).
> log() and exp() stolen from:
> [http://martin.ankerl.com/2007/02/11/optimized-exponential-functions-for-java/]
> pow() stolen from:
> [http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/]
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira