Nice idea - but surely powers of x are not the best choice
for basis functions. How about instead trying Tchebychev
(or however you spell that - I haven't got Cyrillic here)
polynomials or (as you say) Fourier components?
For the polynomial, the first term will tell you whether
the tune is essentially flat or whether it goes up on average
from beginning to end or down. The second term will
describe whether it sort of goes up in the middle then
down or down in the middle then up. Higher terms
get harder to describe. My guess is that this sort of
description would tend to work better on a short
stretch of music (say the A music or the B music or
4 bars). I feel that Fourier components are a better
bet for the whole tune.
L.
----- Original Message -----
From: John Walsh <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Friday, June 30, 2000 4:12 AM
Subject: Re: [abcusers] ABC, AHC, Do-Re-Mi
>
> We can't just have a single tune-search algorithm. That's not the
> way this group operates. :-) So, for variety, let me suggest another way
> of measuring the difference between two tunes or tune-snippets. This is
> just a slightly fancified version of the "up-down-up-down" method, which
> takes advantage of the fact that we have computers available and don't
> have to make the calculations by hand. (The "up-down-up-down" method will
> give trouble if there are variations which invert intervals. I'm trying
> to get around that.)
>
> Roughly, this method will say that two tunes are alike if they have
> approximately the same outline, and "same outline" means that the patterns
> of notes seen on the staff look about the same.
>
> We go about this as follows.
>
> 1) Express the tune as a sequence of notes of equal duration.
> Suppose there are n of them.
>
> 2) Choose a weighting for each note---presumably the strong beats
> get the largest weighting, weak beats a smaller weighting, etc.
>
> 3) Measure the (signed) distance of each successive note
> above/below middle C. Form a vector of these, (v(1),v(2),...,v(n)).
> Think of this as a function for the moment: v(t), t=1,2,...,n. In order
> to make the result independent of the key, subtract the (weighted) mean
> value from each v(i), and call the resulting vector V.
>
> (4) Choose an integer k <= n, and find the best
> weighted-least-squares approximation of V by a kth order polynomial in t.
>
> (5) Compare two tunes by measuring the distance between their
> polynomials.
>
> That's it. A few remarks.
>
> (a) Think of the polynomial as a smooth curve which "connects
> the dots" on the staff. In general, it can't do quite enough twisting and
> turning to go thru all of them, so it has to compromise. In short, it
> will give a smoother outline of the tune.
>
> (b) Since everything is expressed as a vector, "distance" means
> "distance between vectors", which usually means the (weighted) Euclidean
> distance, but could mean the sup-norm (i.e. the maximum difference of the
> vectors' coordinates.)
>
> (c) The degree of the polynomial influences the number of up and down
> intervals it can represent. If the degree k = n, you just get the tune
> back again, and this method will give the distance between the vectors
> from step (3). (That's what I thought that Mark Vandenbrouck might have
> been suggesting at first.) However, if k is smaller than n, it will have
> the effect of smoothing out the intervals a little, hopefully minimizing
> the effect of minor variations. (A kth degree polynomial can increase for
> a while, then decrease, then increase, etc. but it can only change from
> increasing to decreasing at most k-1 times, so it can't follow all the
> twists and turns of the tune.) I'd guess that a good choice for k would be
> somewhere between one and a half and three times the number of measures in
> the snippet, but this is just a guess. In any case, the distance this
> method measures will get larger as k gets larger.
>
> (d) It takes one matrix-times-vector multiplication to find the
> least-squares approximation in step (4), but one doesn't actually have to
> compute it to compare two tunes. If we use the (weighted) Euclidean
> distance between two vectors, the distance between the two can be
> calculated with a vector-times-matrix-times-vector multiplication. The
> sup-norm, which would also be a reasonable measure of distance, takes a
> roughly the same amount of work. (The two different distances are
> equivalent in a certain sense, but still, one might turn out to be more
> useful than the other.)
>
> (e) There are other ways of doing the approximation which would have
> much the same effect. One could use the first few terms of a Fourier
> series instead of a polynomial, for example. I think a polynomial should
> do a bit better job of smoothing than a Fourier series, but this kind of
> thing pretty well has to be left to experiment--there's no real theory
> behind it.
>
> (f) Obvious problems: one has to be able to compare tunes in
> different time signatures. This might come down to re-scaling the
> polynomial. It's not clear to me how it will behave with respect to
> pick-up notes, but I suspect that weighting the main beats will help, and
> that just a couple pickups won't cause a real problem anyway. (Because of
> the theorem: translation is continuous in L^2.)
>
> Finally: I suppose anyone suggesting an algorithm should have to
> implement it---fair is fair---but while I could probably write the routine
> from step two on (because it's pretty easy), the task of writing a parser
> to get to step one is a bit much for me. Sorry.
>
> Cheers,
> John Walsh
>
> To subscribe/unsubscribe, point your browser to:
http://www.tullochgorm.com/lists.html
>
To subscribe/unsubscribe, point your browser to: http://www.tullochgorm.com/lists.html
