Descubrimientos¶
Esta página reúne lo que el proyecto ha encontrado hasta ahora, del 16 al 20 de noviembre de 2026. Para cada hallazgo dice qué se encontró, con qué evidencia, qué falta y si, en nuestra opinión, tiene cuerpo para una publicación aparte del artículo principal. Esa última valoración es una propuesta para que la discutan los asesores, no una conclusión.
Etiquetas: hecho medido o leído del código; inferencia interpretación sin prueba; publicable aparte, quizá aparte, sección del artículo.
Resumen¶
| # | Descubrimiento | Evidencia | ¿Aparte? |
|---|---|---|---|
| D1 | La fila pivote elegida en cada nodo explica casi toda la distancia entre los algoritmos de testores y los de minimal hitting sets | Ablación dentro de fast-BR | Sección central del artículo |
| D2 | Varios algoritmos de las tres comunidades recorren el mismo árbol de búsqueda: son redescubrimientos | Demostración formal y conteos idénticos | Sí: candidato fuerte |
| D3 | RCC-MAS, publicado en 2025, es MMCS más el núcleo, y su Algoritmo 3 impreso pierde soluciones | Demostración y 296 matrices | Quizá: comentario o nota corta |
| D4 | A igualdad de implementación, la poda perezosa gana al filtrado completo, y en matrices muy ralas las listas ganan a los bitsets; la ventaja de RUNC-M en C++ viene de la implementación | Motor único con tres ejes | Quizá: con el banco ampliado |
| D5 | El código publicado de RegularSearch cuesta de 10 a 20 veces su algoritmo, y el algoritmo queda en la clase de fast-BR | Reescritura con el mismo árbol | Sección del artículo |
| D6 | Cinco errores de conteo en programas publicados del grupo | 442 matrices, referencia independiente | Sección del artículo |
| D7 | El orden de columnas pesa mucho solo en matrices pequeñas, por un desempate | Piloto de 960 corridas | Sección secundaria |
| D8 | Las matrices sintéticas publicadas no son básicas estrictas | 525 de 663 | Nota dentro del artículo |
D1. La fila pivote en cada nodo es el ingrediente decisivo¶
Hallazgo
Los algoritmos de testores (BR, fast-BR, GCreduct) ya usan la «fila pivote»: ponen arriba la fila con menos unos y solo ramifican por sus columnas. Pero lo hacen una sola vez, en la raíz 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 →; 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 →. 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 → y 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 → repiten esa elección en cada nodo de la búsqueda, con la fila que en ese momento tiene menos candidatos. Si a fast-BR se le cambia solo eso, deja de agotar el tiempo y queda a menos de 2,6 veces de MMCS.
hecho mhs.Br reescribe fast-BR con tres modos que solo cambian dónde se ramifica: root (como el original), bound (corta sin reordenar) y pivot (fila mínima en cada nodo). Validados por conjunto de reductos en 300 matrices.
| Matriz | fast-BR original | br-pivot | MMCS |
|---|---|---|---|
| soybean | 3 189 candidatos por reducto | 3,7 | 1,4 |
| dermatology | 196 | 3,4 | 1,4 |
| student-mat | no termina en 30 s | 2,7 s | 1,9 s |
| sintética, densidad 0,17 | no termina | 1,8 s | 0,7 s |
Dos lecturas más, también medidas: reordenar importa, no solo cortar (bound queda de 2 a 20 veces por encima de pivot), y la regla «fila con menos candidatos» no es un detalle (con la primera fila no cubierta, MMCS pasa de 4,3 a 166 candidatos por reducto en la sintética de 0,17).
inferencia La regla de la tesis de 2022 era la idea correcta aplicada solo en el primer nivel. Eso da al artículo una narrativa honesta: no «nuestros algoritmos pierden», sino «la heurística que ya usábamos explica la diferencia cuando se aplica en cada nivel».
Lo que no es nuevo: br-pivot es RUNC-M reconstruido desde fast-BR; no se presenta como algoritmo nuevo.
¿Publicable aparte? sección del artículo
No. Es el argumento central del artículo principal. Separarlo dejaría al artículo sin explicación de sus propios resultados.
Detalle: Por qué MMCS es más rápido.
D2. Tres comunidades, un solo árbol de búsqueda¶
Hallazgo
Varios algoritmos publicados como distintos, en comunidades que no se citan entre sí, recorren exactamente el mismo árbol de búsqueda o difieren en una sola regla. La diferencia de tiempo entre ellos es de implementación, no de método.
| Par | Relación | Evidencia |
|---|---|---|
| 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 → y 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 → |
Mismo árbol; RCC-MAS ahorra solo las columnas del núcleo | hecho demostración formal y 296 matrices (D3) |
mhs.RegSearch y RegularSearch Lefebre-Lobaina y Ruiz-Shulcloper, 2023RegularSearchJairo 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 → |
Mismo árbol; nodos idénticos a los hits del código del autor |
hecho 453 de 453 matrices |
| fast-BR con pivote por nodo y 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 → |
Misma estrategia: fila mínima y filtrado de toda la lista | hecho por lectura; nodos cercanos, no idénticos |
crit de MMCS y la compatibilidad de columnas de Djukova (1977) |
Misma prueba, con 34 años de diferencia | hecho lo dicen Djukova y Prokofjev; lo confirmamos en el código |
Exclusión de fast-BR y crit de MMCS |
Misma prueba | hecho lectura del código |
LV de RegularSearch y la fila pivote |
LV es un pivote estático por profundidad |
hecho lectura del código |
Además, la encuesta de referencia de minimal hitting sets Gainer-Dewar y Vera-Licona, 2017The minimal hitting set generation problem: algorithms and computation
Andrew Gainer-Dewar; Paola Vera-Licona
SIAM Journal on Discrete Mathematics, 31(1), 2017
https://doi.org/10.1137/15M1055024
https://arxiv.org/abs/1601.02939
Resumen: Resumen pendiente.Nuestra nota: Encuesta y banco de pruebas con 17 implementaciones. No incluye a Djukova, RUNC ni testores.Ficha completa → no menciona a Djukova, RUNC ni los testores, y la revisión de algoritmos de testores Sánchez-Díaz et al., 2023A review of algorithms to computing irreducible testors applied to feature selection
Guillermo Sánchez-Díaz; Manuel S. Lazo-Cortés; Carlos A. Aguirre-Salado; Ivan Piza-Dávila; Juan P. García-Contreras
Artificial Intelligence Review, 56, 2023
https://doi.org/10.1007/s10462-022-10162-z
Resumen: Resumen pendiente.Nuestra nota: Revisión de algoritmos de testores. No cita a Murakami ni a Uno.Ficha completa → no cita a Murakami ni a Uno.
¿Publicable aparte? candidato fuerte
opinión Sí, y es probablemente el resultado de más valor a largo plazo. Un artículo de encuesta y taxonomía («las mismas ideas en tres comunidades») con:
- el diccionario de equivalencias entre vocabularios;
- la matriz algoritmo × propiedad de poda (Propiedades de poda);
- las equivalencias demostradas de esta tabla;
- el ejemplo central que recorre cada algoritmo sobre la misma matriz.
Encaja mejor en una revista de revisión (por ejemplo Artificial Intelligence Review, donde salió la revisión de testores) que en un congreso de 12 páginas. El artículo para IJCRS se quedaría con los experimentos y la ablación.
Riesgo: que se lea como fragmentar un mismo trabajo. Para evitarlo, cada artículo necesita una pregunta distinta: el de IJCRS, «¿quién gana y por qué?»; la encuesta, «¿qué es igual y qué es distinto?».
Pregunta a los asesores: ¿dos artículos, o la disección dentro del principal?
D3. RCC-MAS es MMCS más el núcleo, y su pseudocódigo pierde soluciones¶
Hallazgo
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 →, publicado en Machine Learning en 2025, recorre el mismo árbol que MMCS. Lo único propio es calcular antes el núcleo (las columnas de las filas con un solo 1), que ahorra exactamente |K| candidatos. Además, el Algoritmo 3 tal como está impreso arranca un contador en |CA| en vez de |CA| + 1. Cuando toda fila tiene |CA| unos en CA, no elige ninguna fila y pierde soluciones.
hecho Proposición con cinco lemas: candidatos de MMCS = candidatos de RCC-MAS + |K|. Se cumple en las seis matrices de constructos (núcleo vacío, candidatos idénticos) y en 296 aleatorias, 210 de ellas con núcleo no vacío. La opción -asprinted de mhs.RccMas reproduce el error.
Límite: el argumento es sobre el pseudocódigo, no sobre el programa de los autores, que no tenemos.
¿Publicable aparte? quizá: nota o comentario
opinión Hay material para una nota corta: la equivalencia, el contraejemplo del Algoritmo 3 y la verificación. No sabemos si Machine Learning acepta comentarios. Alternativas: incluirlo en la encuesta de D2, o escribir a los autores antes de cualquier publicación.
Pregunta a los asesores: ¿conocen a los autores? ¿Les escribimos primero?
Detalle: RCC-MAS y MMCS, mismo árbol.
D4. Algoritmo contra implementación: el motor único¶
Hallazgo
Comparar programas distintos mezcla dos cosas: la estrategia de búsqueda y el costo de cada operación. mhs.core es un solo motor con tres ejes intercambiables: representación (bitset o lista), elección de fila (mínima o primera) y manejo de candidatos (perezoso como MMCS o filtrado completo como RUNC-M). Con todo lo demás igual: la poda perezosa gana al filtrado en las 20 matrices, y la fila mínima gana mucho a la primera en matrices ralas. La ventaja de 2 a 5 veces del RUNC-M en C++ de Prokofyev sobre nuestro MMCS no sale de la estrategia, sino de la implementación.
hecho Las 8 configuraciones coinciden por conjunto de reductos con la referencia en 453 matrices. Ejemplo, sintética de densidad 0,17: perezoso 744 ms contra filtrado 1 730 ms. El filtrado prueba de 3 a 4 veces más extensiones a cambio de solo 5 % menos nodos.
inferencia Que la ventaja de ppdual sea de implementación es inferencia: falta reproducir su costo por candidato en Java o instrumentar ppdual. No sabemos cuánto aporta C++ frente a la JVM.
Retirado: «MMCS gana en matrices ralas». No se sostiene frente a la implementación de Prokofyev (ver Decisiones).
hecho La hipótesis de Vladímir se confirma en matrices muy ralas. En 14 matrices de densidad real entre 2,7 % y 5,2 % (de 913 × 60 a 4000 × 100, experiments/baseline/results/core_sparse.md), las listas ganan a los bitsets con poda perezosa en 13 de 14, hasta 2,2 veces (4000 × 100 con densidad 0,029: 6,5 s contra 14,2 s). Con filtrado completo, las listas ganan en las 14 y en las tres más grandes alcanzan o superan a bitset-min-lazy. Con densidad de 17 % o más, las listas no ganan de forma clara (ver arriba). El punto de cruce entre 5 % y 17 % no está medido.
Límite: con densidad fija, el número de reductos explota al subir las columnas, así que estas matrices tienen de 60 a 100 columnas. No dice nada todavía de matrices de cientos de columnas.
¿Publicable aparte? quizá, con banco ampliado
opinión La idea metodológica, «medir estrategias en el mismo motor», tiene valor propio y casi no se ve en esta literatura. Para un artículo aparte faltan una máquina de verdad, más algoritmos (HTC-BDD, FastRS) y matrices grandes. Encaja con el trabajo conjunto que se acordó con Jairo Lefebre para después del artículo principal.
D5. RegularSearch: la implementación publicada cuesta de 10 a 20 veces¶
Hallazgo
El código publicado de 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 → recalcula el número de unos en cada operación con bloques de 32 bits. Reescrito con las mismas estructuras que MMCS, recorre el mismo árbol (nodos idénticos) y corre de 10 a 20 veces más rápido. Aun así queda en la clase de fast-BR, de 2 a 70 veces detrás de MMCS: su cota LV poda menos que la fila pivote por nodo.
hecho Validación por conjunto y por nodos en 453 matrices. Dermatology: 90 s del original contra 4,8 s de la reescritura; MMCS, 0,15 s.
Contradice la Tabla 7 del artículo, donde RegularSearch gana a fast-BR en dermatology. Causas posibles, sin ordenar por falta de datos: otra versión del código, el fast-BR original con sus errores, otra matriz básica (la nuestra tiene 1 103 filas y la suya 1 124).
¿Publicable aparte? sección del artículo
No. Va en el artículo reportando las dos versiones, la original y la reescrita. Jairo Lefebre colabora y conoce los resultados de corrección; el tono tiene que acordarse con él.
D6. Errores de conteo en programas publicados¶
Hallazgo
Cinco errores en programas publicados del grupo: GCreduct, MinReduct, sRGA y fast-BR dan conteos de reductos equivocados bajo condiciones concretas, y cuatro de ellos fallan o no terminan en matrices degeneradas. Además, una errata en un artículo de Susmaga y una fuga de memoria en CAMARDF.
hecho Corregidos en java/fixed/ y verificados por conjunto contra una referencia que no comparte código, en 442 matrices. El impacto sobre lo publicado es pequeño: tres matrices de los paquetes públicos. Ningún fallo ocurrió fuera de las cinco condiciones que los disparan.
El argumento para el artículo: programas usados como referencia daban conteos distintos y nadie podía notarlo, porque solo imprimían conteos. Por eso validamos por conjunto.
¿Publicable aparte? sección del artículo
No. Solo, es una fe de erratas. Como sección de validación, justifica la metodología.
Detalle: Errores en el código publicado.
D7. El orden de columnas importa solo en matrices pequeñas¶
Hallazgo
En matrices UCI pequeñas, cambiar el orden de columnas cambia el trabajo de GCreduct hasta 59 526 veces. En las sintéticas de 2000 × 30 no pasa de 1,2 veces en ningún algoritmo. MMCS casi no depende del orden (máximo 2,1). El caso extremo, MED, se explica por un desempate: entre 24 filas con un solo 1, ordenInicial() elige la primera del archivo.
¿Publicable aparte? sección secundaria
No con lo medido. Las sintéticas tienen columnas casi equivalentes por construcción, así que no dicen nada de matrices reales grandes.
D8. Las matrices sintéticas publicadas no son básicas¶
hecho 525 de las 663 matrices sintéticas de los paquetes tienen filas que son superconjunto de otra (mediana 19, máximo 601 de 2000). No cambia el conjunto de reductos, pero sí el trabajo de cada algoritmo. Va como nota en la descripción de los datos.