Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Complexity and Fragility?

Содержание

The popular media has given us three similar visions of our technological future
Complexity and Fragility?John DoyleControl and Dynamical SystemsBioEngineeringElectrical EngineeringCaltechwith Prajna, Papachristodoulou, and Parrilo The popular media has given us three similar visions Is there any hope? Is there any hope?What is the ultimate showstopper? Is there any hope?What is the ultimate showstopper? Is there any hope?What is the ultimate showstopper?We can make everything as Robust to uncertainty in environment and componentsEfficient use of scarce resources Scalable Robust EfficientScalableVerifiable with short proofsEngineering design objectives Want robustness & efficiency that is verifiably soMay require highly complex organization Threshold theoremsIID bit sourceErasureErasureError correcting codesE(latency)log(E(error))CodeDecodeThanks to Arum and Ben With feedbackIID bit sourceErasureE(latency)log(E(error))CodeDecodeZero error with bounded E(latency) Erasure With feedbackIID bit sourceErasureCodeDecodeZero error with bounded E(latency)! Danger: new fragilities!Erasure Two opposite views of complexityPhysics:Pattern formation by reaction/diffusionEdge-of-chaosOrder for freeSelf-organized criticalityPhase transitionsScale-free Two opposite views of lifePhysics:If you are dead, you are likely to NPP (Number partitioning problem)A “classic” NP complete problemThe “simplest” hard problem 501001502002503002468101214160Example 50100150200250300246810121416|77+65-62-59-31|= min=10max=294 = |77+65+62+59+31|140 = |77-65-62-59-31|0Scalable algorithms? 7765625931 62 59 31625931 31 123112593101234050100 59 3131311014212121 38020413921BranchandBound 012345678900.20.40.60.81 0.2116 0.1677 0.1358 0.1312 0.1307 0.1552 0.1479 0.1448 0.1216 0.1204 0.20900902553447 0.16372175132032 0.11474666241757 0.11060830317527 0.10264423321886 0.11874666798309 0.11211512926647 0.11169327453340 0.11095064177068 0.09412186438521 024681010-310-210-1100 0.16212567898594 0.14166406741328 0.13672813657519 0.13542304261100 0.11591869442981 010020030040050000.20.40.60.8SortedUnsortedn=10 010020030040050000.20.40.60.8Energy landscape Mertens, Derrida, Gross & Mezard, …Large statistical physics literature 024681010-310-210-1100n=10 024681010-3 Why should anyone care?Computational problems in biology and advanced technologies are even Toy problem:In general:Central computational problems in biology and advanced technologies can be 024681000.20.40.60.81n=10RobustnessComplexity Various levels of paranoiaexplicitly modeled uncertaintycheck for fragilities to model parameters RobustnessComplexitysimplehardrobustfragile☺☹☹In general RobustnessComplexitysimplehardrobustfragile☺☹☹☹What if robust systems are intrinsically hard to verify and understand?Nightmare? What if robust systems are intrinsically hard to verify and understand?Nightmare? Biology: 024681000.20.40.60.81n=10 024681000.20.40.60.81There exist example instances in all the regions permitted by the theorem. 024681010-310-210-1100semilogy024681000.20.40.60.81n=10 024681010-310-210-1100semilogyn=10Random problems are highly complex and extremely fragileRobust problems are rare and 024681010-310-210-1100Random problems are highly complex and extremely fragile.Robust problems are rare and RobustnessComplexityBiology and technologyPhysicssimplehardrobustfragile Random problemsRobust problemsRandom problems are hopelessly fragile, and it’s easy to show that: RobustnessComplexitysimplehardrobustfragile☺☹☹Avoiding the nightmare? ?If systems biology is here, it will fail. Avoiding the nightmare? ☺☹☹☺ Must decouple organizational and computational complexity Must explicitly NPcoNPHard ProblemsP“easy”HardComputational complexity NPcoNPPControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsHard Problems PControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithms Domain-specific assumptions Enormously successful Handcrafted theories Incompatible assumptions Tower of NPcoNPPControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsHard ProblemsInternet NPcoNPPControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsHard ProblemsBiologyInternet NPcoNPHard ProblemsControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsGoalGoalInternetBiologyUnifiedTheory “handcrafted” theories are special cases immediate improvements new questions and answers PControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithms The unifying language is (new) mathematics Tried to describe one NPcoNPPHard ProblemsControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsGoalGoalInternetBiologyUnifiedTheoryPedagogical strategy:Describe theorems on highly abstracted & simplified toy models
Слайды презентации

