Propiedades de poda¶
Borrador
Esta matriz sale de lo que ya leímos en artículos y código. Las celdas con «?» no están verificadas. Cada propiedad tendrá su propia página con la definición, el paso del ejemplo central donde actúa, el contador del motor único que la mide y la ablación que estima su efecto (pasos 4 y 5 de la Meta 2).
Las propiedades¶
Todas se explican sobre la búsqueda en profundidad que arma un conjunto de columnas \(S\) agregando una columna a la vez.
| Id | Propiedad | Qué hace |
|---|---|---|
| P1 | Fila crítica | Descarta \(S \cup \{v\}\) si alguna columna de \(S\) se queda sin fila que solo ella cubra. |
| P2 | Contribución | Solo agrega \(v\) si cubre alguna fila todavía no cubierta. |
| P3 | Fila pivote en la raíz | En el primer nivel, solo ramifica por las columnas de la fila con menos unos. |
| P4 | Fila pivote en cada nodo | En cada nodo, solo ramifica por las columnas candidatas de la fila no cubierta con menos candidatas. |
| P5 | Fila pivote por profundidad (LV) |
Cota fija, calculada antes de la búsqueda, de hasta qué columna se puede ramificar según la profundidad. |
| P6 | Filtrado completo | Al bajar a un hijo, quita de toda la lista de candidatas las columnas que ya no pueden extender. |
| P7 | Filtrado perezoso | Solo prueba las columnas de la fila pivote; las demás se descartan cuando les toca. |
| P8 | Fusión de columnas iguales | Trabaja con una columna por grupo de columnas idénticas y multiplica al final. |
| P9 | Eliminación de huecos | Salta posiciones de la lista que no pueden dar testores (gaps). |
| P10 | Núcleo | Agrega de entrada las columnas de las filas con un solo 1. |
| P11 | Sin repetición por exclusión de hermanos | Al probar la i-ésima columna de la fila pivote, saca de las candidatas a las i−1 anteriores. |
Algoritmo × propiedad¶
✓ tiene la propiedad, — no la tiene, ? sin verificar.
| P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8 | P9 | P10 | P11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| BR Lias-Rodríguez y Pons-Porrata, 2009BR: A New Method for Computing All Typical Testors Alberto Lias-Rodríguez; Aurora Pons-Porrata Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications (CIARP 2009), 5856, 433–440, 2009 Resumen: Resumen pendiente.Nuestra nota: BR original. Reordena filas y columnas una sola vez, en la raíz. Compara solo con LEX y CT-EXT.Ficha completa → |
? | ✓ | ✓ | — | — | ? | — | ? | — | — | — |
| fast-BR Lias-Rodríguez y Sanchez-Diaz, 2013An Algorithm for Computing Typical Testors Based on Elimination of Gaps and Reduction of Columns Alberto Lias-Rodríguez; Guillermo Sanchez-Diaz International Journal of Pattern Recognition and Artificial Intelligence, 27(8), 2013 https://doi.org/10.1142/S0218001413500225 Resumen: Resumen pendiente.Nuestra nota: fast-BR. Fila pivote solo en la raíz; fusiona columnas iguales y elimina huecos. Leído por las partes de preproceso e ideas centrales.Ficha completa → |
✓ | ✓ | ✓ | — | — | ✓ | — | ✓ | ✓ | — | — |
| GCreduct Rodríguez-Diez et al., 2018 (GCreduct)A fast hill-climbing algorithm for computing all reducts of a decision system (GCreduct) Vladímir Rodríguez-Diez; José Fco. Martínez-Trinidad; Jesús A. Carrasco-Ochoa; Manuel S. Lazo-Cortés Information Sciences, 2018 https://doi.org/10.1016/j.ins.2017.12.027 Resumen: Resumen pendiente.Nuestra nota: Artículo propio. Título provisional en esta ficha: falta copiar el título, volumen y páginas de la versión publicada.Ficha completa → |
— | ✓ | ✓ | — | — | — | — | ✓ | ✓ | — | — |
| RegularSearch Lefebre-Lobaina y Ruiz-Shulcloper, 2023RegularSearch Jairo A. Lefebre-Lobaina; José Ruiz-Shulcloper Information Sciences, 649, 119665, 2023 Resumen: Resumen pendiente.Nuestra nota: Título provisional en esta ficha: falta copiar el título completo. Leído completo salvo figuras. Código MIT en github.com/J41R0/RegularSearch.Ficha completa → |
✓ | ✓ | ✓ | — | ✓ | — | — | — | — | — | — |
| RoPM Pino Gómez et al., 2021 (RoPM)RoPM J. Pino Gómez; Yenny Villuendas-Rey; others IEEE Access, 9, 128220–128231, 2021 https://doi.org/10.1109/ACCESS.2021.3112385 Resumen: Resumen pendiente.Nuestra nota: Título y autores provisionales en esta ficha. Compara solo con fast-BR y GCreduct. Parece usar la fila de menos unos como pivote (inferencia, sin código).Ficha completa → |
? | ? | ✓ | ? | — | ? | ? | ? | ? | ? | ? |
| RCC-MAS González-Díaz et al., 2025 (RCC-MAS)RCC-MAS Y. González-Díaz; others Machine Learning, 114, 168, 2025 https://mlanthology.org/mlj/2025/gonzalezdiaz2025mlj-rccmas Resumen: Resumen pendiente.Nuestra nota: Título y autores provisionales en esta ficha. Seguimos los Algoritmos 1-5; el Algoritmo 3 impreso pierde constructos.Ficha completa → |
✓ | ✓ | ✓ | ✓ | — | — | ✓ | — | — | ✓ | ✓ |
| RUNC Djukova y Prokofjev, 2015Asymptotically optimal dualization algorithms E. V. Djukova; P. A. Prokofjev Computational Mathematics and Mathematical Physics, 55(5), 891–905, 2015 https://doi.org/10.1134/S0965542515050103 Resumen: Resumen pendiente.Nuestra nota: Leído completo (traducción al inglés). Es la traducción del artículo de 2014 en Mach. Learn. Data Anal.; no son dos conjuntos de experimentos.Ficha completa → |
✓ | ✓ | — | — | — | ✓ | — | ? | — | — | ✓ |
| RUNC-M Djukova y Prokofjev, 2015Asymptotically optimal dualization algorithms E. V. Djukova; P. A. Prokofjev Computational Mathematics and Mathematical Physics, 55(5), 891–905, 2015 https://doi.org/10.1134/S0965542515050103 Resumen: Resumen pendiente.Nuestra nota: Leído completo (traducción al inglés). Es la traducción del artículo de 2014 en Mach. Learn. Data Anal.; no son dos conjuntos de experimentos.Ficha completa → |
✓ | ✓ | ✓ | ✓ | — | ✓ | — | ? | — | — | ✓ |
| MMCS Murakami y Uno, 2014Efficient algorithms for dualizing large-scale hypergraphs Keisuke Murakami; Takeaki Uno Discrete Applied Mathematics, 170, 83–94, 2014 https://doi.org/10.1016/j.dam.2014.01.012 https://arxiv.org/abs/1102.3813 Resumen: Resumen pendiente.Nuestra nota: Leída la versión final (DAM) y arXiv 1102.3813v2. La numeración de secciones cambia: en DAM la elección de la hiperarista mínima es §3.5 y la poda es §3.6.Ficha completa → |
✓ | ✓ | ✓ | ✓ | — | — | ✓ | — | — | — | ✓ |
br-pivot (nuestro) |
✓ | ✓ | ✓ | ✓ | — | ✓ | — | ✓ | ✓ | — | ? |
Notas:
- P1 en GCreduct. No poda por fila crítica durante la búsqueda: comprueba la tipicidad cuando ya encontró un testor.
- P3 en RUNC. Toma la primera fila no cubierta en orden fijo, no la de menos unos.
- P8 en MMCS. El algoritmo del artículo no fusiona columnas; el programa SHD de Uno hace reducción de datos, pero no sabemos si fusiona columnas iguales.
- P11 en BR y fast-BR. No la necesitan: recorren la lista en orden creciente, así que cada conjunto aparece una sola vez.
- RCC-MAS es MMCS más P10 (D3).
Qué dice la medición¶
- P4 es la propiedad decisiva. Agregarla a fast-BR lo lleva de agotar el tiempo a menos de 2,6 veces de MMCS (D1).
- P7 gana a P6 a igualdad de implementación, en las 20 matrices medidas (D4).
- P1 sin P3 ni P4 no sirve: SHD sin fila pivote agota el límite en 10 de 12 matrices.
- P5 poda menos que P4: RegularSearch, con la implementación corregida, queda en la clase de fast-BR (D5).