Пользователь
0,0
рейтинг
6 января 2014 в 14:51

Разработка → Восстановление логической функции из песочницы

image


В данной статье Вы сможете найти готовую реализацию и описание алгоритма предназначенного для реконструкции логических функций методом чёрного ящика. Под логической функцией я подразумеваю такую функцию, которая принимает в качестве аргументов множество булевых значений и соответственно возвращает одно. Пример:
def customlogic(params):
    return params[0] and params[1] and not params[5] and params[11] or params[2] and not params[3] or params[0] and params[5] and not params[6] or params[7] and not params[8]

В конце статьи алгоритм проверяется на данных полученных из реального мира.

По моему мнению, данная задача тесно связана с нейрофизиологией и как Вы могли уже догадаться я вдохновлялся работой нейронов, поэтому будут использованы аналогии связанные с работой и строением данного типа клеток. В частности, желание что-нибудь накодить пришло после прочтения статьи об устройстве и функционировании дендритов. Хоть бОльшую часть материала я не усвоил, но провёл некоторые аналогии.
  • Дендритные деревья выполняют логическую операцию AND, так как потенциалы приходящие от ветвей суммируются, а если нет сигнала от одной или нескольких ветвей, то скорее всего потенциал не дойдёт до сомы.
  • Cома выполняет OR, генерируя потенциал действия если хотя бы одно дерево доставило сигнал.
  • Ингибиторные(тормозящие) связи являются аналогом NOT. Правда есть баг, с точки зрения логики: NOT False = False, так как отсутствие сигнала от тормозящей связи само по себе не способно вызывать потенциал действия. Что сужает круг возможных функций, до тех которые при всех неактивных параметрах(False) не генерируют True. Следовательно единичный нейрон не может симулировать логическое отрицание, но вполне способен сделать XOR. Такое поведение хоть и является «странным», но несёт некоторые выгоды. Данный подход является довольно энергоэффективным, ведь если держать нейрон включённым когда все дендриты не активны — значить тратить энергию впустую. Конечно есть исключения, нейроны которые таки периодически включаются без стимуляции дендритов. Грубо говоря, можно симулировать AND NOT, но OR NOT нельзя

Думаю достаточно лирики, перейдём к делу.
Исходный код класса и пример
import random
class LogicReconstructer:
    groups=[]
    threshold = 0.99
    maxmem = 10
    numparams = 0

    def __init__(self,numparams,threshold = 0.99, totalmem = 10):
        self.numparams=numparams
        self.threshold=threshold
        self.maxmem=totalmem

    def getactive(self,params):
        if len(params)!=self.numparams:
            raise Exception("LogicReconstructer: numparams mismatch")

        active=[]
        for x in range(self.numparams):
            if params[x]:
                active.append(x)
        return  active

    def extractgroups(self,params,result):
        active=self.getactive(params)
        exist = False
        ignore = False

        if result and active:
            ind=0
            while ind<len(self.groups):

                if len(active)>len(self.groups[ind][0]) and self.issublist(self.groups[ind][0],active):
                    ignore=True
                    break

                elif len(active)==len(self.groups[ind][0]) and self.issublist(active,self.groups[ind][0]):
                    exist=True
                    break

                elif len(active)<len(self.groups[ind][0]) and self.issublist(active,self.groups[ind][0]):
                    del self.groups[ind]
                    ind-=1

                ind+=1

            if not exist and not ignore:
                self.groups.append([active,[0]*self.numparams,False])

    def extractinhibitors(self,params,result):
        active=self.getactive(params)

        if result:
            count=0
            for _,grp in enumerate(self.groups):
                if self.issublist(grp[0],active):
                    count+=1
                    if count>1:
                        return

        for _,grp in enumerate(self.groups):
            if not grp[2] and self.issublist(grp[0],active):

                neg=[]
                negvalue=False
                for y in range(self.numparams):
                    if grp[1][y]<=-self.threshold:
                        neg.append(y)
                        negvalue|=params[y]
                    elif grp[1][y]>=self.threshold:
                        grp[2]=True

                for y in range(self.numparams):
                    if params[y]:
                        if y in neg or not negvalue:
                            grp[1][y] = self.counting(grp[1][y],self.maxmem,result)


    def counting(self,prc,total,item):
        result=prc-prc/total
        if not item:
            result-=1/total
        else:
            result+=1/total
        return result

    def issublist(self,a,b):
        for ind,item in enumerate(a):
            if item not in b:
                return False
        return True

    def getsublist(self,a,b):
        result=[]
        for ind,item in enumerate(a):
            if item in b:
                result.append(item)
        return result

    def simulate(self,params):
        result=False
        for ind,item in enumerate(self.groups):
            if item[2]:
                locres=True
                for x in range(len(item[0])):
                    locres&=params[item[0][x]]
                for x in range(len(item[1])):
                    if item[1][x]<=-self.threshold:
                        locres=locres&~params[x]
                result|=locres
        return result

    def getlogicfunc(self,guess=False):
        result=""
        for ind,item in enumerate(self.groups):
            if item[2] or guess:
                locres=""
                for x in range(len(item[0])):
                    if x!=0:
                        locres+=" and "
                    locres+=str(item[0][x])
                for x in range(len(item[1])):
                    if item[1][x]<=-self.threshold:
                        locres+=" and not "+str(x)
                if ind!=0:
                    result+=" or "
                result+=locres
        return result

    def randparams(self):
        result = []
        for x in range(self.numparams):
            result.append(random.choice([True, False]))
        return result

    def isready(self):
        result=bool(self.groups)
        for ind,item in enumerate(self.groups):
            result&=item[2]
        return result

    def getlogicstuct(self):
        result = []
        for _,item in enumerate(self.groups):
            grp=[]
            if item[2]:
                for x in range(len(item[0])):
                    grp.append([item[0][x],True])
                for x in range(len(item[1])):
                    if item[1][x]<=-self.threshold:
                        grp.append([x,False])
            if grp:
                result.append(grp)
        return result

    def simulatebystruct(self,params,grps):
        for _,item in enumerate(grps):
            locres=True
            for _,param in enumerate(item):
                if param[1]:
                    locres&=params[param[0]]
                else:
                    locres&=~params[param[0]]
                if not locres:
                    break
            if locres:
                return True

        return  False

