¿Qué heurísticas existen (si las hay) para saber qué tan cerca está un circuito de una función?

2

Estoy trabajando en un proyecto de inteligencia artificial para minimizar los circuitos.

Estoy tratando de pensar en una heurística para decirme qué tan cerca está un determinado circuito de representar una determinada función.

Por ejemplo, si necesito implementar una función XOR, entonces un circuito que consta de una sola puerta OR estará más cerca de representar la XOR en comparación con un circuito que consta de una sola puerta AND (porque todo lo que falta es una única NO puerta).

¿Existe tal heurística para detectar qué tan "cerca" está un circuito del circuito final?

Hemos intentado puntuar los circuitos contando el número de salidas correctas según la tabla de verdad, pero esto falla. Por ejemplo, si tenemos un circuito que para cada entrada produce la negación de la salida correcta, entonces su "puntaje" sería 0 según esta heurística, pero en realidad está muy cerca del diseño final y todo lo que falta Es no la salida.

Gracias

    
pregunta Tylor Durden

5 respuestas

6

Puede basar su "función de costo" en Clases de error DNF . Para empezar, podrías considerar el siguiente conjunto

  • ENF: error de negación de expresión (a - >! a)
  • TOF: error de omisión de término (a - > a | b)
  • TIF: error de inserción de término (a | b - > a)
  • TNF: término error de negación (a | b - > a |! b)
  • LOF: error de omisión literal (a - > ab)
  • LIF: error de inserción literal (ab - > a)
  • LNF: error de negación literal (ab - > a! b)

Por ejemplo, la distancia desde AND (a & b) a XOR (a &! b |! a & b) sería de 1 LIF y 1 TOF, mientras que una distancia de AND a NAND sería de 1 ENF. Tendrá que experimentar con los pesos que asigne en diferentes tipos de fallas en su función de costo.

Otra idea que quizás desee considerar es tomar el problema del otro lado: en lugar de generar funciones mínimas y optimizar para corregir, podría generar funciones correctas y optimizar para el minimalismo. Es mucho más fácil encontrar una función de costo razonable en este último caso, y no tiene que alcanzar el óptimo para obtener una solución aceptable.

    
respondido por el Dmitry Grigoryev
3

Muchos otros algoritmos de aprendizaje automático (por ejemplo, para el entrenamiento de perceptrón) utilizan una métrica de rendimiento como el error de estimación cuadrática, la covarianza de errores o lo que sea más lógico. Llamemos a este parámetro \ $ J \ $. En general, el objetivo del algoritmo es alcanzar una época (una iteración) en la que \ $ J \ $ esté como mínimo (local o global). Esto se puede lograr empleando conceptos de optimización numéricos, como los métodos de pendiente de gradiente y de segunda derivada.

En el ejemplo descrito, donde solo una operación NO terminaría obteniendo una respuesta correcta, el rendimiento \ $ J \ $ es máximo (el circuito está equivocado todo el tiempo). Sin embargo, ajustar el sistema solo un poco da como resultado \ $ J \ $ a un mínimo global (correcto todo el tiempo). Esto significa que al evaluar los derivados en el punto actual, debe haber un vector de gradiente empinado que apunte hacia la solución correcta.

Idealmente, el algoritmo empleado evaluaría dicho gradiente correctamente e iteraría hacia la solución correcta. Sin embargo, si este gradiente es demasiado pronunciado, esto puede causar una condición numérica errónea, en el sentido de que cambiar la solución solo un poco provoca enormes fluctuaciones en \ $ J \ $. Si esto sucede, entonces debería emplearse una escala adecuada de \ $ J \ $ y una mejor granulación de los parámetros del sistema.

Quizás una opción adecuada para \ $ J \ $ sería la distancia de Hamming entre los resultados.

    
respondido por el Vicente Cunha
2

Su puntaje debe estar especializado para el circuito que le interesa.

A partir de los sonidos del mismo, buscas marcar un circuito como una caja negra. La configuración real de las puertas no es importante, pero las salidas sí lo son. Presumiblemente, a partir de los comentarios, usted no conoce el circuito ideal.

