Геометрический подход к упрощению логических схем

💡 Усі статті, обговорення, новини про AI — в одному місці. Приєднуйтесь до AI спільноти!

Об авторе: Денис Морозов, к.ф.-м.н., работает на должности доцента кафедры математики НаУКМА, также является консультантом компании GlobalLogic. Работает над докторской диссертацией, сфера научных интересов — конечные автоматы и группы автоморфизмов деревьев.

Комбинационные логические схемы — альтернатива нейронным сетям при реализации формализованных реакций системы на заданные входные состояния. Естественно, чем проще схема, тем легче она тестируется и тем прозрачнее работа с ней. Геометрическому подходу упрощения комбинационных логических схем и посвящена данная статья.

Методы работы с такими схемами будут полезны инженерам, занимающимся разработкой интеллектуальных систем принятия решений и управления, а также hardware-инженерам, непосредственно занимающимися цифровой схемотехникой.

Исследование искусственного интеллекта (ИИ) требует уверенного владения различными техниками, и не ограничивается только использованием нейронных сетей. Одной из важных техник является теория комбинационных логических схем. У данной техники есть своя определенная ниша.

Комбинационно-логические схемы vs нейронные сети

Не так давно нейронные сети пережили второе рождение и сейчас большой процент задач, например, задачи распознавания звука, изображений, проблематики естественного языка, перевода решаются именно при помощи аппарата нейронных сетей. И возникает естественный вопрос: а зачем еще что-то другое? Ведь нейронные сети неплохо решают задачи, которые перед ними ставятся. Но здесь надо понимать, что такое нейронная сеть, каковы ее преимущества и ограничения.

Часто при использовании нейронных сетей возникают следующие ситуации: вы получили почти то, что вы хотите, но не совсем точно. Это отголоски того факта, что нейронные сети — это достаточно сложные хаотические структуры, с ними трудно работать. Хаотические — это не в смысле фэнтези, а в чисто математическом смысле. Под хаотической мы понимаем систему, в которой небольшое изменение входных параметров может существенно изменить наблюдаемые. Это первая причина, по которой не стоит ограничиваться только нейронными сетями. Вторая же, не менее важная причина, состоит в том, что такие системы очень трудно тестировать.

В областях, где критически важна безопасность, например, в разработке систем космических аппаратов, авиационной и автомобильной промышленности, вопросы соответствия определенным safety-стандартам и прозрачности процедур тестирования чрезвычайно важны.

Возвращаясь к комбинационно-логическим схемам, их преимущество как раз и заключается в том, что если вам удалось среду, с которой вы работаете, разбить на маленькие модули, то уже не нужны нейронные сети. Можно строить логические схемы, а у них есть замечательное свойство — существует достаточное количество прозрачных эффективных методов тестирования таких схем. То есть мы можем фиксировать определенные стандарты безопасности для этих маленьких модулей. Реализовать не просто интеллектуальное поведение, которое является достаточно сложным, но реализовать сложное поведение, отвечающее определенным стандартам безопасности, и это очень важный момент.

Кроме того, комбинационные логические схемы самодокументируемы. Логические связки конъюнкция и дизъюнкция представляются с сохранением контекста в естественном языке союзами «и», «или». Простыми словами, по виду логической схемы вполне возможно понять, как она работает. Нейронные сети не обладают данным преимуществом, являясь в определенном смысле черными ящиками. Понять по матрице нейронной сети особенности ее работы — задача нетривиальная. По этой же причине функциональные требования, записанные на естественном языке, проще реализовывать именно в виде логических схем.

Как мы уже упоминали, чем проще логическая схема, тем легче она тестируется и тем прозрачнее работа с ней. Поэтому важно понимать суть механизмов упрощения подобных схем.

Кратко, геометрический метод упрощения состоит в представлении булевой функции в виде многомерного гиперкуба, часть вершин которого отмечена. После этого происходит поиск возможных покрытий данного множества вершин минимальной системой гиперплоскостей максимальной размерности, что осуществляется путем анализа соответствующего плоского графа, построенного на данных вершинах.