def customlogic(params):
    return params[0] and  params[1] and not params[5]and  params[11] or params[2] and not params[3]  \
               or params[0] and  params[5] and not params[6] or  params[7] and not params[8]

def newme():
    numparams = 12
    neuron=LogicReconstructer(numparams)
    while not neuron.isready():
        params=neuron.randparams()
        funcresult=customlogic(params)
        neuron.extractgroups(params,funcresult)
        neuron.extractinhibitors(params,funcresult)

    for x in range(1000):
        params=neuron.randparams()
        if neuron.simulate(params)!=customlogic(params):
            print("Simulate is wrong.")
            return

    print(neuron.getlogicfunc())

if __name__ == "__main__":
    newme()


Итак, мы имеем набор входных параметров, причём некоторые из них могут никак не влиять на результат выполнения, поэтому первым делом нужно понять какие параметры важны. Лучше начать со сбора независимых активационных групп, другими словами если результат работы функции — True, то записываем номера активных параметров в базу, с некоторыми оговорками, которые Вы можете посмотреть в методе extractgroups. Таким образом мы найдем параметры связанные логическим оператором AND. Этот этап можно сравнить с отращиванием дендритов.

Теперь же перейдем к настройке синапсов и прежде всего нужно выделить тормозящие связи. Так как группы являются условно независимыми от тормозящих связей, то значит можно воспользоваться теоремой Байеса. Иными словами если активационная группа сработала, то подсчитываем влияние остальных параметров на результат. Если параметр негативно влияет на результат, т.е. при его активации результат в большинстве случаев был False, то он и является тормозящим(AND NOT). Подробности смотрим в методе extractinhibitors.

Работа алгоритма считается завершённой когда, все группы получили подтверждение того, что все тормозящие связи были найдены. Подтверждение заключается в том, что Байесова вероятность одного из параметров перешагнула через threshold.

Но допустим, что у нас не хватает каких-то важных параметров, с которыми работает функция, то как это определить? Например:
params[0] and params[1] and not params[2] or params[3] and random.choice([True, False])

Мы знаем про 4 параметра, но не учитываем пятый. Конкретно в этом случаи активационная группа, которая состоит лишь из параметра 3, не переступит порог срабатывания(threshold). Но если бы мы всё-таки его учли, то он находился бы в одной группе с 3-им. Как Вы поняли группы разделяются логическим оператором OR.

А вот если не хватает целой группы:
params[0] and params[1] and not params[2] or random.choice([True, False]) and random.choice([True, False])
то группы(простите за тавтологию) при анализе разделяются на единичные параметры и каждый параметр станет активационным, что и является признаком.

Попробуйте поиграться с customlogic, дабы убедиться, что алгоритм работает. Я например заметил, что при большом количестве тормозящих связей в группе, она может не определиться.
Бонусная C++ простыня
// neuro.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <vector>
#include <map>
#include <stdlib.h>
#include <time.h>
#include <iostream>

using namespace std;

class Bool
{
public:

	Bool(): m_value(){}
	Bool( bool value ) : m_value(value){}

	operator bool() const { return m_value;}

	bool* operator& () { return &m_value; }
	const bool * const operator& () const { return &m_value; }

private:

	bool m_value;

};

class neuron
{
public:
	double threshold;
	int synapticmem;
	int numparams;
	map<int,vector<char>> groups;
	map<int,vector<double>> bayesian;
	map<int,map<char,bool>> grouplogic;
	int maxid;

	neuron(int numparams, double threshold = 0.99, int synapticmem = 10)
	{
		this->numparams=numparams;
		this->threshold=threshold;
		this->synapticmem=synapticmem;
		maxid=0;
		srand ( time(NULL) );
	}
	~neuron()
	{

	}
	
	vector<char> getactive(vector<Bool>& params)
	{
		if (params.size()!=numparams)
			throw 1;// numparams mismatch
		
		vector<char> active;
		for (int i=0;i<this->numparams;i++)
			if (params[i])
				active.push_back((char)i);

		return active;
	}

	void extractgroups(vector<Bool>& params, bool result)
	{
		vector<char> active= this->getactive(params);
		bool ignore = false;
		bool exist = false;
		
		if (result && active.size()>0)
		{
			map<int,vector<char>>::iterator i=this->groups.begin();
			while (i!=this->groups.end())
			{
				if (active.size()>i->second.size()&&this->issublist(i->second,active))
					{
						ignore=true;
						break;
					}
				else if (active.size()==i->second.size()&&this->issublist(active,i->second))
					{
						exist=true;
						break;
					}
				else if (active.size()<i->second.size()&&this->issublist(active,i->second))
					{
						this->bayesian.erase(i->first);
						this->grouplogic.erase(i->first);
						i=this->groups.erase(i);
					}
					else
						i++;
			}
			if (!exist && !ignore)
			{
				this->groups[this->maxid]=active;
				this->bayesian[this->maxid]=*new vector<double>(numparams,0);
				this->maxid++;
			}
		}
	}

	template< class T >
	bool issublist(vector<T>& sublist, vector<T>& fulllist)
	{
		for (int i=0;i<sublist.size();i++)
		{
			bool match = false;
			for (int n=0;n<fulllist.size();n++)
				if (sublist[i]==fulllist[n])
				{
					match=true;
					break;
				}
			if (!match)
				return false;	
		}
		return true;
	}

	template<class InputIterator, class T>
	InputIterator find (InputIterator first, InputIterator last, const T& val)
	{
		while (first!=last) {
			if (*first==val) return first;
			++first;
		}
		return last;
	}

	void extractinhibitors(vector<Bool>& params, bool result)
	{
		vector<char> active= this->getactive(params);

		if (result)
		{
			bool count = false;
			for (map<int,vector<char>>::iterator i=this->groups.begin();i!=this->groups.end();++i)
				if(this->issublist(i->second,active))
					if (!count)
						count=true;
					else
						return;
		}

		for (map<int,vector<char>>::iterator i=this->groups.begin();i!=this->groups.end();++i)
			if (grouplogic.count(i->first)==0)  
				if (this->issublist(i->second,active))
				{
					vector<char> neg;
					bool negvalue = false;
					for (int n=0;n<this->numparams;n++)
						if (this->bayesian[i->first][n]<=-1*this->threshold)
						{
							neg.push_back((char)n);
							negvalue|=params[n];
						}
						else if (this->bayesian[i->first][n]>=this->threshold)
							if (grouplogic.count(i->first)==0)
								this->build_grouplogic(i->first);
					
					for (int n=0;n<this->numparams;n++)
						if (params[n])
							if (!negvalue || this->find(neg.begin(), neg.end(), n) != neg.end())
 									this->bayesian[i->first][n]=counting(this->bayesian[i->first][n],result);
				}
	}

