Transcript Applications : Fashion Design

Interactive Evolutionary Computation:
A Framework and Applications
November 10, 2009
Sung-Bae Cho
Dept. of Computer Science
Yonsei University
1
Agenda
• Overview
• Methodology
– IGA
– Knowledge-based encoding
– Partial evaluation based on clustering
– Direct manipulation of evolution with NK-landscape model
• Applications
– Media retrieval
– Media design
• Concluding remarks
2
Overview
Interactive Computational Intelligence
Interaction/Evolution
Human
Computer
Interface
User Modeling
(Efficiency)
(Emotion)
AI
(Soft Computing)
FL
3
GA
NN
Overview
Interactive Evolutionary Computation (IEC)
• Difficulty of optimization problems in interactive system
– Outputs must be subjectively evaluated (graphics or music)
• Definition
– Evolutionary computation that optimizes systems based on
subjective human evaluation
– Fitness function is replaced by a human user
My goal is …
Target system
f(p1,p2,…,pn)
Interactive
EC
4
System output
Subjective evaluation
From Takagi (2001)
Overview
Inherent Problems in IEC
• Human fatigue problem
– Common to all human-machine interaction systems
• IEC
– Acceleration of EC convergence with small population size and a
few generation numbers
– Usually within 10 or 20 search generations
• Limitation of the individuals simultaneously displayed on a
screen
• Limitation of the human capacity to memorize the timesequentially displayed individuals
• Requirement to minimize human fatigue
I’m
tired
5
Overview
Proposed Framework
Direct
Manipulation
Media Retrieval
& Design
Media Retrieval
& Design
IEC
IEC
Partial
Evaluation
Domain Knowledge
Conventional
6
Proposed
Methodology
Interactive Genetic Algorithm
7
Methodology
Knowledge-based Encoding
New Search Space
Removing impractical solutions
Effective
encoding?
Using partially known information
about the final solution
Domain Knowledge
Focusing on a specific search space
Encoding in a modular manner
Search Space
8
Methodology
Partial Evaluation based on Clustering
Issues  Clustering algorithm selection, Indirect fitness allocation strategy
9
Methodology
Direct Manipulation of Evolution
It is very similar
to the final
solution but a bit
different.
IGA
Direct Manipulation
Proof of usefulness of the direct manipulation  NK-landscape
10
Applications
Overview
Humanized Media Retrieval & Design
Media Retrieval
Image Retrieval
Video Retrieval
Music Retrieval
11
Media Design
Fashion Design
Flower Design
Intrusion Pattern
Design
Applications: Image Retrieval
Content-based Image Retrieval
• Keyword-based method
– Much time and labor to construct indexes in a large databases
– Performance decrease when index constructor and user have
different point of view
– Inherent difficulty to describe image as a keyword
• Content-based method
– Image contents as a set of features extracted from image
– Specifying queries using the features
12
Applications: Image Retrieval
Motivation
• Systems for content-based image retrieval
– QBIC (IBM, 1993)
– QVE (Hirata and Kato, 1993)
– Chabot (Berkeley, 1994)
• Needs for image retrieval based on human intuition
– Difficult to get perfect expression by queries
– Lack of expression capability
13
Applications: Image Retrieval
System Structure
14
Applications: Image Retrieval
Chromosome Structure
R
G
B
0
Original image
15
Transformed image
1
2
3
49 50
Chromosome
Applications: Image Retrieval
Convergence Test
• The case of gloomy image retrieval
Initial population
16
The 8th population
Applications: Image Retrieval
Subjective Test by Sheffe’s Method
Confidence interval
17
95%
99%
Applications: Video Retrieval
Motivation
• Evolution of computing technology (Huge computing storage,
networking)
– Necessary for management of video data transfer, processing
and retrieval
• Change of view point
– Query by keyword  Query by content  Difficult to represent
human’s semantic information
– Query by semantics
• Emotion-based retrieval
18
Applications: Video Retrieval
Hierarchical Structure of Video
19
Applications: Video Retrieval
System Architecture
20
Applications: Video Retrieval
Chromosome Structure
21
Applications: Video Retrieval
System Interface
22
Applications: Video Retrieval
User’s Satisfaction
23
Applications: Music Retrieval
Emotional Music Retrieval
• Music information retrieval  Immature field
• Query by singing
• Query by content
– Uploading pre-recording humming via web browser
– Typing the string to represent the melody contour
• Preprocessing
– Query by humming  transforms user’s humming into
symbolized representation
• Conventional music retrieval system
– Fast and effective extraction of musical patterns and
transformation of user’s humming into systematic notes
• Problem : User cannot remember some parts of melody
24
Applications: Music Retrieval
Power Spectrum Analysis
a : classic
b : jazz
c : rock
d : news channel
25
Applications: Music Retrieval
System Architecture
③ Retrieved music
IGA
:
④ User evaluates
the music retrieved
① Query
26
Music
Database
⑤ Generation of
new offspring
② Retrieval of music
by the query
Applications: Music Retrieval
Chromosome Structure
27
Applications: Music Retrieval
Convergence Test (1)
28
Applications: Music Retrieval
Convergence Test (2)
29
Applications : Fashion Design
Change of Consumer Economy
Manufacturer
Oriented
Before the Industrial Revolution :
Customers have few choices on buying their clothes
After the Industrial Revolution :
Customers can make their choices with very large variety
Consumer
Oriented
30
Near Future :
Customers can order and get clothes of their favorite design
Applications : Fashion Design
Need for Interactive System
• Almost all consumers are non-professional at design
• To make designers contact all consumers is not effective
• Need for the design system that can be used by non-professionals
31
Applications : Fashion Design
Fashion Design
• Definition
– To make a choice within various
styles that clothes can take
• Three shape parts of fashion design
– Silhouette
– Detail
– Trimming
32
Applications : Fashion Design
System Architecture
OpenGL Program
Models of
each part
Combine
Display
Decode
Interactive Genetic Algorithm
GA operation
33
Reproduce
User Fitness
Applications : Fashion Design
Knowledge-based Encoding
A
B
C
D
F
E
Total 23 bits
E : Skirt and waistline style(9)
A : Neck and body style(34) B : Color(8)
F : Color(8)
…
…
C : Arm and sleeve style(11) D : Color(8)
…
34
Search space size
=34*8*11*8*9*8
=1,880,064
Applications : Fashion Design
Direct Manipulation Interface
35
Applications : Fashion Design
Fitness Changes for Encoding Schemes
70
Average Fitness
60
50
40
30
20
Knowledge-based Encoding
10
Sequential Encoding
0
1
2
3
4
5
6
Generation
36
7
8
9
10
Applications : Fashion Design
Hypercube Analysis
1110
1110
No mapped
20
design
0111 pagoda
design
0111 pagoda
1111
0110 mutton
1111
0110 mutton
No mapped
20
60
No mapped
65
75
60
No mapped
65
75
1010 tucked
0010 flare
1010 tucked
0010 flare
0011 french
1011 no sleeves
0011 french
100
80
100
80
1011 no sleeves
DM
0101 melon
0101 melon
1101
1101
80
80
No mapped
No mapped
design
design
0001 china
0001 china
1100
35
85
85
design
50
No mapped
design
50
0100 mandarin
0100 mandarin
1001 tight
1001 tight
15
1000 poncho
One-Mutant Neighbors using Genetic Operator
37
1100
35
No mapped
45
0000 bishop
design
design
45
15
0000 bishop
1000 poncho
Shortest Path Using DM Method
Applications : Flower Design
Motivation
• Proposed Method
– Representation of knowledge-based genotype using the
structure of real flower
– Automatic generation of creatures
• Process
– Directed graph: Define the genotype of flower structure
– IGA: Evaluation of created individuals and automatic creation
– Math Engine: Representation of phenotype
• Objective
– Creation of character morphology similar to real flower
– Find optimal solution in small solution space using knowledgebased genotype representation such as directed graph
– Automatic creation of character using IGA
38
Applications : Flower Design
Related Works
• Tree, flower and feather modeling
– L-System
• Box-based artificial characters (Karl
Sims) evolution
– Graph model representation
• Golem
– Robotic form and controller
evolution
– Graph-based data structure
39
Applications : Flower Design
Overall Procedure
Create initial edges between nodes
Set dimension and color of each part
Set parameters of parts and edges
Create 3D world in simulation
Create rigid parts in genotype
Perform 3D rendering
Evaluate fitness of each individual
Satisfied individual ?
No
Selection
Crossover/Mutation
Create individuals of next generation
40
Yes
Stop
Applications : Flower Design
Chromosome Structure
41
Applications : Flower Design
Convergence Test
Fitness value
10
8
6
4
2
0
1
2
3
4
5
6
Generation
Average fitness value
42
7
8
9
Best fitness value
10
Applications : Flower Design
Subjective Test by Sheffe’s Method
99%
95%
-3
43
-2
-1
0
1
2
3
Applications : Intrusion Pattern Design
Motivation (1)
• Various intrusion detection systems
– For evaluating, IDS uses known intrusions
• Possibility of having different patterns within identical
intrusion type
• Difficult to detect transformed intrusions
• Problem
– For better evaluation, intrusion patterns are needed more
• Difficult to generate all possible proper intrusion patterns
manually
– Automatic generation is needed
44
Applications : Intrusion Pattern Design
Motivation (2)
• Evolutionary pattern generation
– Needs a variety of intrusion patterns
• It is possible to generate new patterns by combining
primitives
– Generation of transformed intrusion patterns using simple
genetic algorithm
• IGA-based intrusion pattern generation
– Difficult to estimate the fitness of patterns automatically
– Using interactive genetic algorithm for the evaluation of patterns
45
Applications : Intrusion Pattern Design
Method
• Intrusive behavior can be conducted in 5 steps
– Proposed by DARPA
– Possible path of U2R attacks
46
TRANSPORT
ENCODING
EXECUTION
ACTIONS
CLEAN UP
web download
archive
shell variables
change file
permissions
editor
octal character
shell script
display files
remove files
ftp
simple
encryption
encrypted
shell interaction
delete files
restore
permissions
mail
character
stuffing
generate chaft
output in bg
transfer files
edit audit logs
floopy
encoding
delayted
execution
alter files
Applications : Intrusion Pattern Design
System Architecture
Known
Intrusion Patterns
IGA
GA
Initial Population
Fitness
Evaluation
Generate
Audit Data
47
Intrusion
Patterns
000100.....
001100.....
Exploit
Code
Concluding Remarks
• Humanized CI framework using IEC
– Knowledge-based encoding
– Partial evaluation based on clustering
– Direct manipulation of evolution with NK-landscape
• Applications in media retrieval & design
– Image, video and music retrievals
– Fashion, flower and intrusion pattern designs
• Contribution of humanized CI to engineering fields
 Developing Emotional HC Interface by
Evolving models through Interaction with Humans
48