Funktionell nedbrytning

I matematik är funktionell nedbrytning processen att lösa upp ett funktionellt förhållande till dess beståndsdelar på ett sådant sätt att den ursprungliga funktionen kan rekonstrueras (dvs. omkomponeras) från dessa delar genom funktionssammansättning .

Denna nedbrytningsprocess kan genomföras för att få insikt i identiteten av de ingående komponenterna som kan återspegla individuella fysiska processer av intresse. Även funktionell nedbrytning kan resultera i en komprimerad representation av den globala funktionen, en uppgift som är genomförbar endast när de ingående processerna har en viss nivå av modularitet (dvs. oberoende eller icke-interaktion).

Interaktioner ^{[ förtydliga ]} mellan komponenterna är avgörande för samlingens funktion. Alla interaktioner kanske inte är observerbara ^{[ klargöra ]} , men möjligen härledda genom repetitiv perception ^{[ klargör ]} , syntes, validering och verifiering av sammansatt beteende.

Grundläggande matematisk definition

Ett exempel på en glest sammankopplad beroendestruktur. Orsaksflödets riktning är uppåt.

För en multivariat funktion $y=f(x_{1},x_{2},\dots ,x_{n})$ avser funktionell nedbrytning i allmänhet till en process för att identifiera en uppsättning funktioner $\{g_{1},g_{2},\dots g_{m}\}$ så att

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}))

där $\phi$ är någon annan funktion. ^{[ förtydligande behövs ]} Således skulle vi säga att funktionen $f$ är uppdelad i funktioner $\{g_{1},g_{2},\dots g_{m}\}$ . Denna process är i sig hierarkisk i den meningen att vi kan (och ofta gör det) försöka sönderdela funktionerna $g_{i}$ i en samling av ingående funktioner $\{h_{1},h_{2},\dots h_{p}\}$ så att

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}))

där $\gamma$ är någon annan funktion. Nedbrytningar av detta slag är intressanta och viktiga av en mängd olika skäl. I allmänhet är funktionella nedbrytningar värda när det finns en viss "gleshet" i beroendestrukturen; det vill säga när ingående funktioner befinns bero på ungefär disjunkta uppsättningar av variabler. Således, till exempel, om vi kan erhålla en nedbrytning av $x_{1}=f(x_{2},x_{3},\dots ,x_{6})$ till en hierarkisk sammansättning av funktioner $\{g_{1},g_{2},g_{3}\}$ så att $x_{1}=g_{1}(x_{2})$ , $x_{2}=g_ {2}(x_{3},x_{4},x_{5})$ , $x_{5}=g_{3}(x_{6})$ , som visas i figuren till höger skulle detta förmodligen anses vara en mycket värdefull nedbrytning.

Exempel: Aritmetik

Ett grundläggande exempel på funktionell nedbrytning är att uttrycka de fyra binära aritmetiska operationerna addition, subtraktion, multiplikation och division i termer av de två binära operationerna addition $a+b$ och multiplikation $a\times b,$ och de två unära operationerna additiv inversion $-a$ och multiplikativ inversion $1/a.$ Subtraktion kan sedan realiseras som sammansättningen av addition och additiv inversion, $ab=a+(-b),$ och division kan realiseras som sammansättningen av multiplikation och multiplikativ invers, $a\div b=a\times (1/b).$ Detta förenklar analysen av subtraktion och division, och gör det också lättare att axiomatisera dessa operationer i begreppet ett fält , eftersom det bara finns två binära och två unära operationer, snarare än fyra binära operationer.

För att utöka dessa primitiva operationer finns det en rik litteratur om ämnet polynomnedbrytning .

Exempel: Nedbrytning av kontinuerliga funktioner

Motivation för nedbrytning