Далее рассмотрим пример применения данной техники. Пример придуман и написан мной для одной лекции на данную тему.

Генерация и минимизация структурных блоков над бинарным алфавитом

1. Основные определения

Пусть $(x_1,...,x_n)$ булевый вектор входных данных структурного блока $\mathfrak{B}$ , $(y_1,...,y_m)$ — выходных.

Определение 1. Будем обозначать блок $\mathfrak{B}:(x_1,...,x_n)\rightarrow (y_1,...,y_m)$ как $\mathfrak{B}(n,m)$ .

Данный блок можно получить, как декартово произведение блоков $\mathfrak{B_i}:(x_1,...,x_n)\rightarrow y_i$ :

$\mathfrak{B}(n,m) = \mathfrak{B_1}(n,1) \times ... \times \mathfrak{B_m}(n,1)$

Следовательно, без ограничения общности, далее можно рассматривать блоки с одним булевым выходом.

Определение 2. Формализированным требованием к блоку $\mathfrak{B}(n,1)$ будем называть подмножество $\mathfrak{R}_{\mathfrak{B}} = <(x_1,...,x_n) \in bool^n | \mathfrak{B}(x_1,...,x_n) = 1>$

2. Автоматическая генерация булевой функции, представляющей блок с одним выходом

Лемма 1. Блок $\mathfrak{B_1}(n,1)$ представим следующей булевой функцией:

$\lor_{(t_1,...,t_n)\in \mathfrak{R}_{\mathfrak{B}}}(\land_{1\leq i \leq n}x_i^{t_i})$

Доказательство. Согласно представлению булевой функции в совершенной дизъюнктивной нормальной форме.

Пример. Пусть имеется следующее требование к работе блока:

На вход подается значения двух датчиков $A_1, A_2$ и датчика проверки $C$ , в разном ли они состоянии. Схема должна сигнализировать о корректной работе датчика проверки.

Данное требование имеет следующий формализированный вид:

Согласно лемме 1 работа блока описывается функцией:

$(\neg A_1 \land \neg A_2 \land \neg C)\lor (\neg A_1 \land A_2 \land C)\lor (A_1 \land \neg A_2 \land C)\lor ( A_1 \land A_2 \land \neg C)$

3. Оптимизация булевого блока с одним выходом

Пусть блок с одним выходом задается следующей таблицей истинности:

Что соответсвует булевой формуле:

$(\neg A_1 \land \neg A_2 \land \neg A_3 \land A_4 )\lor (\neg A_1 \land \neg A_2 \land A_3 \land \neg A_4 )\lor (\neg A_1 \land A_2 \land \neg A_3 \land A_4 )\lor$
$\lor ( A_1 \land \neg A_2 \land \neg A_3 \land A_4 )\lor ( A_1 \land \neg A_2 \land A_3 \land \neg A_4 )\lor ( A_1 \land \neg A_2 \land A_3 \land A_4 )\lor ( A_1 \land A_2 \land A_3 \land \neg A_4 )$

Оставим значащие для ДДНФ строки:

Переставим строки в соответствии с кодом Грея:

Построим граф, соединив пары строк $(s_1, s_2)$ , для которых расстояние Хэмминга $\rho_H(s_1,s_2) = 1$ :

Выберем множество пар, что покрывают все вершины:

Выбранному множеству пар

(2,3)
(4,5)
(5,7)
(1,6)

соответствует следующая таблица:

Согласно полученной таблице, минимизированная формула примет вид:

$(\neg A_2 \land A_3 \land \neg A_4 )\lor ( A_1 \land A_3 \land \neg A_4 )\lor (\neg A_1 \land \neg A_3 \land A_4 )\lor ( A_1 \land \neg A_2 \land A_4 )$

Заметим, что естественное упрощение с использованием сокращений булевой алгебры может привести к неоптимальному результату. Например, применив правило сокращения булевой алгебры $a \lor (\neg a \land b) = a \lor b$ к таблице:

получим:

Что соответствует булевой формуле:

