¿Qué algoritmos de aprendizaje automático pueden producir una función de puntuación para medir la “similitud” entre dos objetos?

Si las reglas son completamente arbitrarias, puede que no haya nada que aprender. En cuyo caso puedes memorizar los pares, y eso es lo mejor que puedes hacer.

Si cree que hay algunas reglas, considere entrenar un transductor de estado finito. Estos pueden usarse para generar una probabilidad de transformar X a Y.

Si esto es demasiado complicado, puede utilizar una red neuronal u otro algoritmo de ML incrustando. Puede incrustar cada palabra X en el espacio [matemático] R ^ n [/ matemático] y, a continuación, tener características con valor real [matemático] 2n [/ matemático] y entrenar un clasificador / regresión sobre eso. Con las redes neuronales puede aprender una incrustación automáticamente, pero el modelo de incrustación también puede ser bastante complicado, ya que probablemente no pueda usar una bolsa de caracteres.

También puede construir un árbol de decisión. Ese podría ser el algoritmo más sencillo, pero no estoy seguro de qué tan bien funcionaría. Las características pueden ser cualquier propiedad de cualquiera de las cadenas.

En cualquier caso, sugeriría agregar algunos ejemplos negativos, lo que sea que use para entrenar.

No entiendo la necesidad de un algoritmo de aprendizaje automático aquí. Lo que podría necesitar sería una métrica de similitud.

Existen algunas medidas de similitud que proporcionan un valor cuantificado después de comparar dos o más objetos. En su caso, Jaccard Index sería un buen lugar para comenzar. También puede echar un vistazo a las medidas no simétricas como la divergencia Kullback-Leibler.