Слайд 2 The popular media has given us three similar

The popular media has given us three similar visions of our technological future

visions of our technological future

Слайд 3 Is there any hope?

Is there any hope?

Слайд 4 Is there any hope?
What is the ultimate showstopper?

Is there any hope?What is the ultimate showstopper?

Слайд 5 Is there any hope?
What is the ultimate showstopper?

Is there any hope?What is the ultimate showstopper?

Слайд 6 Is there any hope?
What is the ultimate showstopper?
We

Is there any hope?What is the ultimate showstopper?We can make everything

can make everything as robust and reliable as our

software!

Слайд 7 Robust to uncertainty in environment and components
Efficient use

Robust to uncertainty in environment and componentsEfficient use of scarce resources

of scarce resources
Scalable to large system sizes

(to do

this, it may be necessary to have high internal complexity (complicated),

but we want simple, robust, verifiable external behavior, so…)

Engineering design objectives

Слайд 8 Robust
Efficient
Scalable


Verifiable with short proofs
Engineering design objectives

Robust EfficientScalableVerifiable with short proofsEngineering design objectives

Слайд 9 Want robustness & efficiency that is verifiably so
May

Want robustness & efficiency that is verifiably soMay require highly complex

require highly complex organization and structure


Robustness, evolvability, and verifiability

are compatible
and
Tradeoff to some extent against efficiency, cost, complexity, etc.

Bottom line

Слайд 10 Threshold theorems
IID bit source
Erasure
Erasure
Error correcting codes
E(latency)
log(E(error))
Code
Decode
Thanks to Arum

Threshold theoremsIID bit sourceErasureErasureError correcting codesE(latency)log(E(error))CodeDecodeThanks to Arum and Ben

and Ben

Слайд 11

With feedback
IID bit source
Erasure
E(latency)
log(E(error))
Code
Decode


Zero error with bounded E(latency)

With feedbackIID bit sourceErasureE(latency)log(E(error))CodeDecodeZero error with bounded E(latency) Erasure


Erasure

Слайд 12

With feedback
IID bit source
Erasure
Code
Decode
Zero error with bounded E(latency)!

With feedbackIID bit sourceErasureCodeDecodeZero error with bounded E(latency)! Danger: new fragilities!Erasure


Danger: new fragilities!
Erasure

Слайд 13 Two opposite views of complexity
Physics:
Pattern formation by reaction/diffusion
Edge-of-chaos
Order

Two opposite views of complexityPhysics:Pattern formation by reaction/diffusionEdge-of-chaosOrder for freeSelf-organized criticalityPhase

for free
Self-organized criticality
Phase transitions
Scale-free networks
Equilibrium, linear
Nonlinearity & complexity as

exotica

Engineering:
Constraints
Tradeoffs
Structure
Organization
Optimality
Robustness/fragility
Verification
Far from equilibrium
Nonlinearity & complexity as tool

Слайд 14 Two opposite views of life
Physics:
If you are dead,

Two opposite views of lifePhysics:If you are dead, you are likely

you are likely to stay that way
Engineering:
If you are

alive, it is very easy to kill you

The bad news (unfortunately):
Robustness is less fungible with other features than you think.

The good news (hopefully):
If we can identify our fragilities, we can
verify that we are otherwise robust
and keep ourselves that way

Слайд 15 NPP (Number partitioning problem)
A “classic” NP complete problem
The

NPP (Number partitioning problem)A “classic” NP complete problemThe “simplest” hard problem

“simplest” hard problem

Слайд 16 50
100
150
200
250
300
2
4
6
8
10
12
14
16
0
Example

501001502002503002468101214160Example

Слайд 17 50
100
150
200
250
300

2
4
6
8
10
12
14
16
































|77+65-62-59-31|
= min=10
max=294 =
|77+65+62+59+31|
140 =
|77-65-62-59-31|
0
Scalable algorithms?

50100150200250300246810121416|77+65-62-59-31|= min=10max=294 = |77+65+62+59+31|140 = |77-65-62-59-31|0Scalable algorithms?

Слайд 18 77
65
62
59
31
62
59
31
62
59
31
31
12
31
12
59
31
0
1
2
3
4
0
50
100







