\documentclass{article}
\usepackage{fullpage}
\bibliographystyle{plain}
\usepackage[catalan]{babel}
\usepackage{latexsym}
\usepackage[dvips]{graphicx}
\usepackage{multicol}
\usepackage{mathenv}
\usepackage{float}
\usepackage[iso,french]{isodate}

\title{Estudi i millores de Relief}
\author{ Rafael Castillo \\ rafaelc@lsi.upc.edu \and Gabriel Prat \\ gprat@lsi.upc.edu}
%\address{\small{Departament de Llenguatges i Sistemes Inform{\`a}tics (LSI)
% \\ Universitat Polit{\`e}cnica de Catalunya (UPC)  }}
\date{\printdate{2004-1-19}}

\begin{document}

\maketitle


\begin{multicols}{2}





\section{Introducci\'{o}}

Pretenem fer un estudi d'aquest m\`{e}tode de selecci\'{o} d'atributs 
presentat per Kira i Rendell \cite{DBLP:conf/aaai/KiraR92}, partint de les millores aportades per 
Kononenko \cite{DBLP:conf/ecml/Kononenko94} i incorporant algunes noves idees.





L'estudi es centra b\`{a}sicament en dos punts: el primer seria provar de 
variar la m\`{e}trica usada per l'algorisme en les variables 
categ\`{o}riques emprant la m\`{e}trica VDM introdu\"{\i}da a 
\cite{DBLP:journals/cacm/StanfillW86}; el segon, veure els problemes de l'algorisme 
amb els atributs redundants i intentar aportar alguna millora.

\section{Estudi de la m\`{e}trica emprada}

Necessitem una m\`{e}trica heterog\`{e}nia per tal de poder treballar 
indistintament amb variables cont\'{\i}nues i categ\`{o}riques. La 
m\`{e}trica HEOM emprada en l'algorisme original, usa la dist\`{a}ncia 
eucl\'{\i}dea com a m\`{e}trica per a les variables cont\'{\i}nues, mentre 
que per les categ\`{o}riques empra la coneguda amb el nom de ``overlap''. 
Aquesta darrera \'{e}s tan simple com dir que les que s\'{o}n iguals estan a 
dist\`{a}ncia 0 i les que no s\'{o}n iguals a dist\`{a}ncia 1. Com ja 
apuntaven Wilson i Martinez \cite{DBLP:journals/jair/WilsonM97}, aquest 
tractament tan simplista de la m\`{e}trica als atributs nominals no est\`{a} 
fent \'{u}s de informaci\'{o} addicional que ens aporten aquestes variables 
i que podria \'{e}sser \'{u}til en la generalitzaci\'{o}.





Per solucionar aquest problema emprarem la VDM (Value Difference Metric). 
Aquesta m\`{e}trica es basa en les freq\"{u}\`{e}ncies d'aparici\'{o} de 
cada valor d'un atribut per cada classe. Tal i com ho proposa a 
\cite{DBLP:journals/cacm/StanfillW86} la dist\`{a}ncia VDM entre dos individus 
$i,j$\'{e}s:


\begin{MultiLine}[1]
D_{VDM} (i,j) = \\
\sum\limits_{a \in A} {d_{VDM} \left( {i_a ,j_a ,a} \right)} 
\mbox{ }w\left( {a,i_a } \right)
\end{MultiLine}



On $i_a $ \'{e}s el valor de l'atribut a en l'individu i.


\begin{MultiLine}[2]
d_{VDM} (x,y,a) = \\
\sum\limits_{c \in C} {\left( {\frac{N_{a = x,c} }{N_{a = 
x} } - \frac{N_{a = y,c} }{N_{a = y} }} \right)} ^2
\end{MultiLine}

\begin{Equation}[3]
w(a,x) = \sqrt {\sum\limits_{c \in C} {\left( {\frac{N_{a = x,c} }{N_{a = x} 
}} \right)^2} } 
\end{Equation}



On $N_{a = x,c} $ \'{e}s el n\'{u}mero d'individus de la classe c que tenen 
$x$ com a valor de l'atribut $a$ i $N_{a = x} $ \'{e}s el n\'{u}mero d'individus 
que tenen $x$ com a valor de l'atribut $a$. 

Tamb\'{e} podem escriure aquestes f\'{o}rmules d'una forma m\'{e}s simple 
veient-les com a probabilitats condicionades:


\begin{MultiLine}[4]
d_{VDM} (x,y,a) = \\
\sum\limits_{c \in C} {\left[ {P\left( {c\vert x_a } 
\right) - P\left( {c\vert y_a } \right)} \right]} ^2
\end{MultiLine}
\begin{Equation}[5]
w(a,x) = \sqrt {\sum\limits_{c \in C} {\left[ {P\left( {c\vert x_a } 
\right)} \right]^2} } 
\end{Equation}



On $P\left( {c\vert x_a } \right)$ \'{e}s la probabilitat condicionada de 
que un individu sigui de la classe c sabent que el seu atribut a t\'{e} un 
valor $x$.



El factor $w(a,x)$\'{e}s el pes d'un atribut i intenta aportar 
informaci\'{o} sobre la capacitat de discriminaci\'{o} d'aquest atribut. El 
valor m\'{\i}nim d'aquest atribut representa una distribuci\'{o} uniforme de 
les classes on cada valor de l'atribut apareix amb igual probabilitat per 
cada classe i podem veure que prendr\`{a} el valor:


\begin{MultiLine}[6]
w(a,x) = \sqrt {\sum\limits_{c \in C} {\frac{1}{\left| C \right|^2}} } = 
\sqrt {\frac{\left| C \right|}{\left| C \right|^2} = } \\
\sqrt 
{\frac{1}{\left| C \right|}} = \left| C \right|^{ - 1 / 2}
\end{MultiLine}



I que prendr\`{a} el seu valor m\`{a}xim quan $a$ sigui un discriminador 
perfecte i per tant aquest valor nom\'{e}s aparegui en una classe. A m\'{e}s 
podem veure f\`{a}cilment com aquest valor m\`{a}xim \'{e}s 1. Aix\'{\i} 
doncs, aquest pes ens d\'{o}na una idea de fins a quin punt la 
distribuci\'{o} de probabilitats d'un atribut respecte la classe est\`{a} 
esbiaixada o \'{e}s uniforme.



Aquesta m\`{e}trica, per\`{o} t\'{e} tamb\'{e} algun problema. Com hem vist, 
no t\'{e} en compte la semblan\c{c}a dels atributs dels individus per 
calcular la dist\`{a}ncia sin\'{o} la distribuci\'{o} de probabilitats 
condicionades en funci\'{o} de la classe. Aix\`{o} ens porta a que dos 
atributs amb igual distribuci\'{o} de probabilitats en funci\'{o} de la 
classe estiguin a dist\`{a}ncia 0 segons aquesta m\`{e}trica, cosa que pot 
ser interessant en alguns casos per\`{o} que en d'altres no ho \'{e}s en 
absolut. En especial no \'{e}s interessant en els problemes on la 
distribuci\'{o} d'alguns atributs respecte la classe \'{e}s poc esbiaixada 
per\`{o} la seva combinaci\'{o} s\'{\i} que t\'{e} un biaix gran. 

Podem trobar un bon exemple en el problema de la paritat (parity-n) on tenim 
n atributs que poden prendre els valors 1 o 0 i la seva classe \'{e}s 1 
nom\'{e}s quan el nombre d'atributs amb valor 1 \'{e}s parell i 0 altrament. 
Cada valor de cada atribut t\'{e} una distribuci\'{o} uniforme respecte la 
classe, per\`{o} la combinaci\'{o} de tots ells ens permet predir exactament 
la classe. En aquest cas la dist\`{a}ncia calculada per la VDM entre dos 
individus qualsevol ser\`{a} sempre 0 donat que totes les probabilitats 
condicionades prendran el mateix valor, de manera que no tindrem cap 
informaci\'{o} sobre quin individu escollir com a ve\'{\i} m\'{e}s proper. 

A m\'{e}s, si afegim atributs irrellevants distribu\"{\i}ts uniformement, 
aquests tamb\'{e} tindran la mateixa distribuci\'{o} en les probabilitats i 
per tant la difer\`{e}ncia entre ells tamb\'{e} ser\`{a} 0 i per tant el 
Relief els assignar\`{a} exactament el mateix pes que a als rellevants. 
Aix\`{o} doncs ens fa pensar que per alguns problemes on els atributs siguin 
molt dependents entre ells no ser\`{a} bona idea utilitzar HVDM. 

\section{Estudi de la redund\`{a}ncia}

Relief ens d\'{o}na una mesura de rellev\`{a}ncia de les variables, per\`{o} 
qu\`{e} passa amb la redund\`{a}ncia? Ens podem fer moltes preguntes 
interessants al respecte, per\`{o} potser les primeres a respondre s\'{o}n 
les seg\"{u}ents:




\begin{enumerate}
\item Donar\`{a} el mateix pes a dues variables si s\'{o}n redundants entre 
elles? 
\item Si dues variables tenen el mateix pes, podem concloure que s\'{o}n 
redundants?
\item Les variables redundants es perjudiquen entre s\'{\i}?
\end{enumerate}




Intentarem respondre i justificar les preguntes fetes comen\c{c}ant per 
l'algorisme original, i despr\'{e}s intentarem tornar a respondre-les amb 
algunes modificacions sobre aquest (que explicarem despr\'{e}s juntament amb 
la seva motivaci\'{o}).





Suposem doncs que tenim dos atributs $A_{1}$ i $A_{2}$ que s\'{o}n 
redundants, entenent que dos atributs s\'{o}n redundants si ens permeten 
determinar la classe de l'individu no nom\'{e}s en el mateix nombre de casos 
sin\'{o} tamb\'{e} en els mateixos casos (en els problemes reals aix\`{o} no 
succeir\`{a} completament entre cap parella d'atributs, pel que podem pensar 
m\'{e}s aviat en la norma donada com una mesura de redund\`{a}ncia entre 
atributs). 





Per respondre la pregunta 1 partirem d'un problema amb els dos atributs 
esmentats i un tercer (al que anomenarem $A_{3})$ que no \'{e}s redundant 
als dos primers. Tan sols cal demostrar que la difer\`{e}ncia entre el 
``nearest hit'' i el ``nearest miss'' i ell \'{e}s la mateixa per $A_{1}$ i 
A$_{2}$, ja que si aix\`{o} \'{e}s cert \'{e}s evident que 
l'actualitzaci\'{o} a cada volta ser\`{a} la mateixa per tots dos i per tant 
acabaran tenint el mateix pes. 





Primerament farem aquesta demostraci\'{o} tan sols per dues classes, amb 
atributs binaris i suposant que no hi ha soroll i despr\'{e}s parlarem de 
qu\`{e} passa en el cas m\'{e}s general. En el cas plantejat tenim els 
seg\"{u}ents valors:



\begin{description}
\item[Cas 1:] $A_{1} = X_{1}$  $A_{2} = X_{1}$  $A_{3} = Y_{1 }$  $C = Z_{1}$
\item[Cas 2:] $A_{1} = X_{1}$  $A_{2} = \neg X_{1}$  $A_{3} = Y_{1 }$  $C = Z_{1}$
\end{description}




Ja que altrament les variables no ens servirien per determinar la classe en 
els mateixos casos. El ``nearest hit'' i el ``nearest miss'' s\'{o}n de la 
forma:





\begin{description}
\item[Cas 1:] $A_{1} = X'_{1}$  $A_{2} = \neg X'_{1}$  $A_{3} = Y'_{1}$  $C = Z'_{1}$
\end{description}

On $Z'_{1 }$ ser\`{a} igual a $Z_{1}$ pel ``nearest hit'' i igual a $\neg Z_{1}$ 
pel ``nearest miss''. Si $X'_{1}$ \'{e}s diferent de $X_{1}$ 
llavors la difer\`{e}ncia als dos atributs ser\`{a} 1 i si \'{e}s igual 
ser\`{a} 0. 

\begin{description}
\item[Cas 2:] $A_{1} = X'_{1}$  $A_{2} = \neg X'_{1}$  $A_{3} = Y'_{1 }$  $C = Z'_{1}$
\end{description}

Si $X'_{1}$ \'{e}s diferent de $X_{1}$ llavors $\neg X'_{1}$ tamb\'{e} 
ser\`{a} diferent de $\neg X_{1}$ i la difer\`{e}ncia ser\`{a} 1, mentre 
que en el cas contrari ambdues valdran 0. 





La extensi\'{o} a variables no bin\`{a}ries es bastant simple: els atributs 
tindran m\'{e}s possibles valors, per\`{o} si al ``nearest hit'' i al 
``nearest miss'' $A_{1}$ t\'{e} el mateix valor, for\c{c}osament $A_{2}$ 
tamb\'{e} haur\`{a} de tenir-lo per complir amb la hip\`{o}tesi de la 
redund\`{a}ncia. Passa el mateix en el cas que el valors siguin diferents. 
Si pensem en problemes amb m\'{e}s de dues classes (extensi\'{o} del Relief 
proposada per Kononenko), tot el que hem dit fins ara es mant\'{e}: a 
cadascun dels ``nearest misses'' succeeix que es mant\'{e} la relaci\'{o} 
entre l'atribut original i l'afegit redundant a ell, fet que fa que 
l'increment tamb\'{e} acabi essent el mateix.





Anem a parlar de qu\`{e} varia si hi ha una certa probabilitat (que 
anomenarem ps) de que les dues variables no siguin redundants en alguns 
valors per culpa del soroll. M\'{e}s concretament anem a veure la 
probabilitat amb qu\`{e} aquest soroll far\`{a} variar la difer\`{e}ncia 
d'una certa inst\`{a}ncia $I_{1}$ amb el seu ``nearest hit'' i el seu 
``nearest miss'' d'un atribut $A$ a una r\`{e}plica seva afectada amb una 
probabilitat ps que anomenarem $A'$ (de fet, la f\'{o}rmula seg\"{u}ent 
serveix en general per veure el canvi de difer\`{e}ncia amb qualsevol altre 
inst\`{a}ncia $I_{2})$:

\begin{MultiLine}[8]
pcd_{A - A'}  = p(V_1  = V_2 ) \wedge p(V_1 ' \ne V_2 ') + \\*
p(V_1  \ne V_2 ) \wedge p(V_1 ' = V_2 ')
\end{MultiLine}

On $pcd_{A - A'}$ \'{e}s la probabilitat del canvi de difer\`{e}ncia a les 
inst\`{a}ncies $I_{1}$ i $I_{2}$ entre els atribut $A$ i $A'$, $V_{1}$ i $V_{2}$ 
s\'{o}n els valors de $I_{1}$ i $I_{2}$ respectivament per aquest atribut i 
$V_{1}'$ i $V_{2}'$ s\'{o}n els valors de l'atribut $A'$. Com que la 
relaci\'{o} entre els valors de l'atribut $A$ i els valors de l'atribut $A'$ no 
s\'{o}n independents entre s\'{\i}, podem rescriure la f\'{o}rmula:

\begin{MultiLine}[9]
pcd_{A - A'}  = p(V_1 ' = V_2 '|V_1  \ne V_2 ) \\*
p(V_1  \ne V_2 ) + \\*
p(V_1 ' \ne V_2 '|V_1  = V_2 )p(V_1  = V_2 )
\end{MultiLine}

Seguint amb el desenvolupament de la f\'{o}rmula, quina \'{e}s la 
probabilitat de que $V_{1}'$ sigui igual a $V_{2}'$ sabent que $V_{1}$ i 
$V_{2}$ eren diferents? Distingim varis casos: si $V_{1}'$ ha canviat 
per\`{o} $V_{2}'$ no, tenim que la probabilitat de que siguin iguals sabent 
que abans no ho eren \'{e}s d`una entre el conjunt de valors possibles que 
podria prendre menys un (el que tenia). Si qui ha canviat \'{e}s $V_{2}'$ 
per\`{o} $V_{1}'$ s'ha quedat igual passaria el mateix. Si tots dos canvien 
llavors la probabilitat de que tinguin el mateix valor \'{e}s igual a la 
probabilitat que el primer en canviar (suposem que ha estat $V_{1}'$) no 
hagi pres el valor que tenia l'altre (en el cas explicat, $V_{2}'$), ja que 
de fer-ho seria impossible que el segon fos igual per la hip\`{o}tesi de que 
tots dos canvien, i de que l'altre passi a prendre el mateix valor, cosa que 
far\`{a} novament en un d'entre els possibles $\vert V\vert -1$ casos que 
pot triar (tots menys el valor que tenia). Com la probabilitat de que un 
valor hagi canviat \'{e}s ps ja tindr\'{\i}em desglossada la primera part 
del sumatori. Ara la pregunta \'{e}s, quina \'{e}s la probabilitat de que 
$V_{1}'$ sigui diferent a $V_{2}'$ sabent que $V_{1}$ i $V_{2}$ eren iguals 
? aquest cas \'{e}s m\'{e}s simple: si tan sols varia una d'elles llavors 
segur que la difer\`{e}ncia varia. Si en canvi varien les dues el que hem de 
veure \'{e}s la probabilitat de que les dues no hagin pres el mateix valor, 
que es pot comprovar que \'{e}s igual a $\vert V \vert - 2$ dividit entre 
$\vert V \vert - 1$, doncs un cop a triat el valor per la primera aquesta 
ser\`{a} la proporci\'{o} de casos en qu\`{e} la segona ser\`{a} diferent. 
Aix\'{\i} doncs, podem rescriure la f\'{o}rmula:

\begin{MultiLine}[10]
pcd_{A - A'}  = \frac{{2\left( {ps\left( {1 - ps} \right)} \right)}}{{\left| V \right| - 1}} + \\*
\frac{{ps^2 \left( {\left| V \right| - 2} \right)}}{{\left( {\left| V \right| - 1} \right)^2 }}p(V_1  \ne V_2 ) + \\*
2\left( {ps\left( {1 - ps} \right)} \right) + \\*
\frac{{ps^2 \left( {\left| V \right| - 2} \right)}}{{\left( {\left| V \right| - 1} \right)}}p(V_1  = V_2 )
\end{MultiLine}

Un cas particular d'aquesta f\'{o}rmula el tenim quan $\vert V \vert $ 
\'{e}s igual a 2 (atributs binaris). En aquest cas, els dos termes que 
multipliquen per una banda a la probabilitat de que $V_{1}$ i $V_{2}$ siguin 
diferents i per l'altre a la probabilitat de que siguin iguals passen a ser 
el mateix, pel que podem treure factor com\'{u} i com les dues probabilitats 
sumen 1 (donats dos valors $V_{1}$ i $V_{2}$ o b\'{e} s\'{o}n iguals o 
b\'{e} s\'{o}n diferents), ens queda quelcom tan simple com:


\begin{MultiLine}[pcd]
pcd_{A - A'} = 2\left( {ps\left( {1 - ps} \right)} \right) = \\
\left( {2ps - 2ps^2} \right)
\end{MultiLine}

Anem a veure ara que passa amb l'increment dels pesos. Per simplificar, 
direm X al factor que est\`{a} multiplicant la probabilitat de que $V_{1}$ i 
V$_{2}$ siguin diferents i Y al factor que multiplica a la de que siguin 
iguals. Tenim:

\begin{MultiLine}[pcw1]
pcw_{A - A'}  = X \cdot p(V_1  \ne V_2 )_{NM}  + \\*
Y \cdot p(V_1  = V_2 )_{NM}  - \\*
( X \cdot p(V_1  \ne V_2 )_{NH}  + \\* 
Y \cdot p(V_1  = V_2 )_{NH} ) 
\end{MultiLine}

En aquesta f\'{o}rmula simplement hem aplicat les idees presentades a les 
anteriors a la f\'{o}rmula que ens serveix per incrementar els pesos: el 
``nearest miss'' t\'{e} una influ\`{e}ncia amb el mateix signe de la 
difer\`{e}ncia (interessa que els ve\"{\i}ns d'altres classes estiguin 
lluny) mentre que al ``nearest hit'' succeeix el contrari. Simplificant (la 
probabilitat de que dues variables siguin iguals \'{e}s 1 menys la 
probabilitat de que siguin diferents) i traient factor com\'{u}:


\begin{MultiLine}[pcw2]
pcw_{A - A'}  = X( p(V_1  \ne V_2 )_{NM}  - \\*
p(V_1  \ne V_2 )_{NH}) + \\*
Y( p(V_1  \ne V_2 )_{NH}  - \\*
p(V_1  \ne V_2 )_{NM} )
\end{MultiLine}

Una primera observaci\'{o} \'{e}s que aquesta f\'{o}rmula, pel cas 
particular presentat abans on els atributs que tractem s\'{o}n binaris 
($\vert  V \vert = 2$), com X=Y i els altres termes es contraresten, ens diu 
que el soroll afegit no afectar\`{a} al pes. Per altres valors de $\vert 
 V \vert $ ens recolzarem en una gr\`{a}fica que ens permetr\`{a} esbrinar 
la import\`{a}ncia de cada terme:

\begin{figure}[H]
\centering
\centering
\includegraphics[width=\columnwidth]{relief1.eps}
  \caption{ps = 0.1, $\vert V \vert =3$ }
\end{figure}

Veiem que a mesura que s'incrementa la relaci\'{o} entre les probabilitats 
de canvi entre els valors de l'atribut original i la seva r\`{e}plica en el 
``nearest hit'' i el ``nearest miss'', tamb\'{e} s'incrementa la 
probabilitat de canvi del pes. Aix\`{o} far\`{a} que el soroll afecti 
m\'{e}s a les variables on aquesta relaci\'{o} \'{e}s gran, \'{e}s a dir, 
per un cant\'{o} a aquelles on la probabilitat de que el valor dels dos 
atributs al ``nearest hit'' sigui diferent sigui alta mentre que al 
``nearest miss'' sigui baixa (per tant a les variables m\'{e}s rellevants), 
i per l'altre a les variables on succeeixi el contrari (per tant a les 
variables m\'{e}s irrellevants, on tan sols hi havia contribucions negatives 
per culpa dels ``nearest hits''). 

La conclusi\'{o} de tot aquest desenvolupament \'{e}s doncs que el soroll 
tendir\`{a} a fer que els pesos s'apropin a zero, incrementant m\'{e}s 
aquells que estaven per sota i decrementant els que estaven per sobre. Anem 
a veure ara quin \'{e}s doncs el paper de la probabilitat de que hi hagi 
soroll (a les f\'{o}rmules presentades, ps).

\begin{figure}[H]
\centering
\centering
\includegraphics[width=\columnwidth]{relief2.eps}
  \caption{ps = 0.2, $\vert V \vert = 3$}
\end{figure}

Pel que fa a l'efecte de ps, veiem com sembla ser que simplement ens 
est\`{a} controlant el rang de la probabilitat de que l'increment de pes 
vari\"{\i}.





Un cop acabat l'estudi sobre la relaci\'{o} entre els pesos d'atributs 
redundants, anem a seguir amb la implicaci\'{o} en sentit contrari que ens
plantejavem a la pregunta 2: quan dues variables tenen el mateix pes, 
podem pensar que el tenen perqu\`{e} s\'{o}n redundants? 

Doncs b\'{e}, 
sembla bastant clar que el suggerit no ser\`{a} cert. Com hem dit abans el 
Relief ens d\'{o}na una mesura de la rellev\`{a}ncia de l'atribut, per la 
qual cosa si acceptem que funciona b\'{e} tamb\'{e} hem d'acceptar que dos 
atributs igualment rellevants i no redundants (serveixen per determinar la 
classe de l'individu en el mateix nombre de casos per\`{o} en casos 
completament disjunts) rebin el mateix pes. En aquest cas amb un 
contraexemple que mostri aquest fet ens valdr\`{a}, i un problema molt 
simple en el que es d\'{o}na aquest fet \'{e}s XOR (o la seva extensi\'{o} 
parity-n): en aquest problema els ``nearest hits'' sempre restaran (els 
individus de la mateixa classe tenen valor diferent en tots els atributs), i 
els ``nearest misses'' sumaran o restaran en funci\'{o} de com fem la tria 
en cas d'empat. Si ho fem aleat\`{o}riament al l\'{\i}mit \'{e}s f\`{a}cil 
veure que l`aportaci\'{o} dels ``nearest misses'' ser\`{a} tamb\'{e} la 
mateixa per tots dos atributs, amb el que tots dos acabaran amb el mateix 
pes.





Anem finalment a donar resposta a la pregunta 3, on se'ns plantejava si la 
redund\`{a}ncia estava afectant al rendiment de l'algorisme. Podr\'{\i}em 
veure primer qu\`{e} passa amb els pesos que d\'{o}na Relief als atributs 
abans i despr\'{e}s d'afegir-ne de redundants a un d'ells, i despr\'{e}s 
explicar el motiu del canvi. Podr\'{\i}em partir per tant del cas emprat a 
1, primer nom\'{e}s amb $A_{2}$ i $A_{3}$ i despr\'{e}s afegint $A_{1}$. El 
que observem emp\'{\i}ricament \'{e}s que el pes de $A_{2}$ ha baixat (responent a 
la pregunta 1 ja hem vist que $A_{1}$ ser\`{a} igual a $A_{2})$. El motiu 
\'{e}s que per l'efecte d'afegir l'atribut redundant pot haver-hi un canvi 
al ``nearest miss'', i si aquest canvi afecta a la variaci\'{o} de la 
difer\`{e}ncia llavors ho fa negativament: 





Imaginem que tenim un individu $R_{1}$ i que el seu ``nearest miss'' 
est\`{a} a dist\`{a}ncia de hamming $d$ d'ell. Si a l'atribut $A_{1}$ 
ambd\'{o}s tenen el mateix valor, llavors no pot ser que afegint $A_{2}$ 
canviem de ve\'{\i} (ja que la dist\`{a}ncia entre els dos es mant\'{e} i 
com era el ve\'{\i} m\'{e}s proper de la mateixa classe ho ha de seguir 
sent). En canvi si els dos tenien diferent valor a l'atribut $A_{1}$, com a 
molt a l'afegir $A_{2}$ ens pot passar que un altre individu $R_{2}$ passi a 
estar a la mateixa dist\`{a}ncia $(d+1)$ que $R_{1}$ (en el cas que abans el 
``nearest miss'' fos l'\'{u}nic a dist\`{a}ncia $d$) o b\'{e} a dist\`{a}ncia 
menor que $R_{1}$ (en el cas que abans el ``nearest miss'' no fos l'\'{u}nic 
a dist\`{a}ncia $d$), per\`{o} el que \'{e}s segur \'{e}s que el nou ``nearest 
miss'' tindr\`{a} el mateix valor a l'atribut $A_{1}$ i que per tant aquest 
fet tindr\`{a} una influ\`{e}ncia negativa en el pes.





De igual forma \'{e}s cert que al ``nearest hit'', passar\`{a} quelcom 
contrari:





Imaginem novament que tenim un individu $R_{1}$ i que el seu ``nearest hit'' 
est\`{a} a dist\`{a}ncia de hamming $d$ d'ell. Si a l'atribut $A_{1}$ els dos 
tenen el mateix valor, llavors no pot ser que afegint $A_{2}$ canviem de 
ve\'{\i} (pel mateix motiu que abans). En canvi, si els dos tenien diferent 
valor a l'atribut $A_{1}$, com a molt l'afegir $A_{2}$ ens pot passar que un 
altre individu $R_{2 }$passi a estar a la mateixa dist\`{a}ncia $(d+1)$ que 
R$_{1}$ (en el cas que abans el ``nearest hit'' fos l'\'{u}nic a 
dist\`{a}ncia $d$) o b\'{e} a dist\`{a}ncia menor que $R_{1}$ (en el cas que 
abans el ``nearest hit'' no fos l'\'{u}nic a dist\`{a}ncia $d$), per\`{o} el 
que \'{e}s segur \'{e}s que el nou ``nearest hit'' tindr\`{a} el mateix 
valor a l'atribut $A_{1}$ i que per tant aquest fet tindr\`{a} una 
influ\`{e}ncia positiva en el pes.





Vist aix\`{o} es podria pensar que ambd\'{o}s influ\`{e}ncies es 
contraresten, per\`{o} \'{e}s evident que a mesura que un atribut \'{e}s 
rellevant les difer\`{e}ncies amb els ve\"{\i}ns de la seva classe haurien 
de tendir a 0 i les difer\`{e}ncies amb els ve\"{\i}ns de les altres classes 
a 1, i aquest fet provoca el que podr\'{\i}em anomenar un ``efecte sostre'' 
a la influ\`{e}ncia dels ``nearest hits'': per molt que anem apropant les 
inst\`{a}ncies dels ve\"{\i}ns m\'{e}s propers de la meva classe en la 
direcci\'{o} de l'atribut que hem ``replicat'' no hi ha variaci\'{o} en la 
difer\`{e}ncia, ja que els ve\"{\i}ns no em penalitzaven abans d'afegir-lo. 
En canvi apropar els ve\"{\i}ns de les altres classes en aquesta 
direcci\'{o}, que abans no em penalitzaven per tenir valors diferents, 
far\`{a} que ara si que em penalitzin. Igualment aquest ``efecte sostre'' 
passar\`{a} a la influ\`{e}ncia dels ``nearest misses'' pels atributs 
irrellevants, ara per\`{o} amb un efecte contrari. El resultat \'{e}s que a 
mesura que afegim variables redundants a una de les existents, el seu pes 
s'anir\`{a} apropant a 0, tal i com ja avan\c{c}aven M. Robnik-\v{S}ikonja, 
I. Kononenko a \cite{DBLP:journals/ml/Robnik-SikonjaK03}.

\section{Compet\`{e}ncia de pesos}

En aquesta secci`{o} introdu\"{\i}m una normalitzaci\'{o} de l'increment dels 
pesos per tal de fer-los competir, o sigui fer que l'increment d'un cert pes 
impliqui la disminuci\'{o} dels altres i veure si aquesta modificaci\'{o} 
t\'{e} algun impacte sobre les q\"{u}estions plantejades a la secci\'{o} 
anterior i en el cas que el tingui si aplicar aquesta modificaci\'{o} ens 
ajuda a detectar les variables redundants.





Seguint el mateix esquema que abans, primer comprovarem si ara l'algorisme 
assigna el mateix pes a les variables redundants o si la competici\'{o} les 
afecta i els seus pesos varien. Com abans, estudiarem l'efecte que pugui 
tenir l'actualitzaci\'{o} del pes que fa Relief per cada individu que ara 
podem pensar que s'assemblar\`{a} a:


\begin{Equation}[13]
w_a (t + 1) = w_a (t) + \frac{\Delta w_a (t)}{\sum\limits_{a \in A} {\Delta 
w_a (t)} }
\end{Equation}





On $A$ representa el conjunt de tots els atributs i $w_a (t)$ \'{e}s el pes 
de l'atribut $a$ en l'instant de temps $t$ i $\Delta w_a (t)$ el seu 
increment en el mateix instant. Aquesta f\'{o}rmula, per\`{o} ens presenta 
un problema que \'{e}s que com que $\Delta w_a (t)$ est\`{a} entre -1 i 1 el 
sumatori podria tenir un valor negatiu i fer canviar el signe de 
l'increment. Per tornar a un increment entre 0 i 1 fem:


\begin{Equation}[14]
w_a (t + 1) = w_a (t) + \Delta 'w_a (t)
\end{Equation}
\begin{Equation}[15]
\Delta 'w_a (t) = 2\left( {\frac{\Delta w_a (t) + 1}{\sum\limits_{a \in A} 
{\Delta w_a (t) + \left| A \right|} }} \right) - 1
\end{Equation}