Considere dos casos. Una es una simulación de una sinapsis. Este es un problema bastante fácil de resolver. Una solución que produce una respuesta del 99% probablemente esté muy cerca de una respuesta "correcta". Contraste esto con un circuito diseñado para hacer sumas de comprobación SHA-1. Una solución que arroja una respuesta del 99,999999999% es indescriptiblemente lejos de una respuesta "correcta" para un circuito de este tipo, porque la medida de "corrección" para una suma de comprobación criptográfica es muy exigente.

Es la aplicación de su circuito que definirá su mejor métrica de puntuación.

    
respondido por el Cort Ammon
0

Nuestra inteligencia es realmente analógica con billones de entradas de memoria y sensores, cada una con diferentes ponderaciones o factores de ganancia y compensación que también pueden ser no lineales. La secuencia de tiempo o la secuencia lógica y las combinaciones también pueden ser parte de una decisión en la que cada resultado potencial tenga diferentes factores de ponderación en las entradas y consecuencias a decidir.

Entonces, cuando usted dice casi, puede significar que cualquiera de estos umbrales o ponderación o tiempo o las operaciones de secuencia deben definirse para que sean "Artificiales" o se parezcan a la respuesta humana. Es por esto que la experiencia para la lógica difusa es tan poderosa.

¿Le gustaría realizar pruebas experimentales con lógica difusa y factores de confianza o definir todos estos factores "casi" por adelantado?

por ejemplo, para 5V logic 2.2v es casi un "1" lógico. Si se está moviendo en esa dirección, necesitamos un factor de ganancia lineal o Proporcional (P) y Derivativo (D) para darle más "peso" binario para "casi"

Cada decisión de memoria que tomamos son miles de millones de estos cálculos analógicos con múltiples salidas de comparación con consecuencias negativas y positivas y ciclos de retroalimentación.

NO es simplemente ser o no ser?

¡Por supuesto, depende de cuán "inteligente" este diseño desea llegar a ser!

  

Respuesta: {Las heurísticas y el estado actual} y "casi" de cada uno, pueden tener cualquier importancia, dependiendo de su especificación para "casi".

La función de correlación cruzada es un método de análisis para sistemas tanto analógicos como digitales. La cobertura digital de fallas con vectores de prueba para detección y corrección es otro método.

    
respondido por el Tony EE rocketscientist
-1

Su pregunta, y las diversas respuestas, se centran en los comportamientos digitales (máquina de estados lógicos).

Le sugiero que comience con una tabla de estado COMPLETA, o tabla lógica si no se necesitan flip flops, y que su métrica sea el% de respuestas correctas.

Ahora, en tu pregunta, ya has probado esto. Como se nota, para ciertas no soluciones, todo lo que se necesita es la adición de un inversor de salida para que sea completamente exitoso. Su pregunta se convierte entonces en "¿cómo podemos aprender, a menos que ya se conozca la respuesta óptima, o al menos una respuesta exitosa?" que es una excelente pregunta.

¿Cómo aprenden los humanos en entornos desconocidos? Intentan algo, cualquier cosa, en trozos pequeños, en trozos grandes. Intentan algo.

Esto significa que necesita definir qué son "piezas pequeñas" (agregue un inversor, aleatoriamente, en cualquiera o todas las rutas.

También debe definir qué son las "piezas grandes", y esto requiere una cirugía con gráfico, lo que hace surgir la necesidad de "entender", o ¿debe un sistema entender? ¿Si la exploración aleatoria es el camino a la iluminación?

Una vez más, ¿cómo los humanos exploran nuevas situaciones? Hacen cambios y ven lo que pasa. Eso significa que necesitan tener un conocimiento de las entradas y salidas.

Cuando se dio cuenta de que la adición de un solo inversor, en la salida, sería el siguiente y último paso, ¿cómo llegó a esa conclusión el humano? Probablemente exploraste todos los cambios posibles, usando tu visión para examinar una tabla lógica. La tabla y su capacidad de visión / cerebro para encontrar patrones útiles (y ha entrenado a su cerebro para que reconozca "útil" para sistemas digitales), permiten su realización "Oh. Solo agregue un inversor de salida".

¿Cómo llegó tu cerebro allí? amplitud / profundidad / búsqueda aleatoria.

En el mundo del diseño de RF, con numerosas especificaciones (fidelidad, consumo de energía, filtros utilizados), las heurísticas son mucho más flexibles.

Nuevamente, para el diseño lógico, un inversor faltante puede deteriorarse.

    
respondido por el analogsystemsrf

Lea otras preguntas en las etiquetas