Saltar a contenido

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, 2009; Lias-Rodríguez y Sanchez-Diaz, 2013. MMCS Murakami y Uno, 2014 y RUNC-M Djukova y Prokofjev, 2015 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) y MMCS Murakami y Uno, 2014 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, 2023 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, 2015 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, 2017 no menciona a Djukova, RUNC ni los testores, y la revisión de algoritmos de testores Sánchez-Díaz et al., 2023 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:

  1. el diccionario de equivalencias entre vocabularios;
  2. la matriz algoritmo × propiedad de poda (Propiedades de poda);
  3. las equivalencias demostradas de esta tabla;
  4. 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), 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, 2023 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.