Reproducing Kernel Hilbert Spaces (RKHS)

15 de febrero de 2016

1.

Elementos de base

Abordar el tema de RKHS requiere (ó es más fácil si se tiene familiaridad con) los siguientes conceptos: *Topología > Métrica + (*Espacios Vectoriales otra raiz) >Espacios Normados> Completitud > Banach Spaces > Inner product Spaces > Completitud > Hilbert Spaces. Y la dinámica de como se van construyendo y probando sus propiedades. [Completar con las notas del curso de DTU]. -Explicar que nosotros podemos arrancar por la raiz de definir que es una topología, pero que no es el camino que pienso seguir. De todas maneras la métrica nos induce una topología. Guías para cuando lo escriba: Motivación: Todo esto es una formalización teórica que nos va a permitir extender los conceptos que aplicamos a espacios vectoriales finitos (Rn ): bases, combinaciones lineales, independencia lineal, ortogonalidad. A espacios vectoriales infinitos. Todo queda más claro cuando a cada elemento nuevo que introducimos en este nuevo espacio podemos marcar claramente el equivalente finito (ejemplo vector vs sucesión). Primer “Idea nueva”. Un vector infinito: Mostrar que una sucesión (sequence, una función sobre el dominio de los naturales) es un vector infinito. Recordar que existen infinitos numerables y no numerables. Que el caso antes expuesto se corresponde con el caso del infinito numerable y que el caso del infinito no numerable es el de las funciones sobre el dominio real. -Base: Dada una cierta base, cualquier vector en Rn , tiene una única representación como lo suma de los vectores de la base. v=

n X

ci bi = B T c

i=1

(dónde B es la matriz que se forma tomando los vectores columna que forman la base (B = b1 , . . . , bn ) y los ponemos uno al lado del otro B = (b1 | . . . |bn ) ) La primera concecuencia importante tiene que ver con que si queremos definir una base en este espacio que contiene a estos vectores infinitos, vamos a necesitar ´b P∞ sumas infinitas, en el caso de numerables i=1 en el caso de no numerables a . 1

Si seguimos adelante, va a llegar un momento que vamos a querer usar el concepto de norma (que nos da la idea de tamaño de un vector y que a su vez nos puede servir como medida de distancia (si pensamos que podemos crear un vector extra que vaya desde las puntas de los dos vectores que quiero comparar, el tamaño de ese vector me sirve como medida de distancia entre los dos vectores.)). Cuando entra el concepto de norma, en el espacio infinito, me doy cuenta que surgen varias cuestiones: - La primera es que la norma por definición siempre me tiene que dar un elemento de un cuerpo (por ahora dejamos R ó C) y en ese caso si quiero respetar eso, no puede haber normas que me den ∞. - Todavía previo tengo que usar solo funciones (sucesiones o funciones sobre el dominio real) que cuando sume todas sus componentes no me den ∞. Es por eso que se nombra tanto la convergencia. - Además otra condición todavía más de base, es que la suma de dos elementos del espacio me tiene que dar otro elemento del espacio. De ahí puedo conectar eso con X kv− vi k → 0 i=1

