diff options
Diffstat (limited to 'si')
| -rw-r--r-- | si/n.lyx | 60 | ||||
| -rw-r--r-- | si/n3.lyx | 6 | ||||
| -rw-r--r-- | si/n4.lyx | 1378 | ||||
| -rw-r--r-- | si/n5.lyx | 989 | ||||
| -rw-r--r-- | si/n6.lyx | 620 | ||||
| -rw-r--r-- | si/n7.lyx | 776 |
6 files changed, 3827 insertions, 2 deletions
@@ -189,6 +189,10 @@ Frame (artificial intelligence) \emph on And–or tree \emph default +, +\emph on +Formal system +\emph default . \end_layout @@ -287,5 +291,61 @@ filename "n3.lyx" \end_layout +\begin_layout Chapter +Búsqueda no clásica +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n4.lyx" + +\end_inset + + +\end_layout + +\begin_layout Chapter +Representación del conocimiento +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n5.lyx" + +\end_inset + + +\end_layout + +\begin_layout Chapter +Planificación +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n6.lyx" + +\end_inset + + +\end_layout + +\begin_layout Chapter +Aprendizaje computacional +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n7.lyx" + +\end_inset + + +\end_layout + \end_body \end_document @@ -1486,9 +1486,11 @@ gets n$ \backslash -Repetir{para $(u_i,S) +Repetir{$ \backslash -in A$ sea $S +forall(u_i,S) +\backslash +in A,S \backslash nsubseteq R$}{ \end_layout diff --git a/si/n4.lyx b/si/n4.lyx new file mode 100644 index 0000000..458941f --- /dev/null +++ b/si/n4.lyx @@ -0,0 +1,1378 @@ +#LyX 2.3 created this file. For more info see http://www.lyx.org/ +\lyxformat 544 +\begin_document +\begin_header +\save_transient_properties true +\origin unavailable +\textclass book +\begin_preamble +\usepackage{amssymb} +\end_preamble +\use_default_options true +\begin_modules +algorithm2e +\end_modules +\maintain_unincluded_children false +\language spanish +\language_package default +\inputencoding auto +\fontencoding global +\font_roman "default" "default" +\font_sans "default" "default" +\font_typewriter "default" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_osf false +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures true +\graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default +\paperfontsize default +\spacing single +\use_hyperref false +\papersize default +\use_geometry false +\use_package amsmath 1 +\use_package amssymb 1 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 1 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false +\paperorientation portrait +\suppress_date false +\justification true +\use_refstyle 1 +\use_minted 0 +\index Index +\shortcut idx +\color #008000 +\end_index +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style french +\dynamic_quotes 0 +\papercolumns 1 +\papersides 1 +\paperpagestyle default +\tracking_changes false +\output_changes false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\end_header + +\begin_body + +\begin_layout Section +Búsqueda local +\end_layout + +\begin_layout Standard +En muchos problemas, como en diseño de circuitos u optimización de redes, + solo importa el estado objetivo, no cómo se llega a él. +\end_layout + +\begin_layout Standard +Los métodos que veremos operan con un único estado actual, no suelen recordar + los caminos, usan muy poca memoria y pueden encontrar soluciones razonables + en espacios de estados grandes o continuos en que los algoritmos clásicos + no son adecuados. +\end_layout + +\begin_layout Standard +Podemos considerar el espacio de estados como un paisaje donde la posición + es un estado y la elevación viene dada por una función objetivo a maximizar + o minimizar; supondremos que maximizar. +\end_layout + +\begin_layout Standard +Por ejemplo, en el +\series bold +problema de las 8 reinas +\series default +, consistente en situar 8 reinas en un tablero de ajedrez de forma que ninguna + esté en jaque, como cada reina debe estar en una columna, podemos representar + los estados como una tupla con la fila en la que está cada reina; cada + estado tendría 56 vecinos correspondientes a cambiar la posición de una + reina y la función a minimizar sería el número de jaques, que habría que + bajar a 0. +\end_layout + +\begin_layout Subsection +Búsqueda local avara o ascensión de colinas +\end_layout + +\begin_layout Standard +Se mueve en cada paso al vecino del estado actual con el valor objetivo + más alto. + A menudo se atasca en máximos locales; +\series bold +crestas +\series default +, secuencias de máximos locales que dificultan mucho la navegación, y sobre + todo en +\series bold +mesetas +\series default + o +\series bold +terrazas +\series default +, áreas donde la función objetivo es plana. +\end_layout + +\begin_layout Standard +Para evitar que se atasque en terrazas, se puede permitir un movimiento + lateral aleatorio cuando no hay ningún movimiento ascendente. + Esto lleva a un bucle infinito si el método alcanza un máximo local plano, + por lo que se suele limitar el número de movimientos laterales consecutivos. +\end_layout + +\begin_layout Standard +La +\series bold +ascensión de colinas de reinicio aleatorio +\series default + consiste en ejecutar la ascensión de colinas repetidamente con distintos + estados iniciales. + Es completa con probabilidad 1, aunque no garantiza terminar, en espacios + de estados finitos +\begin_inset Foot +status open + +\begin_layout Plain Layout +En general cuando caer en un estado final tiene probabilidad no nula y ascender + infinitamente tiene probabilidad nula. +\end_layout + +\end_inset + +, y es muy eficaz. +\end_layout + +\begin_layout Subsection +Temple simulado +\end_layout + +\begin_layout Standard +Para templar metal, este se calienta mucho para favorecer el movimiento + de las partículas y se enfría gradualmente para que estas se estabilicen + en estructuras cristalinas de baja energía. + Para tratar de colar una bola en el hueco más profundo de una superficie + con agujeros, esta se agita mucho para favorecer escapar de depresiones + locales y se reduce gradualmente la fuerza para que la bola se estabilice + en huecos profundos. +\end_layout + +\begin_layout Standard +Esta idea la usa el algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:sim-annealing" +plural "false" +caps "false" +noprefix "false" + +\end_inset + + para resolver problemas. +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Problema de espacio de estados sin costes $(V,A,s,F)$, función objetivo + $f:V +\backslash +to +\backslash +mathbb R$ y { +\backslash +bf esquema} de temperaturas $e: +\backslash +mathbb N +\backslash +to +\backslash +mathbb{R}^{ +\backslash +geq0}$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Solución $s +\backslash +in V$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwFunction{rand}{rand} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Para{$t +\backslash +gets1$ en adelante}{ +\end_layout + +\begin_layout Plain Layout + + $T +\backslash +gets e(t)$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$T=0$}{ +\backslash +Devolver $s$} +\end_layout + +\begin_layout Plain Layout + + $ +\backslash +{n_0, +\backslash +dots,n_{k-1} +\backslash +} +\backslash +gets +\backslash +{v +\backslash +in V:(s,v) +\backslash +in A +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Para{$i +\backslash +gets0$ +\backslash +KwA $k-1$}{ +\end_layout + +\begin_layout Plain Layout + + $c +\backslash +gets n_{ +\backslash +lfloor k +\backslash +rand{} +\backslash +rfloor}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $ +\backslash +Delta E +\backslash +gets f(c)-f(e)$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$ +\backslash +Delta E>0 +\backslash +lor +\backslash +rand{}<e^{ +\backslash +Delta E/T}$}{$s +\backslash +gets c$} +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:sim-annealing" + +\end_inset + +Temple simulado. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Subsection +Haz local +\end_layout + +\begin_layout Standard +Se empieza con +\begin_inset Formula $k$ +\end_inset + + estados elegidos aleatoriamente y, en cada paso, se generan los sucesores + de cada estado, se comprueba si alguno es objetivo para terminar y, si + ninguno lo es, se toman los +\begin_inset Formula $k$ +\end_inset + + mejores sucesores de entre todos. + Si hay poca diversidad entre los +\begin_inset Formula $k$ +\end_inset + + estados, esto no es mucho mejor que la ascensión de colinas, por lo que + los nuevos estados se suelen elegir de forma estocástica. +\end_layout + +\begin_layout Subsection +Algoritmos genéticos +\end_layout + +\begin_layout Standard +Son una variante de la búsqueda de haz local estocástica. + Cada estado, +\series bold +individuo +\series default + o +\series bold +cromosoma +\series default + se codifica como una cadena, normalmente de longitud finita, de un alfabeto + finito, en la que cada símbolo es un +\series bold +gen +\series default +. + Las codificaciones más usadas son +\series bold +binaria +\series default + mediante cadenas de dígitos binarios, +\series bold +entera +\series default + mediante cadenas de enteros de algún conjunto finito, y +\series bold +de orden +\series default +, en que la cadena es una permutación. +\end_layout + +\begin_layout Standard +En cada paso hay una +\series bold +población +\series default + de +\begin_inset Formula $k$ +\end_inset + + estados generados aleatoriamente. + Mediante un algoritmo de +\series bold +selección +\series default +, se escogen +\begin_inset Formula $k$ +\end_inset + + individuos de la población, posiblemente repetidos, que podrán reproducirse. + Estos se emparejan y cada pareja, con una probabilidad +\begin_inset Formula $p_{c}$ +\end_inset + +, se sustituye por dos individuos hijos mediante un algoritmo de +\series bold +cruce +\series default +. + Finalmente, se usa un algoritmo de +\series bold +mutación +\series default + para mutar cada gen de cada individuo con una probabilidad +\begin_inset Formula $p_{m}$ +\end_inset + +, y el resultado es la nueva población. + Esto se repite hasta que haya un individuo en la población suficientemente + bueno o pase bastante tiempo. +\end_layout + +\begin_layout Standard +Los +\series bold +operadores genéticos +\series default + son los algoritmos de selección, cruce y mutación. + Algunos algoritmos de selección: +\end_layout + +\begin_layout Itemize + +\series bold +Ruleta +\series default +: Para cada uno de los +\begin_inset Formula $k$ +\end_inset + + puestos, se elige un individuo con probabilidad proporcional a su valor + por la función objetivo, su +\series bold +idoneidad +\series default + o +\series bold +\emph on +\lang english +fitness +\series default +\emph default +\lang spanish +. +\end_layout + +\begin_layout Itemize + +\series bold +Torneo +\series default +: Se eligen +\begin_inset Formula $2k$ +\end_inset + + parejas por un algoritmo como la ruleta y se toma el de mayor idoneidad + en cada una. +\end_layout + +\begin_layout Standard +Algunos algoritmos de cruce: +\end_layout + +\begin_layout Itemize + +\series bold +Por un punto +\series default +: Se elige una posición al azar de las cadenas de los padres. + Un hijo adopta la parte a la izquierda de un padre y la parte a la derecha + del otro y el otro hijo al revés. +\end_layout + +\begin_layout Itemize + +\series bold +Por dos puntos +\series default +: Se eligen dos posiciones. + Un hijo adopta los extremos de un padre y el centro del otro y el otro + hijo al revés. +\end_layout + +\begin_layout Standard +Algunos de mutación: +\end_layout + +\begin_layout Itemize +Cambio de un gen aleatorio de un individuo por otro valor. +\end_layout + +\begin_layout Itemize +Intercambio de dos genes del individuo. +\end_layout + +\begin_layout Section +Búsqueda entre adversarios +\end_layout + +\begin_layout Standard +Un +\series bold +juego +\series default + o +\series bold +problema de búsqueda entre adversarios +\series default + es un entorno competitivo en que los objetivos de distintos agentes están + en conflicto. + Se deben considerar las decisiones de los otros agentes, pero su imprevisibilid +ad puede generar muchas contingencias. +\end_layout + +\begin_layout Standard +Consideramos juegos de suma cero (la suma del valor objetivo de cada agente + es 0), de dos jugadores, por turnos, determinista y de información perfecta + (entorno totalmente observable). + Los jugadores son +\family typewriter +max +\family default +, que mueve primero e intenta maximizar una cierta función utilidad +\begin_inset Formula $u$ +\end_inset + + de los estados terminales, y +\family typewriter +min +\family default +, que intenta minimizar +\begin_inset Formula $u$ +\end_inset + + +\end_layout + +\begin_layout Standard +Podemos representar un juego por una tupla +\begin_inset Formula $(V,A,M,s,F,u)$ +\end_inset + +, donde +\begin_inset Formula $(V,A)$ +\end_inset + + es un grafo como el de la búsqueda clásica de espacios de estados pero + en el que todos los nodos hoja son terminales; +\begin_inset Formula $M\subseteq V$ +\end_inset + + es un conjunto computable de +\series bold +estados +\family typewriter +max +\family default +\series default + (en los que el turno es de +\family typewriter +max +\family default +), cuyo complementario es el conjunto de +\series bold +estados +\family typewriter +min +\family default +\series default + y tal que los sucesores de un estado +\family typewriter +max +\family default + son estados +\family typewriter +min +\family default + y viceversa; +\begin_inset Formula $s\in M$ +\end_inset + + es el estado inicial; +\begin_inset Formula $F\subseteq V$ +\end_inset + + es un conjunto computable de estados finales, y +\begin_inset Formula $u:F\to\mathbb{R}$ +\end_inset + + es una función de utilidad. +\end_layout + +\begin_layout Subsection +Minimax +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Juego $(V,A,M,s,F,u)$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Sucesor $s'$ óptimo.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwProg{Fn}{función}{}{fin} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwFunction{minimax}{minimax} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Fn{ +\backslash +minimax{$n$}}{ +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$n +\backslash +in F$}{ +\backslash +Devolver $u(n)$} +\end_layout + +\begin_layout Plain Layout + + +\backslash +lEnOtroCasoSi{$n +\backslash +in M$}{ +\backslash +Devolver$ +\backslash +max +\backslash +{ +\backslash +minimax{v} +\backslash +}_{(n,v) +\backslash +in A}$} +\end_layout + +\begin_layout Plain Layout + + +\backslash +lEnOtroCaso{ +\backslash +Devolver$ +\backslash +min +\backslash +{ +\backslash +minimax{v} +\backslash +}_{(n,v) +\backslash +in A}$} +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver $s'$ con $(s,s') +\backslash +in A$ y $ +\backslash +minimax{s'}$ máximo +\backslash +; +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:minimax" + +\end_inset + +Algoritmo minimax. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +El +\series bold +minimax +\series default + (algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:minimax" +plural "false" +caps "false" +noprefix "false" + +\end_inset + +) intenta maximizar el valor final de +\begin_inset Formula $u$ +\end_inset + + anticipándose a que el oponente intentará minimizarlo, y es óptimo. + Su complejidad en tiempo es +\begin_inset Formula $O(b^{m})$ +\end_inset + +, y su complejidad en espacio es +\begin_inset Formula $O(bm)$ +\end_inset + + si se generan todos los sucesores de un nodo a la vez u +\begin_inset Formula $O(m)$ +\end_inset + + si se generan uno a uno, donde +\begin_inset Formula $b$ +\end_inset + + es el factor de ramificación y +\begin_inset Formula $m$ +\end_inset + + es la profundidad máxima del árbol de búsqueda. +\end_layout + +\begin_layout Standard +El algoritmo se puede extender a juegos de más de dos jugadores; en este + caso la utilidad sería de la forma +\begin_inset Formula $V\to\mathbb{R}^{n}$ +\end_inset + +, donde +\begin_inset Formula $n$ +\end_inset + + es el número de jugadores y +\begin_inset Formula $u(n_{i})$ +\end_inset + + es el valor objetivo del nodo +\begin_inset Formula $u$ +\end_inset + + para el jugador +\begin_inset Formula $i$ +\end_inset + +, y en vez de +\begin_inset Formula $M$ +\end_inset + + tendríamos una función computable +\begin_inset Formula $J:V\to\{1,\dots,n\}$ +\end_inset + + que indica de quién es el turno y tal que para +\begin_inset Formula $(i,j)\in A$ +\end_inset + +, +\begin_inset Formula $J(j)\equiv J(i)+1\bmod n$ +\end_inset + +. + Entonces, en cada nodo +\begin_inset Formula $u$ +\end_inset + + no terminal, nos quedaríamos con el valor minimax de los sucesores con + coordenada +\begin_inset Formula $J(u)$ +\end_inset + +-ésima máxima, y el algoritmo seguiría siendo óptimo aun cuando el juego + no fuera de suma cero. +\end_layout + +\begin_layout Subsection +Poda alfa-beta +\end_layout + +\begin_layout Standard +Es posible acelerar el algoritmo minimax con +\series bold +poda alfa-beta +\series default + (algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:alpha-beta" +plural "false" +caps "false" +noprefix "false" + +\end_inset + +). + La idea es que +\begin_inset Formula $\alpha$ +\end_inset + + es el mayor valor encontrado para +\family typewriter +max +\family default + y +\begin_inset Formula $\beta$ +\end_inset + + es el menor valor encontrado para +\family typewriter +min +\family default +. + Entonces, si +\family typewriter +MinValor +\family default + encuentra un +\begin_inset Formula $v\leq\alpha$ +\end_inset + +, el valor que devuelva será no mayor a +\begin_inset Formula $\alpha$ +\end_inset + + porque está minimizando, y no merece la pena seguir porque +\family typewriter +MaxValor +\family default +, que llamó a +\family typewriter +MinValor +\family default +, descartaría el valor. + Del mismo modo, si +\family typewriter +MaxValor +\family default + encuentra un +\begin_inset Formula $v\geq\beta$ +\end_inset + +, termina porque su valor de retorno sería descartado por +\family typewriter +MinValor +\family default +. +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Juego $(V,A,M,s,F,u)$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Sucesor $s'$ óptimo.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwProg{Fn}{función}{}{fin} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwFunction{MaxValor}{MaxValor} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwFunction{MinValor}{MinValor} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Fn{ +\backslash +MaxValor{$n, +\backslash +alpha, +\backslash +beta$}}{ +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$n +\backslash +in F$}{ +\backslash +Devolver $n$} +\end_layout + +\begin_layout Plain Layout + + $v +\backslash +gets- +\backslash +infty$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Para{$i:(n,i) +\backslash +in A$}{ +\end_layout + +\begin_layout Plain Layout + + $v +\backslash +gets +\backslash +max +\backslash +{v, +\backslash +MinValor{$i, +\backslash +alpha, +\backslash +beta$} +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$v +\backslash +geq +\backslash +beta$}{ +\backslash +Devolver $i$} +\end_layout + +\begin_layout Plain Layout + + $ +\backslash +alpha +\backslash +gets +\backslash +max +\backslash +{ +\backslash +alpha,v +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver $v$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Fn{ +\backslash +MinValor{$n, +\backslash +alpha, +\backslash +beta$}}{ +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$n +\backslash +in F$}{ +\backslash +Devolver $n$} +\end_layout + +\begin_layout Plain Layout + + $v +\backslash +gets+ +\backslash +infty$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Para{$i:(n,i) +\backslash +in A$}{ +\end_layout + +\begin_layout Plain Layout + + $i +\backslash +gets +\backslash +min +\backslash +{i, +\backslash +MaxValor{$i, +\backslash +alpha, +\backslash +beta$} +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$v +\backslash +leq +\backslash +alpha$}{ +\backslash +Devolver $v$} +\end_layout + +\begin_layout Plain Layout + + $ +\backslash +beta +\backslash +gets +\backslash +min +\backslash +{ +\backslash +beta,v +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver $v$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + +Tomar el sucesor $s'$ de $s$ asociado al resultado de +\backslash +MaxValor{$n,- +\backslash +infty,+ +\backslash +infty$} +\backslash +; +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:alpha-beta" + +\end_inset + +Minimax con poda alfa-beta. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +La eficiencia de minimax con poda alfa-beta es +\begin_inset Formula $O(b^{m/2})$ +\end_inset + + en el caso mejor y +\begin_inset Formula $O(b^{m})$ +\end_inset + + en el caso peor, y la diferencia es muy dependiente del orden en que se + examinan los sucesores de cada nodo. + En el caso medio tenemos +\begin_inset Formula $O(b^{3m/4})$ +\end_inset + +. +\end_layout + +\begin_layout Subsection +Heurísticas +\end_layout + +\begin_layout Standard +Buscar hasta los estados terminales no suele ser práctico porque los movimientos + deben hacerse en una cantidad razonable de tiempo, por lo que se usan heurístic +as +\begin_inset Formula $h:V\to\mathbb{R}$ +\end_inset + + para sustituir a +\begin_inset Formula $u$ +\end_inset + + y un test de corte +\begin_inset Formula $D\subseteq V\times\mathbb{N}$ +\end_inset + + (computable) que decide cuándo parar la búsqueda y aplicar +\begin_inset Formula $h$ +\end_inset + + según el estado y la profundidad. + +\end_layout + +\begin_layout Standard +Una opción es parar a una profundidad fija, elegida para que el tiempo usado + no exceda lo permitido por las reglas del juego. + Un test más sofisticado solo para cuando encuentra una posición suficientemente + estable, en la que sea de esperar que la heurística sea buena. +\end_layout + +\begin_layout Subsection +Juegos estocásticos +\end_layout + +\begin_layout Standard +Muchos juegos incluyen un elemento aleatorio. + Esto se puede modelar como que entre un nivel de nodos +\family typewriter +max +\family default + y uno de nodos +\family typewriter +min +\family default +, y viceversa, hay un nivel de nodos de posibilidad cuyos sucesores son + posibles alternativas, y en minimax, en esos nodos, en vez de tomar el + máximo o el mínimo, tomamos la media ponderada a la probabilidad de cada + suceso. +\end_layout + +\end_body +\end_document diff --git a/si/n5.lyx b/si/n5.lyx new file mode 100644 index 0000000..fe6616b --- /dev/null +++ b/si/n5.lyx @@ -0,0 +1,989 @@ +#LyX 2.3 created this file. For more info see http://www.lyx.org/ +\lyxformat 544 +\begin_document +\begin_header +\save_transient_properties true +\origin unavailable +\textclass book +\begin_preamble +\usepackage{amssymb} +\end_preamble +\use_default_options true +\begin_modules +algorithm2e +\end_modules +\maintain_unincluded_children false +\language spanish +\language_package default +\inputencoding auto +\fontencoding global +\font_roman "default" "default" +\font_sans "default" "default" +\font_typewriter "default" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_osf false +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures true +\graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default +\paperfontsize default +\spacing single +\use_hyperref false +\papersize default +\use_geometry false +\use_package amsmath 1 +\use_package amssymb 1 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 1 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false +\paperorientation portrait +\suppress_date false +\justification true +\use_refstyle 1 +\use_minted 0 +\index Index +\shortcut idx +\color #008000 +\end_index +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style french +\dynamic_quotes 0 +\papercolumns 1 +\papersides 1 +\paperpagestyle default +\tracking_changes false +\output_changes false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\end_header + +\begin_body + +\begin_layout Standard +El +\series bold +conocimiento +\series default + consiste en descripciones declarativas explícitas formadas por conceptos + y relaciones entre los conceptos específicos a un dominio de aplicación, + y en métodos genéricos de resolución de problemas, formados por +\series bold +técnicas de razonamiento +\series default + que usan las relaciones entre conceptos para inferir conclusiones y una + estructura de control para aplicar las técnicas. + Por ejemplo, se puede representar el conocimiento por cláusulas de lógica + de predicados de primer orden, y entonces una técnica de razonamiento es + el principio de resolución. +\end_layout + +\begin_layout Standard +Algunos tipos de conocimiento: +\end_layout + +\begin_layout Itemize + +\series bold +De entidades +\series default +: Propiedades y estructura física de entes del mundo real. +\end_layout + +\begin_layout Itemize + +\series bold +De conducta +\series default +: Comportamiento o forma de proceder de los entes. +\end_layout + +\begin_layout Itemize + +\series bold +De eventos +\series default +: Secuencias de eventos, distribución temporal y relaciones causales. +\end_layout + +\begin_layout Itemize + +\series bold +Procedimental +\series default +: Cómo realizar determinados procesos. +\end_layout + +\begin_layout Itemize + +\series bold +Sobre incertidumbre +\series default +: Nivel de certeza asociada a hechos. +\end_layout + +\begin_layout Itemize + +\series bold +Meta-conocimiento +\series default +: Conocimiento sobre el propio conocimiento, sus propiedades y cómo usarlo. +\end_layout + +\begin_layout Standard +Los sistemas inteligentes son +\series bold +intensivos en datos +\series default + si minan grandes cantidades de datos para obtener conclusiones e +\series bold +intensivos en conocimiento +\series default + ( +\series bold +sistemas basados en conocimiento +\series default +) si aplican gran cantidad de conocimiento a los datos. +\end_layout + +\begin_layout Standard + +\series bold +Diagnosticar +\series default + es encontrar una causa para un comportamiento observado distinto a lo normal, + partiendo de hallazgos normales y anormales y dando uno o más diagnósticos, + puede que ordenados por grado de certeza, que explican los hallazgos anormales + sin contradecir los normales. + Con sistemas basados en conocimiento, esto requiere de las siguientes fases: +\end_layout + +\begin_layout Enumerate + +\series bold +Adquisición +\series default + de conocimiento de alguna fuente, sea un experto o un proceso de prueba + y error mediante técnicas de aprendizaje. +\end_layout + +\begin_layout Enumerate + +\series bold +Conceptualización +\series default + o +\series bold +modelado +\series default +, fase central en la ingeniería del conocimiento, consistente en definir + y organizar los componentes de conocimiento. +\end_layout + +\begin_layout Enumerate + +\series bold +Representación +\series default + o +\series bold +formalización +\series default + del conocimiento en estructuras como cláusulas lógicas o reglas, normalmente + agrupadas en módulos para facilitar su recuperación y poder añadir, modificar + y borrar estructuras de forma independiente del resto. + Puede ser necesario que las estructuras de datos sean comprensibles por + humanos. +\end_layout + +\begin_layout Enumerate + +\series bold +Implementación +\series default + del software con el conocimiento y las técnicas de inferencia. + Las técnicas se suelen implementar de forma imperativa. +\end_layout + +\begin_layout Enumerate + +\series bold +Acceso +\series default + al conocimiento desde la recuperación. + La velocidad de acceso es muy importante cuando hay mucho conocimiento, + es complejo o se requiere funcionamiento en tiempo real. +\end_layout + +\begin_layout Enumerate + +\series bold +Selección +\series default + o +\series bold +recuperación +\series default + de un elemento concreto de conocimiento, adecuado al problema y el estado + del proceso de resolución. + Muchas veces se selecciona un módulo completo, y se usa meta-conocimiento + para elegir el siguiente módulo a cargar. + Si hay varios métodos de resolución, se puede usar meta-conocimiento para + usar el más apropiado. +\end_layout + +\begin_layout Standard +El +\series bold +ámbito +\series default + de una representación de conocimiento es el dominio en que se va a aplicar. + Definir conocimiento genérico es muy costoso, por lo que son más adecuadas + representaciones para contextos restringidos. +\end_layout + +\begin_layout Standard +La +\series bold +granularidad +\series default + es el tamaño de la unidad mínima de representación, +\series bold +gránulo +\series default + o +\series bold +grano +\series default +. + Con un grano grueso, los contenidos de alto nivel se representan de forma + sencilla pero el tratamiento es difícil, mientras que uno fino permite + representar procesos de bajo nivel y construir estructuras jerárquicas + fácilmente pero da problemas para representar conceptos de alto nivel. +\end_layout + +\begin_layout Standard +El conocimiento es +\series bold +redundante +\series default + si se representa el mismo de varias formas, lo que permite una aplicación + más efectiva porque algunas formas de conocimiento son más adecuadas para + ciertos casos que otras pero aumenta el volumen de datos. +\end_layout + +\begin_layout Section +Sistemas basados en reglas +\end_layout + +\begin_layout Standard +Un +\series bold +sistema basado en reglas +\series default + o +\series bold +sistema experto +\series default + es un sistema basado en conocimiento que usa reglas de la forma +\begin_inset Quotes cld +\end_inset + +si +\emph on +condición +\emph default + entonces +\emph on +acción +\emph default + +\begin_inset Quotes crd +\end_inset + +, dadas por un +\series bold +antecedente +\series default + o +\series bold +condición +\series default + formado por una lista de cláusulas a verificar y un +\series bold +consecuente +\series default + o +\series bold +acción +\series default + formado por una lista de acciones a ejecutar cuando se cumplen las condiciones. + Consta de: +\end_layout + +\begin_layout Itemize +Una +\series bold +base de hechos +\series default + o +\series bold +memoria de trabajo +\series default + con hechos conocidos de una situación particular. + Los hechos son: +\end_layout + +\begin_deeper +\begin_layout Itemize +De entrada, introducidos por el usuario u obtenidos de fuentes como sensores + o bases de datos, iniciales o introducidos durante el proceso conforme + se obtienen. +\end_layout + +\begin_layout Itemize +Inferidos por el sistema durante el proceso. +\end_layout + +\begin_layout Itemize +Los objetivos y subobjetivos a alcanzar. +\end_layout + +\end_deeper +\begin_layout Itemize +Una +\series bold +base de conocimiento +\series default + con las reglas del dominio. + La ejecución de una acción puede modificar de la base de hechos, normalmente + añadiendo hechos inferidos. +\end_layout + +\begin_deeper +\begin_layout Standard +Una +\series bold +red de inferencia +\series default + es una representación gráfica de una red de conocimiento de forma similar + a un grafo. + Las reglas se dibujan como puertas lógicas en función de cómo tengan que + combinarse los antecedentes para que la regla sea aplicable. + +\end_layout + +\begin_layout Standard +Un hecho que sea se representa como una flecha que va hacia la entrada de + las reglas que lo tengan como antecedente, posiblemente dividiéndose en + el camino. + Si el hecho es resultado del consecuente de una única regla, la flecha + parte del consecuente; si lo es de varias reglas, parte de un rectángulo + y se dibujan flechas de dichas reglas al rectángulo, y si no lo es de ninguna + regla, parte de la nada. + +\end_layout + +\begin_layout Standard +Generalmente las flechas se dibujan de izquierda a derecha, con los hechos + de partida a la izquierda y las metas a la derecha. + Los hechos y las reglas pueden etiquetarse. +\end_layout + +\end_deeper +\begin_layout Itemize +Un +\series bold +mecanismo +\series default + o +\series bold +motor de inferencias +\series default + que selecciona reglas aplicables para obtener alguna conclusión. +\end_layout + +\begin_layout Standard +Los sistemas expertos son importantes en escenarios gobernados por reglas + deterministas, y sobre todo en los que escasean expertos humanos, porque + permiten capturar la experiencia humana de forma natural. + Las reglas indican implicación causal, pero se les aplica razonamiento + deductivo basado en +\emph on +\lang latin +modus ponens +\emph default +\lang spanish +. +\end_layout + +\begin_layout Standard + +\series bold +Equiparar +\series default + es buscar un conjunto, el +\series bold +conjunto conflicto +\series default +, de reglas de la base de conocimiento, las reglas +\series bold +aplicables +\series default + o +\series bold +activadas +\series default +, cuyas condiciones o acciones sean compatibles con los datos almacenados. + +\series bold +Resolver +\series default + es seleccionar una regla del conjunto conflicto. + Así, mientras la base de hechos no haya alcanzado una condición de finalización +, normalmente alcanzar un hecho meta, y no se haya ejecutado una acción + de parada, el motor de inferencias equipara, resuelve y ejecuta la regla + elegida, actualizando la base de hechos con los hechos resultantes de aplicar + la regla. +\end_layout + +\begin_layout Standard +El motor de inferencias usa +\series bold +encadenamiento hacia delante +\series default + o +\series bold +dirigido por datos +\series default + si parte de los hechos conocidos y busca qué metas se verifican a partir + de estos, equiparando hechos con antecedentes de reglas, y usa +\series bold +encadenamiento hacia atrás +\series default + o +\series bold +dirigido por metas +\series default + si parte de la meta dada y comprueba si se deduce de los hechos creando + subobjetivos, equiparando metas con consecuentes de reglas. + +\end_layout + +\begin_layout Standard +Equiparar no siempre es trivial, pues las reglas pueden ser generales y + por ejemplo contener variables. + Además, examinar todas las reglas en cada ciclo es costoso si la base de + conocimiento es grande, por lo que se indizan las reglas y se usan técnicas + que evitan examinar todo el conocimiento. + El +\series bold +algoritmo RETE +\series default +, usado en las herramientas Jess y DROOLS, busca patrones en reglas y construye + un grafo para acelerar la equiparación de reglas al usar encadenamiento + hacia delante. +\end_layout + +\begin_layout Standard +Un +\series bold +método de resolución de conflictos +\series default + elige qué regla aplicar del conjunto conflicto, y de este depende el tiempo + de respuesta del sistema ante cambios del entorno y la posibilidad de ejecutar + secuencias de acciones relativamente largas. + Estos métodos pueden ser: +\end_layout + +\begin_layout Itemize + +\series bold +Estáticos +\series default +, basados solo en la base de conocimiento, como seleccionar las reglas ordenadas + por un criterio como su número de antecedentes. +\end_layout + +\begin_layout Itemize + +\series bold +Dinámicos +\series default +, como elegir las reglas que usan elementos más recientes de la base de + hechos o reglas no usadas previamente. +\end_layout + +\begin_layout Standard +Los sistemas expertos son de grano fino, modulares, uniformes, simples y + aplicables a muchos ámbitos. + Separan estrictamente la representación del conocimiento, declarativa, + de la técnica de razonamiento, y los razonamientos son relativamente comprensib +les por humanos, aunque su baja granularidad dificulta entender posibles + superestructuras cuando hay muchas reglas. + Es fácil extenderlos para que incluyan meta-conocimiento mediante meta-reglas, + y conocimiento sobre incertidumbre. +\end_layout + +\begin_layout Section +Lógicas no clásicas +\end_layout + +\begin_layout Standard +Una +\series bold +lógica +\series default + es un lenguaje de +\series bold +proposiciones +\series default + junto con un conjunto de +\series bold +reglas de inferencia +\series default + que transforman unas proposiciones en otras. + Una +\series bold +teoría +\series default + es un conjunto de proposiciones o +\series bold +axiomas +\series default + en el contexto de una lógica, y todas las proposiciones que se puedan obtener + de esta por aplicación de reglas de inferencia de la lógica, incluyendo + los propios axiomas, son sus +\series bold +teoremas +\series default +. + Escribimos +\begin_inset Formula ${\cal T}\vdash P$ +\end_inset + + si +\begin_inset Formula $P$ +\end_inset + + es un teorema de la teoría +\begin_inset Formula ${\cal T}$ +\end_inset + +. + Las lógicas suelen incluir una semántica +\begin_inset Quotes cld +\end_inset + +genérica +\begin_inset Quotes crd +\end_inset + + para las proposiciones que las teorías completan. +\end_layout + +\begin_layout Standard +Una lógica es +\series bold +monótona +\series default + si siempre que +\begin_inset Formula ${\cal T}\vdash P$ +\end_inset + + y +\begin_inset Formula ${\cal T}'$ +\end_inset + + sea una teoría cuyos axiomas incluyan los de +\begin_inset Formula ${\cal T}$ +\end_inset + +, se tiene +\begin_inset Formula ${\cal T}'\vdash P$ +\end_inset + +. + Las lógicas clásicas son monótonas, pero la monotonía no es apropiada cuando + el conocimiento es incompleto, pues puede que haya que hacer suposiciones + por defecto que puedan invalidarse cuando se tenga más conocimiento, ni + cuando el mundo es cambiante. +\end_layout + +\begin_layout Standard +Las lógicas clásicas no son apropiadas para tratar conocimiento incompleto, + incierto, impreciso o inconsistente, y los algoritmos para manipular conocimien +to lógico son ineficientes, por lo que se crean otras lógicas más apropiadas. +\end_layout + +\begin_layout Subsection +Lógica de situaciones +\end_layout + +\begin_layout Standard +Introducida por McCarthy en 1969. + Como la lógica de predicados de primer orden pero todos los predicados + tienen un argumento extra que indica en qué situación la fórmula es cierta, + pues una fórmula puede pasar a ser falsa tras un cambio. + Existe una función +\begin_inset Formula $R/2$ +\end_inset + + de modo que +\begin_inset Formula $R(e,s)$ +\end_inset + + es la situación resultante de que ocurra el evento +\begin_inset Formula $e$ +\end_inset + + en la situación +\begin_inset Formula $s$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Al crear el modelo, hay que indicar qué proposiciones simples se siguen + cumpliendo al aplicar un cambio a la situación. +\end_layout + +\begin_layout Subsection +Lógica difusa +\end_layout + +\begin_layout Standard +En lógica de predicados, a todo predicado +\begin_inset Formula $P$ +\end_inset + + sobre un dominio +\begin_inset Formula $U$ +\end_inset + + le corresponde un conjunto +\begin_inset Formula $\{x\in U:P(x)\}$ +\end_inset + + y una +\series bold +función de pertenencia +\series default + +\begin_inset Formula $f:U\to\{0,1\}$ +\end_inset + + dada por +\begin_inset Formula +\[ +f(x):=\begin{cases} +1, & P(x);\\ +0, & \neg P(x); +\end{cases} +\] + +\end_inset + +distinguiendo entre predicados ciertos y falsos. + En lógica difusa usamos +\series bold +predicados vagos +\series default +, de modo que a un predicado +\begin_inset Formula $P$ +\end_inset + + sobre un dominio +\begin_inset Formula $U$ +\end_inset + + le corresponde un +\series bold +conjunto difuso +\series default + y una función de pertenencia +\begin_inset Formula $f:U\to[0,1]$ +\end_inset + +. + La lógica clásica y la teoría de conjuntos difusos nos permiten razonar + con afirmaciones vagas con palabras como +\begin_inset Quotes cld +\end_inset + +joven +\begin_inset Quotes crd +\end_inset + +, +\begin_inset Quotes cld +\end_inset + +alto +\begin_inset Quotes crd +\end_inset + +, +\begin_inset Quotes cld +\end_inset + +muy +\begin_inset Quotes crd +\end_inset + +, +\begin_inset Quotes cld +\end_inset + +muchos +\begin_inset Quotes crd +\end_inset + +, +\begin_inset Quotes cld +\end_inset + +bastantes +\begin_inset Quotes crd +\end_inset + +, +\begin_inset Quotes cld +\end_inset + +pocos +\begin_inset Quotes crd +\end_inset + +, etc., pues de otra forma tendríamos inconsistencias. +\end_layout + +\begin_layout Subsection +Factores de certeza +\end_layout + +\begin_layout Standard +Para razonar con hechos con fiabilidad o precisión limitada o sobre los + que no estamos seguros, se suele incorporar la incertidumbre a una lógica + que no la incluye. + Esto se suele hacer con probabilidades y redes bayesianas, basadas probabilidad + condicionada e independencia de sucesos. +\end_layout + +\begin_layout Standard +A finales de los 70 se crea Mycin, un sistema basado en reglas usado para + identificar la bacteria causante de una infección y seleccionar un tratamiento + basándose en datos clínicos y encadenamiento hacia atrás. + Por entonces no se habían inventado las redes bayesianas y era difícil + obtener valores objetivos para las probabilidades, por lo que se usaron + factores de certeza obtenidos de estimaciones subjetivas. +\end_layout + +\begin_layout Standard +El +\series bold +factor de certeza +\series default + de una +\series bold +hipótesis +\series default + +\begin_inset Formula $h$ +\end_inset + + según una +\series bold +evidencia +\series default + +\begin_inset Formula $e$ +\end_inset + +, +\begin_inset Formula $\text{FC}(h,e)$ +\end_inset + + es la diferencia de una +\series bold +medida de creencia +\series default +, un número en +\begin_inset Formula $[0,1]$ +\end_inset + + que indica en qué grado +\begin_inset Formula $e$ +\end_inset + + apoya +\begin_inset Formula $h$ +\end_inset + +, y una +\series bold +medida de incredulidad +\series default +, un número en +\begin_inset Formula $[0,1]$ +\end_inset + + que indica en qué grado +\begin_inset Formula $e$ +\end_inset + + apoya +\begin_inset Formula $\neg h$ +\end_inset + +. + Las medidas de creencia e incredulidad no pueden ser positivas a la vez, + por lo que +\begin_inset Formula $\text{FC}(h,e)\in[-1,1]$ +\end_inset + + es suficiente para despejar ambas. +\end_layout + +\begin_layout Standard +El antecedente de una regla es una conjunción o disyunción de proposiciones + atómicas en lógica preposicional y el consecuente es una proposición atómica. + Las funciones de combinación deben ser conmutativas y asociativas, pues + el orden en que se obtienen las evidencias es arbitrario; el resultado + de encadenar inferencias debe tener menor certeza que cada inferencia individua +l, y si una evidencia adicional confirma una hipótesis, su factor de creencia + debe aumentar. + +\end_layout + +\begin_layout Standard +Con esto, cada regla +\begin_inset Formula $h\to e$ +\end_inset + + lleva un factor de certeza asociado +\begin_inset Formula $\text{FC}(h,e)$ +\end_inset + +, cada hipótesis +\begin_inset Formula $h$ +\end_inset + + en la base de hechos lleva un factor de certeza +\begin_inset Formula $\text{FC}(h,\bot)$ +\end_inset + +, donde +\begin_inset Formula $\bot$ +\end_inset + + es la situación particular, y las reglas son: +\begin_inset Foot +status open + +\begin_layout Plain Layout +En las diapositivas, las dos primeras reglas aparecen como +\begin_inset Formula $\text{FC}(h,e_{1}\land e_{2})=\min\{\text{FC}(h,e_{1}),\text{FC}(h,e_{2})\}$ +\end_inset + + y +\begin_inset Formula $\text{FC}(h,e_{1}\lor e_{2})=\max\{\text{FC}(h,e_{1}),\text{FC}(h,e_{2})\}$ +\end_inset + +, pero esto tendría menos sentido aún que las reglas que realmente usamos, + que son las que se muestran. +\end_layout + +\end_inset + + +\begin_inset Formula +\begin{align*} +\text{FC}(h_{1}\land h_{2},e) & =\min\{\text{FC}(h_{1},e),\text{FC}(h_{2},e)\},\\ +\text{FC}(h_{1}\lor h_{2},e) & =\max\{\text{FC}(h_{1},e),\text{FC}(h_{2},e)\},\\ +\text{FC}(h,e) & =\text{FC}(h,s)\max\{0,\text{FC}(s,e)\},\\ +\text{FC}(h,e_{1}\land e_{2}) & =\begin{cases} +\text{FC}(h,e_{1})+\text{FC}(h,e_{2})-\text{FC}(h,e_{1})\text{FC}(h,e_{2}), & \text{FC}(h,e_{1}),\text{FC}(h,e_{2})\geq0;\\ +\text{FC}(h,e_{1})+\text{FC}(h,e_{2})+\text{FC}(h,e_{1})\text{FC}(h,e_{2}), & \text{FC}(h,e_{1}),\text{FC}(h,e_{2})\leq0;\\ +\frac{\text{FC}(h,e_{1})+\text{FC}(h,e_{2})}{1-\min\{|\text{FC}(h,e_{1})|,|\text{FC}(h,e_{2})|\}}, & \text{FC}(h,e_{1})\text{FC}(h,e_{2})\leq0. +\end{cases} +\end{align*} + +\end_inset + +Las dos primeras se usan para evaluar el factor de certeza de antecedentes + de reglas; la tercera para obtener el factor de certeza del consecuente + de una regla sabiendo el de su antecedente y la cuarta para combinar factores + de certeza obtenidos por distintas reglas. +\end_layout + +\begin_layout Section +Representaciones estructuradas del conocimiento +\end_layout + +\begin_layout Standard +Las +\series bold +redes semánticas +\series default +, inventadas por Quillian en 1961, se basan en grafos para modelar la capacidad + de la memoria humana de recuperar conceptos a través de las relaciones + que los enlazan. + Los +\series bold +marcos +\series default + o +\series bold +\emph on +\lang english +frames +\series default +\emph default +\lang spanish +, inventados por Minsky en 1975, se basan en estructuras parecidas a formularios + y permiten hacer inferencias basadas en herencia. +\end_layout + +\begin_layout Standard +En los años 90, en ingeniería del conocimiento se adoptan las +\series bold +ontologías +\series default +, especificaciones formales explícitas de conceptos organizados en forma + jerárquica para servir de soporte a aplicaciones que requieren conocimiento + específico sobre una materia concreta. + En la segunda mitad de los 90, estas se aplican a la web para añadir descripcio +nes semánticas a los contenidos, creándose la +\series bold +web semántica +\series default +. +\end_layout + +\end_body +\end_document diff --git a/si/n6.lyx b/si/n6.lyx new file mode 100644 index 0000000..b4b3e21 --- /dev/null +++ b/si/n6.lyx @@ -0,0 +1,620 @@ +#LyX 2.3 created this file. For more info see http://www.lyx.org/ +\lyxformat 544 +\begin_document +\begin_header +\save_transient_properties true +\origin unavailable +\textclass book +\begin_preamble +\usepackage{amssymb} +\end_preamble +\use_default_options true +\begin_modules +algorithm2e +\end_modules +\maintain_unincluded_children false +\language spanish +\language_package default +\inputencoding auto +\fontencoding global +\font_roman "default" "default" +\font_sans "default" "default" +\font_typewriter "default" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_osf false +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures true +\graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default +\paperfontsize default +\spacing single +\use_hyperref false +\papersize default +\use_geometry false +\use_package amsmath 1 +\use_package amssymb 1 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 1 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false +\paperorientation portrait +\suppress_date false +\justification true +\use_refstyle 1 +\use_minted 0 +\index Index +\shortcut idx +\color #008000 +\end_index +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style french +\dynamic_quotes 0 +\papercolumns 1 +\papersides 1 +\paperpagestyle default +\tracking_changes false +\output_changes false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\end_header + +\begin_body + +\begin_layout Standard + +\series bold +Planificar +\series default + es obtener una secuencia de acciones para llegar a un estado objetivo. + Esto se puede hacer con técnicas de búsqueda, pero el espacio de búsqueda + suele ser muy complejo, los problemas no suelen ser descomponibles y los + estados de búsqueda suelen ser complejos porque requieren buena parte del + entorno, por lo que se suelen usar algoritmos específicos. + +\end_layout + +\begin_layout Standard +El +\series bold +problema del marco +\series default + o +\series bold +de la estructura +\series default + ( +\emph on +\lang english +frame problem +\emph default +\lang spanish +) es el de qué permanece sin cambios al aplicar una regla; el de la +\series bold +cualificación +\series default + es qué necesita la regla que se cumpla para poder ejecutable, y el de la + +\series bold +ramificación +\series default + es qué elementos cambian. +\end_layout + +\begin_layout Standard +Un +\series bold +plan lineal +\series default + es una secuencia de acciones para ir de un estado inicial a un estado objetivo, + y un +\series bold +plan no lineal +\series default + es una familia de acciones con un orden parcial de forma que cada secuenciación + de esas acciones que respete el orden parcial es un plan lineal. +\end_layout + +\begin_layout Section +STRIPS +\end_layout + +\begin_layout Standard + +\series bold +STRIPS +\series default + ( +\emph on +\lang english +Stanford Research Institute Problem Solver +\emph default +\lang spanish +) es un planificador lineal o +\series bold +de orden total +\series default + que usa una forma restringida de lógica de situaciones. + Los problemas están formados por un estado inicial, un estado objetivo + y un conjunto de acciones, y los literales o proposiciones atómicas que + aparecen no tienen variables resultado de funciones. +\end_layout + +\begin_layout Standard +Los estados inicial e intermedios son conjunciones de literales sin variables, + y los estados objetivo y subobjetivos son conjunciones de literales en + las que todas las variables se cuantifican existencialmente con ámbito + global en la proposición. +\end_layout + +\begin_layout Standard +Un +\series bold +unificador +\series default + entre dos fórmulas lógicas que no comparten variables libres es una asociación + de variables a valores tal que, al aplicarla por sustitución a las variables + libres de las dos fórmulas, queda la misma fórmula. + Si existe, las dos fórmulas +\series bold +unifican +\series default +. +\end_layout + +\begin_layout Standard +Las acciones están formadas por: +\end_layout + +\begin_layout Itemize +Un +\series bold +antecedente +\series default + o +\series bold +fórmula de precondición +\series default +, una conjunción de proposiciones atómicas en que las variables (libres) + se entienden cuantificadas existencialmente, y que indica cuándo se puede + aplicar la regla. + Para que la regla sea aplicable a un estado, debe existir un +\series bold +unificador más general +\series default + de la fórmula a la conjunción de un subconjunto de los literales en el + estado, que se puede obtener creando unificadores de literales y viendo + que sean consistentes. +\end_layout + +\begin_layout Itemize +Una +\series bold +lista de supresión +\series default +, una lista de literales cuyas variables deben aparecer en el antecedente + y que, al aplicar la regla, dejan de ser ciertos. +\end_layout + +\begin_layout Itemize +Una +\series bold +fórmula de adición +\series default +, una lista de literales cuyas variables deben aparecer en el antecedente + y que, al aplicar la regla, se hacen ciertos. +\end_layout + +\begin_layout Section +Búsqueda +\end_layout + +\begin_layout Standard +Lo más sencillo es obtener un plan lineal con técnicas de búsqueda ya conocidas, + pero como las descripciones de acciones indican tanto precondiciones como + efectos, la búsqueda se puede hacer hacia delante, del estado inicial hasta + un objetivo, o hacia atrás, del objetivo al estado inicial. +\end_layout + +\begin_layout Standard +En el caso de reglas tipo STRIPS, aplicar una regla hacia atrás genera un + subobjetivo. + Para obtenerlo, unificamos un subconjunto de los literales del objetivo + con la fórmula de adición, aplicamos el unificador a todo el objetivo y + la regla y tomamos la conjunción de la fórmula de precondición de la regla + con la regresión de los literales del objetivo que no aparecen en el subconjunt +o unificado. + La +\series bold +regresión +\series default + de un literal es Falso si el literal aparece en la lista de supresión, + Cierto si aparece en la de adición y el propio literal en otro caso. +\end_layout + +\begin_layout Standard +El espacio de subobjetivos es más amplio que el espacio de estados obtenido + de aplicar las reglas hacia delante, pero el literal Cierto se puede obviar + y se pueden podar los subobjetivos que contienen Falso o que es fácil ver + en el contexto que son imposibles. +\end_layout + +\begin_layout Standard +La búsqueda exhaustiva no es práctica, por lo que se deben usar heurísticas. +\end_layout + +\begin_layout Section +Pila de objetivos +\end_layout + +\begin_layout Standard +STRIPS usa una planificación lineal mediante una pila de subobjetivos con + el algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:strips" +plural "false" +caps "false" +noprefix "false" + +\end_inset + +, que puede usar heurísticas para ordenar los literales de un objetivo compuesto + al apilarlos y para elegir qué unificador usar y qué regla elegir para + un objetivo simple. + Se pueden obtener planes subóptimos por una mala ordenación de los objetivos. +\begin_inset Foot +status open + +\begin_layout Plain Layout +De hecho, en algunos problemas una mala ordenación puede evitar encontrar + una solución. +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Estado inicial $s$, estado objetivo $o$ y conjunto de reglas $R$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Camino $P$ de $s$ a $f$.} +\end_layout + +\begin_layout Plain Layout + +$P +\backslash +gets(s)$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +$S +\backslash +gets(o)$% +\end_layout + +\begin_layout Plain Layout + + +\backslash +tcp*{{ +\backslash +rm $S$ es la pila de objetivos, que también contiene reglas.}} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Mientras{$S +\backslash +neq +\backslash +emptyset$}{ +\end_layout + +\begin_layout Plain Layout + + Extraer el último $p$ de $S$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +uSSi{$p$ es una regla aplicable a $s$}{ +\end_layout + +\begin_layout Plain Layout + + Aplicar $p$ a $s$ obteniendo un nuevo $s$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $P +\backslash +gets Pps$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\backslash +uEnOtroCasoSi{$p$ unifica con $s$ por algún $U$}{ +\end_layout + +\begin_layout Plain Layout + + Aplicar $U$ a todos los elementos de $S$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\backslash +uEnOtroCasoSi{$p=:l_1 +\backslash +land +\backslash +dots +\backslash +land l_n$ con $n +\backslash +geq2$}{ +\end_layout + +\begin_layout Plain Layout + + $S +\backslash +gets Spl_1 +\backslash +cdots l_n$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\backslash +uEnOtroCaso{ +\end_layout + +\begin_layout Plain Layout + + Elegir $r +\backslash +in R$ cuya fórmula de adición unifique con $p$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + Sea $l_1 +\backslash +land +\backslash +dots +\backslash +land l_n$ la precondición de $r$ unificada, +\end_layout + +\begin_layout Plain Layout + + $S +\backslash +gets Srl_1 +\backslash +cdots l_n$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:strips" + +\end_inset + +Método de planificación de STRIPS. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Planificación de orden parcial +\end_layout + +\begin_layout Standard +La planificación no lineal o +\series bold +de orden parcial +\series default + se basa en descomponer el problema y trabajar en varios subobjetivos independie +ntemente y creando un plan a partir de ellos. + Suele haber acciones ficticias inicio y final. + La +\series bold +planificación de compromiso mínimo +\series default + es la idea de tomar solo las acciones y unificaciones estrictamente necesarias. +\end_layout + +\begin_layout Standard +Aunque podemos representar un plan con un diagrama de grafo de orden parcial, + también podemos hacerlo como sigue: dibujamos todas las acciones a realizar + con un círculo, conectado por debajo a los literales de la precondición + y por encima a los de la lista de adición, representados por un cuadrado, + y en particular inicio tiene como lista de adición las condiciones iniciales + y fin tiene como precondiciones los literales del objetivo unificados. + +\end_layout + +\begin_layout Standard +Cuando una acción +\begin_inset Formula $A$ +\end_inset + + va antes que otra +\begin_inset Formula $B$ +\end_inset + +, en general conectamos cada precondición de +\begin_inset Formula $B$ +\end_inset + + con una adición igual de +\begin_inset Formula $A$ +\end_inset + + o de otro ancestro que no aparezca en la lista de supresión de otra acción + posterior en el camino, pero si el motivo que vaya antes es que +\begin_inset Formula $B$ +\end_inset + + suprime una precondición de +\begin_inset Formula $A$ +\end_inset + +, se dibuja una flecha de +\begin_inset Formula $A$ +\end_inset + + a la precondición de +\begin_inset Formula $B$ +\end_inset + + que suprime, llamada +\series bold +arco amenaza +\series default +. +\end_layout + +\begin_layout Standard +Son planificadores no lineales NOAH, MOLGEN y SIPE. +\end_layout + +\begin_layout Section +Planificación jerárquica +\end_layout + +\begin_layout Standard +Consiste en dividir el problema en niveles de complejidad, de forma que + se crea un plan de alto nivel y cada acción del plan se ejecuta con las + acciones de un plan del nivel inferior, hasta llegar a un nivel suficiente + de detalle. + Esto permite resolver problemas complejos en los que no es posible hacer + una búsqueda completa. + +\series bold +ABSTRIPS +\series default + ( +\emph on +\lang english +Abstraction-Based STRIPS +\emph default +\lang spanish +) es un planificador jerárquico creado por Earl D. + Sacerdoti en 1973. +\end_layout + +\begin_layout Standard +El +\series bold +valor crítico +\series default + de una precondición es una medida de la dificultad de satisfacerla, como + por ejemplo el número de acciones que satisfacen la precondición. + En cada nivel de la jerarquía se tratan precondiciones con igual valor + crítico, empezando con un plan que considera las precondiciones de mayor + valor crítico dando por satisfechas las demás. + Si hay problemas, volvemos al nivel anterior para buscar otro plan. +\end_layout + +\end_body +\end_document diff --git a/si/n7.lyx b/si/n7.lyx new file mode 100644 index 0000000..90829cc --- /dev/null +++ b/si/n7.lyx @@ -0,0 +1,776 @@ +#LyX 2.3 created this file. For more info see http://www.lyx.org/ +\lyxformat 544 +\begin_document +\begin_header +\save_transient_properties true +\origin unavailable +\textclass book +\begin_preamble +\usepackage{amssymb} +\end_preamble +\use_default_options true +\begin_modules +algorithm2e +\end_modules +\maintain_unincluded_children false +\language spanish +\language_package default +\inputencoding auto +\fontencoding global +\font_roman "default" "default" +\font_sans "default" "default" +\font_typewriter "default" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_osf false +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures true +\graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default +\paperfontsize default +\spacing single +\use_hyperref false +\papersize default +\use_geometry false +\use_package amsmath 1 +\use_package amssymb 1 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 1 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false +\paperorientation portrait +\suppress_date false +\justification true +\use_refstyle 1 +\use_minted 0 +\index Index +\shortcut idx +\color #008000 +\end_index +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style french +\dynamic_quotes 0 +\papercolumns 1 +\papersides 1 +\paperpagestyle default +\tracking_changes false +\output_changes false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\end_header + +\begin_body + +\begin_layout Standard +El +\series bold +aprendizaje +\series default + es el cambio adaptativo del comportamiento de un organismo resultante de + su interacción con el medio, y es un aspecto esencial de la inteligencia. + Permite implementar tareas que solo podemos describir bien mediante ejemplos, + hallar correlaciones entre grandes cantidades de datos, mejorar automáticamente + el diseño de un sistema con el tiempo, usar grandes cantidades de conocimiento + que sobrepasan la capacidad de codificación por un humano, adaptar el programa + a cambios en el entorno y actualizar automáticamente el conocimiento del + programa. +\end_layout + +\begin_layout Standard +El aprendizaje ocurre con una fase de entrenamiento, en la que el programa + adquiere experiencia con ejemplos etiquetados si el aprendizaje es +\series bold +supervisado +\series default + o con observaciones del entorno si no lo es, y una fase de prueba, en la + que se comprueba que el programa +\series bold +clasifica +\series default + los nuevos ejemplos o +\series bold +predice +\series default + su solución correctamente (da un resultado correcto). +\end_layout + +\begin_layout Standard +La +\series bold +precisión +\series default + es la fiabilidad del modelo aprendido, medida normalmente por la proporción + de ejemplos clasificados correctamente, aunque a veces es preferible sacrificar + precisión por velocidad de predicción, por ejemplo en detección de errores + en cadenas de producción. +\end_layout + +\begin_layout Standard +Si el modelo lo usa un humano, el razonamiento debe ser fácil de entender + para evitar errores. + También es importante reducir el tiempo de aprendizaje y el número de observaci +ones necesarias. +\end_layout + +\begin_layout Section +Estimación del error +\end_layout + +\begin_layout Standard +El +\series bold +estimador del error en los ejemplos +\series default + es la proporción de ejemplos de la prueba clasificados incorrectamente, + y es un buen estimador si los ejemplos de prueba no se usaron en el entrenamien +to. + El +\series bold +error de resustitución +\series default + es el estimador del error poniendo como ejemplos los mismos datos que en + el entrenamiento, y es una aproximación optimista al error real. +\end_layout + +\begin_layout Standard +La estimación del error por +\series bold +validación cruzada +\series default + mide el error de un método, no de un modelo concreto, y se aplica cuando + los datos son escasos. + El conjunto de ejemplos +\begin_inset Formula $S$ +\end_inset + + se particiona en trozos +\begin_inset Formula $S_{1},\dots,S_{v}$ +\end_inset + + de tamaño semejante, y para cada +\begin_inset Formula $i\in\{1,\dots,v\}$ +\end_inset + +, se construye un modelo sobre +\begin_inset Formula $S\setminus S_{i}$ +\end_inset + + y se calcula su error estimador de los ejemplos +\begin_inset Formula $R_{i}$ +\end_inset + + usando el conjunto de prueba +\begin_inset Formula $S_{i}$ +\end_inset + +. + El error de validación cruzada es +\begin_inset Formula $\sum_{i=1}^{v}\frac{|S_{i}|}{|S|}R_{i}$ +\end_inset + +. + Un buen valor de +\begin_inset Formula $v$ +\end_inset + + es 10, y entonces el método se llama +\series bold +\emph on +\lang english +10-fold cross-validation +\series default +\emph default +\lang spanish +. + Otro caso es el +\series bold +\emph on +\lang english +leave-one-out +\series default +\emph default +\lang spanish +, en el que +\begin_inset Formula $S$ +\end_inset + + se particiona en +\begin_inset Formula $|S|$ +\end_inset + + trozos de un elemento. + Solo se usa cuando +\begin_inset Formula $S$ +\end_inset + + es pequeño, pues es computacionalmente costoso. +\end_layout + +\begin_layout Standard +A veces algunos errores son más costosos que otros; por ejemplo es más costoso + un falso negativo de una enfermedad que un falso positivo. + Si el problema es clasificar ejemplos en +\begin_inset Formula $n$ +\end_inset + + categorías, una +\series bold +matriz de confusión +\series default + es una matriz +\begin_inset Formula $A\in{\cal M}_{n}(\mathbb{N})$ +\end_inset + + en la que +\begin_inset Formula $a_{ij}$ +\end_inset + + es el número de ejemplos de clase +\begin_inset Formula $i$ +\end_inset + + que fueron clasificados como de clase +\begin_inset Formula $j$ +\end_inset + +, y una +\series bold +matriz de costos +\series default + es una matriz +\begin_inset Formula $C\in{\cal M}_{n}(\mathbb{R})$ +\end_inset + + en la que +\begin_inset Formula $c_{ij}$ +\end_inset + + es el coste de clasificar un ejemplo de clase +\begin_inset Formula $i$ +\end_inset + + como de clase +\begin_inset Formula $j$ +\end_inset + +, y que por tanto tiene diagonal nula. + Entonces el estimador de coste de una mala clasificación es +\begin_inset Formula +\[ +\sum_{i=1}^{n}\sum_{\begin{subarray}{c} +j=1\\ +j\neq i +\end{subarray}}^{n}a_{ij}c_{ij}. +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +Cuando el rango de soluciones es numérico y continuo, un buen estimador + es el +\series bold +error cuadrático medio +\series default + ( +\series bold +MSE +\series default +, +\emph on +\lang english +Mean Squared Error +\emph default +\lang spanish +), que con +\begin_inset Formula $n$ +\end_inset + + ejemplos con soluciones +\begin_inset Formula $x_{1},\dots,x_{n}$ +\end_inset + + para los que el programa da soluciones respectivas +\begin_inset Formula $y_{1},\dots,y_{n}$ +\end_inset + + es +\begin_inset Formula +\[ +\frac{1}{n}\sum_{i=1}^{n}(x_{i}-y_{i})^{2}. +\] + +\end_inset + + +\end_layout + +\begin_layout Section +Aprendizaje memorístico +\end_layout + +\begin_layout Standard +Es una técnica consistente en almacenar todo es conocimiento nuevo para + usarlo cuando se encuentre un caso similar, y puede estar integrada en + un sistema de aprendizaje más complejo. +\end_layout + +\begin_layout Standard +Es adecuada cuando es más conveniente almacenar los datos que re-calcular. + En particular el acceso debe ser rápido, lo que requiere indizado. + No es adecuada cuando el entorno cambia rápidamente y lo almacenado puede + quedar fácilmente desfasado. +\end_layout + +\begin_layout Standard +Se puede decidir si almacenar o no cada vez que llega nueva información + o almacenar todo y después olvidar lo que se usa menos. +\end_layout + +\begin_layout Section +Resolución de problemas +\end_layout + +\begin_layout Standard +Un programa para resolver problemas puede recordar la estructura del programa + que ha resuelto, los métodos usados para resolverlo y su solución, generalizar + la experiencia y usarla para resolver problemas similares. +\end_layout + +\begin_layout Standard +El primer programa en hacer esto fue STRIPS, que tras cada episodio de planifica +ción tomaba el plan calculado o una parte y lo transformaba en un +\series bold +macro-operador +\series default +, una secuencia de acciones abstracta encapsulada en un +\series bold +operador +\series default + o acción para su uso posterior como una acción normal. +\end_layout + +\begin_layout Standard +Como es raro que se de un mismo problema dos veces, el macro-operador debe + generalizarse, cambiando constantes por variables siempre que se pueda. + STRIPS sustituye todas las constantes por variables y después re-evalúa + las precondiciones de cada operador usado para unificar y convertir variables + en constantes si es necesario. + Los buenos macro-operadores son muy útiles, y pueden producir un pequeño + cambio local en el mundo aunque los operadores que lo forman produzcan + muchos cambios locales. +\end_layout + +\begin_layout Section +Reglas de asociación +\end_layout + +\begin_layout Standard +Las +\series bold +reglas de asociación +\series default + relacionan los elementos que pueden aparecer en una base de datos, y son + útiles para toma de decisiones, diagnóstico y predicción. + +\end_layout + +\begin_layout Standard +Sea +\begin_inset Formula $I$ +\end_inset + + un conjunto de ítems que pueden aparecer en la descripción de un elemento + de una base de datos, una regla de asociación tiene forma +\begin_inset Quotes cld +\end_inset + +Si +\begin_inset Formula $X$ +\end_inset + + entonces +\begin_inset Formula $Y$ +\end_inset + + +\begin_inset Quotes crd +\end_inset + + o +\begin_inset Quotes cld +\end_inset + + +\begin_inset Formula $X\Rightarrow Y$ +\end_inset + + +\begin_inset Quotes crd +\end_inset + +, donde +\begin_inset Formula $X,Y\subseteq I$ +\end_inset + + son disjuntos. + Sea +\begin_inset Formula $D\subseteq{\cal P}(I)$ +\end_inset + + un conjunto finito de elementos de la base de datos, el +\series bold +soporte +\series default + de un +\begin_inset Formula $Z\subseteq I$ +\end_inset + + es +\begin_inset Formula $s(Z):=\frac{|\{e\in D:Z\subseteq e\}|}{|D|}$ +\end_inset + +; la +\series bold +confianza +\series default + o +\series bold +precisión +\series default + de la regla +\begin_inset Quotes cld +\end_inset + +si +\begin_inset Formula $X$ +\end_inset + + entonces +\begin_inset Formula $Y$ +\end_inset + + +\begin_inset Quotes crd +\end_inset + + es +\begin_inset Formula $c(X\Rightarrow Y):=\frac{s(X\cup Y)}{s(X)}$ +\end_inset + +, y su +\series bold +soporte +\series default + o +\series bold +cobertura +\series default + es +\begin_inset Formula $s(X\Rightarrow Y):=s(X\cup Y)$ +\end_inset + +. +\begin_inset Foot +status open + +\begin_layout Plain Layout +Las diapositivas usan la notación de mierda +\begin_inset Formula $|X|:=|\{e\in D:X\subseteq e\}|$ +\end_inset + +. +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Conjunto de ítems $I$ de tamaño $k +\backslash +in +\backslash +mathbb{N}$, conjunto de elementos $D +\backslash +subseteq{ +\backslash +cal P}(I)$ y soporte mínimo $f +\backslash +in[0,1]$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Conjunto ${ +\backslash +cal L} +\backslash +subseteq{ +\backslash +cal P}(I)$ de conjuntos de ítems con soporte al menos $f$.} +\end_layout + +\begin_layout Plain Layout + +$L_1 +\backslash +gets +\backslash +{ +\backslash +{i +\backslash +} +\backslash +}_{i +\backslash +in D,s( +\backslash +{i +\backslash +}) +\backslash +geq f}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +$k +\backslash +gets1$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Mientras{$L_k +\backslash +neq +\backslash +emptyset$}{ +\end_layout + +\begin_layout Plain Layout + + $G +\backslash +gets +\backslash +{S +\backslash +cup +\backslash +{i +\backslash +} +\backslash +}_{S +\backslash +in L_k,i +\backslash +in I +\backslash +setminus S}$% +\end_layout + +\begin_layout Plain Layout + + +\backslash +tcp*{{ +\backslash +rm Fase de formación.}} +\end_layout + +\begin_layout Plain Layout + + $C +\backslash +gets +\backslash +{S +\backslash +in G: +\backslash +forall i +\backslash +in S,S +\backslash +setminus +\backslash +{i +\backslash +} +\backslash +in L_k +\backslash +}$% +\end_layout + +\begin_layout Plain Layout + + +\backslash +tcp*{{ +\backslash +rm Fase de poda.}} +\end_layout + +\begin_layout Plain Layout + + $L_{k+1} +\backslash +gets +\backslash +{S +\backslash +in C:s(S) +\backslash +geq f +\backslash +}$% +\end_layout + +\begin_layout Plain Layout + + +\backslash +tcp*{{ +\backslash +rm Candidatos de tamaño $k$ frecuentes.}} +\end_layout + +\begin_layout Plain Layout + + $k +\backslash +gets k+1$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + +${ +\backslash +cal L} +\backslash +gets +\backslash +bigcup_{i=1}^{k-1}L_i$ +\backslash +; +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:a-priori" + +\end_inset + +Algoritmo a priori. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Para obtener reglas con buenos valores de soporte y confianza, primero ejecutamo +s el algoritmo a priori (algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:a-priori" +plural "false" +caps "false" +noprefix "false" + +\end_inset + +) para obtener los conjuntos de ítems frecuentes en +\begin_inset Formula ${\cal L}$ +\end_inset + + y luego tomamos las reglas +\begin_inset Formula $r\in\bigcup_{L\in{\cal L}}\{X\Rightarrow L\setminus X\}_{X\subseteq L}$ +\end_inset + + con +\begin_inset Formula $c(r)\geq p$ +\end_inset + +, donde +\begin_inset Formula $p$ +\end_inset + + es la precisión mínima. +\end_layout + +\end_body +\end_document |