Till varför nedbrytningen är värdefull är anledningen tvåfaldig. För det första tillåter nedbrytning av en funktion till icke-samverkande komponenter i allmänhet mer ekonomiska representationer av funktionen. Till exempel, på en uppsättning kvartära (dvs. 4-ära) variabler, som representerar den fullständiga funktionen $x_{1}=f(x_{2) },x_{3},\dots ,x_{6})$ kräver lagring av $4^{5}=1024$ värden, värdet på funktionen för varje element i den kartesiska produkten ${\displaystyle \{x_{2},x_{3},\dots ,x_{6}\}} ,$ dvs var och en av de 1024 möjliga kombinationerna för $\{x_{2},x_{3},\dots ,x_{6}\}$ . Men om nedbrytningen till $\{g_{1},g_{2},g_{3}\}$ som anges ovan är möjlig, då är $g_{1}=g_{1}(x_{2})$ kräver lagring av 4 värden, $g_{2}= g_{2}(x_{3},x_{4},x_{5})$ kräver lagring av $4^{3}=64$ värden, och $g_{3}=g_{3}(x_{6})$ kräver återigen att endast 4 värden lagras. Så i kraft av nedbrytningen behöver vi bara lagra $4+64+4=72$ värden snarare än 1024 värden, en dramatisk besparing.

Orsakspåverkan på West Side Highway-trafiken. Väder och trafik på GW Bridge skärmar av andra influenser

Intuitivt uppnås denna minskning av representationsstorleken helt enkelt för att varje variabel endast beror på en delmängd av de andra variablerna. Variabel $x_{1}$ beror alltså bara direkt på variabel ${\displaystyle x_{2}} ,$ snarare än beroende på hela uppsättningen av variabler. Vi skulle säga att variabel $x_{2}$ skärmar bort variabel $x_{1}$ från resten av världen. Praktiska exempel på detta fenomen omger oss, som diskuteras i "Filosofiska överväganden" nedan, men låt oss bara överväga det speciella fallet med "norrgående trafik på West Side Highway ." Låt oss anta att denna variabel ( ${x_{1}}$ ) antar tre möjliga värden av {"rör sig långsamt", "rör sig dödligt långsamt", "rör sig inte alls"}. Låt oss nu säga att variabel ${x_{1}}$ beror på två andra variabler, "väder" med värden på {"sol", "regn", "snö"} och " GW Bridge- trafik" med värden {"10mph", "5mph", "1mph"}. Poängen här är att även om det säkerligen finns många sekundära variabler som påverkar vädervariabeln (t.ex. lågtryckssystem över Kanada, fjärilsfladder i Japan, etc.) och brotrafikvariabeln (t.ex. en olycka på I-95 , presidentvalet) kortegen, etc.) alla dessa andra sekundära variabler är inte direkt relevanta för West Side Highway-trafiken. Allt vi behöver (hypotetiskt) för att förutsäga West Side Highway-trafiken är vädret och GW Bridge-trafiken, eftersom dessa två variabler avskärmar West Side Highway-trafiken från all annan potentiell påverkan. Det vill säga alla andra influenser verkar genom dem.

Utanför rent matematiska överväganden är det kanske största värdet av funktionell nedbrytning den insikt den ger i världens struktur. När en funktionell nedbrytning kan uppnås ger detta ontologisk information om vilka strukturer som faktiskt finns i världen, och hur de kan förutsägas och manipuleras. Till exempel, i illustrationen ovan, om man lär sig att ${x_{1}}$ direkt endast beror på ${x_{2}}$ , betyder detta att för förutsägelseändamål av ${x_{1}}$ , det räcker med att bara veta ${x_{2}}$ . Dessutom kan interventioner för att påverka ${x_{1}}$ göras direkt på ${\displaystyle {x_{2}}},$ och inget ytterligare kan erhållas genom att intervenera på variablerna $\{x_{3},x_{4},x_{5}\}$ eftersom dessa i alla fall endast verkar genom ${\displaystyle {x_{2}}} .$

Filosofiska överväganden