59
31
31
31
10
142
12
121

7765625931 62 59 31625931 31 123112593101234050100 59 3131311014212121 38020413921BranchandBound

3
80
204
139
21

Branch
and
Bound

Слайд 19

0
1
2
3
4
5
6
7
8
9
0
0.2
0.4
0.6
0.8
1















0.2116
0.1677
0.1358

012345678900.20.40.60.81 0.2116 0.1677 0.1358 0.1312 0.1307 0.1079 0.0892 0.0259n=8

0.1312
0.1307
0.1079
0.0892
0.0259
n=8

Слайд 20 0.1552
0.1479
0.1448

0.1552 0.1479 0.1448 0.1216 0.1204 0.1044 0.0932 0.0848 0.0149 0.0129051010-210-1100n=10

0.1216
0.1204
0.1044
0.0932
0.0848

0.0149
0.0129



0

5

10

10

-2

10

-1

10

0




















n=10

Слайд 21 0.20900902553447
0.16372175132032
0.11474666241757

0.20900902553447 0.16372175132032 0.11474666241757 0.11060830317527 0.10264423321886 0.09262647734766 0.06575709562532 0.04944987218796 0.04533843900729 0.02356457821016 0.02025723346225 0.00227632849288n=12

0.11060830317527
0.10264423321886
0.09262647734766
0.06575709562532
0.04944987218796

0.04533843900729
0.02356457821016
0.02025723346225
0.00227632849288

n=12

Слайд 22 0.11874666798309
0.11211512926647
0.11169327453340

0.11874666798309 0.11211512926647 0.11169327453340 0.11095064177068 0.09412186438521 0.08685317462754 0.08118017281551 0.06766995122518 0.05718523360114 0.03754549903682

0.11095064177068
0.09412186438521
0.08685317462754
0.08118017281551
0.06766995122518

0.05718523360114
0.03754549903682
0.03586488042322
0.03254947795691
0.01521112174069
0.01506074475625
0.01423812298937
0.00901404288853

n=16

Why so hard?

Still exponentially bad.

Слайд 23 0
2
4
6
8
10
10
-3
10
-2
10
-1
10
0


















0.16212567898594
0.14166406741328
0.13672813657519

024681010-310-210-1100 0.16212567898594 0.14166406741328 0.13672813657519 0.13542304261100 0.11591869442981 0.11370146803691 0.06062893005904 0.05985800729769 0.04919688814988 0.02475508644126n=10

0.13542304261100
0.11591869442981
0.11370146803691
0.06062893005904
0.05985800729769

0.04919688814988
0.02475508644126

n=10

Слайд 24 0
100
200
300
400
500
0
0.2
0.4
0.6
0.8
Sorted




Unsorted
n=10

010020030040050000.20.40.60.8SortedUnsortedn=10

Слайд 25 0
100
200
300
400
500
0
0.2
0.4
0.6
0.8




Energy landscape

010020030040050000.20.40.60.8Energy landscape

Слайд 26 Mertens, Derrida, Gross & Mezard, …
Large statistical physics

Mertens, Derrida, Gross & Mezard, …Large statistical physics literature

literature

Слайд 27 0
2
4
6
8
10
10
-3
10
-2
10
-1
10
0

















n=10

024681010-310-210-1100n=10

Слайд 28 0
2
4
6
8
10
10
-3









024681010-3

Слайд 29 Why should anyone care?
Computational problems in biology and

Why should anyone care?Computational problems in biology and advanced technologies are

advanced technologies are even harder.
If we can’t do this

“simple” problem, what hope is there for scalability of computational methods to large networks?
Is there some other reason for optimism?

Слайд 30 Toy problem:
In general:
Central computational problems in biology and

Toy problem:In general:Central computational problems in biology and advanced technologies can

advanced technologies can be written this way and are

formally “hard” (NP/coNP hard or undecidable)

Слайд 31
0
2
4
6
8
10
0
0.2
0.4
0.6
0.8
1


















n=10
Robustness
Complexity

024681000.20.40.60.81n=10RobustnessComplexity

Слайд 32 Various levels of paranoia
explicitly modeled uncertainty

check for fragilities

Various levels of paranoiaexplicitly modeled uncertaintycheck for fragilities to model parameters

to model parameters

Слайд 33 Robustness
Complexity

