1

IIb-Técnicas de conformación de haz: Algoritmos alternativos

� Referencia y función de coste� Referencia temporal.� Referencia espacial� Referencia ciega

� Algoritmos clásicos:� LMS (Mínimos Cuadrados).� RLS (Mínimos Cuadrados Recursivos).� CG (Gradiente Conjugado)� GSLC (Cancelador de Lóbulos Secundarios)

� Algoritmos alternativos:� FL (Lógica Borrosa).� NN (Redes Neuronales)

II- Técnicas de Conformación de Haz

2

Introducción a la lógica borrosa

� La lógica borrosa surgió como otra aproximación al funcionamiento del cerebro

� Redes Neuronales: Estudio a través de la interacción entre las unidades básicas de la corteza cerebral: las neuronas. Enfoque a “bajo nivel”.

� Lógica Borrosa: Intenta emular el proceso de razonamiento, es decir, cómo piensa el cerebro. Es un enfoque a “alto nivel”

� Debido a esto, la lógica borrosa permite tratar de mejor manera conceptos como “conocimiento ambiguo” o “sentido común” a la hora de resolver problemas.

3

Lógica borrosa vs. Redes neuronales

� Lógica borrosa

� Trabaja con: Conjuntos borrosos y relaciones lógicas entre ellos

� Se diseña: Número y tipo de “categorías”, relaciones sintácticas entre categorías (reglas).

� Redes neuronales

� Trabaja con: “neuronas”, sus conexiones y su función básica de procesado

� Se diseña: Número y niveles de neuronas, tipos de interconexión.

4

Antecedentes de la lógica borrosa

� Lofti A. Zadeh en sus artículos de 1965 y 1973. Universidad de Berkeley

� No se trata de una teoría unificada ni asentada. Existen varias aproximaciones:� 1993: Combettes establece la teoría de conjuntos borrosos, ampliación

de las lógicas n-valuadas de Lukasiewiez (1930)� 1999: Zadeh establece el paralelismo entre sistemas borrosos y

“computación con palabras

5

Aplicaciones de la Lógica borrosa

� Objetivo de la lógica borrosa: “…proporcionar un soporte formal al razonamiento en el lenguaje natural, que se caracteriza por tratarase de un razonamiento de tipo aproximado, que hace uso de unas proposiciones que a su vez expresan información de carácter impreciso…” (Redes Neuronales y Sistemas Borrosos. Martín del Brío y Sanz Molina. 2001)

� Por tanto, la aplicación fundamental de la lógica borrosa es la construcción de “sistemas de control borroso”, que trabajan sobre una serie de “reglas de conducta” establecidas a través de lenguaje natural.

� Ventaja fundamental: facilidad de implementar rápidamente un “conocimiento ambiguo” o “experiencia acumulada” de expertos a la hora de diseñar el comportamiento del controlador.

6

Conjuntos borrosos

� A alto nivel, el razonamiento humano (y por tanto el lenguaje) se basa en la clasificación del entorno en clases, categorías (ej: la temperatura en muy fría, fría, templada…). “Orden en el caos”.

� La pertenencia del objeto a una categoría casi nunca se realiza de manera absoluta, sino siempre con cierto grado de “intensidad depertenencia”.

� Por tanto, en primera aproximación, una categoría o conjunto borrosoqueda caracterizado unívocamente por la función matemática que mida este grado de pertenencia (membership function).

� En la implementación real de sistemas borrosos se usan generalmente un reducido tipo de funciones de pertenencia: Singleton (delta), Trapezoidal, Triangular,Tipo S o En ∏.

7

Tipos de conjuntos borrosos Tipo Singleton

µ

1

a

8

Tipos de conjuntos borrosos Tipo Triangular

µ

1

ba c

>

≤≤−−

≤≤−−

<

=

cu

cubbcuc

buaabau

au

cbauT

0

