如何将过程算法转换为逻辑程序？
How to convert a procedural algorithm to a logic program?
我如何根据过程描述在 Prolog 中实现算法，以便最好地利用逻辑范例。
我有时发现很难根据给定的算法过程描述来编写序言程序。我在下面给出了一个尝试的具体例子。请注意，我有称为 innerforloop 或 convergedloop 的谓词。这似乎不对，而且很难检查我的实现是否与算法描述相匹配。此代码是否与描述相符？这些谓词的更好名称是什么？还是应该以不同的方式组织代码？
示例算法：训练感知器分类器。
Input: labelled training data in D homogeneous coordinates;
learning rate n.
Output: weight vector W defining classifier ŷ = sign(w⃗ ⋅ x⃗).
w⃗ <- 0;
converged <- false;
While converged = false do
converged <- true;
for i = 1 to |D| do
if yiw⃗⋅x⃗i <0
then
w⃗<- w⃗+n * yi * x⃗i;
converged <-false
end
end
end
我的实现：
perceptron(Pos,Neg,classifier(W,0)):-
Pos =[OneExample|_],
length(OneExample,NumberOfFeatures),
populate_list(0,NumberOfFeatures,Zerovector),
maplist(myappend([1]),Pos,PosClass),
maplist(myappend([-1]),Neg,NegClass),
append(PosClass,NegClass,Examples),
convergedloop(Examples,Zerovector,W).
convergedloop(Examples,Inputvector,OutputVector):-
innerforloop(Examples,Inputvector,UpdateVector),
check_converged(Examples,Inputvector,UpdateVector,OutputVector).
check_converged(_Examples,W1,W2,W2):-W1=W2.
check_converged(Examples,W1,W2,W3):-
dif(W1,W2),
convergedloop(Examples,W2,W3).
innerforloop([],W,W).
innerforloop(ExamplesWithClass,W1,WFin):-
ExamplesWithClass =[One|Rest],
update_weight(One,W1,W2),
innerforloop(Rest,W2,WFin).
learning_rate(0.1).
update_weight(Example_with_class,W1,W2):-
misclassified(W1,Example_with_class,true),
learning_rate(N),
append(Example,[Class|[]],Example_with_class),
Scalar is N *Class,
scalar_multiplication(Scalar,Example,ExampleScaled),
vector_addition(W1,ExampleScaled,W2).
update_weight(Example_with_class,W,W):-
misclassified(W,Example_with_class,false).
misclassified(W,Example_with_class,TrueFalse):-
append(Example,[Class|[]],Example_with_class),
dot_product(Example,W,Dot),
multiply(Dot,Class,Value),
( Value =<0->TrueFalse=true;TrueFalse=false).
%%%background predicates
myappend(Y,X,Z):-
append(X,Y,Z).
multiply(X,Y,Z):-
Z is X*Y.
vector_addition(X,Y,Z):-
maplist(my_plus,X,Y,Z).
dot_product(V1,V2,Dot):-
maplist(multiply,V1,V2,VMul),
sumlist(VMul,Dot).
scalar_multiplication(S,X,SX):-
maplist(multiply(S),X,SX).
populate_list(Pop,Length,ListPoped):-
length(List,Length),findall(X,(member(X,List),X=Pop),ListPoped).
%%%Data
linear_sep_data(Pos,Negs,All):-
All=[
[1.5998426,0.52985437,1],
[0.25065517,1.30425162,1],
[0.76148911,0.60419602,1],
[0.75591032,-0.78994764,1],
[1.63605539,0.9225655,1],
[2.70520379,0.93285704,1],
[1.82870703,2.34804646,1],
[-0.08549264,0.99868399,1],
[0.44906531,0.90555838,1],
[0.49966187,1.59299327,1],
[1.00003726,-0.13822094,1],
[1.67943676,1.25283262,1],
[-1.00158649,2.73839505,1],
[3.32539035,-0.39289509,1],
[2.17885898,0.05984356,1],
[1.85977529,0.76782626,1],
[1.34470454,0.18312675,1],
[0.5974872,0.1228956,1],
[-1.52394333,-1.24558361,-1],
[-2.48452861,-1.91070328,-1],
[-1.04605257,-2.55270759,-1],
[1.02370408,-1.67944911,-1],
[-0.80492117,-1.49215482,-1],
[-1.64954319,-3.41635041,-1],
[-2.35543276,-0.37750433,-1],
[-0.32384031,-2.08235145,-1],
[-1.56576954,-1.22018985,-1],
[-1.27853841,-1.28469686,-1],
[-1.97696119,0.23717806,-1],
[-1.78965834,-1.09026084,-1]],
findall(Instance,(member(InstanceC,All),append(Instance,[1|[]],InstanceC)),Pos),
findall(Instance,(member(InstanceC,All),append(Instance,[-1|[]],InstanceC)),Negs).
在 Prolog 中命名事物的关键见解是逻辑程序定义了实体之间的关系。理想情况下，谓词名称会指示每个参数描述了哪些实体。
因此，在这种情况下，forloop 或 innerloop 这样的名字对您来说是 错误的 ：来自像 forloop 这样的名字（或更具可读性：for_loop)，我们宁愿期望例如 "for loop" 是什么的句法描述，但肯定不是循环的实际 计算 应该执行。
命令式算法描述了全局状态的一系列破坏性修改。为了将命令式算法转化为声明式范式，我们改变了观点，转而描述状态之间的关系。
我们使用以下命名约定，这在许多程序中都很有用：S0表示初始状态。 S1表示一步计算后的状态。 S2、S3等表示进一步的状态，最后，S表示最终状态。
现在考虑您引用的具体示例：
命令式算法的本质是反复修改状态，直到达到最终状态。在声明性范式中描述这种状态转换序列的一种方法如下：
state0_state(S0, S) :-
state_next(S0, S1),
state0_state_(S0, S1, S).
state0_state_(S0, S, S) :-
close_enough(S0, S).
state0_state_(S0, S1, S) :-
not_close_enough(S0, S1),
state0_state(S1, S).
其中 state_next/2、close_enough/2 和 not_close_enough/2 必须由您提供。我把它留作练习。请注意，谓词 state0_state/2 的命名方式使每个参数的含义一目了然。稍加思考，您可能会找到更多描述性的名称，例如 training0_training/2.
根据您在这方面的表现，我们观察到声明式范例的一个重要优势：代码可以全方位使用。这意味着例如您还可以 post 最一般的查询：
?- state0_state(S0, S).
并理想地获得处于这种关系中的答案状态。
关于命名谓词的另一个提示：避免命令式。命令式在声明式范式中没有什么意义，因为许多谓词可以用于多个方向，而命令式总是暗示一个方向。
我如何根据过程描述在 Prolog 中实现算法，以便最好地利用逻辑范例。
我有时发现很难根据给定的算法过程描述来编写序言程序。我在下面给出了一个尝试的具体例子。请注意，我有称为 innerforloop 或 convergedloop 的谓词。这似乎不对，而且很难检查我的实现是否与算法描述相匹配。此代码是否与描述相符？这些谓词的更好名称是什么？还是应该以不同的方式组织代码？
示例算法：训练感知器分类器。
Input: labelled training data in D homogeneous coordinates;
learning rate n.
Output: weight vector W defining classifier ŷ = sign(w⃗ ⋅ x⃗).
w⃗ <- 0;
converged <- false;
While converged = false do
converged <- true;
for i = 1 to |D| do
if yiw⃗⋅x⃗i <0
then
w⃗<- w⃗+n * yi * x⃗i;
converged <-false
end
end
end
我的实现：
perceptron(Pos,Neg,classifier(W,0)):-
Pos =[OneExample|_],
length(OneExample,NumberOfFeatures),
populate_list(0,NumberOfFeatures,Zerovector),
maplist(myappend([1]),Pos,PosClass),
maplist(myappend([-1]),Neg,NegClass),
append(PosClass,NegClass,Examples),
convergedloop(Examples,Zerovector,W).
convergedloop(Examples,Inputvector,OutputVector):-
innerforloop(Examples,Inputvector,UpdateVector),
check_converged(Examples,Inputvector,UpdateVector,OutputVector).
check_converged(_Examples,W1,W2,W2):-W1=W2.
check_converged(Examples,W1,W2,W3):-
dif(W1,W2),
convergedloop(Examples,W2,W3).
innerforloop([],W,W).
innerforloop(ExamplesWithClass,W1,WFin):-
ExamplesWithClass =[One|Rest],
update_weight(One,W1,W2),
innerforloop(Rest,W2,WFin).
learning_rate(0.1).
update_weight(Example_with_class,W1,W2):-
misclassified(W1,Example_with_class,true),
learning_rate(N),
append(Example,[Class|[]],Example_with_class),
Scalar is N *Class,
scalar_multiplication(Scalar,Example,ExampleScaled),
vector_addition(W1,ExampleScaled,W2).
update_weight(Example_with_class,W,W):-
misclassified(W,Example_with_class,false).
misclassified(W,Example_with_class,TrueFalse):-
append(Example,[Class|[]],Example_with_class),
dot_product(Example,W,Dot),
multiply(Dot,Class,Value),
( Value =<0->TrueFalse=true;TrueFalse=false).
%%%background predicates
myappend(Y,X,Z):-
append(X,Y,Z).
multiply(X,Y,Z):-
Z is X*Y.
vector_addition(X,Y,Z):-
maplist(my_plus,X,Y,Z).
dot_product(V1,V2,Dot):-
maplist(multiply,V1,V2,VMul),
sumlist(VMul,Dot).
scalar_multiplication(S,X,SX):-
maplist(multiply(S),X,SX).
populate_list(Pop,Length,ListPoped):-
length(List,Length),findall(X,(member(X,List),X=Pop),ListPoped).
%%%Data
linear_sep_data(Pos,Negs,All):-
All=[
[1.5998426,0.52985437,1],
[0.25065517,1.30425162,1],
[0.76148911,0.60419602,1],
[0.75591032,-0.78994764,1],
[1.63605539,0.9225655,1],
[2.70520379,0.93285704,1],
[1.82870703,2.34804646,1],
[-0.08549264,0.99868399,1],
[0.44906531,0.90555838,1],
[0.49966187,1.59299327,1],
[1.00003726,-0.13822094,1],
[1.67943676,1.25283262,1],
[-1.00158649,2.73839505,1],
[3.32539035,-0.39289509,1],
[2.17885898,0.05984356,1],
[1.85977529,0.76782626,1],
[1.34470454,0.18312675,1],
[0.5974872,0.1228956,1],
[-1.52394333,-1.24558361,-1],
[-2.48452861,-1.91070328,-1],
[-1.04605257,-2.55270759,-1],
[1.02370408,-1.67944911,-1],
[-0.80492117,-1.49215482,-1],
[-1.64954319,-3.41635041,-1],
[-2.35543276,-0.37750433,-1],
[-0.32384031,-2.08235145,-1],
[-1.56576954,-1.22018985,-1],
[-1.27853841,-1.28469686,-1],
[-1.97696119,0.23717806,-1],
[-1.78965834,-1.09026084,-1]],
findall(Instance,(member(InstanceC,All),append(Instance,[1|[]],InstanceC)),Pos),
findall(Instance,(member(InstanceC,All),append(Instance,[-1|[]],InstanceC)),Negs).
在 Prolog 中命名事物的关键见解是逻辑程序定义了实体之间的关系。理想情况下，谓词名称会指示每个参数描述了哪些实体。
因此，在这种情况下，forloop 或 innerloop 这样的名字对您来说是 错误的 ：来自像 forloop 这样的名字（或更具可读性：for_loop)，我们宁愿期望例如 "for loop" 是什么的句法描述，但肯定不是循环的实际 计算 应该执行。
命令式算法描述了全局状态的一系列破坏性修改。为了将命令式算法转化为声明式范式，我们改变了观点，转而描述状态之间的关系。
我们使用以下命名约定，这在许多程序中都很有用：S0表示初始状态。 S1表示一步计算后的状态。 S2、S3等表示进一步的状态，最后，S表示最终状态。
现在考虑您引用的具体示例：
命令式算法的本质是反复修改状态，直到达到最终状态。在声明性范式中描述这种状态转换序列的一种方法如下：
state0_state(S0, S) :-
state_next(S0, S1),
state0_state_(S0, S1, S).
state0_state_(S0, S, S) :-
close_enough(S0, S).
state0_state_(S0, S1, S) :-
not_close_enough(S0, S1),
state0_state(S1, S).
其中 state_next/2、close_enough/2 和 not_close_enough/2 必须由您提供。我把它留作练习。请注意，谓词 state0_state/2 的命名方式使每个参数的含义一目了然。稍加思考，您可能会找到更多描述性的名称，例如 training0_training/2.
根据您在这方面的表现，我们观察到声明式范例的一个重要优势：代码可以全方位使用。这意味着例如您还可以 post 最一般的查询：
?- state0_state(S0, S).
并理想地获得处于这种关系中的答案状态。
关于命名谓词的另一个提示：避免命令式。命令式在声明式范式中没有什么意义，因为许多谓词可以用于多个方向，而命令式总是暗示一个方向。