	 double counting(double prc, bool result)
	 {
		 double oneless = prc - prc/this->synapticmem;
		 if (result)
			 oneless+=1.0/this->synapticmem;
		 else
			 oneless-=1.0/this->synapticmem;
		 return oneless;
	 }
	void build_grouplogic(int indgroup)
	{
		for (int i=0;i<this->groups[indgroup].size();i++)
			 this->grouplogic[indgroup][(char)groups[indgroup][i]]=true;
		
		for (int i=0;i<numparams;i++)
			if (this->bayesian[indgroup][i]<=-1*threshold)
				this->grouplogic[indgroup][(char)i]=false;
	}
	bool isready()
	{
		int count = 0;
		for (map<int,vector<char>>::iterator i=this->groups.begin();i!=this->groups.end();++i) 
			if (grouplogic.count(i->first)!=0)
				count++;
		if (count==groups.size()&&groups.size()>0)
			return true;
		return false;
	}
	bool randomBool() {
		return rand() % 2 == 1;
	}
	void randparams(vector<Bool>& params)
	{
		for (int i=0;i<this->numparams;i++)
			params[i]=this->randomBool();
	}
	string getfunction()
	{
		string result="";
		bool maincount=false;
		for (map<int,map<char,bool>>::iterator i=this->grouplogic.begin();i!=this->grouplogic.end();++i)
		{	
			if (maincount)
				result+=" or ";

			string locres="";
			bool count = false;
			for (map<char,bool>::reverse_iterator n=i->second.rbegin();n!=i->second.rend();++n)
			{
				if (count)
					locres+=" and ";
				if (!n->second)
					locres+="not ";
				locres+=(char)(((int)'0')+(int)n->first);
				count=true;
			}
			result+=locres;
			maincount=true;
		}
		return result;
	}

	bool simulate(vector<Bool>& params)
	{
		bool result=false;
		for (map<int,map<char,bool>>::iterator i=this->grouplogic.begin();i!=this->grouplogic.end();++i)
		{	
			bool locres=true;
			bool count = false;
			for (map<char,bool>::iterator n=i->second.begin();n!=i->second.end();++n)
			{
				if (n->second)
					locres&=params[(int)n->first];
				else
					locres&=!params[(int)n->first];
			}
			result|=locres;
		}
		return result;
	}

};

bool customlogic(vector<Bool>& params)
{
	return params[0] && params[1] && !params[2] || params[3] && !params[1] || params[5] && !params[0] && params[1];
}

int _tmain(int argc, _TCHAR* argv[])
{
	int numparams = 6;
	
	clock_t start = clock() ;
	
	neuron* nine=new neuron(numparams);
	while (!nine->isready())
	{
		vector<Bool> params(numparams, false);
		nine->randparams(params);
		bool result = customlogic(params);
		nine->extractgroups(params,result);
		nine->extractinhibitors(params,result);
	}
	clock_t end = clock();
	double elapsed_time = (end-start)/(double)CLOCKS_PER_SEC;
	
	for (int i=0;i<1000;i++)
	{	
		vector<Bool> params(numparams, false);
		nine->randparams(params);
		if (nine->simulate(params)!=customlogic(params))
		{
			printf("Simulate is wrong");
			return 0;
		}
	}

	printf("%s\n%.3f sec\n",nine->getfunction().c_str(),elapsed_time);

	getchar();
	return 0;
}


Эксперимент


Конечно хорошо, что алгоритм работает, но справиться ли он с данными из реального мира? Я решил это проверить на одном наборе данных взятом отсюда. Задача заключается в том, чтобы классифицировать фальшивые банкноты от настоящих по четырём параметрам типа float. Надо сказать я совсем не понял что, они означают. Впрочем это только на руку чистоте эксперимента, ведь обучаться должна машина, а не я.
Вот что получилось
def getbinary(num,max,min =0 ):
    result=[]
    binnums=int(math.ceil(math.log(abs(min-max),2)))
    binstr=('{0:0'+str(binnums)+'b}').format(-min+num)
    for _,item in enumerate(binstr):
        if item=='1':
            result.append(True)
        else:
            result.append(False)
    return result

def banknotes():
    file = open('C:/bankdata.txt', 'r')# http://archive.ics.uci.edu/ml/datasets/banknote+authentication
    lines = file.readlines()
    file.close()

    data = []

    for i in range(len(lines)):
        data.append(lines[i].strip().split(","))
    lines.clear()

    numdata = []
    paramsmax=[0,0,0,0]
    paramsmin=[0,0,0,0]
    for i in range(len(data)):
        tmp=[]
        for x in range(len(data[i])):
            if x!=4:
                tmp.append(int(round(float(data[i][x]))))
                paramsmax[x]=max(paramsmax[x],int(round(float(data[i][x]))))
                paramsmin[x]=min(paramsmin[x],int(round(float(data[i][x]))))
            else:
                if data[i][x]=='0':
                    tmp.append(False)
                else:
                    tmp.append(True)
        numdata.append(tmp)
    data.clear()


    bindata=[]
    for i in range(len(numdata)):
        tmp=[]
        for x in range(len(numdata[i])):
            if x!=4:
                tmp.extend(getbinary(numdata[i][x],paramsmax[x],paramsmin[x]))
            else:
                tmp.extend([numdata[i][x]])
        bindata.append(tmp)
    numdata.clear()

    neuron = LogicReconstructer(len(bindata[0])-1,totalmem=7, threshold=0.98)

    for _,item in enumerate(bindata):
        neuron.extractgroups(item[:-1],item[-1:][0])

    ready=False
    while not neuron.isready():
        rnd=random.randint(0,len(bindata)-1)
        neuron.extractinhibitors(bindata[rnd][:-1],bindata[rnd][-1:][0])

    logicstruct=neuron.getlogicstuct()
    print(logicstruct)

    falsepositive = 0
    falsenegative = 0
    for _,item in enumerate(bindata):
       res = neuron.simulatebystruct(item[:-1],logicstruct)
       if res!=item[-1:][0]:
           if res:
               falsepositive+=1
           else:
               falsenegative+=1
    print(falsenegative/len(bindata),falsepositive/len(bindata))