0

),,,(

9

Tipo de conjuntos borrososTipo Trapezoidal

µ

1

ba c d

>

≤≤−−

≤≤

≤≤−−

<

=

du

duccdud

cub

buaabau

au

dcbauT

0

1

0

),,,,(

10

Tipos de conjuntos borrosos Tipo S

µ

1

ba c

0.5

>

≤≤

−−−

≤≤

−−

<

=

cu

cubabau

buaabau

au

dcbauT

1

21

2

0

),,,,(2

2

11

Tipos de conjuntos borrososTipo ∏

µ

1

cc-b/2c-b

0.5

c+b/2 c+b

b

≥−−−<−−

=cucbcbcuScucbcbcuS

dcbauT ),2/,,(1

),2/,,(),,,,(

12

Conjuntos borrososVariables lingüísticas

� Son aquellas que pueden tomar por valor términos del lenguaje natural, como “mucho, poco,…”

� En el predicado “la temperatura es fría”, a la v.l. “temperatura” se le asignaría como valor el conjunto borroso “frío”.

� En términos matemáticos, una variable lingüística se define como la tupla (A,T(A),U,G,M), donde:� A: Nombre de la variable� T(A): Conjuntos borrosos que clasifican a “A”� U: Universo donde se definen los conjuntos borrosos� G: Regla sintáctica que asocia a la variable “A” con los conjuntos

borrosos� M: Regla semántica que asocia a cada conjunto un valor

13

Conjuntos borrososParticiones

� Se llama partición al conjunto de conjuntos borrosos definidos para la v.l. “A”

� Será “completa” cuando para cualquier valor de “U” existe en la partición un conjunto borroso con función de pertenencia no nula.

� Será “solapada” cuando la intersección entre conjuntos es no nula

� Como reglas generales de diseño, se suelen utilizar particiones con un número impar de conjuntos borrosos (3 a 7) y con solapamientos de 20 al 50%

14

Operaciones con conjuntos borrosos

� Los sistemas borrosos operan a través de operaciones con conjuntos borrosos. Se definen las operaciones:

Operación Rango

Igualdad )()( xx BA µµ = Ux ∈ Unión [ ])(),(max)( xxx BABA µµµ =∪ Ux ∈∀

Intersección [ ])(),(min)( xxx BABA µµµ =∩ Ux ∈∀ Complemento )(1)( xx AA µµ −= Ux ∈

Norma [ ])(max

)()()( x

xxA

AANorma µ

µµ = Ux ∈

Concentración ( )2)( )()( xx AAConc µµ = Ux ∈

Dilatación )()()( xx AADilat µµ = Ux ∈

15

Inferencia borrosa

� Los sistemas borrosos funcionan a través de “deducciones” con conjuntos borrosos. Es un razonamiento aproximado (como el humano) en el que a través de unas reglas se llega a una conclusión, aunque el antecedente no se cumpla por completo.

� Se denomina base al conjunto de reglas con las que trabaja el sistema, relacionando conjuntos borrosos de entrada (premisas) con conjuntos borrosos de salida (consecuencias). Típicamente la “base” se expresa a través de una matriz (FAM: Memoria Asociativa Borrosa)

� En el lenguaje, las reglas suelen expresarse con preposiciones de la forma IF-THEN. Básicamente, existen 2 tipos de leyes de inferencia:� Modus ponens generalizado (GMP). Razonamiento Directo� Modus tolens generalizado (GMT). Razonamiento Inverso

16

Inferencia borrosaGMP

� Este tipo de razonamiento utiliza el siguiente planteamiento lógico:

(Conocimiento): Si “x” es “A”, entonces “y” es “B”(Hecho): “x” es A’---------------------------------------------------------(Consecuencia) “y” es B’

x es A’ y es B’ Criterio 1 x es A y es B Criterio 2-1 x es muy A y es muy B Criterio 2-2 x es muy A y es B Criterio 3-1 x es más o menos A y es más o menos B Criterio 3-2 x es más o menos A y es B Criterio 4-1 x no es A y es desconocido Criterio 4-2 x no es A y no es B

17

Inferencia borrosaGMT

� Sigue el siguiente esquema:(Conocimiento): Si “x” es “A”, entonces “y” es “B”(Hecho): “y” es B’---------------------------------------------------------(Consecuencia) “x” es A’

y es B’ x es A’ Criterio 5 y no es B x no es A Criterio 6 x no es muy B y no es muy A Criterio 7 y no es más o menos B x no es más o menos A Criterio 8-1 y es B x es desconocido Criterio 8-2 y es B x es A

18

Tipos de bases

� Existen 2 modelos:

� Mamdani o Borroso Puro (1974):Si x1 es F1 y…y xn es Fn entonces y es G

� Sugeno (1985):Si x1 es F1 y…y xn es Fn entonces y es f(x1…xn)

� Con bases Mamdani es más sencillo construir las FAM

� Las bases Sugeno son más apropiadas para crear mecanismos de aprendizaje borroso

19

Mecanismo de Inferencia

� Es el proceso por el que se interpretan la base de reglas para obtener los valores de salida, a partir de los valores de las variables lingüísticas de entrada.

� Las bases Mamdani se interpretan como implicación borrosa de: F1x…xFn->G. Utilizando la composición Sup-Star, obtenemos:

[ ])(*),(sup)( ...1xyxy AGFFUxB n

µµµ →××∈=

20

Mecanismo de Inferencia (2)

� Existen 6 formas de interpretar la implicación borrosa, pero las 2 más frecuentes son:

� Implicación borrosa por la regla del mínimo:

� Implicación borrosa por la regla del producto

)()(),( ...... 11yxyx GFFGFF nn

µµµ ⋅= ××→××

[ ])(),(min),( ...... 11yxyx GFFGFF nn

µµµ ××→×× =

[ ])(),...,(min)(11 ... xxx

nn FFFF µµµ =××

)()...()(11 ... xxx

nn FFFF µµµ =××

21

Mecanismo de Inferencia (3)

� La salida final del proceso puede ser:

� “M” conjuntos borrosos, cada uno resultado de una regla sintáctica (modelo Mamdani)

� Un único conjunto borroso “B” por medio de (modelo Sugeno):

� Debemos definir cómo se relacionan entradas y salidas no borrosas con los conjuntos borrosos con los que trabaja el dispositivo: procesos de Borrisificación y Desborrisificación

)(...)()( 1' xxx MBBB µµµ••++=

22

Esquema de controlador lógico borroso (FLC)

FLCFLC

Base de ReglasBase de Reglas

Disp. de Inferencia Borrosa

Disp. de Inferencia Borrosa

BorrisificadorBorrisificador DesborrisificadorDesborrisificador

Entradas Salidas

23

Borrosificador (fuzzifier)

� 2 modalidades:� Borrosificador singleton: Se consideran los valores

discretos de entrada como conjuntos borrosos.

� Borrosificador no singleton. La función de pertenencia más frecuente en este caso es en campana:

−−=2'exp.)'(

σµ xxaxA

24

Desborrisificador (Defuzzifier)

� Para reglas Mamdani:� Desborrisificador por máximo

� Desborrisificador por media de centros

� Desborrisificador por centro de área

� Para reglas Sugeno

( ))(suparg ' yy BVy µ∈=

( )

( )∑

∑

=

−

=

−−

=M

l

lB

M

l

lB

l

y

yyy

1'

1'

)(

)(

µ

µ

( )

( )∑

∑

=

−

=

−

=M

l

lB

l

M

l

lB

l

yA

yMy

1'

1'

)(

)(

µ

µ

( )

( )∑

∑

=

−

=

−

=M

l

lA

M

l

lA

l

y

yyy

1'

1'

)(

)(

µ

µ

∑=

+==n

iiilll

l xaaxfy1

,0,)(

25

Aprendizaje de sistemas borrosos

� ¿Cómo se definen las particiones borrosas? ¿Y las reglas sintácticas?

� Los métodos más usados son:� Retropropagación (tomado de las RN)� Algoritmos genéticos� Mínimos cuadrados ortogonales � Tablas de búsqueda (look-up table)

26

Opciones en el diseño

� Existen una gran variedad de posibilidades, pero en líneas generales existen 2 vertientes:

� Eficiencia computacional. Si nuestro problema es complejo (muchas reglas y variables) es conveniente seleccionar opciones que necesiten de pocos cálculos y poca memoria:

� Funciones de inclusión triangulares o trapezoidales.� Cálculo de máximos/mínimos frente a multiplicaciones� Funciones singleton para las entradas/salidas� Arquitectura Mamdani

� Facilidad de adaptación/apredizaje.� Uso de funciones derivables� Uso intensivo de multiplicaciones frente a máximos/mínimos� Arquitectura singleton

27

Ejemplo práctico LMS Vs. LMS borroso

� El esquema general del sistema es el típico de “antena inteligente”

CorreladorCorrelador

GESGES

LMSLMS

···

CorreladorCorrelador

CorreladorCorrelador

Referencia

Saliday(n)

x1(n)

x2(n)

xk(n)

w1(n)

w2(n)

wk(n)

28

Ejemplo práctico LMS Vs. LMS borroso (2)

� Ecuaciones LMS:

[ ] )()()()(),...,(),()( 21 nnnsAnxnxnxnx TK +== θ [ ]T

K nsnsnsns )(),...,(),()( 21=

[ ]TK nanananA )(),...,(),()( 21= [ ] ),...,2,1( )(),...,(),()( 21 Klaaana Mllll == θθθ

)()()( nxnwny H=

[ ]TK nwnwnwnw )(),...,(),()( 21=

)()()( nyndne −=

)()()()()1( * nxnennwnw µ−=+

29

Ejemplo práctico LMS Vs. LMS borroso (3)

� Lo novedoso es aplicar Lógica borrosa al tamaño del paso en función del error cuadrático medio.

� Para clasificar el error cuadrático medio y el tamaño de paso se usan el siguiente tipo de partición:

µ

1

Muy Pequeño Enorme

Pequeño Medio Grande

30

Ejemplo práctico LMS Vs. LMS borroso (4)

� Las reglas sintácticas establecidas son las siguientes:

Si MSE(e(n)) es “Muy Pequeño” Entonces el paso es “Enorme”Si MSE(e(n)) es “Pequeño” Entonces el paso es “Grande”Si MSE(e(n)) es “Medio” Entonces el paso es “Medio”Si MSE(e(n)) es “Grande” Entonces el paso es “Pequeño”Si MSE(e(n)) es “Enorme” Entonces el paso es “Muy Pequeño”

� El proceso de desborrisificación es del tipo “centro de áreas”:

∑

∑

=

== N

kk

N

kkk

MBF

MBFn

1

12

)(

)()(

µ

µµµ

31

Ejemplo práctico LMS Vs. LMS borroso (5)

� Pero en el artículo:� No se especifica el grado de solapamiento entre conjuntos

borrosos� No se habla nada del tipo de inferencia� No se dice nada sobre un posible mecanismo de entrenamiento

� Parámetros de la simulación� CDMA, SF=64, BPSK� Array de 6 elementos separados λ/2� 2 usuarios interferentes� Canal mutitrayecto con 30 rayos. Frecuencia Doppler: 66’67 Hz� SNR=7 dB

32

Ejemplo práctico LMS Vs. LMS borroso (6)

33

Redes Neuronales

� Son caso concreto de método de clasificación o reconocimiento de patrones.� El primer modelo de red neuronal McCulloch y Pitts (1943)� Otros: modelo de Von Neumann o el de Marvin Minsky.

� Surgen a “imitación” de las redes neuronales biológicas.� “neuronas” = “nodos”, y interconexiones = “sinapsis”

� Matemáticamente son una evolución de los clasificadores basados en funciones lineales discriminantes.

� Características:� Adaptatibilidad y autoorganización� Procesado no lineal� Procesamiento en paralelo:

34

Red Neuronal y Neuronas

Umbral

Función de

Activación

Pesos

Función

de Red

Valor de

Activación

Estructura de una Neurona

Red Neuronal

Salida

35

Función de Base o de Red

� Función de Base Lineal (LBF)

� Función de Base Radial (RBF)

� Función de Base no Lineal (neurona sigma-pi)

( )txwtu jj

iji ∑=)(

( )( )∑ −=j

ijji wtxtu 22 )(

( ) ( ) ( )∑=p

ppjjj

jjjjjiji txtxtxwtu�

�

�

21

2121)(

36

Función de Activación

Identidad xy =

Escalón ( )xsignoy =

Lineal a Tramos

>≥≥−

−<−=

lxlxlx

lxy

1

1Sigmoidea ( )xtghy =

Gausiana ( )2exp BxAy −=

Sinusoidal ( )Φ+= xAy ωsin

37

Función de Salida

Identidad xy =

Escalón ( )xsignoy =

Estocástica ( )xrndy = Máquina de Boltzman

MLP o Adalina

38

Estructuras de Conexión

� Conexiones hacia delante� Las que hacen que los datos de salida de una neurona pasen hacia las

entradas de las neuronas de la capa superior.

� Conexiones hacia atrás:� Las que hacen que las salidas de las neuronas de una capa afecten a las

neuronas de una capa inferior.

� Conexiones laterales:� Se dan cuando las neuronas de una capa afectan a las otras neuronas de

esa misma capa.

� Conexiones con retardo:� En las que se incluyen elementos de retardo, para permitir simular

modelos que requieren de memoria.

� Conexiones totales, si todas las neuronas se interconectan con todas las demás, o parciales, en caso contrario.

39

Tamaño de la Red

� Número de Neuronas de entrada: Fijado por el numero de entradas.

� Número de neuronas en las capas ocultas.

� Número de capas que forman la red.

40

Clasificación de Categorías

� Solución ACON (“all class in one network”): � Se utiliza una única red para clasificar todas las clases.

� Solución OCON (“one class in one network”):� Esta solución el problema se divide en tantos sub-problemas como

clases se quieran clasificar. Se utilizan tantas redes como clases hay.

� Solución intermedia:� Se pueden utilizar varias sub-redes, de modo que cada una se

encargue de la clasificación de un subconjunto de clases.

41

Tipo de Entrenamiento

� No supervisado� Las muestras son sólo los patrones de entrada. No se tiene

información de los patrones de salida� La red se adapta basándose en las experiencias recogidas de los

patrones de entrenamiento anteriores. � El aprendizaje es competitivo

� Supervisado� Las muestras de entrenamiento son pares de entrada-salida.� Se ajustan los pesos de modo iterativo� Se actualizan los pesos de la red, mediante una cierta función de

adaptación, que depende del tipo de red neuronal

42

Tipos de Redes Neuronales: Con Pesos Fijos

� Su entrenamiento es no supervisado.� Su memoria es asociativa:

� Memoria proasociativa: un mapeado de los valores de entrada hacia los valores de salida, y pueden basarse en funciones lineales o no lineales

� Ejemplo: Las redes de Hamming muy utilizado para el caso de tener entradas binarias.

� Utiliza la distancia de Hamming para clasificar la entrada como de la clase para la que el vector de entrada está más cerca, según dicha distancia.

� Memoria retroasociativa: los pesos son fijos, pero se realimenta la entrada con los valores de la salida.

� Ejemplo: Las redes de Hopfield,� secuencial (o asíncrono)� paralelo (o síncrono).

43

Tipos de Redes Neuronales: No supervisadas

� Su entrenemaniento es No Supervisado.� Los pesos no son fijos se adaptan en función de unas reglas de

aprendizaje no supervisado. � Dichas redes están formadas por una o varias redes excitadoras hacia

delante y una o varias redes inhibidoras laterales.� La rede excitadora sigue la regla de aprendizaje de Hebb.� La red lateral se encarga de seleccionar la clase a la que se clasifica el

patrón de entrada, mediante un método de aprendizaje competitivo.

� Ejemplo: Red MAXNET método de aprendizaje “winner-take-all”.� Ejemplo: Mapas de Kohonen, implementados como mapas de

características. Incorpora un cierto grado de sensibilidad con respecto al vecindario o a la historia, evitando así que algunas neuronas nunca lleguen a entrenarse.

44

Tipos de Redes Neuronales: Supervisadas

� Su entrenamiento es Supervisado.� Redes basadas en la decisión (DBNN),

� Un par de entrenamiento de entrada el maestro indicará únicamente si la clase a la que se ha clasificado es correcta o no.

� Los pesos de la red se van actualizando a partir de los valores de entrenamiento hasta que no se cometen errores en la clasificación.

� Las redes basadas en la decisión pueden tener una o varias capas ocultas.� Ejemplo: perceptrón lineal, diseñado en principio para separar dos clases� Ejemplo: perceptrón no lineal. En este caso las funciones de base utilizadas son no

lineales: función de base radial (RBF) y la función de base elíptica (EBF).� Redes basadas en la optimización.

� En las redes neuronales de optimización o aproximación, a diferencia de en las redes de decisión, el maestro no sólo indica si la clasificación fue correcta. Se buscan los pesos óptimos para minimizar el error entre los valores del maestro y las salidas de respuesta.

� Se calcula el error entre los valores obtenidos y los deseados. � Ejemplo: Aplimar LMS como en la red ADALINE (ADaptive LINear Element), que es una

red de una sola capa con una función de red lineal y una regla de actualización de los pesos tipo LMS.

� Se puede mejor ADALINE con otras optimizaciones no lineales� Para lograr una capacidad de aproximación no lineal, es muy común utilizar redes

multicapa, junto con el algoritmo de back-propagation o retropropagación.

45

Algoritmos NN para conformacion

g

g

Σ

Σ

Lx

2x

1x

1ijω

2ijω

1s

MsSteeringvector

Sigmoid

Arquitectura MLP (Multilayer Perceptron)

Entrada

Layer de Entrada Layer Oculto Layer de Salida

46

Algoritmos NN para Conformación (2)

Entrenamiento: Regla BP (Back Propagation)

∑=

ε=εM

1ppT

( ) ( )1tt p −ω∆α+ω∂ε∂

η−=ω∆

Minimiza

2

ppp sd21 −=ε

Pesos del MLP

47

Referencias

� L.C. Godara, “Aplication of Antenna Arrays to Mobile Communications, Part II: BF and DOA Consierations”. Proceedings of the IEEE, vol 85., No 8., pp 1195-1245. August 1997

� P.V. Su et al., “A new Fuzzy Logic Applications to Variable Step Size LMS Algoritm for Adaptive Antennas in CDMA System”. 2002 3rd ICMMT.

� K.L. Du et al., “Neural method for Anenna Array Signal Processing: A review”. Signal Processing 82 (2002) pp 547-561.