simple
hard
robust
fragile
☺
☹
☹
In general

RobustnessComplexitysimplehardrobustfragile☺☹☹In general

Слайд 34 Robustness
Complexity

simple
hard
robust
fragile
☺
☹
☹
☹
What if robust systems are intrinsically hard to

RobustnessComplexitysimplehardrobustfragile☺☹☹☹What if robust systems are intrinsically hard to verify and understand?Nightmare?

verify and understand?
Nightmare?

Слайд 35 What if robust systems are intrinsically hard to

What if robust systems are intrinsically hard to verify and understand?Nightmare?

verify and understand?
Nightmare?
Biology: We might accumulate more complete

parts lists but never “understand” how it all works.
Technology: We might build increasingly complex and incomprehensible systems which will eventually fail completely yet cryptically.

Nothing in the orthodox views of complexity says this won’t happen (apparently).
Fortunately, there is some good news.
Illustrate the “good news” in our simple problem.

Слайд 36

0
2
4
6
8
10
0
0.2
0.4
0.6
0.8
1



















n=10

024681000.20.40.60.81n=10

Слайд 37

0
2
4
6
8
10
0
0.2
0.4
0.6
0.8
1

There exist example instances in all the regions

024681000.20.40.60.81There exist example instances in all the regions permitted by the theorem.

permitted by the theorem.

Слайд 38

0
2
4
6
8
10
10
-3
10
-2
10
-1
10
0



















semilogy



0
2
4
6
8
10
0
0.2
0.4
0.6
0.8
1



















n=10

024681010-310-210-1100semilogy024681000.20.40.60.81n=10

Слайд 39

0
2
4
6
8
10
10
-3
10
-2
10
-1
10
0



















semilogy

n=10
Random problems are highly complex and extremely fragile
Robust

024681010-310-210-1100semilogyn=10Random problems are highly complex and extremely fragileRobust problems are rare

problems are rare and highly structured
Computing is HARD at

phase boundaries.

Слайд 40

0
2
4
6
8
10
10
-3
10
-2
10
-1
10
0






Random problems are highly complex and extremely fragile.
Robust

024681010-310-210-1100Random problems are highly complex and extremely fragile.Robust problems are rare

problems are rare and highly structured
The most “interesting” problems

are on the boundary.

Слайд 41


Robustness
Complexity

Biology and technology

Physics
simple
hard
robust
fragile

RobustnessComplexityBiology and technologyPhysicssimplehardrobustfragile

Слайд 42

Слайд 43 Random problems
Robust problems
Random problems are hopelessly fragile, and

Random problemsRobust problemsRandom problems are hopelessly fragile, and it’s easy to show that:

it’s easy to show that:

Слайд 44

Robustness
Complexity
simple
hard
robust
fragile
☺
☹
☹
Avoiding the nightmare?
?
If systems biology is here,

RobustnessComplexitysimplehardrobustfragile☺☹☹Avoiding the nightmare? ?If systems biology is here, it will fail.

it will fail.

Слайд 45 Avoiding the nightmare?


☺
☹
☹
☺
Must decouple organizational and

Avoiding the nightmare? ☺☹☹☺ Must decouple organizational and computational complexity Must

computational complexity
Must explicitly exploit robustness/fragility in computation


Substantial recent progress
Small tip of a huge and growing iceberg, yet…
New approach in its infancy

Слайд 46




NP
coNP
Hard
Problems
P
“easy”
Hard
Computational complexity

NPcoNPHard ProblemsP“easy”HardComputational complexity

Слайд 47




NP
coNP
P
Controls
Communications
Economics
Dynamical Systems
Physics
Algorithms
Hard
Problems

NPcoNPPControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsHard Problems

Слайд 48
P
Controls
Communications
Economics
Dynamical Systems
Physics
Algorithms
Domain-specific assumptions
Enormously successful

Handcrafted theories

PControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithms Domain-specific assumptions Enormously successful Handcrafted theories Incompatible assumptions Tower

Incompatible assumptions

Tower of Babel where even experts cannot

communicate
“Unified theories” failed
New challenges unmet

Слайд 49




NP
coNP
P
Controls
Communications
Economics
Dynamical Systems
Physics
Algorithms
Hard
Problems
Internet

NPcoNPPControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsHard ProblemsInternet

Слайд 50