¿Por qué de `p solo nos sirve ``2 para formar un espacio de Hilbert? Aunque todas las `p tienen norma y esos espacios son completos bajo esa norma, la única norma que nos induce un producto interno “valido” es `2 . Además agregar las intuiciones sobre Kernels (funciones que comparan dos patrones x y me devuelve un número real que me indica un grado de similitud)

2.

¿Qué es un RKHS?

A través de los kernels se puede formar un espacio vectorial particular que va a cumplir todos los requisitos para ser considerado un espacio de Hilbert, pero que además va a tener otras propiedades específicas que van a ser útiles para resolver problemas de aprendizaje a través de algoritmos como, por ejemplo, SVM y KPCA (técnicas dónde usamos kernels). A ese espacio vectorial se lo conoce como reproducing kernel Hilber Space (RKHS). Entonces, no es una técnica en sí misma, sino más bien un desarrollo teórico que nos permite extender herramientas que ya poseíamos dándole un respaldo matemático formal. También nos permite dar nuevas interpretaciones (guíadas por conceptos matemáticos) a lo que uno está haciendo cuando aplicamos algoritmos con kernels.

3.

Motivación (uso en Statistical Learning)

El concepto de RKHS (y los conceptos asociados) se fue formando “poco a poco” (ver sección histórica). Pero la teoría alrededor del concepto fue abordada sistemáticamente en la decada del 50 con los trabajos de Nachman Aronszajn y Stefan Bergman.

2

Pero a nosotros nos interesa su aplicación en Statistical Learning Theory. En particular nos interesa usar este espacio de funciones (los RKHS), como el espacio de hipotesis para nuestros algoritmos de aprendizaje. Esto quiere decir que las funciones que “vivan” en nuestro RKHS, formarán el conjunto de las funciones que nuestro algoritmo de aprendizaje va a considerar como candidatas a ser la que mejor aproxima a la función objetivo que queremos aprender (o descubrir) de los datos. Cuando decimos encontrar la mejor aproximación, en realidad, lo que estamos buscando es una función que sea la mejor en un sentido muy específico (basada en un principio que se llama Empirical Risk Minimization) y es que nuestra función h minimize un funcional que se conoce como Empirical Risk, m 1 X L(h(xi ), yi ). ER(h) = m i=1 Dónde tenemos pares (xi , yi ) que representan los datos (un xi representa un patrones e yi la categoría a la que ese patrón corresponde). h representa la función que aprendimos, es la que va a asignarle a cada patrón (xi ) una categoría. L es una función de perdida (loss function) que nos indica el “costo” de a un patrón (xi ) asigarle una determinada categoría comparando con la categoría que le correspondía (yi ). Vemos entonces que lo que este funcional hace es promediar el “costo”. El único inconveniente es que así como la definimos antes, sin ninguna restricción sobre el tipo de funciones “candidatas” a usar cómo h, el problema de encontrar esta función, no es “well-posed” esto quiere decir que no cumple las siguientes 3 condiciones: Una solución existe, es única y el comportamiento de la solución cambia continuamente con las condiciones iniciales. Para poder lograr que sea well-posed, Tikhonov, propuso un tipo particular (linear regularization) de lo que se conoce como regularización. Esto es agregar un término a mi problema de minimización que se conoce como regularizador y lo que hace es favorizar el uso de funciones más “suaves”. Básicamente el regularizador es un nuevo funcional que crece proporcionalmente al “tamaño” (norma) de la función h. En general si el valor de h es pequeño, la función es más suave, y por lo tanto ajusta menos en detalle a los puntos dato. Esto es bueno, porque nos permite respetar el principio de generalización, que dice que es bueno evitar ajustar al máximo posible a los datos ya que así, obtenemos una mejor performance al evaluar puntos nuevos. ER(h) + λR(h)

4.

Introducción

Insertar figura (RKHS - R(PD)K - Feature Map) y sus relaciones Supongamos que nos dan un dataset D = {(x1 , y1 ), . . . , (xn , yn )} dónde cada (xn , yn ) ∈ X × R. Acá los xi son los patrones que vienen de un dominio

3

X . El conjunto X puede ser cualquiera menos el conjunto vacío. Las yi son las etiquetas de esos patrones. Para dar un ejemplo concreto, podríamos pensar en identificación de piezas defectuosas. Nuestro dataset X = {xi }ni= puede estar compuesto de vectores (i) (i) (i) (i) xi = (x1 , x2 ) dónde x1 y x2 son mediciones de ciertas características de las piezas, de por ejemplo, el diametro y la altura de la pieza. Las mediciones son número reales, por lo tanto nuestros xi ∈ R2 , es decir forma un vector en el espacio R2 . Podemos imaginarnos que decidimos que nuestras yi van a indicar para cada xi , que tan buena es la pieza mediante un número real asignado por un operario de la planta. Finalmente, nuestro objetivo es poder darle este dataset a un algoritmo y que “aprenda” (que encuentre una función) que para cada punto del dataset y para todo nueva pieza para la que midamos esas altura y diametro, nos diga la nota que el operario le asignaría. Si no limitamos de ninguna manera el tipo de funciones que vamos a aceptar como respuesta, existen infinitas funciones que podemos elegir como candidatas a ser “la” función que mapee puntos xi 7→ yi . Al conjunto de funciones que vamos a aceptar como candidatas se lo llama generalmente Espacio de Hipotesis (Hypothesis Space) H, que en el caso no limitado se definiría: H = {f | f : X → R}. “Espacio” porque en general este conjunto de funciones forman un espacio vectorial (cumplen las condiciones de un espacio vectorial) y de “hipotesis” porque son las funciones “candidatas” a ser la función más adecuada. Para dar un ejemplo concreto, por ejemplo, podemos solo considerar como funciones candidatas solo a las funciones lineales de x, y esto se notaría H ⊂ F ={f | ∃w ∈ Rd , f (x) = wT x ∀x ∈ Rd }. Ahora que tenemos nuestro espacio de hipotesis, nos preguntamos ¿qué es lo que esperamos de él? Lo ideal es que por lo menos tenga dos características: Que contenga “buenas modelos”. Recordemos que cada una de nuestras funciones en el espacio de hipotesis, es en sí un modelo. Es un posible modelo de la manera en la que el operario de la planta le asigna la etiqueta yi a cada pieza xi . En general lo que nosotros buscamos es que no sea un modelo ni muy simple (que nos genere problemas de underfitting), ni muy complejo (que produce overfitting, que significa que no generaliza, ó que no sigue el principio de Occam’s razor). Que sea eficiente. Esto significa que, por ejemplo, tiene que ser fácil una vez que elegí mi modelo (o sea que elegí un f ) saber que nota le asigna mi modelo a un punto xi (esto sería computar f (x)). Ejemplo concreto: Siguiendo con el espacio de funciones lineales, definamos nuestro espacio de hipotesis como: H ⊂ F ={f | ∃w ∈ R3 , f (x) = wT x ∀x ∈ R3 , x0 = 1} Esto quiere decir que como funciones (modelos) candidatas solo vamos a aceptar planos en el espacio R3 que no necesariamente pasan por el origen, esto sería f (x) = w0 x0 + w1 x1 + w2 x2 . Lo primero que nos damos cuenta es que cada 4

función f se puede identificar de manera única y sin riesgo de confundirla con otra (unívoca) usando un vector. Este vector es el vector normal, en este caso sería el formado por w =(w0 , w1 , w2 ), que como sabemos identifica a un plano. Esto es muy bueno porque este mapeo (isomorfo) entre f 7→ w nos va a permitir aplicar todas las técnicas tradicionales del álgebra lineal en las funciones, a através de su representación como vectores w. Lo que nos da entonces, la carácterística que nos interesaba de que sea “eficiente” trabajar con este espacio de funciones. Concretamente, aprovechando esta relación, vamos a definir entonces: El producto interno entre dos funciones de mi espacio: hf, f 0 iF := wT w0 El definir un producto interno, nos induce una norma: √ kf kF = kwk = wT w y esa norma nos induce una métrica: d(f, f 0 ) =kf − f 0 kF = kw − w0 k =

q (w − w0 )T (w − w0 ).

Entonces vemos cómo gracias a definir ese mapeo, pudimos definir conceptos que ya sabemos que funcionan para los vectores ( el producto interno, la norma y la distancia) a elementos que antes no los tenían definidos (nuestras funciones).

4.1.

Continuidad y boundeness

Existe una propiedad que va ser muy interesante a la hora de buscar “la mejor” función en nuestro espacio. Esta es que si, por ejemplo, yo estoy considerando una f y obtengo un cierto resultado al evaluar un punto f (x), si veo que me gustaría que ese resultado sea “un poco” mejor (o peor), intuitivamente buscaría reemplazar mi f por una f 0 que sea “un poco” diferente de f . Esto quiere decir, si yo modifico “un poco” mi f , lo que yo esperaría es que mis resultados solo cambien “un poco” y no “mucho”. Si a pequeñas variaciones de la función, mis resultados cambiarían “drasticamente” sería muy dificil poder buscar la mejor función. Esta característica se conoce como continuidad y está estrechamente relacionada con la definción de límite. Más formalmente nos gustaría que exista un funcional, que es un mapeo entre f y su valor en un punto f (x) que sea continuo. Definición clásica para una función ∀x ∈ (a, b), ∀ε > 0 ∃δ > 0 (δ = δ(ε)) / 0 < |x − x0 | < δ ⇒ |f (x) − f (x0 )| < ε Definicion de un funcional continuo. 5

∀f, f 0 ∈ F, ∀ε > 0 ∃δ > 0 (δ = δ(ε)) / 0 < kf − f 0 k < δ ⇒ |f (x) − f 0 (x)| < ε Ahora demostramos que si usamos las definiciones en el punto anterior ese funcional que nos evalua la función en el punto es continuo. |f (x) − f 0 (x)| = |wT x − w0T x| = |(w − w0 )T x| kw − w0 kkxk

≤

= kf − f 0 k c Esto quiere decir que basta definir δ = |f (x) − f 0 (x)|

≤

ε kxk ,

así si 0 < kf − f 0 k < δ ⇒

kf − f 0 k kxk

δ kxk ε = kxk kxk = ε <

4.2.

Diccionarios finitos (ganando más más flexibilidad) .

Con este “truco” de mapear funciones lineales con vectores en Rd , logramos usar nuestras herramientas de algebra lineal para computar estas medidas de distancia. Pero el problema, es que esto nos sirve solo para funciones lineales. Si quisieramos pasar a una función, por ejemplo, cuadrática f (x) = w0 x0 + w1 x21 + w2 x22 , no podríamos usar este truco. Por eso a continuación muestramos una manera en la que podemos aumentar la flexibilidad de nuestras funciones. Puedo definir lo que se conoce como una diccionario, que es un conjunto de funciones Φ = {ϕn : X → R | n = 1, . . . , p} con p ≥ d, que van a definir p X un espacio de funciones H = {f | ∃w ∈ Rp , f (x) : wi φi (x)}. Se fija p ≥ i=1

d porque si fuera el caso de que cada característica me traer información, si uso p < d estaría perdiendo información. O sea, si por ejemplo, usamos un conjunto de funciones ϕn = sen(nx), mis funciones candidatas van a ser las combinaciones lineales de esos senos que forman el diccionario. Ganaríamos entonces la posibilidad de usar en nuestro modelo funciones no lineales. Para no perder las herramientas de computo que ya teníamos, usamos el mismo “truco” que antes. Podemos usar un mapeo dónde ahora el vector wi representa los pesos por los que multiplicamos a las funciones del diccionario. Ahora el notamos que si queremos que ese mapeo sea uno a uno. Las funciones del diccionario deben ser linealmente independientes, así cada función, tendrá una sola manera de obtenerse. wi 7→ f =

p X i=1

6

wi φ i

Ahora los problema con este approach son por lo menos 2: 1. es que a priori tengo que elegir p (la cantidad de funciones que voy a tener en mi diccionario) y si veo que no fue “suficientemente” flexible, tengo que aumentar p y volver a entrenar el algoritmo. Digamos que sería ideal poder fijar p = ∞ (modelo no paramétrico). 2. Que el algoritmo en sí, no me dice que tipo de funciones me conviene usar como φ.

5.

Reproducing Kernel Hilbert Spaces

Es finalmente acá cuando entra en juego la teoría de los RKHS. Que nos va a permitir usar un diccionario con (hasta) un infinito número de funciones, lo que nos da un espacio de dimensión infinita. Pero lamentablemente nos va a seguir dejando sin resolver el problema de encontrar cuales son las funciones φ ideales a utilisar. Una dificultad que encontré al estudiar los RKHS es que existen 3 conceptos que se implican entre si. Por tanto, en la bibliografía uno se encuentra con distintos autores introducen el tema desde distintas conceptos. Esto es lo que sucedió históricamente. Por ejemplo, Aronzajn introduce el tema a partir del estudio de los reproducing kernels, pero lo que vamos a descubrir es que uno puede empezar definiendo cualquiera de los 3 objetos de la figura y descubrir que estos implican a los otros. Estos caminos son los que vamos a mostrar. Siguiendo con el razonamiento que presentamos en la introducción nos damos cuenta que nos gustaría trabajar con un espacio de hipotesis donde podamos usar nuestras herramientas de algebra lineal (esto se cumple si nuestro espacio de hipotesis es un espacio de Hilbert) y nos gustaría que tenga una característica extra, que es que “sea fácil” ver como esa hipotesis clasificaría un punto y que “a pequeñas” modificaciones de mi hipotesis la manera en la que clasifica cambie “un poco”. Todas estas descripciones son muy informales y por eso vamos a indicar exactamente en que sentido nos referimos a “fácil”, “pequeñas” y “poco”. Para esto tenemos que introducir el concepto de point evaluation functional: Definición 1. Un point evaluation functional sobre un espacio de Hilbert H es un funcional lineal Lx : H → R que evalua cada función del espacio f ∈ H, en un punto x. Lx (f ) = f (x) con este concepto en mente, podemos definir finalmente que característica extra queremos que tenga nuestro espacio de Hilbert. Definición 2. (Reproducing Kernel Hilbert Space) Un espacio de Hilbert H de funciones f : X → K (con X 6= ∅ y K bien R ó C) es un reproducing kernel Hilbert space si los point evaluation functionals son continuos (lo que implica acotados).

7

Que nuestros espacio de Hilbert tenga point evaluation functionals continuos, es lo que nos formaliza esta impresión de variaciones pequeñas de la función, variaciones pequeñas de los resultados. Formalmente:

∀f, f 0 ∈ H, ∀ε > 0 ∃δ > 0 (δ = δ(ε)) / 0 < kf − f 0 k < δ ⇒ |f (x) − f 0 (x)| < ε Además, existe un teorema en análisis funcional que muestra que todo operador es continuo si y solo si es acotado. Ahora mostramos que el haber impuesto esta condición sobre el espacio de Hilbert, efectivamente, reduce el tipo de espacios que podemos considerar. Entonces solo vamos a poder considerar espacios que cumplan dos condiciones simultaneamente : a) ser Hilbert Space y b) tener un continuos evaluation functional. Ejemplo de un espacio que tiene que point evaluational functionals continuos pero que no es un Espacio de Hilber es el siguiente: Sea C[a, b] el espacio de funciones continuas en el intervalo [a, b] con la norma definida por kf k∞ = m´ axx∈[a,b] |f (x)|, podemos demostrar que es acotado (y por lo tanto continuo) ya que cualquier punto de la función siempre va ser menor o igual que el máximo de la función (por definición de máximo), pero al mismo tiempo vemos que esa norma, no se puede expresar mediante un producto interno y por lo tanto este espacio no forma un espacio de Hilbert. Otro ejemplo interesante es el de un espacio que es un espacio de Hilbert pero sus point evaluation functionals no son continuos (lo que implica que no son acotados). Notamos que el espacio de funciones ˆ

b

|f (x)|2 dx < ∞}

L2 [a, b] = {f | a

no cuenta con funcionales acotados. Cada elemento del espacio (cada f ) forma parte de una clase equivalente de funciones que tienen la misma integral ˆ b |f (x)|2 dx, esto quiere decir que para una dada función la integral de lebesgue a

no cambia si modificamos los valores que toma para una cantidad contable de puntos de su dominio. Por lo perdemos la posibilidad de controlar el valor que toman dos funciones en un punto a través de la norma. Puntualmente esto quiere decir que definir kf − f 0 k < δε no implica que |f (x) − f 0 (x)| < ε.

6.

(Positive Definite) Reproducing Kernel

Ahora vamos a notar que si tenemos un RKHS, vamos a “obtener” también un nuevo objeto que cumple dos propiedades. Primero vamos a definir cual es ese objeto. (Kernel) Un kernel es una función de dos variables k : X ×X → R, (x, x0 ) 7→ k(x, x0 ).

8

(Reproducing Kernel) Sea X un conjunto no vacío. Sea H ⊆ CX un espacio de Hilbert de funciones de valores complejos definidos en X . Un kernel k : X × X → C se llama núcleo reproductor (reproducing kernel) de H si posee dos propiedades: 1. ∀x0 ∈ X , k(·, x0 ) ∈ H. 2. ∀x0 ∈ X y f ∈ H, f (x0 ) = hf (·), k(·, x0 )iH Ahora estamos en condiciones de probar que si H es RKHS entonces ∃! k que es Reproducing Kernel de ese espacio. Prueba: (Dirección RKHS⇒ R.K.) Para probar esto necesitamos primero dos teoremas de análisis funcional. (Riesz’ Theorem) Todo funcional lineal acotado (bounded linear functional) f en un espacio de Hilbert H puede ser representado como un producto interno f (x) = hx, zi dónde z depende de f, queda completamente determinado por f y tiene norma kzk = kf k. Y el teorema (Riesz Representation), que en base al teorema de Riesz nos da una representación del kernel como un producto interno. Entonces si H es un RKHS, los funcionales lineales acotados en el espacio de Hilbert tendrán una representación Lx (f ) = hKx , f i = f (x) dónde Kx será el reproducing kernel. Prueba: (Dirección R.K ⇒RKHS) Vamos a demostrar que si existe un reproducing kernel, entonces nuestro point evaluation functional es acotado, lo que implica continuo. |Lx (f )| = |f (x)| =

|hf (·), k(·, x)iH |

≤

kf kH kKx k p = kf kH hk(·, x), k(·, x)iH p = kf kH k(x, x) Otro camino sería probar directamente la continuidad: |Lx (f ) − Lx (f 0 )| = |hf (·), k(·, x)iH − hf 0 (·), k(·, x)iH | = |hf − f 0 , Kx iH | ≤

kf − f 0 kH kKx kH

Vemos entonces que si fijamos kf −f 0 kH < δ =

9

ε kKx kH

⇒ |Lx (f )−Lx (f 0 )| < ε

6.1.

Definido Positivo

Una función continua y simétrica (Hermitian form si fuera en los complejos) k : X × X → R es definida positiva si ∀n ≥ 1 ∈ N, a1 , . . . , an ∈ R, x1 , . . . , xn ∈ X n X ai aj k(xi , xj ) ≥ 0 i,j=1

Partiendo de un kernel definido positivo, podemos probar que existe un RKHS asociado a él. Esto lo demostró Aronszajn en su paper. Lo primero que tenemos que considerar es un kernel k definido positivo, un espacio de funciones H0 = span{k(·, x) | x ∈ X }, lo que sería equivalente a n X decir que H0 está formado por el conjunto de funciones f (·) = αi k(xi , ·). A i=1

continuación definimos un producto interno en H0 , siendo f (·) =

n X

αi k(xi , ·)

i=1

y g(·) =

l X

βj k(xj , ·)

j=1

hf, gi =

n X l X

αi k(xi , x0j )βj

i=1 j=1

El cual vemos que cumple las condiciones de un producto interno, siendo i) linearidad respecto del primer argumento. ii) simetría (lo cual demuestra también que es lineal respecto del segundo argumento, o sea es bilineal) iii) por ser definido positivo cumple hf, f i ≥ 0 ∀f ∈ H0 y solo es hf, f i = 0 si kf k= 0 . Además si consideramos el producto interno entre una función una función f (·) y otra función h(·) = k(x0 , ·), vemos que

hf, hi = hf, k(x, ·)i =

n X

αi k(xi , x0 )

i=1

= f (x0 ) Finalmente nos resta agregar la propiedad de que el espacio se completo y en ese caso tendremos un RKHS. Para hacer esto, lo primero que hacemos es observar que dada una sucesión de Cauchy {fn }∞ n=1 , m < n y un punto x, fn (x) − fm (x)

=

hfn , k(x, ·)i − hfm , k(x, ·)i

=

hfn − fm , k(x, ·)i

≤

kf − f 0 kH kKx kH

(resultado que ya habíamos obtenido anteriormente), con esto vemos que {fn }∞ n=1 es acotada y que por lo tanto converge a una función f . Si agregamos 10

a todas estas funciones a nuestro espacio, finalmente, obtenemos un espacio de Hilbert. Este espacio es a su vez un RKHS. En particular, este es el RKHS asociado a nuestro kernel definido positivo.

7.

Feature Maps

Finalmente vamos a mostrar que el kernel define un feature map, o sea un mapeo que transforma nuestros puntos datos.

8.

Integral Operator and Integral Transforms

La idea en esta sección es mostrar el rol que los kernels juegan en los operadores integrales. Más que nada para completar el interés de los matemáticos en estudiarlos.

9.

Un poco de historia

(1907) Stanislaw Zaremba: Introduce la propiedad del núcleo reproductor (reproducing kernel property). 1. Stanislaw Zaremba, L’équation biharmonique et une class remarquable de functions fondamentales harmoniques, Bulletin International de l’Acadmie des Sciences de Cracovie 1907, 147-196. 2. Stanislaw Zaremba, Sur le calcul numérique des fonctions demandées dans le probléme de Dirichlet et le probléme hydrodynamique, ibidem, 1909, 125-195. [1907, 1908, 1909] Series exapansions of positive definite kernels (James Mercer y Erhard Schmidt ) (1909) James Mercer: Trabaja con funciones que satisfacen la reproducing property y prueba que bajo ciertas condiciones un P kernel definido positivo puede ∞ descomponerse de la siguiente manera k(x, x0 ) = i=1 λi ϕi (x)ϕi (x0 ). [1]J. Mercer, “Functions of Positive and Negative Type, and their Connection with the Theory of Integral Equations,” Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 209, no. 441–458, pp. 415–446, Jan. 1909. Reproducing Kernel (1950) Nachman Aronszajn, Publica un paper donde muestra que todo Positive Definite Kernel define un RKHS (acredita este resultado a Moore) (1970) Grace Wahba, publica el Representer Theorem que usa los RKHS.

Apéndice (Function space) F cuyos elementos son funciones, e.g. f : n es un espacio o ´∞ 2 Rd → R ó L2 (R) = f : R → C | −∞ |f (x)| < ∞ .

11

(Bounded linear operator) Let V1 and V2 be normed spaces. A linear operator T : V1 → V2 is bounded if there existes a constant K ≥ 0 such that kT vkV2 ≤ KkvkV1 , ∀v ∈ V1 The smallest possible value of K that can be used in the former equation is called norm of the operator T , and is denoted by kT k. (RKHS) Un RKHS es un espacio de Hilbert que cumple: - Todo evaluation functional es continuo y acotado. (funcional) Sea H un espacio de Hilbert. Un funcional es un operador lineal Φ : H → C. (funcional acotado) Un funcional es acotado si existe una constante K tal que |Φv| ≤Kkvk, ∀v ∈ H Todo funcional acotado se puede reprensentar mediante un producto interno. Sea un elemento del espacio de Hilbert w ∈ H se puede definir un funcional acotado mediante un producto interno Φ : H → C, Φv := hv, wi, diferentes w nos proveen diferentes funcionales. (Riesz’ Representation Theorem) Dado cualquier funcional acotado Φ : H → C, existe un único vector w ∈ H tal que Φv = hv, wi se cumple. El vector asociaciado con el funcional es único. Sea H un espacio de Hilbert. Asumimos que u,w ∈ H satisface hv, ui = hv, wi,∀v ∈H ⇒ u = w

Comentarios ¿Cuales fueron mis dificultades al estudiar este tema? ¿Cómo las abordo? Al estudiar este tema i) vi que existen 3 “conceptos” que se implican mutuamente (RKHS, Reproducing Kernel, Positive Definite Kernel) y cada autor comienza por lados diferentes y hasta algunos no cubren completamente los 3 “aspectos”. Esto hace muy dificil usar textos distintos para “complementar” el aprendizaje; ii) el grado de profundidad diferente con el que se trata (sin que sea esto aclarado a priori) hizo que a veces lea un texto con la sensación de que no estaba leyendo realmente sobre RKHS; iii) encontré muchos textos donde la introducción de nuevos conceptos no me pareció suficientemente bien motivados, muchos solo son una enumeración de teoremas y demostraciones que no explica el razonamiento que siguen o el por qué precisan definir elementos con ciertas propiedades. Tenemos teoremas para probar todas las “flechas” que relacionan los conceptos: 12

RKHS y Reproducing Kernels

13