RCC-MAS y MMCS recorren el mismo árbol de búsqueda¶
Nota del 17 de noviembre de 2026. Sostiene con un argumento formal lo que se midió en experiments/constructs/: nuestra implementación de RCC-MAS evalúa los mismos candidatos que nuestro MMCS.
Enunciado¶
Sea M una matriz básica con núcleo K: las columnas de las filas con un solo 1. Se comparan dos algoritmos:
- RCC-MAS tal como lo describen los Algoritmos 1-5 de González-Díaz y otros (Machine Learning 114:168, 2025), con dos cambios. El Algoritmo 3 corrige el valor inicial de
numb_ones: arranca por encima de |CA|, no en |CA|. Los Algoritmos 2 y 5 se leen como se explica enjava/src/mhs/RccMas.java. - MMCS de Murakami y Uno (2014). Elige la fila no cubierta con menos columnas candidatas y, en empate, la de menor índice. Es lo que hace
mhs.Mmcs.
Proposición. Ambos algoritmos devuelven los mismos conjuntos. Hay una biyección entre sus evaluaciones de candidatos, salvo |K| evaluaciones que solo hace MMCS. Si se cuenta un candidato por cada conjunto A ∪ {v} cuya irreducibilidad se prueba, entonces:
\mathrm{cand}_{\mathrm{MMCS}}(M) = \mathrm{cand}_{\mathrm{RCC\text{-}MAS}}(M) + |K|
Lo único que cambia es el orden en que se visitan los hermanos: MMCS los recorre en orden creciente de columna y RCC-MAS en orden decreciente.
Correspondencia de conceptos¶
| RCC-MAS | MMCS | Diferencia |
|---|---|---|
| A, atributos elegidos | S | ninguna |
| Z, filas en cero de M^A | uncov(S) | ninguna |
| RI_a | crit(a, S) | ninguna (Lema 2) |
| CA, atributos candidatos | CAND | RCC-MAS descarta columnas que ya no cubren ninguna fila no cubierta; MMCS las conserva (Lema 3) |
| MAS | e ∩ CAND, con e la fila elegida | ninguna (Lema 4) |
| attrList | CAND \ e, restringido a columnas que cubren alguna fila no cubierta | ver Lema 3 |
| isIrreducible (Alg. 4) | condición crit | ninguna |
| núcleo (Alg. 1) | no existe | MMCS lo recorre como |
Lemas¶
Lema 1 (núcleo). En una matriz básica, una columna del núcleo tiene un solo 1, el de su fila unitaria. Si otra fila tuviera un 1 en esa columna, sería superconjunto de la fila unitaria y la absorción la habría eliminado.
En la raíz de MMCS, CAND son todas las columnas y la cantidad de candidatos de una fila es su número de unos. Las filas unitarias tienen 1 y las demás al menos 2, así que MMCS elige la primera fila unitaria {k₁}. Evalúa un solo candidato, k₁, que pasa la condición crit porque S está vacío. Al descender, solo k₁ sale de CAND, y k₁ no aparece en ninguna otra fila, así que el número de candidatos de las demás filas no cambia. MMCS elige entonces la siguiente fila unitaria, y así sucesivamente.
Tras |K| niveles de un solo hijo y |K| candidatos, el estado es S = K, uncov = filas que K no cubre y CAND = C \ K. Las columnas del núcleo nunca pierden su fila crítica, porque solo ellas la cubren. Ese estado es la raíz de RCC-MAS (Algoritmo 1, líneas 5 y 9) con A = ∅ y el núcleo guardado aparte. Si uncov ya está vacío, los dos devuelven solo K.
Lema 2 (RI = crit). El Algoritmo 5 calcula RI_v = Z ∩ col(v) y luego RI_a ← RI_a \ col(v) para cada a ∈ A. Es la actualización de crit en MMCS: las filas críticas de v son las no cubiertas que v cubre, y las de cada a pierden las que v también cubre. Las dos parten de conjuntos vacíos, así que por inducción RI_a = crit(a) en cada nodo.
La prueba del Algoritmo 4 (cada a ∈ A conserva alguna fila de RI_a fuera de col(v)) es entonces exactamente la condición crit de MMCS.
El núcleo no necesita RI. Como sus columnas no aparecen en ninguna fila de Z, nunca quitan filas críticas a otras columnas ni se las quitan a ellas.
Lema 3 (columnas que ya no contribuyen). Llamemos U a la unión de las filas no cubiertas en un nodo. Una columna u de CAND con col(u) ∩ U = ∅ no influye en nada debajo de ese nodo: U solo se achica al descender, así que u nunca aparece en e ∩ CAND para una fila no cubierta e. Por eso no cuenta para elegir la fila ni se ramifica sobre ella.
Para comparar los dos algoritmos basta con su parte efectiva. Sea CAND* = CAND ∩ U en MMCS y CA* = CA ∩ U en RCC-MAS. El Algoritmo 3 arma attrList solo con columnas que tienen un 1 en alguna fila de Z, así que RCC-MAS descarta justo las columnas que MMCS conserva sin usarlas.
Lema 4 (misma fila elegida). Para una fila e no cubierta, e ∩ CAND = e ∩ CAND, porque toda columna de e está en U. Si CAND = CA*, los dos cuentan lo mismo en cada fila.
Los dos recorren las filas en orden de índice y se quedan con la primera de cuenta mínima: MMCS con < desde infinito y el Algoritmo 3 corregido con < desde |CA|+1. Eligen la misma fila, y por lo tanto MAS = e ∩ CAND.
Con el valor impreso, numb_ones = |CA|, si toda fila tiene |CA| unos en CA no se elige ninguna y la MAS queda vacía. Ahí se separan, y RCC-MAS pierde soluciones.
Lema 5 (misma poda por fila sin candidatos). MMCS abandona el nodo en cuanto encuentra una fila no cubierta sin candidatos. El Algoritmo 3 hace lo mismo (líneas 13-14). En ese caso ninguno de los dos evalúa candidatos.
Prueba de la proposición¶
Por el Lema 1, después del prefijo del núcleo los dos parten del mismo estado (S, uncov, crit, CAND*). La inducción es sobre la profundidad. Supongamos que un nodo de MMCS y uno de RCC-MAS tienen el mismo estado efectivo:
S = A,\quad \mathrm{uncov} = Z,\quad \mathrm{crit} = RI,\quad \mathrm{CAND}^{*} = \mathrm{CA}^{*}
- Poda. Por el Lema 5, los dos podan o ninguno.
- Fila elegida. Por el Lema 4, los dos eligen la misma fila e y MAS = e ∩ CAND = {v₁ < … < v_k}.
- Candidatos y hojas. Para cada vᵢ, los dos evalúan un candidato con la misma prueba (Lema 2) y aceptan o rechazan igual. Si vᵢ cubre todo uncov, los dos reportan S ∪ {vᵢ}. MMCS lo hace en un nodo hijo y RCC-MAS sin descender, pero ninguno evalúa candidatos ahí.
- Candidatos del hijo de vᵢ.
- MMCS saca e ∩ CAND de CAND antes del ciclo y devuelve cada v al terminar su rama. Como recorre en orden creciente, el hijo de vᵢ recibe (CAND \ e) ∪ {v₁, …, v_{i−1}}.
- RCC-MAS usa
removeLasty recorre en orden decreciente, así que lo que queda de la MAS al procesar vᵢ es {v₁, …, v_{i−1}}. El hijo recibe attrList ∪ {v₁, …, v_{i−1}}, con attrList = (CA ∩ U) \ MAS. - Al intersecar con el U del hijo, que está contenido en U, las dos partes efectivas coinciden.
- Resto del estado del hijo. S ∪ {vᵢ}, uncov \ col(vᵢ) y crit actualizado coinciden con A ∪ {vᵢ}, Z \ col(vᵢ) y RI actualizado (Lema 2).
Así, cada nodo tiene los mismos hijos con el mismo estado efectivo, y la biyección se extiende a todo el árbol. Los dos visitan los hijos de un nodo en orden inverso, pero el subárbol de cada hijo depende solo de su estado, no del orden de visita. Sumando, hay un candidato por cada vᵢ evaluado en ambos árboles, más los |K| del prefijo de MMCS. ∎
Verificación empírica¶
- En las seis matrices de
experiments/constructs/results/(constructos y reductos de flags, dermatology y lung-cancer) el núcleo es vacío y los candidatos son idénticos: 547.688, 527.876, 49.983.120, 108.130, 244.812 y 17.351.510. experiments/constructs/check_kernel_offset.pyprueba la predicción cand(MMCS) − cand(RCC-MAS) = |K| en 296 matrices aleatorias, 210 de ellas con núcleo no vacío. Se cumple en todas.- Una predicción que fallara refutaría el argumento o revelaría una diferencia entre el código y la descripción. No falló ninguna.
Alcance y límites¶
- Qué se demuestra. El argumento es sobre el pseudocódigo con la corrección del Algoritmo 3 y las lecturas indicadas. No dice nada del programa de los autores. Su implementación puede usar otras estructuras de datos, desempatar distinto o tener la errata. Por eso hace falta su código.
- Desempate. La equivalencia exacta requiere que los dos elijan la misma fila en empate. Si RCC-MAS desempatara de otra forma, sería MMCS con otra regla de desempate: los árboles podrían diferir en tamaño, pero el método sería el mismo.
- Contadores. El contador de nodos no coincide: MMCS cuenta como nodo cada hoja reportada y RCC-MAS no desciende para reportar. Por eso la comparación se hace con candidatos.
- Comparación con SHD. MMCS aquí es el algoritmo del artículo de Murakami y Uno, no el programa SHD de Uno, que añade reducción de datos y otras estructuras. Sus candidatos no se comparan.
- Diferencia en tiempo. La diferencia de tiempo medida (RCC-MAS entre 1,7 y 3 veces más lento) viene de la implementación:
RccMascopia arreglos en cada nodo yMmcsreutiliza buffers por profundidad. No es una diferencia del método. - Qué aporta RCC-MAS. El cálculo previo del núcleo es lo único propio de RCC-MAS respecto de MMCS. Ahorra |K| candidatos, y además la verificación de irreducibilidad ignora las columnas del núcleo. Es una mejora menor y no cambia el orden de complejidad.