$(\neg A_2 \land \neg A_3 \land A_4 )\lor (\neg A_1 \land \neg A_3 \land A_4 )\lor (\neg A_2 \land A_3 \land \neg A_4 )\lor (A_1 \land \neg A_2 \land A_3 )\lor (A_1 \land A_3 \land \neg A_4 )$

Которая содержит 5 блоков $AND$ и не является оптимальной по количеству связок.

Данному упрощению соотвествует следующий граф, содержащий 5 отмеченных ребер, накрывающих все вершины:

Для полного же накрытия достаточно 4-х ребер. В общем случае, накрывающую систему ребер можно выбрать различными способами, поэтому упрощение по количеству булевых связок не является однозначным.

4. Абстрактная схема алгоритмов упрощения

Определение 3. Будем считать, что блок A проще блока B, если:

$\exists C \in \mathfrak{B}, B = A \land C$

На блоках естественным образом вводится отношение порядка $\preceq_r$ . Будем считать, что $B \preceq_r A$ , если блок А проще блока В.

Определение 4. Пусть формула А является дизъюнктивным объединением блоков $\lor_{1\leq i \leq n}A_i$ , а формула B является дизъюнктивным объединением блоков $\lor_{1\leq i \leq m}B_i$ . Будем говорить, что $B \preceq_r A$ , если:

$\forall i (1\leq i \leq n) \exists j\ B_j \preceq_r A_i$

Отношение порядка $\preceq_r$ на множестве формул не является линейным. Например, формулы $a \land b$ и $b \land c$ — несравнимы.

Определение 5. Для формулы $F(x_1,...,x_n)$ определим $\mathfrak{R}(F)$ как множество эквивалентных F формул над множеством переменных $<x_1, ..., x_n>$ . Определим $\mathfrak{R}_{\sup}(F)$ как множество формул:

$\mathfrak{R}_{\sup}(F) = <X | X \in \mathfrak{R}(F), \nexists Y \in \mathfrak{R}(F), X \preceq_r Y >$

Будем называть $\mathfrak{R}_{\sup}(F)$ множеством упрощений формулы F.

Определение 6. Для формулы $F(x_1,...,x_n)$ определим $\mathfrak{C}_F$ как множество конъюнктивных блоков над множеством переменных $(x_1,...,x_n)$ , удовлетворяющих следующему условию:

$B \in \mathfrak{C}_F \Leftrightarrow F \preceq_{semantic} B$

Схему различных алгоритмов упрощения булевых формул с одним выходом можно представить в виде следующей теоремы:

$\forall F'\in \mathfrak{R}_{\sup}(F), \exists n\ F' = \cup_{1 \leq i \leq n} B_i(B_i\in \mathfrak{C}_F )$

Выводы

Итак, геометрическое представление упрощения комбинационных логических схем является удобным языком, позволяющим получить однородное описание для различных схем упрощения данных схем, таких как карты Карно, метод гиперкуба, метод Куайна и т.д. Подобное описание является ключом к прозрачному пониманию данных методов, что является основой для их корректного использования и возможной модификации.

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU

Теми: AI, tech

static inline uint32_t eval_texas_rank7_via_fsm7(const card_t * const cards) { uint32_t current = 52; current = texas_fsm7[current + cards[0]]; current = texas_fsm7[current + cards[1]]; current = texas_fsm7[current + cards[2]]; current = texas_fsm7[current + cards[3]]; current = texas_fsm7[current + cards[4]]; current = texas_fsm7[current + cards[5]]; current = texas_fsm7[current + cards[6]]; return current; }

Andrii Sevastianov 27.11.2018 13:49

Нейросети немного из другой области, всё-таки. Основное их преимущество в том, что после обучения они выдают приемлемые результаты в точках, которые не входили в обучающую выборку. Тут же нам надо знать значение функции в каждой точке. Для большинства нейросетей это невозможно. Ну хорошо, допустим мы распознаём изображение 160×160. Итого у нас на входе 160×160×3x8 = 614400 бит, а на выходе, например, один бит типа порно или нет. Где нам взять таблицу c 2^614400 строками? Если ли у нас хоть шанс обработать 1.0E+184934 вариантов и где их взять??? Где же тут замена?