NP
coNP
P
Controls
Communications
Economics
Dynamical Systems
Physics
Algorithms
Hard
Problems
Biology
Internet

NPcoNPPControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsHard ProblemsBiologyInternet

Слайд 51




NP
coNP
Hard
Problems

Controls
Communications
Economics
Dynamical Systems
Physics
Algorithms
Goal
Goal
Internet
Biology

Unified
Theory
“handcrafted” theories are special cases

NPcoNPHard ProblemsControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithmsGoalGoalInternetBiologyUnifiedTheory “handcrafted” theories are special cases immediate improvements new questions and answers

immediate improvements
new questions and answers

Слайд 52
P
Controls
Communications
Economics
Dynamical Systems
Physics
Algorithms
The unifying language is (new) mathematics

PControlsCommunicationsEconomicsDynamical SystemsPhysicsAlgorithms The unifying language is (new) mathematics Tried to describe

Tried to describe one important idea using simplest example

and minimal math
Just the beginning, but promising foundation for ASE?

Internet

Biology

Challenge

  • Имя файла: complexity-and-fragility.pptx
  • Количество просмотров: 168
  • Количество скачиваний: 0
- Предыдущая До свидания, детский сад
Следующая - Экология оболочек Земли

Похожие презентации

Москва Москва 126
Places in London Places in London 142
Презентация с документальными фотографиями к учебному тексту Yungay earthquake к учебнику М. З. Биболетовои Enjoy English 8 класс Презентация с документальными фотографиями к учебному тексту Yungay earthquake к учебнику М. З. Биболетовои Enjoy English 8 класс 150
Презентация по английскому языку на тему: Московский кремль(10 класс) Презентация по английскому языку на тему: Московский кремль(10 класс) 145
Merry-Christmas Merry-Christmas 188
Македония Македония 129
Les portraits des monstres Les portraits des monstres 147
TENSES IN ENGLISH TENSES IN ENGLISH 148
Презентация по английскому языку на тему: Обычаи и традиции Презентация по английскому языку на тему: Обычаи и традиции 100
Анализ УМК Spotlight 5 Анализ УМК Spotlight 5 390
Викторина По волнам английского языка 2 класс презентация к уроку по иностранному языку (2 класс) по теме Викторина По волнам английского языка 2 класс презентация к уроку по иностранному языку (2 класс) по теме 155
Scotland Scotland 139
Остров Сокровищ. Р.Л. Стивенсон Презентация. глава 5 Остров Сокровищ. Р.Л. Стивенсон Презентация. глава 5 158
London Overview London Overview 131
The eleventh of October Tuesday The eleventh of October Tuesday 158
Презентация по английскому языку на тему Animal world in Kazakhstan Презентация по английскому языку на тему Animal world in Kazakhstan 145
Презентация по английскому языку Американские президенты (6 класс) Презентация по английскому языку Американские президенты (6 класс) 174
Презентация по английскому языку на тему Глазго, к учебнику 5 класса из линии УМК О. В. Афанасьевой, И. В. Михеевой. Rainbow English Презентация по английскому языку на тему Глазго, к учебнику 5 класса из линии УМК О. В. Афанасьевой, И. В. Михеевой. Rainbow English 156
School subjects School subjects 169
Легенда о дружбе Легенда о дружбе 129
Презентация к уроку английского языка на тему Present Simple Презентация к уроку английского языка на тему Present Simple 145
Презентация к уроку на развитие навыка письменной речи по английскому языку на тему Description of a Criminal Презентация к уроку на развитие навыка письменной речи по английскому языку на тему Description of a Criminal 153
Welcome to DisneyLand Welcome to DisneyLand 156
Презентация по английскому языку на тему Притяжательный падеж Презентация по английскому языку на тему Притяжательный падеж 133
Презентация по английскому языку на тему Притяжательный падеж в английском языке-Possessive Case (2 класс) Презентация по английскому языку на тему Притяжательный падеж в английском языке-Possessive Case (2 класс) 162
Transportation and giving directions Transportation and giving directions 157
fg fg 165
Sport and physical culture are secrets of longevity Sport and physical culture are secrets of longevity 140
Разработка урока по английскому языку для 9 кл. Разработка урока по английскому языку для 9 кл. 166
Загадки о животных презентация к уроку по иностранному языку (2 класс) по теме Загадки о животных презентация к уроку по иностранному языку (2 класс) по теме 151