La programación lógica inductiva ( ILP ) es un subcampo de la inteligencia artificial simbólica que utiliza la programación lógica como una representación uniforme de ejemplos, conocimientos previos e hipótesis. Dada una codificación del conocimiento previo conocido y un conjunto de ejemplos representados como una base de datos lógica de hechos, un sistema ILP derivará un programa lógico hipotético que implica todos los ejemplos positivos y ninguno negativo.
- Esquema: ejemplos positivos + ejemplos negativos + conocimientos previos ⇒ hipótesis .
La programación lógica inductiva es particularmente útil en bioinformática y procesamiento del lenguaje natural . Gordon Plotkin y Ehud Shapiro sentaron las bases teóricas iniciales para el aprendizaje automático inductivo en un entorno lógico. [1] [2] [3] Shapiro construyó su primera implementación (Model Inference System) en 1981: [4] un programa Prolog que infería inductivamente programas lógicos a partir de ejemplos positivos y negativos. El término programación lógica inductiva fue introducido por primera vez [5] en un artículo de Stephen Muggleton en 1991. [6] Muggleton también fundó la conferencia internacional anual sobre programación lógica inductiva, presentó las ideas teóricas de predicado invención, resolución inversa , [7] y Vinculación inversa. [8] Muggleton implementó la vinculación inversa primero en el sistema PROGOL . El término " inductivo " aquí se refiere a una inducción filosófica (es decir, que sugiere una teoría para explicar los hechos observados) en lugar de matemática (es decir, que demuestra una propiedad para todos los miembros de un conjunto bien ordenado).
Definicion formal
El conocimiento previo se da como una teoría lógica B , comúnmente en forma de cláusulas de Horn utilizadas en la programación lógica . Los ejemplos positivos y negativos se dan como una conjunción. y de literales de terreno innecesarios y negados , respectivamente. Una hipótesis correcta h es una proposición lógica que satisface los siguientes requisitos. [9]
La " necesidad " no impone una restricción a h , pero prohíbe cualquier generación de una hipótesis siempre que los hechos positivos sean explicables sin ella. La " suficiencia " requiere que cualquier hipótesis generada h explique todos los ejemplos positivos. " Consistencia débil generación prohíbe" de cualquier hipótesis h que contradice el conocimiento de fondo B . La " consistencia fuerte " también prohíbe la generación de cualquier hipótesis h que sea inconsistente con los ejemplos negativos., dado el conocimiento previo B ; implica " Consistencia débil "; si no se dan ejemplos negativos, ambos requisitos coinciden. Džeroski [10] solo requiere " Suficiencia " (llamada "Completitud" allí) y " Consistencia fuerte ".
Ejemplo
El siguiente ejemplo bien conocido sobre el aprendizaje de definiciones de relaciones familiares utiliza las abreviaturas
- par : padre , fem : mujer , dau : hija , g : George , h : Helen , m : Mary , t : Tom , n : Nancy y e : Eve .
Comienza con el conocimiento previo (ver imagen)
- ,
los ejemplos positivos
- ,
y la proposición trivial verdadera para denotar la ausencia de ejemplos negativos.
El enfoque de Plotkin [11] [12] de " generalización mínima relativa (rlgg) " para la programación lógica inductiva se utilizará para obtener una sugerencia sobre cómo definir formalmente la relación hija dau .
Este enfoque utiliza los siguientes pasos.
- Relativice cada literal de ejemplo positivo con el conocimiento previo completo:
- ,
- Convertir a la forma normal de la cláusula :
- ,
- Anti-unifica cada par [ 13] compatible [14] de literales:
- de y ,
- de y ,
- de y ,
- de y , similar para todos los demás literales de conocimiento previo
- de y , y muchos más literales negados
- Elimine todos los literales negados que contienen variables que no ocurren en un literal positivo:
- después de eliminar todos los literales negados que contienen otras variables que , solo permanece, junto con todos los literales básicos del conocimiento previo
- Convierta las cláusulas a la forma de Horn:
La cláusula de Horn resultante es la hipótesis h obtenida por el enfoque rlgg. Ignorando los hechos del conocimiento previo, la cláusula dice informalmente " se llama hija de Si es el padre de y es mujer ", que es una definición comúnmente aceptada.
Con respecto a los requisitos anteriores , se satisfizo " Necesidad " porque el predicado dau no aparece en el conocimiento de fondo, lo que por lo tanto no puede implicar ninguna propiedad que contenga este predicado, como los ejemplos positivos. La " suficiencia " se satisface con la hipótesis calculada h , ya que, junto con del conocimiento previo, implica el primer ejemplo positivo , Y de manera similar h y del conocimiento previo implica el segundo ejemplo positivo . La " consistencia débil " se satisface con h , ya que h se mantiene en la estructura (finita) de Herbrand descrita por el conocimiento previo; similar para " Consistencia fuerte ".
La definición común de la relación de abuela, a saber. , no se puede aprender usando el enfoque anterior, ya que la variable y aparece solo en el cuerpo de la cláusula; los literales correspondientes se habrían eliminado en el cuarto paso del enfoque. Para superar esta falla, ese paso debe modificarse de manera que se pueda parametrizar con diferentes heurísticas de post-selección literal . Históricamente, la implementación de GOLEM se basa en el enfoque rlgg.
Sistema de programación lógica inductiva
El sistema de programación lógica inductiva es un programa que toma como entrada las teorías lógicas y genera una hipótesis correcta H wrt teoríasUn algoritmo de un sistema ILP consta de dos partes: búsqueda de hipótesis y selección de hipótesis. Primero se busca una hipótesis con un procedimiento de programación de lógica inductiva, luego se elige un subconjunto de las hipótesis encontradas (en la mayoría de los sistemas una hipótesis) mediante un algoritmo de selección. Un algoritmo de selección puntúa cada una de las hipótesis encontradas y devuelve las que tienen la puntuación más alta. Un ejemplo de función de puntuación incluye la longitud de compresión mínima donde una hipótesis con una complejidad de Kolmogorov más baja tiene la puntuación más alta y se devuelve. Un sistema ILP está completo si se aplica a cualquier teoría de lógica de entradacualquier hipótesis correcta H wrt a estas teorías de entrada se puede encontrar con su procedimiento de búsqueda hipótesis.
Búsqueda de hipótesis
Los sistemas modernos de ILP como Progol, [6] Hail [15] e Imparo [16] encuentran una hipótesis H usando el principio de la implicación inversa [6] para las teorías B , E , H :. Primero construyen una teoría intermedia F llamada teoría puente que satisface las condiciones y . Entonces como, generalizan la negación de la teoría del puente F con la anti-vinculación. [17] Sin embargo, la operación de la anti-vinculación, dado que es altamente no determinista, es computacionalmente más costosa. Por lo tanto, se puede realizar una búsqueda de hipótesis alternativas utilizando la operación de la subsunción inversa (anti-subsunción), que es menos no determinista que la anti-vinculación.
Surgen preguntas sobre la completitud de un procedimiento de búsqueda de hipótesis de un sistema ILP específico. Por ejemplo, el procedimiento de búsqueda de hipótesis de Progol basado en la regla de inferencia de vinculación inversa no está completo con el ejemplo de Yamamoto . [18] Por otro lado, Imparo se completa tanto con el procedimiento anti-vinculación [19] como con su procedimiento extendido de subsunción inversa [20] .
Implementaciones
- 1BC y 1BC2: clasificadores bayesianos ingenuos de primer orden:
- ACE (un motor combinado)
- Aleph
- Átomo
- Claudien
- Aprendiz de DL
- DMax
- FastLAS (aprendizaje rápido a partir de conjuntos de respuestas)
- FOIL (alumno inductivo de primer orden)
- Golem
- ILASP (Programas de aprendizaje inductivo de conjuntos de respuestas)
- Imparo [19]
- Inthelex (aprendiz teórico incremental de ejemplos)
- Lima
- Metagol
- Mio
- MIS (sistema de inferencia modelo) por Ehud Shapiro
- PROGOL
- RSD
- Warmr (ahora incluido en ACE)
- ProGolem [21] [22]
Ver también
- Razonamiento de sentido común
- Análisis de concepto formal
- Razonamiento inductivo
- Programación inductiva
- Probabilidad inductiva
- Aprendizaje relacional estadístico
- Aprendizaje espacial de versiones
Referencias
- ^ Plotkin GD Métodos automáticos de inferencia inductiva , tesis doctoral, Universidad de Edimburgo, 1970.
- ^ Shapiro, Ehud Y. Inferencia inductiva de teorías a partir de hechos , Informe de investigación 192, Universidad de Yale, Departamento de Ciencias de la Computación, 1981. Reimpreso en J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press, Cambridge, MA, 1991, págs. 199-254.
- ^ Shapiro, Ehud Y. (1983). Depuración algorítmica de programas . Cambridge, Mass: MIT Press. ISBN 0-262-19218-7
- ^ Shapiro, Ehud Y. " El modelo de sistema de inferencia ". Actas de la séptima conferencia conjunta internacional sobre inteligencia artificial - Volumen 2. Morgan Kaufmann Publishers Inc., 1981.
- ^ Luc De Raedt. Una perspectiva sobre la programación lógica inductiva. El taller sobre tendencias actuales y futuras en la programación lógica, Shakertown, que aparecerá en Springer LNCS, 1999. CiteSeerX : 10.1.1.56.1790
- ^ a b c Muggleton, SH (1991). "Programación lógica inductiva". Computación de nueva generación . 8 (4): 295–318. CiteSeerX 10.1.1.329.5312 . doi : 10.1007 / BF03037089 .
- ^ Muggleton SH y Buntine W. " Invención de la máquina del predicado de primer orden mediante resolución inversa ", "Actas de la Quinta Conferencia Internacional sobre Aprendizaje Automático, 1988.
- ^ Muggleton, SH (1995). "Vinculación inversora y Progol". Computación de nueva generación . 13 (3–4): 245–286. CiteSeerX 10.1.1.31.1630 . doi : 10.1007 / bf03037227 .
- ^ Muggleton, Stephen (1999). "Programación de lógica inductiva: problemas, resultados y el desafío de aprender el lenguaje en lógica" . Inteligencia artificial . 114 (1–2): 283–296. doi : 10.1016 / s0004-3702 (99) 00067-3 .; aquí: Sección 2.1
- ^ Džeroski, Sašo (1996), "Programación lógica inductiva y descubrimiento de conocimientos en bases de datos", en Fayyad, UM; Piatetsky-Shapiro, G .; Smith, P .; Uthurusamy, R. (eds.), Advances in Knowledge Discovery and Data Mining , MIT Press, págs. 117-152; aquí: Sección 5.2.4
- ^ Plotkin, Gordon D. (1970). Meltzer, B .; Michie, D. (eds.). "Una nota sobre la generalización inductiva". Inteligencia de máquina . 5 : 153-163.
- ^ Plotkin, Gordon D. (1971). Meltzer, B .; Michie, D. (eds.). "Una nota adicional sobre la generalización inductiva". Inteligencia de máquina . 6 : 101-124.
- ^ es decir, compartir el mismo símbolo de predicado y estado negado / innecesario
- ^ en general: n -tuple cuandose dan n ejemplos literales positivos
- ^ Ray, O., Broda, K. y Russo, AM (2003). Aprendizaje inductivo abductivo híbrido . En LNCS: Vol. 2835. Actas de la 13ª conferencia internacional sobre programación lógica inductiva (págs. 311–328). Berlín: Springer.
- ^ Kimber, T., Broda, K. y Russo, A. (2009). Inducción al fracaso: aprendizaje de las teorías de Horn conectadas . En LNCS: Vol. 5753. Actas de la décima conferencia internacional sobre programación lógica y razonamiento no monótono (págs. 169-181). Berlín: Springer.
- ^ Yoshitaka Yamamoto, Katsumi Inoue y Koji Iwanuma. Subsunción inversa para una inducción explicativa completa . Aprendizaje automático, 86 (1): 115-139, 2012.
- ^ Akihiro Yamamoto. ¿Qué hipótesis se pueden encontrar con implicación inversa? En Programación lógica inductiva, páginas 296–308. Springer, 1997.
- ^ a b Timothy Kimber. Aprendizaje de programas lógicos definidos y normales por inducción en caso de falla . Tesis de doctorado, Imperial College London, 2012.
- ^ David Toth (2014). Imparo se completa por subsunción inversa . arXiv: 1407.3836
- ^ Muggleton, Stephen; Santos, José; Tamaddoni-Nezhad, Alireza (2009). "ProGolem: un sistema basado en una generalización mínima relativa" (PDF) . ILP .
- ^ Santos, José; Nassif, Houssam; Page, David; Muggleton, Stephen; Sternberg, Mike (2012). "Identificación automatizada de las características de las interacciones proteína-ligando mediante programación lógica inductiva: un estudio de caso de unión de hexosa" (PDF) . BMC Bioinformática . 13 : 162. doi : 10.1186 / 1471-2105-13-162 . PMC 3458898 . PMID 22783946 .
Otras lecturas
- Muggleton, S .; De Raedt, L. (1994). "Programación lógica inductiva: teoría y métodos" . El diario de la programación lógica . 19-20: 629-679. doi : 10.1016 / 0743-1066 (94) 90035-3 .
- Lavrac, N .; Dzeroski, S. (1994). Programación lógica inductiva: técnicas y aplicaciones . Nueva York: Ellis Horwood. ISBN 978-0-13-457870-5. Archivado desde el original el 6 de septiembre de 2004 . Consultado el 22 de septiembre de 2004 .
- Ejemplo visual de inducir la relación de abuelos por el sistema Atom . http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html