Harmonic entropy: Difference between revisions

<h2>IMPORTED REVISION FROM WIKISPACES</h2>

This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br>

: The revision comment was: <tt></tt><br>

The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br>

where the expression

We have succeeded in representing Harmonic Renyi Entropy in simple terms of two convolution products, each of which can be computed in O(N log N) time.

\newcommand{\cent}{\text{¢}}&amp;lt;br/&amp;gt;[[math]]

  --&gt;&lt;script type="math/tex"&gt;\newcommand{\cent}{\text{¢}}&lt;/script&gt;&lt;!-- ws:end:WikiTextMathRule:0 --&gt;&lt;br /&gt;

&lt;br /&gt;

  The general workings of the human auditory system lead to a plethora of well-documented and sonically interesting phenomena that can occur when a musical chord is played:&lt;br /&gt;

&lt;ul&gt;&lt;li&gt;The perception of partial &lt;strong&gt;timbral fusion&lt;/strong&gt; of the chord into one complex sound&lt;/li&gt;&lt;li&gt;The appearance of a &lt;strong&gt;virtual fundamental&lt;/strong&gt; pitch in the bass&lt;/li&gt;&lt;li&gt;Critical band effects, such as timbral &lt;strong&gt;beatlessness&lt;/strong&gt;, compared to mistunings of the chord in the surrounding area&lt;/li&gt;&lt;li&gt;The appearance of a quick fluttering effect sometimes known as &lt;strong&gt;periodicity buzz&lt;/strong&gt;&lt;/li&gt;&lt;/ul&gt;&lt;br /&gt;

Concordance has often been confused with actual musical consonance, an unfortunate fact made more common by the&lt;span style="line-height: 1.5;"&gt; psychoacoustics literature under the unfortunate name &lt;/span&gt;&lt;strong&gt;&lt;span style="line-height: 1.5;"&gt;sensory consonance&lt;/span&gt;&lt;/strong&gt;&lt;span style="line-height: 1.5;"&gt;, most often used to refer to phenomena related to roughness and beatlessness specifically. This is not to be confused with the more familiar construct of tonal stability, typically just called &amp;quot;consonance&amp;quot; in Western common practice music theory and sometimes clarified as &amp;quot;musical consonance&amp;quot; in the music cognition literature. To make matters worse, the literature has also at times referred to concordance -- and not tonal stability -- as &lt;/span&gt;&lt;strong&gt;&lt;span style="line-height: 1.5;"&gt;tonal consonance&lt;/span&gt;&lt;/strong&gt;&lt;span style="line-height: 1.5;"&gt;, often referring to phenomena related to virtual pitch integration, creating a complete terminological mess. As a result, the term &amp;quot;consonance&amp;quot; has been completely avoided in this article.&lt;/span&gt;&lt;br /&gt;

&lt;br /&gt;

  The original Harmonic Entropy model limited itself to working with dyads. More recently, work by Steve Martin and others has extended this basic idea to higher-cardinality chords. This article will concern itself with dyads, as the dyadic case is still the most well-developed, and many of the ideas extend naturally to larger chords without need for much exposition.&lt;br /&gt;

&lt;br /&gt;

Given a spreading function and set of basis rationals, there are two different procedures commonly used to assign probabilities to each rational. The first, the &lt;strong&gt;domain-integral approach&lt;/strong&gt;, works for arbitrary nowhere dense sets of rationals without any further free parameters. The second, the &lt;strong&gt;complexity-normalization approach&lt;/strong&gt;, has nice mathematical properties which sometimes make it easier to compute and which may lead to generalizations to infinite sets of rationals which are sometimes dense in the reals. It is conjectured that there are certain important limiting situations where the two converge; both are described in detail below.&lt;br /&gt;

&lt;br /&gt;

  For sets of basis rationals which are nowhere dense, the log-frequency spectrum can be divided up into &lt;strong&gt;domains&lt;/strong&gt; assigned to the basis rationals. Each rational is assigned a domain with lower bound equal to the mediant of itself and its nearest lower neighbor, and likewise with upper bound equal to the mediant of itself and its nearest upper neighbor. If no such neighbor exists, ±∞ is used instead. Mathematically, this can be represented via the following expression:&lt;br /&gt;