Aix\'{\i} doncs si $\Delta w_a (t)$ estava entre 0 i 1 $\Delta 'w_a (t)$ 
tamb\'{e} ho estar\`{a} i continuarem mantenint les propietats de 
l'algorisme.





Estudiem doncs qu\`{e} passa ara amb els $\Delta 'w_a (t)$ de dues variables 
redundants. Podem veure que si $\Delta 'w_{a1} (t) = \Delta 'w_{a1} 
(t),\mbox{ }\forall \mbox{t}$ llavors com que els pesos inicials s\'{o}n 
iguals, el pes final dels dos atributs ser\`{a} el mateix, com hem vist que 
passava si no normalitz\`{a}vem. Tamb\'{e} \'{e}s f\`{a}cil adonar-nos que 
aquesta condici\'{o} es complir\`{a} mirant els termes de $\Delta 'w_a (t)$. 
Est\`{a} clar que els factors constants que multipliquen i resten no 
canviaran, a part d'aix\`{o}, el denominador de la divisi\'{o} \'{e}s 
com\'{u} per tots els atributs i al numerador hi trobem $\Delta w_a (t)$ que 
hem demostrat igual per dues variables redundants en la secci\'{o} anterior.





Per tant amb aquesta competici\'{o} d'increments es continua complint que si 
dos atributs s\'{o}n redundants llavors l'algorisme els assigna el mateix 
pes.




Per la pregunta 2, continuem tenint el mateix problema que si no estigu\'{e}ssim 
fent competir els pesos. Si dues variables s\'{o}n igual de rellevants 
per\`{o} en casos diferents (com en el cas de XOR o parity-n) llavors es 
faran les actualitzacions de manera an\`{a}loga al cas sense competici\'{o} 
i la \'{u}nica cosa que variar\`{a} ser\`{a} el valor final del pes, 
per\`{o} tamb\'{e} acabaran tots els atributs igual de rellevants amb el 
mateix pes.





Pel qu\`{e} fa a la pregunta 3, tamb\'{e} podem veure com la resposta no 
canviar\`{a} donat que la relaci\'{o} entre les actualitzacions de pesos de 
les variables no canvia donat que nom\'{e}s hem afegit termes que s\'{o}n 
constants per tots els atributs i per tant no n'estem perjudicant ni 
potenciant cap respecte els altres en cap actualitzaci\'{o} de pesos. 
Aix\'{\i} doncs les mateixes premisses que hem utilitzat abans ens s\'{o}n 
v\`{a}lides per dir que amb la introducci\'{o} d'una variable redundant a 
una altra provoquem que els pesos de les dues variables s'acostin m\'{e}s al 
0 que el pes de la variable inicial. Aix\'{\i} doncs, la competici\'{o} de 
pesos tampoc ha aconseguit que la introducci\'{o} de variables redundants no 
modifiqu\'{e}s el pes de la variable original abans de introduir-les.

\section{Conclusions}

Pel qu\`{e} fa a l'estudi de la m\`{e}trica, caldria estudiar millor les 
propietats de la HVDM per intentar predir en quins problemes ens 
interessar\`{a} aplicar-la i en quins no. Sembla clar que en problemes amb 
atributs dicot\`{o}mics aquesta mesura no \'{e}s tan interessant donat que 
intenta donar dist\`{a}ncies diferents entre els diferents valors d'un 
atribut, per\`{o} est\`{a} clar que si nom\'{e}s en tenim dos la 
dist\`{a}ncia ser\`{a} sempre 0 o un altre valor entre 0 i 1 per\`{o} no ens 
est\`{a} aportant molta m\'{e}s informaci\'{o}. 





A m\'{e}s les proves realitzades han estat amb conjunts de dades 
sint\`{e}tics, tots amb atributs binaris i molts amb distribucions de 
probabilitat de cada valor de cada atribut uniformes en respecte a la 
classe. En definitiva, sembla ser que els pitjors problemes per la VDM. 
Aix\'{\i} doncs nom\'{e}s podem dir que caldria un estudi m\'{e}s intensiu i 
m\'{e}s exhaustiu de la seva utilitat.





Les preguntes a les respostes plantejades pel que fa refer\`{e}ncia a la 
redund\`{a}ncia, ens porten a la conclusi\'{o} que caldria trobar alguna 
forma per tal de fer m\'{e}s robust aquest algorisme enfront aquest problema 
: a la resposta a 1 ja hem vist la forma amb qu\`{e} el soroll afecta als 
pesos, negativa pels nostres interessos; a 2 hem vist com el fet de tenir 
pesos iguals (malgrat no haver soroll) no significa que les variables fossin 
redundants, fet que juntament amb l'anterior ens fa veure que sense cap 
modificaci\'{o} no tenim forma de detectar aquestes relacions; a 3 hem vist 
com, a m\'{e}s a m\'{e}s, aquesta redund\`{a}ncia tamb\'{e} afecta 
negativament al rendiment de l'algorisme (com passava amb el soroll a 1, a 
mesura que afegim redund\`{a}ncia anem fent caure els pesos a 0, potenciant 
els atributs m\'{e}s irrellevants i perjudicant als rellevants i en 
definitiva empobrint el rendiment de l'algorisme.





Per solucionar aix\`{o} hem intentat fer competir els pesos per intentar que 
algunes, idealment totes excepte una, de les variables redundants prenguin 
valors baixos mentre que d'altres prenguin els valors reals. De totes 
maneres, la proposta d'aquest document ha demostrat ser bastant inn\`{o}cua 
al funcionament de l'algorisme. De fet a \cite{DBLP:journals/ml/Robnik-SikonjaK03} ja 
apuntaven que els pesos ja s'estaven normalitzant impl\'{\i}citament en 
certa manera en el funcionament normal de l'algorisme cosa que ja fa pensar 
que la normalitzaci\'{o} dels increments no aporta massa res.

\section{Treball futur}

Vistes les idees aplicades en altres algorismes com en algorismes de ``lazy 
learning'' o com en la mateixa VDM de ponderaci\'{o} de difer\`{e}ncies 
entre atributs a l'hora de calcular les dist\`{a}ncies en funci\'{o} d'un 
pes proporcional a l'estimaci\'{o} de la rellev\`{a}ncia d'aquell atribut, i 
partint de la base que el nostre algorisme intenta predir justament aquesta 
rellev\`{a}ncia, podr\'{\i}em utilitzar el c\`{a}lcul parcial d'aquesta 
magnitud que obtenim al tractar cada individu per ponderar el c\`{a}lcul de 
dist\`{a}ncies en els individus restants. Podr\'{\i}em pensar tamb\'{e} en 
algun factor de temperatura que faci que en les primeres iteracions, 
assumint que el c\`{a}lcul parcial dels pesos \'{e}s poc fiable, el tingui 
menys en compte a l'hora de ponderar les dist\`{a}ncies.





Un aspecte clar a treballar seria millorar la robustesa de l'algorisme a la 
redund\`{a}ncia. Ja hem vist que l'algorisme t\'{e} dos problemes b\`{a}sics 
amb la redund\`{a}ncia. Es fa dif\'{\i}cil de detectar quan hi ha soroll 
entre els atributs redundants donat que l'algorisme els assigna pesos 
semblants per\`{o} no prou, i a m\'{e}s assigna pesos iguals a atributs no 
redundants. I per altra banda, l'exist\`{e}ncia d'atributs redundants a un 
altre que \'{e}s rellevant fa que tots ells obtinguin una ponderaci\'{o} no 
tan elevada com els pertocaria si nom\'{e}s en tingu\'{e}ssim un. Aix\'{\i} 
doncs, seria molt interessant trobar alguna modificaci\'{o} de l'algorisme 
per tal de tractar millor la redund\`{a}ncia.





Inicialment es podria intentar solucionar pels casos de dos atributs 
redundants entre s\'{\i}, cosa que a priori sembla m\'{e}s senzilla. A 
m\'{e}s, hem de tenir en compte que Relief tracta els atributs 
individualment i, per tant, sembla complicat modificar-lo de manera que 
acabi detectant redund\`{a}ncies complexes d'un atribut amb un conjunt 
d'atributs a no ser que es faci alguna modificaci\'{o} important a 
l'algorisme per tal de treballar ja no amb un atribut individual sin\'{o} en 
algun cas amb un conjunt d'atributs.





Tamb\'{e} seria interessant continuar estudiant l'efecte que t\'{e} sobre 
l'algorisme la utilitzaci\'{o} de m\`{e}triques diferents a l'hora de 
calcular les dist\`{a}ncies entre individus o les difer\`{e}ncies entre els 
valors dels atributs. Per comen\c{c}ar, acabar d'estudiar la 
incorporaci\'{o} de la VDM i m\'{e}s enll\`{a} d'aix\`{o} buscar altres 
m\`{e}triques que ens puguin ser \'{u}tils o fins i tot veure si pot ser 
interessant utilitzar-ne una per calcular la dist\`{a}ncia i una altra per 
la difer\`{e}ncia que tinguin en compte aspectes diferents com \'{e}s el cas 
de HEOM i HVDM.





Una altra l\'{\i}nia de treball podria ser donar m\'{e}s suport emp\'{\i}ric 
a les aportacions te\`{o}riques d'aquest document. Les proves realitzades 
com hem esmentat anteriorment eren totes amb conjunts de dades sint\`{e}tics 
que, tot i aportar molta informaci\'{o} donat el nostre extens coneixement 
sobre el domini i dels resultats esperats, poden tenir algun aspecte molt 
exagerat o allunyat dels valors habituals en problemes reals i donar-nos una 
visi\'{o} excessivament optimista (o pessimista) dels resultats obtinguts. 
Aix\`{o} sembla clar en el cas de la VDM, que amb les proves realitzades 
obtenia sempre resultats pitjors per\`{o} sobre el paper i tamb\'{e} en la 
bibliografia sembla ser prou \'{u}til.

\bibliography{relief}

\end{multicols}



\end{document}