Так как алгоритм принимает только бинарные данные мне пришлось округлить числа до целых и перевести в бинарную форму функцией getbinary. После обучения у меня вышла вот такая структура состоящая из 134-ёх логических групп:
logicstruct
    logicstr="[[[2, True], [3, True], [6, True], [7, True], [10, True], [11, True], [12, True], [13, True], [14, True], [16, True]], [[1, True], [3, True], [4, True], [8, True], [12, True], [15, True], [16, True], [17, True]], [[1, True], [3, True], [5, True], [10, True], [12, True], [14, True], [16, True], [6, False], [7, False], [8, False], [11, False]], [[1, True], [2, True], [5, True], [6, True], [7, True], [11, True], [13, True], [14, True], [16, True], [10, False]], [[1, True], [2, True], [5, True], [6, True], [11, True], [12, True], [13, True], [14, True], [16, True]], [[2, True], [3, True], [8, True], [9, True], [12, True], [15, True], [16, True]], [[1, True], [2, True], [3, True], [4, True], [8, True], [15, True], [17, True], [6, False], [7, False], [11, False]], [[1, True], [4, True], [7, True], [8, True], [11, True], [15, True], [2, False], [6, False]], [[1, True], [6, True], [10, True], [11, True], [12, True], [15, True], [16, True], [17, True]], [[0, True], [5, True], [6, True], [7, True], [8, True], [12, True], [14, True], [17, True], [10, False], [11, False], [13, False]], [[0, True], [4, True], [7, True], [15, True], [17, True], [6, False], [16, False]], [[1, True], [3, True], [5, True], [10, True], [12, True], [14, True], [17, True], [2, False], [6, False], [7, False]], [[0, True], [5, True], [6, True], [7, True], [12, True], [13, True], [14, True], [16, True], [2, False], [11, False]], [[0, True], [4, True], [7, True], [8, True], [16, True], [17, True], [6, False], [15, False]], [[1, True], [4, True], [8, True], [11, True], [13, True], [14, True], [2, False]], [[0, True], [4, True], [12, True], [14, True], [17, True], [6, False], [11, False], [13, False]], [[2, True], [3, True], [4, True], [8, True], [11, True], [15, True], [17, True], [1, False], [6, False], [7, False]], [[1, True], [3, True], [5, True], [6, True], [7, True], [11, True], [14, True], [2, False], [10, False], [12, False]], [[1, True], [2, True], [4, True], [12, True], [14, True], [11, False]], [[1, True], [6, True], [7, True], [8, True], [9, True], [14, True]], [[2, True], [5, True], [9, True], [14, True]], [[1, True], [4, True], [7, True], [11, True], [13, True], [14, True], [2, False], [3, False], [8, False], [12, False], [17, False]], [[1, True], [3, True], [5, True], [8, True], [10, True], [11, True], [14, True], [17, True], [6, False]], [[2, True], [3, True], [6, True], [7, True], [9, True], [13, True], [14, True]], [[1, True], [5, True], [6, True], [8, True], [11, True], [12, True], [13, True], [14, True], [16, True], [0, False], [7, False]], [[2, True], [3, True], [7, True], [9, True], [11, True], [14, True]], [[1, True], [5, True], [6, True], [7, True], [11, True], [12, True], [14, True], [16, True], [0, False], [8, False]], [[1, True], [3, True], [4, True], [8, True], [12, True], [13, True], [15, True], [16, True], [2, False], [5, False], [6, False], [11, False]], [[1, True], [6, True], [8, True], [10, True], [11, True], [12, True], [14, True]], [[1, True], [2, True], [4, True], [8, True], [13, True], [15, True], [16, True], [6, False]], [[1, True], [2, True], [5, True], [6, True], [10, True], [14, True], [16, True], [11, False], [13, False]], [[2, True], [3, True], [4, True], [7, True], [8, True], [11, True], [15, True], [1, False], [6, False], [17, False]], [[1, True], [6, True], [10, True], [11, True], [13, True], [15, True], [16, True], [17, True]], [[1, True], [2, True], [5, True], [7, True], [11, True], [12, True], [13, True], [14, True], [16, True]], [[2, True], [4, True], [6, True], [8, True], [11, True], [13, True], [16, True], [0, False], [15, False]], [[1, True], [5, True], [6, True], [7, True], [10, True], [14, True], [17, True], [2, False], [8, False], [11, False], [12, False]], [[1, True], [5, True], [10, True], [12, True], [13, True], [14, True], [16, True]], [[0, True], [4, True], [7, True], [15, True], [16, True], [6, False], [17, False]], [[1, True], [2, True], [3, True], [4, True], [7, True], [8, True], [16, True], [17, True], [6, False]], [[1, True], [2, True], [5, True], [6, True], [11, True], [14, True], [17, True], [10, False], [12, False]], [[1, True], [2, True], [4, True], [8, True], [12, True], [15, True], [16, True]], [[1, True], [4, True], [11, True], [13, True], [15, True], [16, True], [17, True], [5, False], [6, False], [7, False], [8, False]], [[2, True], [3, True], [5, True], [10, True], [11, True], [12, True], [13, True], [14, True]], [[2, True], [5, True], [8, True], [10, True], [11, True], [12, True], [13, True], [14, True]], [[1, True], [2, True], [5, True], [6, True], [7, True], [8, True], [11, True], [14, True], [3, False], [10, False], [12, False], [16, False], [17, False]], [[1, True], [7, True], [9, True], [13, True], [15, True], [16, True]], [[1, True], [2, True], [5, True], [10, True], [13, True], [14, True], [17, True], [3, False], [6, False], [11, False]], [[0, True], [5, True], [6, True], [7, True], [8, True], [11, True], [14, True], [17, True], [12, False], [16, False]], [[1, True], [3, True], [6, True], [7, True], [10, True], [11, True], [14, True], [5, False]], [[0, True], [5, True], [7, True], [8, True], [11, True], [12, True], [13, True], [14, True], [16, True], [2, False], [6, False]], [[2, True], [3, True], [4, True], [6, True], [11, True], [13, True], [16, True], [17, True], [1, False], [7, False], [8, False], [15, False]], [[1, True], [5, True], [6, True], [8, True], [10, True], [14, True], [17, True], [11, False]], [[1, True], [2, True], [5, True], [8, True], [10, True], [14, True], [17, True], [3, False], [6, False], [11, False]], [[2, True], [4, True], [6, True], [7, True], [11, True], [13, True], [15, True], [1, False], [16, False], [17, False]], [[1, True], [4, True], [11, True], [12, True], [14, True], [17, True], [2, False], [3, False], [13, False]], [[1, True], [2, True], [3, True], [5, True], [6, True], [7, True], [8, True], [12, True], [13, True], [14, True]], [[1, True], [2, True], [5, True], [6, True], [10, True], [12, True], [14, True], [17, True], [3, False], [7, False]], [[1, True], [6, True], [7, True], [9, True], [13, True], [14, True]], [[1, True], [9, True], [11, True], [12, True], [13, True], [15, True], [16, True], [17, True]], [[1, True], [7, True], [9, True], [12, True], [13, True], [14, True]], [[1, True], [2, True], [5, True], [10, True], [12, True], [14, True], [16, True]], [[3, True], [4, True], [6, True], [11, True], [12, True], [16, True], [0, False]], [[1, True], [8, True], [9, True], [12, True], [15, True], [16, True]], [[2, True], [4, True], [6, True], [7, True], [11, True], [13, True], [17, True], [15, False]], [[1, True], [2, True], [6, True], [7, True], [8, True], [10, True], [12, True], [14, True], [17, True]], [[2, True], [3, True], [4, True], [8, True], [11, True], [13, True], [14, True], [1, False], [12, False]], [[0, True], [4, True], [8, True], [13, True], [14, True], [2, False], [11, False], [12, False], [16, False], [17, False]], [[2, True], [3, True], [4, True], [8, True], [11, True], [15, True], [16, True], [1, False], [6, False], [7, False], [17, False]], [[2, True], [4, True], [8, True], [11, True], [12, True], [14, True], [0, False], [3, False]], [[1, True], [5, True], [6, True], [7, True], [11, True], [13, True], [14, True], [17, True], [0, False]], [[2, True], [3, True], [6, True], [8, True], [9, True], [13, True], [14, True]], [[1, True], [5, True], [6, True], [8, True], [10, True], [14, True], [16, True], [11, False]], [[1, True], [2, True], [6, True], [7, True], [10, True], [11, True], [14, True], [17, True]], [[1, True], [3, True], [6, True], [10, True], [11, True], [13, True], [14, True], [5, False]], [[1, True], [2, True], [3, True], [5, True], [7, True], [8, True], [11, True], [12, True], [14, True], [16, True]], [[2, True], [3, True], [4, True], [6, True], [11, True], [12, True], [15, True], [1, False], [7, False]], [[1, True], [2, True], [5, True], [10, True], [13, True], [14, True], [16, True], [6, False], [11, False]], [[1, True], [2, True], [3, True], [5, True], [6, True], [8, True], [11, True], [14, True], [16, True]], [[1, True], [2, True], [5, True], [6, True], [7, True], [8, True], [12, True], [13, True], [14, True], [17, True]], [[1, True], [3, True], [5, True], [6, True], [10, True], [13, True], [14, True], [17, True], [2, False], [11, False]], [[2, True], [3, True], [9, True], [11, True], [12, True], [13, True], [15, True], [16, True]], [[2, True], [3, True], [6, True], [7, True], [8, True], [9, True], [14, True], [17, True]], [[1, True], [8, True], [9, True], [11, True], [13, True], [14, True]], [[1, True], [2, True], [6, True], [7, True], [10, True], [11, True], [14, True], [16, True], [5, False], [13, False]], [[1, True], [3, True], [6, True], [10, True], [11, True], [12, True], [14, True], [17, True]], [[1, True], [2, True], [7, True], [8, True], [10, True], [11, True], [12, True], [13, True], [14, True]], [[0, True], [5, True], [6, True], [7, True], [11, True], [14, True], [16, True], [8, False], [12, False], [13, False]], [[1, True], [4, True], [7, True], [11, True], [15, True], [17, True], [2, False], [6, False]], [[0, True], [5, True], [7, True], [11, True], [12, True], [13, True], [14, True], [16, True], [17, True], [2, False], [6, False]], [[3, True], [4, True], [6, True], [7, True], [11, True], [13, True], [15, True], [0, False], [17, False]], [[1, True], [3, True], [5, True], [6, True], [11, True], [12, True], [13, True], [14, True], [16, True]], [[1, True], [3, True], [5, True], [10, True], [11, True], [13, True], [14, True], [17, True], [2, False], [6, False]], [[1, True], [6, True], [7, True], [10, True], [11, True], [12, True], [13, True], [14, True], [16, True]], [[1, True], [3, True], [4, True], [8, True], [12, True], [13, True], [15, True], [17, True], [2, False], [6, False], [7, False], [11, False]], [[4, True], [6, True], [8, True], [11, True], [12, True], [17, True], [0, False], [15, False]], [[1, True], [7, True], [8, True], [10, True], [11, True], [12, True], [15, True], [16, True], [17, True]], [[1, True], [5, True], [10, True], [12, True], [13, True], [14, True], [17, True]], [[1, True], [3, True], [6, True], [7, True], [8, True], [10, True], [12, True], [14, True]], [[0, True], [5, True], [6, True], [7, True], [12, True], [13, True], [14, True], [17, True], [3, False], [8, False], [11, False]], [[3, True], [4, True], [6, True], [7, True], [8, True], [11, True], [13, True], [16, True], [15, False]], [[2, True], [3, True], [4, True], [11, True], [12, True], [14, True], [0, False], [1, False], [8, False]], [[4, True], [6, True], [7, True], [8, True], [11, True], [13, True], [15, True], [1, False], [2, False], [3, False]], [[1, True], [2, True], [4, True], [11, True], [14, True], [3, False], [6, False], [10, False]], [[2, True], [3, True], [6, True], [7, True], [9, True], [12, True], [15, True], [16, True], [17, True]], [[1, True], [3, True], [4, True], [7, True], [11, True], [15, True], [16, True], [2, False], [6, False]], [[2, True], [3, True], [8, True], [9, True], [11, True], [13, True], [15, True], [16, True], [17, True]], [[2, True], [3, True], [6, True], [7, True], [10, True], [11, True], [12, True], [13, True], [14, True], [17, True]], [[1, True], [3, True], [4, True], [7, True], [12, True], [13, True], [15, True], [17, True], [6, False]], [[1, True], [4, True], [8, True], [11, True], [15, True], [16, True], [2, False], [13, False]], [[1, True], [6, True], [7, True], [8, True], [10, True], [12, True], [13, True], [14, True]], [[1, True], [2, True], [5, True], [7, True], [11, True], [12, True], [13, True], [14, True], [17, True]], [[2, True], [4, True], [6, True], [8, True], [11, True], [13, True], [17, True], [0, False], [15, False]], [[1, True], [2, True], [3, True], [5, True], [6, True], [7, True], [12, True], [13, True], [14, True], [17, True]], [[4, True], [5, True], [11, True], [13, True], [16, True], [1, False], [15, False]], [[1, True], [2, True], [4, True], [8, True], [12, True], [15, True], [17, True], [11, False]], [[2, True], [3, True], [4, True], [7, True], [11, True], [15, True], [17, True], [1, False], [6, False]], [[2, True], [4, True], [7, True], [11, True], [12, True], [14, True], [0, False], [3, False]], [[2, True], [3, True], [5, True], [6, True], [7, True], [11, True], [12, True], [14, True], [17, True], [0, False], [8, False], [16, False]], [[1, True], [3, True], [4, True], [11, True], [14, True], [2, False], [6, False], [16, False]], [[2, True], [3, True], [6, True], [7, True], [9, True], [13, True], [15, True], [16, True], [17, True]], [[2, True], [8, True], [9, True], [11, True], [14, True]], [[1, True], [2, True], [3, True], [4, True], [7, True], [15, True], [17, True], [6, False], [11, False]], [[1, True], [6, True], [7, True], [8, True], [10, True], [11, True], [14, True], [5, False]], [[1, True], [2, True], [3, True], [5, True], [6, True], [7, True], [12, True], [13, True], [14, True], [16, True]], [[1, True], [5, True], [6, True], [11, True], [12, True], [14, True], [17, True], [2, False]], [[2, True], [3, True], [4, True], [11, True], [13, True], [15, True], [16, True], [1, False]], [[2, True], [8, True], [9, True], [11, True], [12, True], [15, True], [16, True]], [[0, True], [5, True], [6, True], [7, True], [11, True], [13, True], [14, True], [17, True], [1, False], [2, False], [8, False], [12, False]], [[1, True], [2, True], [6, True], [10, True], [11, True], [12, True], [14, True], [17, True]], [[0, True], [4, True], [8, True], [13, True], [15, True], [17, True], [2, False], [3, False], [5, False], [6, False]], [[1, True], [3, True], [7, True], [8, True], [10, True], [11, True], [12, True], [14, True], [5, False], [6, False], [16, False]], [[1, True], [2, True], [3, True], [5, True], [8, True], [11, True], [12, True], [13, True], [14, True], [16, True]], [[1, True], [2, True], [3, True], [5, True], [6, True], [11, True], [13, True], [14, True], [16, True], [10, False]], [[1, True], [4, True], [8, True], [11, True], [15, True], [17, True], [2, False], [12, False]]]"
    logicstruct=literal_eval(logicstr)