&lt;br /&gt;

This process can be summarized by the following picture, taken from &lt;a class="wiki_link_ext" href="http://sethares.engr.wisc.edu/paperspdf/HarmonicEntropy.pdf" rel="nofollow" target="_blank"&gt;William Sethares' paper on Harmonic Entropy&lt;/a&gt;:&lt;br /&gt;

&lt;br /&gt;

Note the difference in terminology here - in this example, the f&lt;span style="font-size: 90%; vertical-align: sub;"&gt;j+n&lt;/span&gt; are the basis rationals, the r&lt;span style="font-size: 12px; vertical-align: sub;"&gt;j+n&lt;/span&gt; are the domains for each basis rational, and the bounds for each domain are the mediants between each f&lt;span style="font-size: 12px; vertical-align: sub;"&gt;j+n &lt;/span&gt;and its nearest neighbor. The probability assigned to each basis rational is then the area under the spreading function curve for each rational's domain. The entropy of this probability distribution is then the Harmonic Entropy for that dyad.&lt;br /&gt;

&lt;br /&gt;

In the case where the set of basis rationals consists of a finite set bounded by Tenney or Weil height, the resulting set of widths is conjectured to have interesting mathematical properties, leading to mathematically nice conceptual simplifications of the model. These simplifications are explained below.&lt;br /&gt;

&lt;br /&gt;

  It has been noted empirically by Paul Erlich that, given all those rationals with Tenney height under some cutoff N as a basis set, that the domain widths for rationals sufficiently far from the cutoff seem to be proportional to 1/sqrt(nd). While it's still an open conjecture that this pattern holds for arbitrarily large N, the assumption is sometimes made that this is the case, and hence that for these basis rational sets, 1/sqrt(nd) &amp;quot;approximations&amp;quot; to the width are sufficient to estimate domain-integral Harmonic Entropy. This modifies the expression for the p&lt;span style="font-size: 12px; vertical-align: sub;"&gt;d&lt;/span&gt;(b) as follows, noting that for the moment the &amp;quot;probabilities&amp;quot; won't sum to 1:&lt;br /&gt;

&lt;br /&gt;

This approach to assigning probabilities to basis rationals is useful because it hypothetically makes it possible to consider the HE of sets of rationals which are dense in the reals, or even the entire set of positive rationals ℚ&lt;span style="font-size: 80%; vertical-align: super;"&gt;+&lt;/span&gt;, although the best way to do this is a subject of ongoing research.&lt;br /&gt;

&lt;br /&gt;

  &lt;br /&gt;

&lt;span style="background-color: #ffffff;"&gt;In all of these examples, the x-axis represents the width in cents of the dyad, and the y-axis represents &lt;/span&gt;&lt;em&gt;&lt;span style="background-color: #ffffff;"&gt;discordance&lt;/span&gt;&lt;/em&gt; rather than concordance&lt;span style="background-color: #ffffff;"&gt;, measured in nats of Shannon entropy. Note that by convention, the value for s is typically expressed as a percentage of frequency deviation; this can be converted to cents via &lt;/span&gt;&lt;br /&gt;

&lt;br /&gt;

&lt;span style="background-color: #ffffff;"&gt;This uses as a spreading function the Gaussian distribution with s=~17 cents (or a lin-frequency deviation of 1%). The basis set is all rationals of Tenney height less than 10000. This uses the complexity-normalization approach, and the complexity function is sqrt(n·d):&lt;/span&gt;&lt;br /&gt;

&lt;span style="background-color: #ffffff;"&gt;This example uses the same spreading function and standard deviation, but this time the basis set is all rationals of Weil height less than 100. The complexity function here is max(n,d):&lt;/span&gt;&lt;br /&gt;

&lt;br /&gt;

