Conceptos básicos¶
Esta página define lo mínimo para leer el resto del sitio, con un ejemplo de cuatro filas. El ejemplo central para explicar cada propiedad de poda está en preparación (ver Metas).
De la tabla de datos a la matriz básica¶
Partimos de una tabla de decisión: filas son objetos, columnas son atributos, y una columna especial da la clase de cada objeto. Para cada par de objetos de clases distintas se anota en qué atributos difieren: 1 si difieren, 0 si coinciden. Esa es la matriz de discernibilidad.
Muchas de sus filas sobran. Si una fila tiene unos en todos los lugares donde otra los tiene (es un superconjunto de ella), cualquier conjunto de atributos que distinga el par de la fila pequeña también distingue el de la grande. Al quitar las filas vacías, las repetidas y las que son superconjunto de otra, queda la matriz básica. Todos los algoritmos de este sitio trabajan sobre ella.
Ejemplo¶
Matriz básica de 4 filas y 5 columnas (columnas \(c_1\) a \(c_5\)):
| \(c_1\) | \(c_2\) | \(c_3\) | \(c_4\) | \(c_5\) | |
|---|---|---|---|---|---|
| \(r_1\) | 1 | 1 | 0 | 0 | 0 |
| \(r_2\) | 0 | 1 | 1 | 0 | 0 |
| \(r_3\) | 0 | 0 | 1 | 1 | 0 |
| \(r_4\) | 1 | 0 | 0 | 1 | 1 |
Ninguna fila contiene a otra, así que es básica.
Testor, testor típico y reducto¶
- Un testor es un conjunto de columnas que tiene al menos un 1 en cada fila. En el ejemplo, \(\{c_1, c_2, c_3\}\) es testor: \(r_1\) tiene un 1 en \(c_1\), \(r_2\) y \(r_3\) en \(c_3\), y \(r_4\) en \(c_1\).
- Un testor típico (o irreducible) es un testor del que no se puede quitar ninguna columna sin dejar de serlo. \(\{c_1, c_2, c_3\}\) no lo es: sin \(c_2\) sigue cubriendo todas las filas.
- Sobre la matriz básica, reducto y testor típico son lo mismo.
Los testores típicos del ejemplo son tres: \(\{c_1, c_3\}\), \(\{c_2, c_4\}\) y \(\{c_2, c_3, c_5\}\). Los calculó la referencia independiente del proyecto (experiments/lib/bm.py).
Los reductos más cortos son los de menor tamaño: aquí \(\{c_1, c_3\}\) y \(\{c_2, c_4\}\).
El mismo problema con otros nombres¶
Si cada fila se lee como un conjunto de columnas (una hiperarista), la matriz es un hipergrafo. Un testor es un conjunto que toca todas las hiperaristas: un hitting set o transversal. Un testor típico es un minimal hitting set o transversal mínima Alba-Cabrera et al., 2019On the Relation Between the Concepts of Irreducible Testor and Minimal Transversal
Eduardo Alba-Cabrera; others
IEEE Access, 7, 82809–82816, 2019
https://doi.org/10.1109/ACCESS.2019.2922231
Resumen: Resumen pendiente.Nuestra nota: Teorema 3: los testores irreducibles de una matriz básica son exactamente las transversales mínimas del hipergrafo de sus filas. Referencia de la equivalencia.Ficha completa →. Enumerarlos todos es dualizar el hipergrafo, el nombre que usa la escuela rusa 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 →.
| Testores típicos | Minimal hitting sets | Escuela rusa |
|---|---|---|
| matriz básica | hipergrafo (filas = hiperaristas) | matriz booleana |
| columna / atributo | vértice | columna |
| testor | hitting set, transversal | cubrimiento |
| testor típico, reducto | minimal hitting set, transversal mínima | cubrimiento irreducible («тупиковое покрытие») |
| fila de compatibilidad (fila que solo cubre una columna del conjunto) | arista crítica, crit |
compatibilidad de columnas |
Fila crítica: la prueba que comparten casi todos¶
En un testor típico, cada columna tiene que ser imprescindible: debe haber al menos una fila que solo ella cubre dentro del conjunto. Esa fila es crítica para la columna. En \(\{c_2, c_3, c_5\}\): \(r_1\) es crítica para \(c_2\), \(r_3\) para \(c_3\) y \(r_4\) para \(c_5\). La fila \(r_2\) la cubren \(c_2\) y \(c_3\), así que no es crítica para ninguna.
Casi todos los algoritmos rápidos construyen el conjunto columna por columna y descartan una rama en cuanto alguna columna elegida se queda sin fila crítica. La comunidad de testores la llama exclusión o compatibilidad, Murakami y Uno la llaman crit 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 Djukova la usa desde 1977 con el nombre de compatibilidad de columnas 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 →. Las diferencias entre algoritmos están en qué columna se prueba después y qué candidatos se descartan antes: eso es lo que analiza Propiedades de poda.