3
$\begingroup$

I'm trying to understand the motivation of using Pitman-Yor (PY) processes in language modeling, in particular Teh's hierarchical LM based on PY processes. A motivation frequently stated in research literature is "because it produces power laws", pointing out a connection to Zipf's law which says that ordered word frequencies follow a power law.

From my current understanding (please correct me, if I'm wrong), this translates into a claim about the tails of the Dirichlet-Poisson distribution:

Claim 1: Let $\boldsymbol{\tilde{\pi}}\sim\mbox{PD}\left(\alpha,\theta\right)$ with $\alpha\in(0,1)$ and $\theta>-\alpha$ Then

$$\tilde{\pi}_{n}/n^{-\lambda}\to X\mbox{ a.s.}$$

for some bounded random variable $X$ and $\lambda > 0$.

My current understanding:

  • My starting point is the usual stick-breaking construction of the Pitman-Yor process with discount parameter $\alpha\in(0,1)$, concentration parameter $\theta>-\alpha$, and non-atomic base measure $H\in\mathcal{M}_{1}\left(V\right)$:

    $$G:=\sum_{n\in\mathbb{N}}\pi_{n}\delta_{\phi_{n}}\mbox{ with }\boldsymbol{\pi}\sim\mbox{GEM}\left(\alpha,\theta\right)\mbox{ and }\phi_{n}\overset{\operatorname{iid}}{\sim}H,$$ where $\boldsymbol{\pi}$ can be represented as a stick breaking sequence: $\pi_{n}=V_{n}\prod_{k=1}^{n-1}\left(1-V_{k}\right)$ with $V_{k}\sim\mbox{Beta}\left(1-\alpha,\theta+k\alpha\right)$.

  • Drawing from G, $\theta_{1},\ldots,\theta_{n}\overset{\operatorname{iid}}{\sim} G$, gives rise to a sequence of exchangeable partitions $\left(\Pi_{n}\right)_{n\in\mathbb{N}}$ given by the equivalence relation $i\sim j\iff\theta_{i}=\theta_{j}$. The empirical distribution of partition sizes $$\nu_{n}=\sum_{k=1}^{\infty}P_{k}^{\left(n\right)}\delta_{k}$$ with $P_{k}^{\left(n\right)}=n^{-1}\left|\left\{ A\in\Pi_{n}:\left|A\right|=k\right\} \right|$ almost surely converges against $\mbox{GEM}\left(\alpha,\theta\right)$.

  • The distribution of the ordered sequence $\tilde{\pi}_{1}\geq\tilde{\pi}_{2}\geq\ldots$ of stick-breaking weights $\pi_{1},\pi_{2},\ldots$ is called $\mbox{PD}\left(\alpha,\theta\right)$.

Questions:

  1. Is my understanding correct, that is: Is the PY process chosen in language modeling because claim 1 holds? If yes, could you please point me to a proof? (Potential hit: Lemma 3.11. of Pitman, Combinatorial Stochastic Processes - if the PY process gives rise to an $\left(\alpha,\theta\right)$-partition. He doesn't prove the lemma and I'd expect that a property of the PY process, which is taken for granted in so many papers, has an accessible proof.)

  2. To which extent does this reasoning work if I pick a base measure $H$ that has point masses? Will the empirical distribution of partition sizes $\nu_{n}=\sum_{k=1}^{\infty}P_{k}^{\left(n\right)}\delta_{k}$ still converge against $\mbox{GEM}\left(\alpha,\theta\right)$?

$\endgroup$
3
$\begingroup$

As an intermediate solution, I put up with the following proposition. It only gives the asymptotic behavior of the expectation of the stick-breaking weights while almost surely results exist, for sure.

Proposition: Let $\left(\pi_{k}\right)_{k\in\mathbf{N}}$ be the stick-breaking weights of a Pitman-Yor process with concentration parameter $\alpha$ and discount parameter $d$, that is $\boldsymbol\pi\sim\mbox{GEM}(\alpha,d)$. Then

$$\mathbf{E}\left[\pi_{k}\right]\in\begin{cases} O\left(k^{-1/d}\right) & \mbox{for }d>0\\ O\left(\left(\frac{\alpha}{\alpha+1}\right)^{k}\right) & \mbox{for }d=0. \end{cases} $$

Statement in plain English: In the case of the Dirichlet process, $\boldsymbol{\pi}\sim\mbox{GEM}\left(\alpha,0\right)$, the stick-breaking weights $\pi_{k}$ decrease on average exponentially with $k$. In the case of the Pitman-Yor process, $d>0$, the tails of the sequence $\boldsymbol{\pi}\sim\mbox{GEM}\left(\alpha,d\right)$ are on average those of a power law with exponent $-1/d$. The higher the discount parameter, the heavier the tails.

Proof: Recall that $\pi_{k}=V_{k}\prod_{n=1}^{k-1}\left(1-V_{n}\right)$ for independent $V_{n}\sim\mbox{Beta}\left(1-d,\alpha+nd\right)$. By independence and linearity of the expectation we have

$$\mathbf{E}\left[\pi_{k}\right]=\frac{1-d}{1+\alpha+\left(k-1\right)d}\prod\frac{\alpha+nd}{1+\alpha+\left(n-1\right)d}. $$

For $d=0$ , this boils down to

$$\mathbf{E}\left[\pi_{k}\right]=\frac{1}{1+\alpha}\left(\frac{\alpha}{1+\alpha}\right)^{k-1}. $$

For $d>0$, we represent the raising factorials $\left(\alpha\right)_{n,d}$ and $\left(1+\alpha\right)_{n,d}$ by Gamma functions,

$$\mathbf{E}\left[\pi_{k}\right] = C\frac{\Gamma\left(\alpha/d+\left(k-1\right)\right)}{\Gamma\left(\left(1+\alpha\right)/d+\left(k-1\right)\right)}.$$

Using the asymptotic ratio property of the Gamma function, $\frac{\Gamma(x+\epsilon)}{\Gamma(x)}\to x^{-\epsilon}$ with $\epsilon=1/d$, yields the claim.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.