The following image compares the domain-integral and complexity-normalization approaches by overlaying the two curves on top of each other. In both cases, the spreading function is again a Gaussian with s=~17 cents, and the basis set is all those rationals with Tenney height ≤ 10000. It can be seen that the curves are extremely similar, and that the locations of the minima and maxima are largely preserved:&lt;br /&gt;

&lt;span style="font-size: 1.4em; line-height: 1.5;"&gt;&lt;strong&gt;Harmonic Rényi Entropy&lt;/strong&gt;&lt;/span&gt;&lt;br /&gt;

An extension to the base Harmonic Entropy model, proposed by Mike Battaglia, is to generalize the use of &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Entropy_(information_theory)" rel="nofollow" target="_blank"&gt;Shannon entropy&lt;/a&gt; by replacing it instead with &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/R%C3%A9nyi_entropy" rel="nofollow" target="_blank"&gt;Rényi entropy&lt;/a&gt;, a &lt;a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Q-analog" rel="nofollow" target="_blank"&gt;q-analog&lt;/a&gt; of Shannon's original entropy. The &lt;strong&gt;Harmonic Rényi Entropy of order a&lt;/strong&gt; of an incoming dyad can be defined as follows:&lt;br /&gt;

Certain values of &lt;em&gt;a&lt;/em&gt; reduce to simpler expressions and have special names.&lt;br /&gt;

&lt;br /&gt;

  &lt;!-- ws:start:WikiTextMathRule:9:

[[math]]&amp;lt;br/&amp;gt;

  --&gt;&lt;script type="math/tex"&gt;H(d) = \log |R|&lt;/script&gt;&lt;!-- ws:end:WikiTextMathRule:9 --&gt;&lt;br /&gt;

where |R| is the cardinality of the set of basis rationals. This assumes, in essence, an &amp;quot;infinitely dumb&amp;quot; auditory system which can do no better than picking a rational number from a uniform distribution completely at random. All dyads have the same Harmonic Hartley Entropy. The Hartley Entropy is sometimes called the &amp;quot;max-entropy,&amp;quot; and is useful mainly as an upper bound on the other forms of entropy: all Rényi Entropies are always guaranteed to be less than the Hartley Entropy.&lt;br /&gt;

&lt;em&gt;Harmonic Hartley Entropy (a=0) with the basis set all rationals with Tenney height ≤ 10000. Note that the choice of spreading function makes no difference in the end result at all.&lt;/em&gt;&lt;br /&gt;

&lt;br /&gt;

  &lt;!-- ws:start:WikiTextMathRule:10:

[[math]]&amp;lt;br/&amp;gt;

  --&gt;&lt;script type="math/tex"&gt;H(d) = -\sum_{b} p_d(b) \log p_d(b)&lt;/script&gt;&lt;!-- ws:end:WikiTextMathRule:10 --&gt;&lt;br /&gt;

This is Paul's original Harmonic Entropy. Within the cryptographic analogy, this can be thought of as an auditory system which simply selects a rational at random from the incoming distribution, weighted via the distribution itself.&lt;br /&gt;

&lt;em&gt;Harmonic Shannon Entropy (a=1) with the basis set all rationals with Tenney height ≤ 10000, spreading function a Gaussian distribution with s=1% (~17 cents), and sqrt(n·d) complexity.&lt;/em&gt;&lt;br /&gt;

&lt;br /&gt;

  &lt;!-- ws:start:WikiTextMathRule:11:

[[math]]&amp;lt;br/&amp;gt;

  --&gt;&lt;script type="math/tex"&gt;H(d) = -\log \sum_b p_d(b)^2 = -log (P_d = Q_d)&lt;/script&gt;&lt;!-- ws:end:WikiTextMathRule:11 --&gt;&lt;br /&gt;

where P&lt;span style="font-size: 90%; vertical-align: sub;"&gt;d&lt;/span&gt; and Q&lt;span style="font-size: 90%; vertical-align: sub;"&gt;d&lt;/span&gt; are independent and identically distributed random variables corresponding to the same dyad, and the collision entropy is the same as the negative log of the probability that the two variables produce the same outcome.&lt;br /&gt;