Да, если бы можно было построить из ограниченного набора строк некоторое хорошее приближение, это было бы интересно.

Ну хорошо, возьмём задачу попроще. Нам надо оценить силу покерной руки по семи картам (холдем). Итогда на вход подаются семь карт в произвольном порядке, на выходе сила. Ну хорошо, получаем примерно 6 бит на карту, итого 7×6 = 42 бита. На выходе нам надо декодировать одну из 7462 комбинаций, тут или 13 выходов, или 7462, что проще. Казалось бы, тут сам бог велел использовать, а я пока что вижу одни проблемы. Сколько будет идти оптимизацию, что получим в результате, сколько это будет считаться?

Гораздо проще тут синтезировать конечный автомат, который будет выполнять оценку силу руки примерно таким кодом:

Очень быстро, правда необходимо 112401776 байт для Texas Hold’em. Да и сам процесс синтеза может отнять некоторые ресурсы (мои упражнения кому интересно github.com/mustitz/yoo-ofsm. Опять же это решение мало связано c логическими схемами и с нейросетями, тут их учить просто бессмысленно, ибо вряд ли мы можем гарантировать 100% точность :)

Відповісти

Підтримати

Vitaly Chernooky C, Embedded and Linux в Self-Emplyed 26.11.2018 02:01

Нередко Сверточные НС заменяются тривиальной статистикой.

anonymous 26.11.2018 09:05

Vitaly Chernooky

Vitaly Chernooky C, Embedded and Linux в Self-Emplyed 26.11.2018 09:30

Если есть подходящая нейронка

anonymous

anonymous 26.11.2018 09:34

Дмитро Дем'яненко BA/UX 25.11.2018 13:21

универом повеяло )

Vadym Fedyukovych Consultant в Infopulse, Part of Tietoevry Create 23.11.2018 23:49

Эта статья об оптимизации схем (circuits) логических элементов. Нейронные сети, при всем понимании их роста и рекламы, только в качестве введения и для контраста.
Визуализация схем вполне приемлема для десятков элементов, дальше человеку сложно. Схемы из десятков скорее учебные. Верилог придуман совсем не случайно.
Для статьи на DOU можно бы больше внимания ’большим’ (не учебным) проектам. Так например ABC является часто используемым готовым инструментом оптимизации сложности схем people.eecs.berkeley.edu/...ations/2010/cav10_abc.pdf
Оптимизация обычно мало заметна внутри промышленных инструментов синтеза; в Yosys есть шаг с явным вызовом ABC stackoverflow.com/...t-into-high-level-modules

Maksym Ganenko Computer Vision Engineer в Upwork 23.11.2018 16:00

Нейронные сети — это про data-driven подход. В случае логических схем мы реализуем детерменированный вычислительный граф. Это две разные и несравнимые области применения.

Rostislav Nikitin .NET Senior Developer в Freelancer 23.11.2018 21:55

Не, ну data-driven он на этапе обучения, пока обучается сеть. Но затем нейронная сеть по сути превращается в такой себе black box, который по входным параметрам либо выдаёт некоторое знчение функции (в случае регерсионной задачи) или классификатор (в случае задачи классификации). Т.е. в обоих случаях что нейронная сеть, что логическая схема могут выполнять роль модуля принятия решений.
После обучения модель становится детерменированной, если это конечно не сеть с непрерывным обучением. Т.е имея модель обученной сети, и входные параметры, мы всегда можем однозначно определить результат. Если мы два раза попросим сеть выполнить регрессионный анализ с одинаковыми параметрами, она выдаст нам в обоих случаях одинаковый результат.
Но как сказано в предисловии, не всегда модель нейронной сети очевида, прозрачна, оптимальна и осознаваема.
Собственно поэтому ИМХО автор предлогает подход создания модуля принятия решений не путём обучения, а осознанного построения на базе логических схем. Как следствие данная схема понятна, а значит и тестируема.
Ну и приводит метод, как минимизировать количество логических эллементов, дабы повысить экономический показатель эффективности, простоты схемы и как результат тестируемости.

