Functional decomposition: Difference between revisions

Revision as of 03:48, 6 June 2023

Revision as of 03:58, 6 June 2023

Line 14:

{{clarify span|Interactions|reason=The notion of 'interaction' of mathematical functions is undefined, likewise for 'observable', 'perception' etc. I guess this paragraph confuses mathematical notions (like 'function') with physical intuitions (like 'process'); this should be fixed.|date=September 2020}} between the components are critical to the function of the collection. All interactions may not be {{clarify span|observable|date=September 2020}}, but possibly deduced through repetitive {{clarify span|perception|date=September 2020}}, synthesis, validation and verification of composite behavior.

== Basic mathematical definition ==

[[Image:Chow-liu.png|thumb|400 px|An example of a sparsely connected dependency structure. Direction of causal flow is upward.]]

For a multivariate function <math>y = f(x_1,x_2,\dots,x_n)</math>, functional decomposition generally refers to a process of identifying a set of functions <math>\{g_1, g_2, \dots g_m\}</math> such that

:<math>f(x_1,x_2,\dots,x_n) = \phi(g_1(x_1,x_2,\dots,x_n), g_2(x_1,x_2,\dots,x_n), \dots g_m(x_1,x_2,\dots,x_n))</math>

where <math>\phi</math> is some other function.{{clarify|reason=This definition is horribly underspecified, similar to e.g. decomposing a number into the sum of serveral others. Unless the set of admitted g_i or/and phi is given, it does not make sense at all. One trivial solution is m=n, g_i(x_1,...,x_n)=x_i, and phi=f; another one is m=1, g_1=f, and phi(x)=x.|date=September 2020}} Thus, we would say that the function <math>f</math> is decomposed into functions <math>\{g_1, g_2, \dots g_m\}</math>. This process is intrinsically hierarchical in the sense that we can (and often do) seek to further decompose the functions <math>g_i</math> into a collection of constituent functions <math>\{h_1, h_2, \dots h_p\}</math> such that

:<math>g_i(x_1,x_2,\dots,x_n) = \gamma(h_1(x_1,x_2,\dots,x_n), h_2(x_1,x_2,\dots,x_n), \dots h_p(x_1,x_2,\dots,x_n))</math>

where <math>\gamma</math> is some other function. Decompositions of this kind are interesting and important for a wide variety of reasons. In general, functional decompositions are worthwhile when there is a certain "sparseness" in the dependency structure; that is, when constituent functions are found to depend on approximately [[disjoint sets]] of variables. Thus, for example, if we can obtain a decomposition of <math>x_1 = f(x_2,x_3,\dots,x_6)</math> into a hierarchical composition of functions <math>\{g_1, g_2, g_3\}</math> such that <math>x_1 = g_1(x_2)</math>, <math>x_2 = g_2(x_3,x_4,x_5)</math>, <math>x_5 = g_3(x_6)</math>, as shown in the figure at right, this would probably be considered a highly valuable decomposition.

===Example: Arithmetic===

A basic example of functional decomposition is expressing the four binary arithmetic operations of addition, subtraction, multiplication, and division in terms of the two binary operations of addition <math>a + b</math> and multiplication <math>a \times b,</math> and the two unary operations of additive inversion <math>-a</math> and multiplicative inversion <math>1/a.</math> Subtraction can then be realized as the composition of addition and additive inversion, <math>a - b = a + (-b),</math> and division can be realized as the composition of multiplication and multiplicative inverse, <math>a \div b = a \times (1/b).</math> This simplifies the analysis of subtraction and division, and also makes it easier to axiomatize these operations in the notion of a [[Field (mathematics)|field]], as there are only two binary and two unary operations, rather than four binary operations.

Extending these primitive operations, there is a rich literature on the topic of [[polynomial decomposition]].

==Motivation for decomposition==