Lovasz Extensión De La Intuición

Question

Estoy confundido por la definición de Lovasz extensión. El problema es que no tengo la intuición detrás de la definición. Además, Lovasz extensión puede ser definido de diferentes maneras no veo que la definición de estos son de hecho equivalentes. La siguiente es la definición y par mi pregunta con el nivel actual de conocimiento.

Para una función de $f:\{0,1\}^N \rightarrow R, f^L : [0,1]^N \rightarrow R$ está definido por

$f^L(x) = \sum_{i=0}^{n} \lambda_if(S_i)$

donde $\varnothing =S_0 \subset S_1 \subset S_2 \subset ... \subset S_n$ es una cadena tal que $\sum_{}^{} \lambda_i 1_{S_i}=x$ $\sum_{}^{} \lambda_i=1, \lambda_i \geq 0$

Una forma equivalente de definir el Lovasz extensión es : $f^L(x) = E[f(\{i:x_i > \lambda\})]$ donde $\lambda$ uniformemente al azar en $[0,1]$

Pregunta 1. La intuición. No tengo la intuición. $f$ es cierta la valoración de la función definida en todos los subconjuntos de a $N$ elementos. $f^L(x)$ es el similar por $f$, pero como la entrada de $x$ puede tomar valores fraccionarios de los elementos.

Pregunta 2: ¿Cuál de la siguiente función de $\sum_{}^{} \lambda_i 1_{S_i}=x$? En particular, no entiendo lo $1_{S_i}$ medios. Se ve como una combinación lineal de $\lambda_i$ y un mágico cosas $1_{S_i}$ (por favor, ¿qué significa?) tal y como resultado obtenemos la entrada que es el vector de $N$ elementos con valores fraccionarios.

Pregunta 3: definición Equivalente es $f^L(x) = E[f(\{i:x_i > \lambda\})]$, es el valor esperado, ¿significa que puedo volver a escribir como sigue $f^L(x) = x_if(i), \forall x_i > \lambda$, es este el mismo $\lambda$ como en la primera definición.

Pregunta 4: el requisito de $\varnothing =S_0 \subset S_1 \subset S_2 \subset ... \subset S_n$ parece bastante extraño, lo que el objetivo de este requisito.

Answer 1

Una entrada a $f^L$ es un punto en el $N$-dimensiones de la unidad de cubo de $[0,1]^N$. Una entrada a $f$ es uno de los $2^N$ rincones de este cubo. Por lo $f$ asocia un número $f(s)$ a cada esquina,$s$, y el objetivo es "inteligente" o al menos "razonable" extender esto para adjuntar un número a cada momento en el conjunto de cubo.

Lovász toma ventaja del hecho de que este cubo puede ser "razonablemente" se subdivide en $N!$ simplices. ($N$- Dimensiones simplex en Euclidiana $N$-dimensiones del espacio es, por definición, el casco convexo de $N+1$ puntos que no se encuentran en un $(N-1)$-dimensiones hyperplane.) Voy a describir la subdivisión de abajo, y señalar que cada uno de los simplices tiene su $N+1$ esquinas entre las esquinas del cubo, pero primero quiero llegar al punto principal de la construcción. Cada punto en un simplex es un promedio ponderado de las esquinas de la cara. Así que si usted tiene los números de $f(s)$ conectado a las esquinas $s$, entonces es razonable asociar a cualquier medio ponderado $x$ de las esquinas $s$, el correspondiente promedio ponderado de las $f$-valores. Esto es, para cualquier pesos $\lambda_i$, lo definiría $f(\sum_i\lambda_is_i)$$\sum_i\lambda_if(s_i)$. Como en cualquier promedio ponderado, los pesos $\lambda_i$ debe ser no negativo números reales que se suman a la $1$. (Un más rápido, pero menos de modo explícito a decir la misma cosa es definir $f$ a ser lineal en cada uno de los simplices y de acuerdo con los valores dados en las esquinas de la cara.)

Todavía tengo que decirle a usted lo que estos simplices son y cómo encajan entre sí para hacer el cubo. Para la mayoría de los puntos de $x$ en el cubo de la $[0,1]^N$, $N$ coordenadas $x_1,\dots, x_N$ son todos distintos. Permítanme temporalmente considerar sólo los puntos. Para cualquier $x$, podemos enumerar su $N$ coordenadas en orden decreciente, decir $x_{\sigma(1)}>x_{\sigma(2)}>\dots>x_{\sigma(N)}$ para algunos de permutación $\sigma(1),\sigma(2),\dots,\sigma(N)$$\{1,2,\dots,N\}$. Para cualquier permutación fija $\sigma$, todos los puntos de $x$ cuyas coordenadas son ordenados de acuerdo a ese $\sigma$ constituyen (el interior) de uno de los simplices.

Hasta ahora, he ignorado los puntos de $x$ que tienen dos o más coordenadas iguales; estos puntos serán en el límite de dos o más de estos simplices.

Las esquinas del simplex correspondiente a la permutación $\sigma$ $N+1$ puntos obtenidos de la siguiente manera. Recoger algunas $k$ en el rango $0\leq k\leq N$ y deje $s\in\{0,1\}$ ser el punto de con $s_{\sigma(i)}=1$$0<i\leq k$$s_{\sigma(i)}=0$$k<i\leq N$. Estos $N+1$ $s$ (uno por cada elección de $k$) son lo que se llama $S_0,\dots,S_N$ en la pregunta. que la notación tácitamente identifica un $N$-vector componente $s$ $0$'s y $1$'s (es decir, un elemento de $\{0,1\}^N$) con un subconjunto de a $\{1,2,\dots,N\}$, es decir, el conjunto de $\{i:s_i=1\}$. La notación $1_S$ utilizado en la pregunta significa que el vector que corresponde al subconjunto $S$$\{1,2,\dots,N\}$.