Algoritmos de Búsqueda y Redes Neuronales: Conceptos y Aplicaciones
Búsqueda Primero en Mejor
La búsqueda primero en mejor selecciona un nodo para la expansión basándose en una función de evaluación. Esta función no siempre es exacta, ya que no garantiza una marcha directa hacia el objetivo.
Función Heurística h(n)
La función heurística h(n) estima el costo del camino más barato desde el nodo n hasta un nodo objetivo. Si n es el objetivo, entonces h(n) = 0.
Búsqueda Voraz Primero en Mejor
La búsqueda voraz primero en mejor expande el nodo que, según la heurística, está más cercano al objetivo. Se asume que esto conducirá más rápidamente a la solución.
La función de evaluación se define como: f(n) = h(n)
Un ejemplo común de heurística es la «distancia en línea recta» (hdlr). Aunque hdlr no se calcula necesariamente a través del problema en sí, la experiencia a menudo muestra que está correlacionada con las distancias reales, lo que la convierte en una heurística útil.
Limitaciones de la Búsqueda Voraz
- No garantiza encontrar el mejor camino.
- Puede expandir nodos incorrectamente.
- Puede llegar a callejones sin salida.
- Puede caer en bucles infinitos si no se controlan los estados repetidos.
La búsqueda voraz primero en mejor es similar a la búsqueda primero en profundidad, ya que prefiere seguir un camino hacia el objetivo, pero retrocederá si llega a un callejón sin salida.
- No es óptima.
- Es incompleta (puede no encontrar una solución si existen caminos infinitos).
La complejidad en tiempo y espacio es O(b^m), donde m es la profundidad máxima de expansión de la búsqueda. Una buena función de evaluación puede reducir considerablemente la complejidad. La definición de la función de evaluación depende de la heurística y del problema.
Redes Neuronales
Una red neuronal está compuesta por pequeñas unidades de procesamiento (neuronas) conectadas por conexiones sinápticas, que envían y reciben señales. Estas redes son susceptibles a un proceso de entrenamiento y aprendizaje, lo que permite que las conexiones se fortalezcan o debiliten.
Generalización
La generalización implica que si algo funciona para ciertos casos (A y B), podría funcionar para otros, minimizando las características específicas.
Factores que Definen una Arquitectura de Red Neuronal
- Número de capas.
- Número de neuronas por capa.
- Grado de conectividad.
- Tipo de conexiones.
Procesamiento Neuronal
El procesamiento neuronal se divide en dos fases:
Fase de Entrenamiento
En esta fase, se actualizan los pesos sinápticos existentes en las conexiones entre neuronas de diferentes capas. El objetivo es adquirir los datos de entrenamiento y expresarlos como una matriz de pesos.
Para lograr esto, se configura la RNA para aplicar iterativamente el conjunto de datos de entrenamiento. Cada iteración se denomina «época». En cada época, los pesos sinápticos se modifican gradualmente para minimizar el Error Medio Cuadrático (EMC) entre las salidas de la RNA y las funciones objetivo.
Fase de Ejecución
En esta fase, se calcula la salida de una RNA ya entrenada ante una señal de entrada. No hay ajuste de pesos sinápticos, y el tiempo de cómputo es muy reducido.
El EMC (Error Medio Cuadrático) debe ser inferior a una tolerancia definida, lo que indica que se ha alcanzado una aproximación estadísticamente óptima.
Donde:
- N: Número de salidas consideradas.
- Ei: Diferencia entre la i-ésima salida y su correspondiente objetivo.
Algoritmo de Retropropagación
- Inicializar los pesos sinápticos de forma aleatoria.
- Presentar un vector de entrada y obtener una salida de la red.
- Calcular el EMC entre la salida y su objetivo.
- Calcular la señal del error.
- Calcular la variación de pesos en la capa de salida y en las capas ocultas, y ajustar los pesos.
- Si existen más vectores de entrada, repetir el proceso desde el paso 2; de lo contrario, ir al paso 7.
- Calcular nuevamente el EMC y verificar si el error alcanzó una tolerancia aceptable.
Criterios para Entrenar
- Utilizar un porcentaje del conjunto de datos para entrenar y el resto para verificar.
- Definir una tolerancia razonable y monitorear el desempeño de las curvas para determinar un punto de parada anticipada.
- Si no se obtienen resultados satisfactorios, ajustar la arquitectura (número de neuronas, capas, funciones de activación).
- Si aún no se obtienen resultados, reformular los datos.
Las redes neuronales se crearon como un paradigma para imitar el funcionamiento del cerebro, copiando su estructura neuronal.
El cerebro humano está compuesto por 
(conexiones neuronales). Una persona podría dedicar 100,000 conexiones para almacenar cada segundo de experiencia; 65 años equivaldrían a 2,000,000,000 segundos.
Durante los dos primeros años de vida, se forman 1,000,000 de sinapsis por segundo.
Comparación: Humano vs. Computador
| Computador | Cerebro |
| Ciclo de 0.25 ms (Procesador 4 GHz) | Ciclo de 2 ms (0.5 kHz) – 1 neurona Debido al procesamiento en paralelo de las neuronas, el cerebro humano es superior. |
Otros Tipos de Entrenamiento
Entrenamiento No Supervisado
Son asociaciones de información que no tienen una finalidad específica. Por ejemplo, asociar a un hombre, una mujer y niños con una familia.
Según Hebb (1961), cuando un axón (salida de la neurona A) está lo suficientemente próximo para excitar otra neurona (B), y dicha activación ocurre repetidamente, un proceso de crecimiento o cambio metabólico ocurre en una o más células, aumentando la eficiencia de A para activar B.
En el entrenamiento no supervisado, no hay un objetivo determinado; los pesos se actualizan cada vez que se ingresa nueva información.
Perceptrón
- Inicializar los pesos sinápticos con valores aleatorios.
- Aplicar un patrón de entrada y calcular la salida.
- Si la salida (Out) es igual al objetivo (T), volver al paso 2 y aplicar de nuevo el patrón.
- Caso contrario, calcular la variación de pesos:
X
- Actualizar los pesos sinápticos.
- Volver al paso 2 y aplicar un nuevo patrón.
- FIN.
Mejorando la Generalización
La función en rosado se utiliza para mejorar la generalización de la línea morada.
Características
- No se entrenan todos los datos para poder definir un punto de parada anticipado.
- Pre y post procesamiento implican la modificación de las entradas y salidas de una RNA para que sean representadas por valores entre -1 y 1.
Ejemplo:
Entradas: 10 válvulas, 20000 ml de combustible, 4x (1-5), 3y (1-10) Salidas: 4000 g (3000 – 4000 -> 1), 200 T (400 – 300 -> 0)
Demostraciones de Declaraciones sobre Algoritmos de Búsqueda
1. Amplitud-primera búsqueda es un caso especial de búsqueda uniforme costo.
Cuando todos los costos de paso son iguales, el costo g(n) de una ruta desde el nodo de inicio a un nodo n es proporcional a la profundidad(n). La búsqueda de costo uniforme reproduce la búsqueda en amplitud (BFS) con el algoritmo de búsqueda modificado (un nodo se prueba para ser el objetivo cuando se retira de la franja).
2. Amplitud-primera búsqueda es un caso especial de la mejor primera búsqueda.
BFS es mejor primera búsqueda con f(n) = profundidad(n).
3. La búsqueda en profundidad es un caso especial de la mejor primera búsqueda.
DFS es mejor primera búsqueda con f(n) = -profundidad(n) o f(n) = 1/profundidad(n).
4. Búsqueda Uniforme costo es un caso especial de búsqueda A*.
UCS es A* con h(n) = 0.
Función Heurística para el 8-Puzzle que Sobrestima
Considere una heurística h(s) que devuelve 0 si el estado es un objetivo y, de lo contrario, devuelve un número aleatorio entre 1 y N, donde N es lo suficientemente grande como para asegurar que a veces sobrestima. Para el ejemplo, sea N = 20 y supongamos que empezamos con el siguiente estado:
1 2 3 4 7 5 6 8
La siguiente traza A* muestra cómo se encontraría una solución subóptima. Cuando se encuentra la meta, todos los nodos no expandidos tienen un costo estimado mayor que el costo real de la meta encontrada.
Nombres de Algoritmos de Búsqueda Resultantes de Casos Especiales
a. Búsqueda haz Local con k = 1: Búsqueda en escalada (Hill Climbing).
b. Búsqueda haz Local con k = ∞ (sin límite de estados): Búsqueda en amplitud (Breadth-First Search).
c. Temple simulado con T = 0 en cualquier momento: Búsqueda en escalada (o primera elección en escalada, como se describe en el libro de texto).
d. Algoritmo genético con tamaño de la población N = 1: Búsqueda en escalada (o primera elección en escalada). Se mantiene el mejor individuo de la población, por lo que el individuo mutado solo reemplaza al individuo actual cuando la función física mejora. Esto es equivalente a la búsqueda en escalada de primera elección.