imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| = Metric Embedding= | | <font color="red" size="2">请在题目一和题目二中任选一题作为本章的作业题目。另外的一题可作为选做题。</font> |
| A '''metric space''' is a pair <math>(X,d)</math>, where <math>X</math> is a set and <math>d</math> is a '''metric''' (or '''distance''') on <math>X</math>, i.e., a function
| | ==Question #1== |
| :<math>d:X^2\to\mathbb{R}_{\ge 0}</math>
| | 在第二章中，我们学习了Budyko的能量平衡气候模型（Simple Energy Balance Climate Model），并用此模型来讨论了存在冰雪线的情况下，气候系统的稳定性问题。冰雪线的南北移动会引起行星反照率及热量的动力输送的变化。我们发现这两种过程的相互作用能够引起气候系统的不稳定。如果使用同样的参数，即<math>A=211.1 W/m^{2}\,</math>, <math>B=1.55 W/(m^{2}{^{\circ}\text{C}})</math>, <math>Q_o=340 W/m^2\,</math>， <math>T_{\text{snow}}=-10^{\circ}\text{C}</math>, <math>s(x)=1-0.241(3x^2-1)\,</math>, 并同样假设: |
| such that for any <math>x,y,z\in X</math>, the following axioms hold:
| |
| # (identity of indiscernibles) <math>d(x,y)=0\Leftrightarrow x=y</math>
| |
| # (symmetry) <math>d(x,y)=d(y,x)</math>
| |
| # (triangle inequality) <math>d(x,z)\le d(x,y)+d(y,z)</math>
| |
|
| |
|
| Let <math>(X,d_X)</math> and <math>(Y,d_Y)</math> be two metric spaces. A mapping
| | <math>\mathcal{A}(T)= |
| :<math>\phi:X\to Y</math>
| | \begin{cases} |
| is called an '''embedding''' of metric space <math>X</math> into <math>Y</math>. The embedding is said to be with '''distortion''' <math>\alpha\ge1</math> if for any <math>x,y\in X</math> it holds that
| | \alpha=0.4& T<T_{\text{snow}},\\ |
| :<math>\frac{1}{\alpha}\cdot d(x,y)\le d(\phi(x),\phi(y))\le \alpha\cdot d(x,y)</math>.
| | \beta =0.7& T>T_{\text{snow}},\\ |
| | | \dfrac{\alpha+\beta}{2} & T=T_{\text{snow}}. |
| In Computer Science, a typical scenario for the metric embedding is as follows. We want to solve some difficult computation problem on a metric space <math>(X,d)</math>. Instead of solving this problem directly on the original metric space, we embed the metric into a new metric space <math>(Y,d_Y)</math> (with low distortion) where the computation problem is much easier to solve.
| | \end{cases}</math> |
| | |
| One particular important case for the metric embedding is to embed a high-dimensional metric space to a new metric space whose dimension is much lower. This is called dimension reduction. This can be very helpful because various very common computation tasks can be very hard to solve on high-dimensional space due to the [https://en.wikipedia.org/wiki/Curse_of_dimensionality curse of dimensionality].
| |
| | |
| = The Johnson-Lindenstrauss Theorem = | |
| The '''Johnson-Lindenstrauss Theorem''' or '''Johnson-Lindenstrauss Transformation''' (both shorten as '''JLT''') is a fundamental result for dimension reduction in Euclidian space.
| |
| | |
| Recall that in Euclidian space <math>\mathbf{R}^d</math>, for any two points <math>x,y\in\mathbf{R}^d</math>, the Euclidian distance between them is given by <math>\|x-y\|=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdots +(x_d-y_d)^2}</math>, where <math>\|\cdot\|=\|\cdot\|_2</math> denotes the Euclidian norm (a.k.a. the <math>\ell_2</math>-norm).
| |
| | |
| The JLT says that in Euclidian space, it is always possible to embed a set of <math>n</math> points in ''arbitrary'' dimension to <math>O(\log n)</math> dimension with constant distortion. The theorem itself is stated formally as follows.
| |
| | |
| {{Theorem | |
| |Johnson-Lindenstrauss Theorem, 1984|
| |
| :For any <math>0<\epsilon<1/2</math> and any positive integer <math>n</math>, there is a positive integer <math>k=O(\epsilon^{-2}\log n)</math> such that the following holds:
| |
| :For any set <math>S\subset\mathbf{R}^d</math> with <math>|S|=n</math>, where <math>d</math> is arbitrary, there is an embedding <math>\phi:\mathbf{R}^d\rightarrow\mathbf{R}^k</math> such that
| |
| ::<math>\forall x,y\in S,\quad (1-\epsilon)\|x-y\|^2\le\|\phi(x)-\phi(y)\|^2\le(1+\epsilon)\|x-y\|^2</math>.
| |
| }}
| |
|
| |
|
| The Johnson-Lindenstrauss Theorem is usually stated for the <math>\ell_2^2</math>-norm <math>\|\cdot\|^2</math> instead of the Euclidian norm <math>\|\cdot\|</math> itself. Note that this does not change anything other than the constant faction in <math>k=O(\epsilon^{-2}\log n)</math> because <math>(1\pm\epsilon)^{\frac{1}{2}}=1\pm\Theta(\epsilon)</math>. The reason for stating the theorem in <math>\ell_2^2</math>-norm is because <math>\|\cdot\|^2</math> is a sum (rather than a square root) which is easier to analyze.
| | 如果行星反照率发生了改变，使得<math>\alpha=0.43</math>， 请讨论： |
| | # 为了保持全球平均温度<math>\bar{T}</math>不变，对于当前的<math>Q</math>和冰雪线, <math>\beta</math>应该取多少？ |
| | # 对于新的 <math>\alpha</math>和<math>\beta</math>值，<math>C</math>的取值应该为多少？ |
| | # 请计算出新的<math>Q(x_s)</math>. |
| | # 请与课堂上所讲的<math>\alpha=0.4</math>, <math>\beta=0.7</math>的情况相比较（请将两种情况下<math>Q(x_s)</math>的曲线画在同一张图上），讨论两种情况的异同，尤其是气候稳定性在<math>\alpha</math>和<math>\beta</math>值改变后发生了何种变化，请讨论为什么会发生这些变化？ |
|
| |
|
| In fact, the embedding <math>\phi:\mathbf{R}^d\rightarrow\mathbf{R}^k</math> can be as simple as a linear transformation <math>A\in\mathbf{R}^{k\times d}</math> so that <math>\phi(x)=Ax</math> for any <math>x\in\mathbf{R}^{d}</math>.
| | ==Question #2== |
| Therefore, the above theorem can be stated more precisely as follows.
| | 假设在大气层顶（TOA），在多年全年平均的情况下，入射的太阳辐射随纬度的分布满足 |
|
| |
|
| {{Theorem
| | <math>\begin{align} |
| |Johnson-Lindenstrauss Theorem (linear embedding)|
| | Q&=Q_o \cdot s(x), \\ |
| :For any <math>0<\epsilon<1/2</math> and any positive integer <math>n</math>, there is a positive integer <math>k=O(\epsilon^{-2}\log n)</math> such that the following holds:
| | s(x)&=s_o \cdot P_o(x)+ s_2 \cdot P_2(x), |
| :For any set <math>S\subset\mathbf{R}^d</math> with <math>|S|=n</math>, where <math>d</math> is arbitrary, there is a linear transformation <math>A\in\mathbf{R}^{k\times d}</math> such that
| | \end{align}</math> |
| ::<math>\forall x,y\in S,\quad (1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2</math>.
| |
| }}
| |
|
| |
|
| The theorem is proved by the probabilistic method. Specifically, we construct a random matrix <math>A\in\mathbf{R}^{k\times d}</math> and show that with high probability (<math>1-O(1/n)</math>) it is a good embedding satisfying:
| | 其中，<math>P_o(x)=1</math>, <math>P_2(x)=\frac{1}{2}(3x^2-1)</math>, <math>s_o=1</math>, <math>s_2=-0.473</math>, <math>x=sin \phi</math>, <math>\phi</math> 为纬度。 |
| :<math>\forall x,y\in S,\quad (1-\epsilon)\|x-y\|\le\|Ax-Ay\|\le(1+\epsilon)\|x-y\|</math>.
| |
| Therefore, if such random matrix <math>A</math> is efficient to construct, it immediately gives us an efficient randomized algorithm for dimension reduction in the Euclidian space.
| |
|
| |
|
| There are several such constructions of the random matrix <math>A\in\mathbf{R}^{k\times d}</math>, including:
| | 如果假设大气层顶的向外净长波辐射为<math>I</math>，其随纬度的分布满足 |
| * projection onto uniform random <math>k</math>-dimensional subspace of <math>\mathbf{R}^{d}</math>; (the original construction of Johnson and Lindenstrauss in 1984; a simplified analysis due to [https://cseweb.ucsd.edu/~dasgupta/papers/jl.pdf Dasgupta and Gupta in 1999])
| |
| * random matrix with i.i.d. Gaussian entries; (due to [https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/IndykM-curse.pdf Indyk and Motwani in 1998])
| |
| * random matrix with i.i.d. -1/+1 entries; (due to [https://www.sciencedirect.com/science/article/pii/S0022000003000254?via%3Dihub#BIB8 Achlioptas in 2003])
| |
| | |
| It was proved by [https://arxiv.org/abs/1609.02094 Kasper Green Larsen and Jelani Nelson in 2016] that the JLT is optimal: there is a set of <math>n</math> points from <math>\mathbf{R}^d</math> such that any embedding <math>\phi:\mathbf{R}^d\rightarrow\mathbf{R}^k</math> having the distortion asserted in the JLT must have dimension <math>k</math> of the target space satisfy <math>k=\Omega(\epsilon^{-2}\log n)</math>.
| |
| | |
| ==JLT via Gaussian matrix==
| |
| Here we prove the Johnson-Lindenstrauss theorem with the second construction, by the random matrix <math>A\in\mathbf{R}^{k\times d}</math> with i.i.d. Gaussian entries. The construction of <math>A</math> is very simple:
| |
| :{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
| |
| |
| |
| *Each entry of <math>A\in\mathbf{R}^{k\times d}</math> is drawn independently from the Gaussian distribution <math>\mathcal{N}(0,1/k)</math>.
| |
| |}
| |
| Recall that a [https://en.wikipedia.org/wiki/Normal_distribution Gaussian distribution] <math>\mathcal{N}(\mu,\sigma^2)</math> is specified by its mean <math>\mu</math> and standard deviation <math>\sigma</math> such that for a random variable <math>X</math> distributed as <math>\mathcal{N}(\mu,\sigma^2)</math>, we have
| |
| :<math>\mathbf{E}[X]=\mu</math> and <math>\mathbf{Var}[X]=\sigma^2</math>,
| |
| and the probability density function is given by <math>p(x)=\frac{1}{\sqrt{2\pi\sigma^2}}\mathrm{e}^{-\frac{(x-\mu)^2}{2\sigma^2}}</math>, therefore
| |
| :<math>\Pr[X\le t]=\int_{-\infty}^t\frac{1}{\sqrt{2\pi\sigma^2}}\mathrm{e}^{-\frac{(x-\mu)^2}{2\sigma^2}}\,\mathrm{d}x</math>.
| |
| | |
| Fix any two points <math>x,y</math> out of the <math>n</math> points in <math>S\subset \mathbf{R}^d</math>, if we can show that
| |
| :<math>\Pr\left[(1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2\right]\ge 1-\frac{1}{n^3}</math>,
| |
| then by the union bound, the following event
| |
| :<math>\forall x,y\in S,\quad (1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2</math>
| |
| holds with probability <math>1-O(1/n)</math>. The Johnson-Lindenstrauss theorem follows.
| |
| | |
| Furthermore, dividing both sides of the inequalities <math>(1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2</math> by the factor <math>\|x-y\|^2</math> gives us
| |
| :<math>(1-\epsilon)\le\frac{\|Ax-Ay\|^2}{\|x-y\|^2}=\left\|A\frac{(x-y)}{\|x-y\|^2}\right\|^2\le(1+\epsilon)</math>,
| |
| where <math>\frac{(x-y)}{\|x-y\|^2}</math> is a unit vector.
| |
| | |
| Therefore, the Johnson-Lindenstrauss theorem is proved once the following theorem on the unit vector is proved.
| |
| {{Theorem
| |
| |Theorem (JLT on unit vector)|
| |
| :For any positive <math>\epsilon,\delta<1/2</math> there is a positive integer <math>k=O\left(\epsilon^{-2}\log \frac{1}{\delta}\right)</math> such that for the random matrix <math>A\in\mathbf{R}^{k\times d}</math> with each entry drawn independently from the Gaussian distribution <math>\mathcal{N}(0,1/k)</math>, for any unit vector <math>u\in\mathbf{R}^d</math> with <math>\|u\|=1</math>,
| |
| ::<math>\Pr\left[\left|\|Au\|^2-1\right|>\epsilon\right]<\delta</math>.
| |
| }}
| |
| | |
| For any <math>u\in\mathbf{R}^d</math>, we have <math>\|Au\|^2=\sum_{i=1}^k(Au)_i^2</math>, where the <math>(Au)_i</math>'s are independent of each other, because each
| |
| :<math>(Au)_i=\langle A_{i\cdot},u\rangle=\sum_{j=1}^dA_{ij}u_j</math>
| |
| is determined by a distinct row vector <math>A_{i\cdot}</math> of the matrix <math>A</math> with independent entries.
| |
| | |
| Moreover, since each entry <math>A_{ij}\sim\mathcal{N}(0,1/k)</math> independently and recall that for any two independent Gaussian random variables <math>X_1\sim \mathcal{N}(\mu_1,\sigma_1^2)</math> and <math>X_2\sim \mathcal{N}(\mu_2,\sigma_2^2)</math>, their weighted sum <math>aX_1+bX_2</math> follows the Gaussian distribution <math>\mathcal{N}(a\mu_1+b\mu_2,a^2\sigma_1^2+b^2\sigma_2^2)</math>, therefore <math>(Au)_i=\langle A_{i\cdot},u\rangle=\sum_{j=1}^dA_{ij}u_j</math> follows the Gaussian distribution
| |
| :<math>(Au)_i\sim\mathcal{N}\left(0,\sum_{j=1}^d\frac{u_j^2}{k}\right)</math>,
| |
| which is precisely <math>\mathcal{N}\left(0,\frac{1}{k}\right)</math> if <math>u\in\mathbf{R}^d</math> is a unit vector, i.e. <math>\|u\|^2=\sum_{j=1}^du_j^2=1</math>.
| |
| | |
| In summary, the random variable <math>\|Au\|^2</math> that we are interested in, can be represented as a sum-of-square form
| |
| :<math>\|Au\|^2=\sum_{i=1}^kY_i^2</math>,
| |
| where each <math>Y_i=(Au)_i</math> independently follows the Gaussian distribution <math>\mathcal{N}\left(0,\frac{1}{k}\right)</math>.
| |
| | |
| ==Concentration of <math>\chi^2</math>-distribution ==
| |
| By the above argument, the Johnson-Lindenstrauss theorem is proved by the following concentration inequality for the sum of the squares of <math>k</math> Gaussian distributions.
| |
| {{Theorem
| |
| |Chernoff bound for sum-of-squares of Gaussian distributions|
| |
| :For any positive <math>\epsilon,\delta<1/2</math> there is a positive integer <math>k=O\left(\epsilon^{-2}\log \frac{1}{\delta}\right)</math> such that for i.i.d. Gaussian random variables <math>Y_1,Y_2,\ldots,Y_k\sim\mathcal{N}(0,1/k)</math>,
| |
| ::<math>\Pr\left[\left|\sum_{i=1}^kY_i^2-1\right|>\epsilon\right]<\delta</math>.
| |
| }}
| |
| | |
| First, we see that this is indeed a concentration inequality that bounds the deviation of a random variable from its mean.
| |
| | |
| For each <math>Y_i\sim\mathcal{N}\left(0,\frac{1}{k}\right)</math>, we know that <math>\mathbf{E}[Y_i]=0</math> and <math>\mathbf{Var}[Y_i]=\mathbf{E}[Y_i^2]-\mathbf{E}[Y_i]^2=\frac{1}{k}</math>, thus
| |
| :<math>\mathbf{E}[Y_i^2]=\mathbf{Var}[Y_i]+\mathbf{E}[Y_i]^2=\frac{1}{k}</math>.
| |
| By linearity of expectation, it holds that
| |
| :<math>\mathbf{E}\left[\sum_{i=1}^kY_i^2\right]=\sum_{i=1}^k\mathbf{E}\left[Y_i^2\right]=1</math>.
| |
| | |
| We prove an equivalent concentration bound stated for the [https://en.wikipedia.org/wiki/Chi-squared_distribution '''<math>\chi^2</math>-distribution'''] (sum of the squares of <math>k</math> '''standard''' Gaussian distributions).
| |
| | |
| {{Theorem
| |
| |Chernoff bound for the <math>\chi^2</math>-distribution|
| |
| :For i.i.d. standard Gaussian random variables <math>X_1,X_2,\ldots,X_k\sim\mathcal{N}(0,1)</math>, for <math>0<\epsilon<1</math>,
| |
| :*<math>\Pr\left[\sum_{i=1}^kX_i^2>(1+\epsilon)k\right]<\mathrm{e}^{-\epsilon^2k/8}</math>,
| |
| :*<math>\Pr\left[\sum_{i=1}^kX_i^2<(1-\epsilon)k\right]<\mathrm{e}^{-\epsilon^2k/8}</math>.
| |
| }}
| |
| | |
| Note that this indeed implies the above concentration bound by setting <math>X_i=\sqrt{k}\cdot Y_i</math> and <math>\delta\ge\mathrm{e}^{-\epsilon^2k/8}</math>.
| |
| | |
| {{Proof|
| |
| We first prove the upper tail. Let <math>\lambda>0</math> be a parameter to be determined.
| |
| :<math>
| |
| \begin{align}
| |
| \Pr\left[\sum_{i=1}^kX_i^2>(1+\epsilon)k\right]
| |
| &=\Pr\left[\mathrm{e}^{\lambda \sum_{i=1}^kX_i^2}>\mathrm{e}^{(1+\epsilon)\lambda k}\right]\\
| |
| &< \mathrm{e}^{-(1+\epsilon)\lambda k}\cdot \mathbf{E}\left[\mathrm{e}^{\lambda \sum_{i=1}^kX_i^2}\right] && \text{(Markov's inequality)}\\
| |
| &= \mathrm{e}^{-(1+\epsilon)\lambda k}\cdot \prod_{i=1}^k \mathbf{E}\left[\mathrm{e}^{\lambda X_i^2}\right]. && \text{(independence)}
| |
| \end{align}
| |
| </math>
| |
| {{Theorem|Proposition|
| |
| :For standard Gaussian <math>X\sim\mathcal{N}(0,1)</math>, <math>\mathbf{E}\left[\mathrm{e}^{\lambda X^2}\right]=\frac{1}{\sqrt{1-2\lambda}}</math>.
| |
| }}
| |
| {{Proof|
| |
| :<math>
| |
| \begin{align}
| |
| \mathbf{E}\left[\mathrm{e}^{\lambda X^2}\right]
| |
| &=
| |
| \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{e}^{\lambda x^2}\mathrm{e}^{-x^2/2}\,\mathrm{d}x\\
| |
| &=
| |
| \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{e}^{-(1-2\lambda)x^2/2}\,\mathrm{d}x\\
| |
| &=
| |
| \frac{1}{\sqrt{1-2\lambda}}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{e}^{-y^2/2}\,\mathrm{d}y &&(\text{set }y=\sqrt{1-2\lambda}x)\\
| |
| &=\frac{1}{\sqrt{1-2\lambda}}.
| |
| \end{align}
| |
| </math>
| |
| The last equation is because <math>\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{e}^{-y^2/2}\,\mathrm{d}y</math> is the total probability mass of a standard Gaussian distribution (which is obviously 1).
| |
| }}
| |
| Then continue the above calculation:
| |
| :<math>
| |
| \begin{align}
| |
| \Pr\left[\sum_{i=1}^kX_i^2>(1+\epsilon)k\right]
| |
| &<
| |
| \mathrm{e}^{-(1+\epsilon)\lambda k}\cdot \left(\frac{1}{\sqrt{1-2\lambda}}\right)^k\\
| |
| &=
| |
| \mathrm{e}^{-\epsilon\lambda k}\cdot \left(\frac{\mathrm{e}^{-\lambda}}{\sqrt{1-2\lambda}}\right)^k\\
| |
| &\le
| |
| \mathrm{e}^{-\epsilon\lambda k + 2\lambda^2 k} && (\text{for }\lambda<1/4)\\
| |
| &=
| |
| \mathrm{e}^{-\epsilon k/8}. && (\text{by setting the stationary point }\lambda=\epsilon/4)
| |
| \end{align}
| |
| </math>
| |
| This proved the upper tail. The lower tail can be symmetrically proved by optimizing over a parameter <math>\lambda<0</math>.
| |
| }}
| |
| | |
| As we argued above, this finishes the proof of the Johnson-Lindenstrauss Theorem.
| |
| | |
| = Nearest Neighbor Search (NNS)=
| |
| {{Theorem|Nearest Neighbor Search (NNS)|
| |
| *'''Data''': a set <math>S</math> of <math>n</math> points <math>y_1,y_2,\ldots,y_n\in X</math> from a metric space <math>(X,\mathrm{dist})</math>;
| |
| *'''Query''': a point <math>x\in X</math>;
| |
| *'''Answer''': a nearest neighbor of the query point <math>x</math> among all data points, i.e. a data point <math>y_{i^*}\in S</math> such that <math>\mathrm{dist}(x,y_{i^*})=\min_{y_i\in S}\mathrm{dist}(x,y_i)</math>.
| |
| }}
| |
| | |
| | |
| {{Theorem|<math>c</math>-ANN (Approximate Nearest Neighbor)|
| |
| :<math>c>1</math> is an approximate ratio.
| |
| *'''Data''': a set <math>S</math> of <math>n</math> points <math>y_1,y_2,\ldots,y_n\in X</math> from a metric space <math>(X,\mathrm{dist})</math>;
| |
| *'''Query''': a point <math>x\in X</math>;
| |
| *'''Answer''': a <math>c</math>-approximate nearest neighbor of the query point <math>x</math> among all data points, i.e. a data point <math>y_{i^*}\in S</math> such that <math>\mathrm{dist}(x,y_{i^*})\le c\, \min_{y_i\in S}\mathrm{dist}(x,y_i)</math>.
| |
| }}
| |
| | |
| | |
| {{Theorem|<math>(c,r)</math>-ANN (Approximate ''Near'' Neighbor)|
| |
| :<math>c>1</math> is an approximate ratio; <math>r>0</math> is a radius;
| |
| *'''Data''': a set <math>S</math> of <math>n</math> points <math>y_1,y_2,\ldots,y_n\in X</math> from a metric space <math>(X,\mathrm{dist})</math>;
| |
| *'''Query''': a point <math>x\in X</math>;
| |
| *'''Answer''': <math>
| |
| \begin{cases}
| |
| \text{a data point }y_{i^*}\in S\text{ such that }\mathrm{dist}(x,y_{i^*})\le c\cdot r & \text{if }\exists y_i\in S, \mathrm{dist}(x,y_{i})\le r,\\
| |
| \bot & \text{if }\forall y_i\in S, \mathrm{dist}(x,y_{i})>c\cdot r,\\
| |
| \text{arbitrary} & \text{otherwise}.
| |
| \end{cases}
| |
| </math>
| |
| }}
| |
|
| |
|
| {{Theorem|Theorem|
| | <math>\begin{align} |
| :For any instance <math>S=\{y_1,y_2,\ldots,y_n\}</math> of the nearest neighbor problem, let <math>D_{\min}\triangleq\min_{y_i,y_j\in S}\mathrm{dist}(y_i,y_j)</math>, <math>D_{\max}\triangleq\max_{y_i,y_j\in S}\mathrm{dist}(y_i,y_j)</math> and <math>R\triangleq \frac{D_{\max}}{D_{\min}}</math>.
| | I&=Q_o \cdot i(x), \\ |
| :If for any <math>r>0</math> there always exists a data structure for the <math>(c,r)</math>-ANN problem, using space at most <math>s</math>, answering each query in time <math>t</math>, correctly with probability <math>1-\delta</math>,
| | i(x)&=i_o \cdot P_o(x)+ i_2 \cdot P_2(x), |
| :then there exists a data structure for the <math>c</math>-ANN problem, using space <math>O(s\log_c R)</math>, answering each query in time <math>O(s\log_c R)</math>, correctly with probability <math>1-O(\delta\log\log_c R)</math>. | | \end{align}</math> |
| }}
| | |
| | 其中， <math>i_o=0.687</math>, <math>i_2=-0.165</math>。 假设行星反照率为<math>\alpha</math>，且忽略它随纬度和经度的变化: |
|
| |
|
| = Locality-Sensitive Hashing (LSH)=
| | #请写出在能量平衡的情况下，大气和海洋的总经向能量输送应满足什么条件？ |
| | #按此条件，请利用合适的边界条件，请推导出大气和海洋的总经向能量输送将如何随纬度<math>\phi</math>和太阳辐射强度<math>Q_o</math>变化。 |