De filosofiska antecedenten och förgreningarna av funktionell nedbrytning är ganska breda, eftersom funktionell nedbrytning i en eller annan skepnad ligger till grund för all modern vetenskap. Här går vi igenom bara några av dessa filosofiska överväganden.

Reduktionistisk tradition

En av de stora skillnaderna som ofta dras mellan österländsk filosofi och västerländsk filosofi är att de österländska filosoferna tenderade att förespråka idéer som gynnar holism medan de västerländska tänkarna tenderade att förespråka idéer som gynnar reduktionism . Denna distinktion mellan öst och väst är besläktad med andra filosofiska distinktioner (som realism vs anti-realism) . Några exempel på den österländska holistiska andan:

"Öppna din mun, öka dina aktiviteter, börja göra skillnader mellan saker, och du kommer att slita för evigt utan hopp." — The Tao Te Ching of Lao Tzu (Brian Browne Walker, översättare)
"Det är ett svårt jobb för [människor] att se innebörden av det faktum att allt, inklusive oss själva, beror på allt annat och inte har någon permanent självexistens." — Majjhima Nikaya (Anne Bankroft, översättare)
"Ett namn påtvingas vad som anses vara en sak eller ett tillstånd och detta skiljer det från andra saker och andra tillstånd. Men när du driver det som ligger bakom namnet, hittar du en större och större subtilitet som inte har några uppdelningar. ." — Visuddhi Magga (Anne Bankroft, översättare)

Den västerländska traditionen, från sitt ursprung bland de grekiska filosoferna , föredrog en position där korrekta distinktioner, uppdelningar och kontraster ansågs vara själva höjdpunkten av insikt. I den aristoteliska / porfyriska världsbilden, att kunna särskilja (via strikta bevis) vilka egenskaper hos en sak som representerar dess väsen kontra egendom vs. olycka vs definition , och i kraft av denna formella beskrivning att separera den entiteten till dess rätta plats i naturens taxonomy - detta var för att uppnå själva höjden av visdom.

Egenskaper för hierarki och modularitet

I naturliga eller artificiella system som kräver att komponenter integreras på något sätt, men där antalet komponenter överstiger vad som rimligen skulle kunna vara helt sammankopplade (på grund av kvadratisk ökning av antalet anslutningar (= n över två eller = n * (n - 1) / 2)), finner man ofta att en viss grad av hierarkitet måste användas i lösningen. De allmänna fördelarna med glesa hierarkiska system framför tätt sammankopplade system – och kvantitativa uppskattningar av dessa fördelar – presenteras av Resnikoff (1989) . I prosaiska termer är en hierarki "en samling av element som lagligen kombineras till komplexa helheter som för sina egenskaper beror på de av deras beståndsdelar", och där nyhet är "fundamentalt kombinatorisk, iterativ och transparent" (McGinn 1994 ) .

En viktig föreställning som alltid uppstår i samband med hierarkier är modularitet, vilket effektivt antyds av glesheten i samband i hierarkiska topologier. I fysiska system är en modul i allmänhet en uppsättning av interagerande komponenter som relaterar till den yttre världen via ett mycket begränsat gränssnitt, vilket döljer de flesta aspekter av dess interna struktur. Som ett resultat av detta skapar modifieringar som görs på insidan av en modul (för att exempelvis förbättra effektiviteten) inte nödvändigtvis en krusningseffekt genom resten av systemet ( Fodor 1983 ). Denna funktion gör effektiv användning av modularitet till en central del av all bra mjukvaru- och hårdvaruteknik.

Ofrånkomlighet av hierarki och modularitet