&lt;em&gt;Harmonic Collision Entropy (a=2) with the basis set all rationals with Tenney height ≤ 10000, spreading function a Gaussian distribution with s=1% (~17 cents), and sqrt(n·d) complexity.&lt;/em&gt;&lt;br /&gt;

&lt;br /&gt;

  &lt;!-- ws:start:WikiTextMathRule:12:

[[math]]&amp;lt;br/&amp;gt;

  --&gt;&lt;script type="math/tex"&gt;-\log \max_b p_d(b)&lt;/script&gt;&lt;!-- ws:end:WikiTextMathRule:12 --&gt;&lt;br /&gt;

This is the min-entropy, which simply takes the negative log of the largest probability in the distribution. This can be thought of as representing the &amp;quot;strength&amp;quot; of the incoming dyad from being &amp;quot;deciphered&amp;quot; by a &amp;quot;best-case&amp;quot; auditory system. The name &amp;quot;min-entropy&amp;quot; reflects that the a=∞ case is guaranteed to be a lower bound among all Rényi entropies.&lt;br /&gt;

&lt;em&gt;Harmonic Rényi Entropy with a=7, with the high value of a being chosen to approximate min-entropy (a=&lt;/em&gt;∞&lt;em&gt;). The basis set is still all rationals with Tenney height ≤ 10000, the spreading function a Gaussian distribution with s=1% (~17 cents), and the complexity function sqrt(n·d).&lt;/em&gt;&lt;br /&gt;

  Below is given an derivation that expresses Harmonic Renyi Entropy in terms of two simpler functions, each of which is a convolution product and hence can be computed quickly using the Fast Fourier Transform. The below derivation depends on the use of complexity-normalization probabilities, although it may be possible to extend to domain-integral probabilities instead.&lt;br /&gt;

&lt;br /&gt;

  The Harmonic Renyi Entropy is defined as&lt;br /&gt;

&lt;br /&gt;

We thus reduce the term inside the logarithm to the quotient of the functions ρ&lt;span style="vertical-align: sub;"&gt;a&lt;/span&gt;(d) and ψ(d)&lt;span style="vertical-align: super;"&gt;a&lt;/span&gt;. Our aim is now to express each of these two functions in terms of a convolution product.&lt;br /&gt;

&lt;br /&gt;

  ψ(d), the normalization function, is written as follows:&lt;br /&gt;

&lt;br /&gt;

  --&gt;&lt;script type="math/tex"&gt;\psi(d) = \left[S \ast K\right](-d)&lt;/script&gt;&lt;!-- ws:end:WikiTextMathRule:26 --&gt;&lt;br /&gt;

&lt;br /&gt;

  The derivation for ρ&lt;span style="vertical-align: sub;"&gt;a&lt;/span&gt;(d) proceeds similarly. Recall the function is written as follows:&lt;br /&gt;

&lt;!-- ws:start:WikiTextMathRule:27:

Note that the function K&lt;span style="vertical-align: super;"&gt;a&lt;/span&gt;(d) involves a slight abuse of notation, as it is not literally K(d) taken to the a'th power (as the square of the delta distribution is undefined). Rather, we are simply taking the weights of each delta distribution in the summation to the a'th power.&lt;br /&gt;

&lt;br /&gt;

  Taking all of this, we can rewrite the original expression for Harmonic Renyi Entropy as follows:&lt;br /&gt;

&lt;!-- ws:start:WikiTextMathRule:33:

where the expression&lt;br /&gt;

&lt;br /&gt;

&lt;br /&gt;

We have succeeded in representing Harmonic Renyi Entropy in simple terms of two convolution products, each of which can be computed in O(N log N) time.&lt;br /&gt;

&lt;br /&gt;

  &lt;a class="wiki_link_ext" href="http://www.webcitation.org/60qOlJVFS" rel="nofollow"&gt;Paul Erlich article&lt;/a&gt;&lt;br /&gt;

&lt;a class="wiki_link_ext" href="http://sethares.engr.wisc.edu/paperspdf/HarmonicEntropy.pdf" rel="nofollow"&gt;William Sethares article&lt;/a&gt;&lt;br /&gt;