которая даёт 2.8% ложно отрицательных и 0.6% ложно положительных ответов. Эти 134 группы обобщили около 700 положительных примеров. Всего было 1372 записи. Каждый запуск может генерировать новую структуру. Так же прошу заметить, что я не разделял данные на обучающею и проверочную выборки и критика в плане: «Да алгоритм просто всё запомнил и на новых данных накроется» — вполне уместна.

image
@whileNotFalse
карма
7,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (8)

  • +4
    > Задача заключается в том, чтобы классифицировать фальшивые банкноты от настоящих по четырём параметрам.

    Дендритные деревья, это конечно интересно. Но вот вы про карты Карно слышали?

    image
    • 0
      Разумеется, правда я их не разу не использовал. Как мне известно, они разработаны для ручного восстановления и плохо справляются с большим числом параметров(а как они разбираются с лишними параметрами?). Чтобы внести ясность, я всё затеял лишь ради аналогии и первоначально никакого эксперимента не предполагалось.
    • +1
      >>четырём параметрам
      Которые являются числами типа float и если их преобразовать в бинарные значения функцией getbinary, то получиться 18 параметров.
    • +1
      Метод карно, на сколько я помню, для минимизации логической функции. А для восстановления есть спосчобы попроще. Аравда потом придется все же минимизировать, но это уже мелочи.
  • +2
    Ох, да. Конечно, для полной ясности качества полученного кода не хватает хотя бы скользящего контроля.

    А вообще, исходная постановка задачи (и заголовок тем более) ну очень напоминает построение ДНФ для функции, заданной таблично.
    • 0
      Да, Вы правильно поняли. Задача заключалась бы в построение ДНФ, если бы не было ограничения на использование логического отрицания.
  • 0
    Один из самых популярных программируемых методов для решения такой задачи — метод Квайна-МакКласки, насколько я помню. Есть кроме него и карт Карно еще один метод, но его к сожалению уже забыл…

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

    Но статья хорошая, понравилась, спасибо.
    • 0
      Не могу выразить на сколько Ваш комментарий важен для меня. Благодарю, за лестные слова.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.