Det finns många övertygande argument angående förekomsten och nödvändigheten av hierarki/modularitet i naturen ( Koestler 1973 ). Simon (1996) påpekar att bland utvecklande system är det sannolikt bara de som klarar av att erhålla och sedan återanvända stabila underenheter (moduler) att kunna söka sig igenom fitnesslandskapet med en någorlunda snabb takt; sålunda hävdar Simon att "bland möjliga komplexa former är hierarkier de som har tid att utvecklas." Denna tankegång har lett till det ännu starkare påståendet att även om "vi inte vet vilka livsformer som har utvecklats på andra planeter i universum, ... kan vi säkert anta att "varhelst det finns liv måste det vara hierarkiskt organiserat '" ( Koestler 1967 ). Detta skulle vara ett lyckligt tillstånd eftersom förekomsten av enkla och isolerbara delsystem anses vara en förutsättning för framgångsrik vetenskap ( Fodor 1983) . Hur som helst tycks erfarenheten verkligen tyda på att mycket av världen har hierarkisk struktur.

Det har föreslagits att perception i sig är en process av hierarkisk nedbrytning ( Leyton 1992 ), och att fenomen som inte är väsentligen hierarkiska till sin natur kanske inte ens är "teoretiskt begripliga" för det mänskliga sinnet ( McGinn 1994 , Simon 1996 ). Med Simons ord,

Det faktum att många komplexa system har en nästan nedbrytbar, hierarkisk struktur är en stor underlättande faktor som gör det möjligt för oss att förstå, beskriva och till och med "se" sådana system och deras delar. Eller så kanske förslaget borde sättas åt andra hållet. Om det finns viktiga system i världen som är komplexa utan att vara hierarkiska, kan de i stor utsträckning undgå vår observation och förståelse. Analys av deras beteende skulle involvera så detaljerad kunskap och beräkningar av växelverkan mellan deras elementära delar att det skulle vara bortom vår kapacitet för minne eller beräkning.

Ansökningar

Praktiska tillämpningar av funktionell nedbrytning finns i Bayesianska nätverk , strukturell ekvationsmodellering , linjära system och databassystem .

Kunskapsrepresentation

Processer relaterade till funktionell nedbrytning är utbredd inom områdena kunskapsrepresentation och maskininlärning . Hierarkiska modellinduktionstekniker såsom logisk kretsminimering , beslutsträd , grammatisk slutledning , hierarkisk klustring och quadtree-nedbrytning är alla exempel på funktionsnedbrytning. En genomgång av andra tillämpningar och funktionsnedbrytning finns i Zupan et al. (1997) , som även presenterar metoder baserade på informationsteori och grafteori .

Många statistiska slutledningsmetoder kan ses som att implementera en funktionsnedbrytningsprocess i närvaro av brus; det vill säga där funktionella beroenden endast förväntas hålla ungefär . Bland sådana modeller finns blandningsmodeller och de nyligen populära metoderna som kallas "kausala nedbrytningar" eller Bayesianska nätverk .

Databasteori

Se databasnormalisering .

Maskininlärning

I praktiska vetenskapliga tillämpningar är det nästan aldrig möjligt att uppnå perfekt funktionell nedbrytning på grund av den otroliga komplexiteten hos systemen som studeras. Denna komplexitet manifesteras i närvaro av "brus", vilket bara är en beteckning för alla oönskade och ospårbara influenser på våra observationer.

Men medan perfekt funktionell nedbrytning vanligtvis är omöjlig, lever andan vidare i ett stort antal statistiska metoder som är utrustade för att hantera bullriga system. När ett naturligt eller artificiellt system är i sig är hierarkiskt, bör den gemensamma fördelningen på systemvariabler ge bevis på denna hierarkiska struktur. Uppgiften för en observatör som försöker förstå systemet är att härleda den hierarkiska strukturen från observationer av dessa variabler. Detta är tanken bakom den hierarkiska nedbrytningen av en gemensam fördelning, försöket att återställa något av den inneboende hierarkiska strukturen som genererade den gemensamma fördelningen.