Годная статья ИМХО. Спасибо автору, пишите ещё.

Maksym Ganenko

Maksym Ganenko Computer Vision Engineer в Upwork 23.11.2018 22:43

Ок, модель обучилась, у нас black box. Потом оказалось, что тренировочная выборка была смещена по сравнению с реальной — ок, берем правильные сэмплы и переобучаем. Data-driven.

В случае с детерменированным алгоритмом если мы что-то не учли, то надо переделывать весь алгоритм. В некоторых случаях типа классификации повседневных предметов на изображении алгоритм будет сильно уступать по точности нейронным сетям. Да, он быстрый, интерпретируемый, но не работает.

Rostislav Nikitin

Rostislav Nikitin .NET Senior Developer в Freelancer 23.11.2018 23:38

Потом оказалось, что тренировочная выборка была смещена по сравнению с реальной — ок, берем правильные сэмплы и переобучаем. Data-driven.

Оказалось что в некоторых случаях логическая схема работает не так как ожидалось. Садится девелопер, перепроектирует. Data-driven.

Разница лишь в том, что в случае нейронной сети, не девелопер, в ручную тренирует сеть (хотя по разному бывает), а процесс обучения автоматизирован. А в приведённой схеме, от начала и до конца, делает человек. И возможно при помощи эффективных инструменты, которые повышают надёжность и сокращают время разработки.

Каждый из подходов имеет место быть ИМХО.
Если нужна высокая надёжность, тестируемость, понтятность — данный случай в приоритете.

Если точность, или 100% предсказуемость не на первом месте, т.е. допустим процент неверных решений, и нужен максимально автоматический процесс обучения — то нейронная сеть подойдёт ИМХО больше. Опять же всё зависет от конкретного случая ИМХО.

Есть такие задачи, где просто необходимо очень чётко понимать как работает алгоритм. Он должен быть перетестирован вдоль и поперёк. Иначе к примеру он не будет соответствовать какому-то стандарту и его просто не примут. Думаю данный подход хорошо покрывает этот случай.

anonymous 23.11.2018 14:33

Rostislav Nikitin .NET Senior Developer в Freelancer 23.11.2018 23:47

Ну не знаю, помоему очевидно, что человек привёл альтернативу нейронным сетям... Т.е. вот есть нейронные сети, которые могут выступать в качестве модели для принятия решений. А вот мы можем запилить руками логическую схему, оптимизировать её (собственно все выкладки об этом) и она будет тоже прнимать решения. К тому же будет более понятная и тестируемая, чем аналогичная нейронная сеть. Я так понял посыл данного поста.
Но вот как заменить в каждом конкретном случае — ИМХО это уже задача не тривиальная. Очень сильно от контекста зависит, и возможно не всегда получится.

anonymous 24.11.2018 08:06

Дмитро Кривошей 25.11.2018 13:48

В багатьох задачах не можна застосувати нейронні мережі, бо вони не дають відповіді на питання «чому і як отриманий результат».

anonymous 26.11.2018 09:13

Дмитро Кривошей

Nikita Podgorbunskyi Software Engineer 23.11.2018 12:49

Для электроники вроде понятна ценность, а вот какие еще можно решать задачи? Есть ли у вас какие-то примеры или рекомендации по применению ?
Просто для человеко-читаемости иногда лучше написать больше кода, чтоб каждый блок был понятен, а не упростить до минимального кол-ва операций сравнения.

Rostislav Nikitin .NET Senior Developer в Freelancer 23.11.2018 23:43

Ну например для какого-нибудь компилятора, который на вход получает человеко-читаемые, возможно избыточные логические выражения, а на выходе выдаёт минимально возможный рантайм код.

Nikita Podgorbunskyi

Andriy Krot Software Engineer в IonIdea 24.11.2018 14:25

Оптимизация логических схем применима и в обычных проектах. Например пользователи могут задавать большой набор условий, часть из которых дорого проверять. Поэтому их алгоритмически оптимизируют, например, хорошо проверенным методом Куайна — макКласки.