Som ett exempel försöker Bayesianska nätverksmetoder att bryta ner en gemensam fördelning längs dess kausala förkastningslinjer och på så sätt "klippa naturen i dess sömmar". Den väsentliga motivationen bakom dessa metoder är återigen att inom de flesta system (naturliga eller artificiella) interagerar relativt få komponenter/händelser med varandra direkt på lika villkor ( Simon 1963 ). Snarare observerar man fickor av täta kopplingar (direkta interaktioner) bland små delmängder av komponenter, men bara lösa kopplingar mellan dessa tätt anslutna delmängder. Det finns alltså en föreställning om "kausal närhet" i fysiska system där variabler naturligt fälls ut i små kluster. Att identifiera dessa kluster och använda dem för att representera sammanfogningen ger grunden för stor effektivitet av lagring (i förhållande till den fullständiga gemensamma distributionen) såväl som för potenta slutledningsalgoritmer.

Mjukvaruarkitektur

Funktionell nedbrytning är en designmetod som avser att producera en icke-implementerad, arkitektonisk beskrivning av ett datorprogram. Istället för att gissa objekt och lägga till metoder till dem ( OOP ), med varje objekt som har för avsikt att fånga någon tjänst i programmet, etablerar mjukvaruarkitekten först en serie funktioner och typer som åstadkommer det huvudsakliga bearbetningsproblemet för datorprogrammet, dekomponerar var och en till avslöja vanliga funktioner och typer, och slutligen härleder moduler från denna aktivitet.

Till exempel kan utformningen av editorn Emacs initialt tänkas på i termer av funktioner:

${\displaystyle e\,\equiv {\text{tillståndet för Emacs-redigeraren och operativsystemet som körs}}} e$ ${\ displaystyle e'\,\equiv e{\text{ med någon komponent/del av dess tillstånd ändrad}}}$

$f:(e,lisp\,\,expression)\rightarrow e'$

Och en möjlig funktionsuppdelning av f :

$fromExpr:lisp\, \,expression\rightarrow {\begin{cases}objekt,&{\text{if success}}\\error,&{\text{if failure}}\end{cases}}$

$evaluate:(object,e)\rightarrow e'$

$print:(error,e)\rightarrow e'$

Detta leder en till den troliga modulen, tjänsten eller objektet för en tolk (som innehåller funktionen fromExpr ). Funktionsnedbrytning ger utan tvekan insikter om återanvändbarhet, till exempel om två funktioner under analysens gång producerar samma typ, är det troligt att en gemensam funktion/ övergripande oro finns i båda. Som kontrast, i OOP är det vanligt att anta moduler innan man överväger en sådan nedbrytning. Detta leder utan tvekan till kostsam omstrukturering senare. FD mildrar den risken till viss del. Vidare, utan tvekan, det som skiljer FD från andra designmetoder - är att det tillhandahåller ett kortfattat högnivåmedium av arkitektonisk diskurs som är från början till slut, avslöjar brister i uppströmskrav och på ett fördelaktigt sätt avslöjar fler designbeslut i förväg . Och slutligen är FD känt för att prioritera utveckling. Förmodligen, om FD är korrekt, identifieras de mest återanvändbara och kostnadsbestämda delarna av programmet långt tidigare i utvecklingscykeln.

Signalbehandling

Funktionell nedbrytning används i analysen av många signalbehandlingssystem , såsom LTI-system . Insignalen till ett LTI-system kan uttryckas som en funktion, $f(t)$ . Då $f(t)$ delas upp i en linjär kombination av andra funktioner, kallade komponentsignaler:

f(t)= a_{1}\cdot g_{1}(t)+a_{2}\cdot g_{2}(t)+a_{3}\cdot g_{3}(t)+\dots +a_{n}\ cdot g_{n}(t)

Här, $\{g_{1}(t),g_{2}(t), g_{3}(t),\dots ,g_{n}(t)\}$ är komponentsignalerna. Observera att $\{a_{1},a_{2},a_{3},\dots ,a_{n}\}$ är konstanter. Denna nedbrytning underlättar analysen, för nu kan systemets utdata uttryckas i termer av ingångens komponenter. Om vi låter $T\{\}$ representera effekten av systemet, så är utsignalen $T\{f(t)\}$ , vilket kan uttryckas som:

{\ displaystyle T\{f(t)\}=T\{a_{1}\cdot g_{1}(t)+a_{2}\cdot g_{2}(t)+a_{3}\cdot g_{ 3}(t)+\dots +a_{n}\cdot g_{n}(t)\}}

=a_{1}\cdot T\{g_{1}(t)\}+a_{ 2}\cdot T\{g_{2}(t)\}+a_{3}\cdot T\{g_{3}(t)\}+\dots +a_{n}\cdot T\{g_{ n}(t)\}

Med andra ord kan systemet ses som att det verkar separat på var och en av komponenterna i insignalen. Vanligt använda exempel på denna typ av nedbrytning är Fourierserien och Fouriertransformen .

Systemteknik

Funktionell nedbrytning i systemteknik hänvisar till processen att definiera ett system i funktionella termer, sedan definiera funktioner på lägre nivå och sekvensera relationer från dessa systemfunktioner på högre nivå. Grundidén är att försöka dela upp ett system på ett sådant sätt att varje block i ett blockschema kan beskrivas utan ett "och" eller "eller" i beskrivningen.

Denna övning tvingar varje del av systemet att ha en ren funktion . När ett system är designat som rena funktioner kan de återanvändas, eller bytas ut. En vanlig bieffekt är att gränssnitten mellan blocken blir enkla och generiska. Eftersom gränssnitten oftast blir enkla är det lättare att ersätta en ren funktion med en relaterad, liknande funktion.

Säg till exempel att man behöver göra en stereoanläggning . Man kan funktionellt bryta ner detta i högtalare , förstärkare , ett kassettdäck och en frontpanel. Senare, när en annan modell behöver en ljud- CD , kan den förmodligen passa samma gränssnitt.

Se även

Anteckningar

Fodor, Jerry (1983), The Modularity of Mind , Cambridge, Massachusetts: MIT Press

Koestler, Arthur (1967), The Ghost in the Machine , New York: Macmillan

Koestler, Athur (1973), "The tree and the candle", i Gray, William; Rizzo, Nicholas D. (red.), Unity Through Diversity: A Festschrift for Ludwig von Bertalanffy , New York: Gordon and Breach, s. 287–314

Leyton, Michael (1992), Symmetry, Causality, Mind , Cambridge, Massachusetts: MIT Press

McGinn, Colin (1994), "The Problem of Philosophy", Philosophical Studies , 76 (2–3): 133–156, doi : 10.1007/BF00989821 , S2CID 170454227

Resnikoff, Howard L. ( The 19 of89 ) Reality , New York: Springer

Simon, Herbert A. (1963), "Kausal ordning och identifierbarhet", i Ando, Albert; Fisher, Franklin M.; Simon, Herbert A. (red.), Essays on the Structure of Social Science Models , Cambridge , Massachusetts: MIT Press, s. 5–31 .
Simon, Herbert A. (1973), "Organisationen av komplexa system", i Pattee, Howard H. (red.), Hierarchy Theory: The Challenge of Complex Systems , New York : George Braziller, s. 3–27 .
Simon, Herbert A. (1996), "The architecture of complexity: Hierarchic systems", The sciences of the artificiell , Cambridge , Massachusetts: MIT Press, s. 183–216 .
Tonge, Fred M. (1969), "Hierarkiska aspekter av datorspråk", i Whyte, Lancelot Law; Wilson, Albert G.; Wilson, Donna (red.), Hierarchical Structures , New York : American Elsevier, s. 233–251 .
Zupan, Blaž; Bohanec, Marko; Bratko, Ivan; Demšar, Janez (1997), "Machine learning by function decomposition" , Proc. 14:e internationella konferensen om maskininlärning , Morgan Kaufmann, s. 421–429