Why is HV in IBEA?

Since the Indicator used in IBEA must be dominance preserving. IHD below is dominance preserving.

Defining orderly mutation

How it is done now (or so we thought!)

not_mutated = true          
while not_mutated:          
 for bit in variable:        
  if rand(0,1)<probability:          
   if deselecting root feature: 
    continue         
   else if selecting feature whose parent is not selected:
    continue
   else if deselecting feature that another selected feature requires:
    continue
   else if cardinality violation: 
    continue
   else:
    flip(bit)       
    not_mutated = false     
    if isSelected(bit):     
     reselect(bit.children) 
    else:
     deselect(bit.children) 

How it might be done otherwise:

not_mutated = true     
     
while not_mutated:
 traverseTree(root)
     
function traverseTree(node):
 if rand(0,1)<probability:          
  if deselecting root feature: 
   continue         
  else if selecting feature whose parent is not selected:
   continue
  else if deselecting feature that another selected feature requires:
   continue
  else if cardinality violation: 
   continue
  else:
   flip(node.bit)       
   not_mutated = false     
   if isSelected(node.bit):     
    reselect(node.children) 
   else:
    deselect(node.children)
 if isSelected(node):
  for child in node:
   traverseTree(child)

signal and the noise

The Signal and the Noise: 
Why So Many Predictions Fail-but Some Don't  
by Nate Silver

 

Permalink: http://amzn.com/159420411X

 

 

Chapter 2: foxes and hedgehogs

• Hedgehogs dig in- say one thing, only, all the time. Do best on the talk show circuit.
• Foxes, sniff around. Craftier.  Do best at prediction.

paper accepted with minor revisions to tse

Local vs. Global Lessons for Defect Prediction and Effort Estimation

Tim Menzies, Member, IEEE,
Andrew Butcher,
David Cok, Member, IEEE,
Andrian Marcus, Member, IEEE,
Lucas Layman,
Forrest Shull, Member, IEEE,
Burak Turhan, Member, IEEE,
Thomas Zimmermann

Abstract—Existing research is unclear on how to generate lessons learned for defect prediction and effort estimation. Should we seek lessons that are global to multiple projects, or just local to particular projects? This paper aims to comparatively evaluate local vs. global lessons learned for effort estimation and defect prediction. We applied automated clustering tools to effort and defect data sets from the PROMISE repository. Rule learners generated lessons learned from all the data, from local projects, or just from each cluster. The results indicate that the lessons learned after combining small parts of different data sources (i.e., the clusters) were superior to either generalizations formed over all the data or local lessons formed from particular projects. We conclude that when researchers attempt to draw lessons from some historical data source, they should (a) ignore any existing local divisions into multiple sources; (b) cluster across all available data; then (c) restrict the learning of lessons to the clusters from other sources that are nearest to the test data.

Download from http://unbox.org/stuff/var/11/gense/gense-v13.pdf

experiments with random projections

Vast literature on random projections: 

• http://www.cs.yale.edu/clique/resources/RandomProjectionMethod.pdf

Doing the simplest way possible...

Given best 3 (ish) random projections on the following data, then a 1-D rnn on each projection, how after are you someone else's nearest neighbor?

---| weather |-----------------------

0,    3,    21%,    *********************
1,    2,    14%,    **************
2,    6,    42%,    ******************************************
3,    1,     7%,    *******
4,    2,    14%,    **************

---| autompg |-----------------------

0,    5,      1%,    *
1,    40,    10%,    **********
2,    99,    24%,    ************************
3,    111,   27%,    ***************************
4,    105,   26%,    **************************
5,    31,     7%,    *******
6,    7,      1%,    *

---| china |-----------------------

0,    7,       1%,    *
1,    43,      8%,    ********
2,    131,    26%,    **************************
3,    156,    31%,    *******************************
4,    101,    20%,    ********************
5,    52,     10%,    **********
6,    9,       1%,    *

---| nasa93 |-----------------------

0,    5,     5%,    *****
1,    27,   29%,    *****************************
2,    34,   36%,    ************************************
3,    21,   22%,    **********************
4,    6,     6%,    ******

Tukutuku paper

The first set of corrections are here.
The second set of corrections are here.
The final version of the paper after these corrections are here.

we're achieving the ICSE'13 results in 7 minutes (as compared with 3 hours)... The only parameter that comes short is spread... but I'm sure we're still performing better than NSGA-II and SPEA2... We haven't yet run those with the new "orderly" mutation operator.

Profiling indicates that we're spending a long time (65%) evaluating the population before sorting and removing worst... This is done a 100 times for our size-100 population... I think if we remove the 5 worst individuals at once we'll be able to shave about half the execution time with little effect on the final results.

So we've got things to try:

1- run more feature models.

2- run more algorithms with orderly mutation.

3- shave time off of IBEA by removing 5 worst.

Metrics of Interest: Keeping Players in the Game

Period: A period of time (i.e. 1 day, 1 week, 1 month)

Retention: How many players are still playing in period i+1

Churn: 1 - Retention

Stickiness: [Users per Period] / [Users per next Largest Period].  i.e. DAU/MAU (daily vs monthly)

Viral Rate: New Unique User per period / Total Users per period

Research Objectives = 

 = Maximize Retention

 = Minimize Churn

 = Maximize Stickiness (shoot for 15-20%)

 = For every 1% increase in Churn, Want 2.3% increase in Viral Rate

 = = (reference)


--------------------------------------------
pom2 charts: http://i.imgur.com/LQxLw.png

Our Guest from China: Zhimin He

http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/h/He:Zhimin.html

Prediction Scientific Success

The following is bogus and stupid but oh my it will be visited by 1,000,000 deans:
http://klab.smpp.northwestern.edu/h-index.html

talks for promise

Top two talks: does size matter and learning to change projects.

Aptamer Deadend Estimation

Cluster A3 doubles from the initial round to round 3, indicating that the cluster is a likely candidate for Atrazine aptamers.

Where the clusters contain a combination of the following attributes:

The cluster A3 has all of the attributes in the A cluster as 1 for its centroid.

The concentration of cluster A3 in subsequent rounds varies in a manner that suggests that the system has reached a steady state.  The concentration in round 3 is a reasonable estimate for the final value reached in round 12.

If the concentration of cluster A3 at round 3 was used as an estimate for the concentration of the target cluster, then the non-target clusters, i.e. deadends, are illustrated by the grey section of the chart.  

The Bromacil experiment shows a similar trend, with an increase of 1 1/2 from the initial round to round 3.

The experiment is once again dominated by cluster A3.

The Cloud is Large

pom2:

http://i.imgur.com/IMzQj.png

games: 

http://aimazed2d-web-dev-env.elasticbeanstalk.com/

cloud pricing:

EC2 Service for Web Hosting a container for Game Applications

http://aws.amazon.com/ec2/pricing/

Cliff notes:

* ~ 10 cents per HOUR of CPU

* ~ 12 cents per GB of data transferred

RDS Service for Relational Database Storage

http://aws.amazon.com/rds/pricing/

Cliff notes:

* ~ 12 cents per GB of storage

Typically; standard projects can expect to pay ~72$/month.
Several high-end gaming companies use Amazon Web Services:http://aws.amazon.com/solutions/case-studies/

Joe Ingram's profiling

The two cases below are not exactly comparable, but the results are intuitive.

Original IBEA with FM43

IBEA with "good mutation"...

Mobile Phone Feature Model for Z3 (in Python)

from z3 import *

# All features are declared as Boolean variables
Mobile_Phone = Bool('Mobile_Phone')
Calls = Bool('Calls')
Screen = Bool('Screen')
GPS = Bool('GPS')
Media = Bool('Media')
Basic = Bool('Basic')
Color = Bool('Color')
High_res = Bool('High_res')
Camera = Bool('Camera')
MP3 = Bool('MP3')

s = Solver()

# Mandatory features; double implication
s.add( Mobile_Phone == Calls )
s.add( Mobile_Phone == Screen )

# Optional features; child implies parent
s.add( Implies (GPS,Mobile_Phone) )
s.add( Implies (Media,Mobile_Phone) )
s.add( Implies (Basic,Screen) )
s.add( Implies (Color,Screen) )
s.add( Implies (High_res,Screen) )
s.add( Implies (Camera,Media) )
s.add( Implies (MP3,Media) )

# [1,1] group
s.add( Or ( And(Basic,Not(Color),Not(High_res)) ,
And(Not(Basic),Color,Not(High_res)) ,
And(Not(Basic),Not(Color),High_res) ) )

# [1,*] group
s.add( Or (Camera,MP3) )

print s.check()
print s.model()

NEMS Graph

NEMS Graphs

Selex Experiment Questions

Questions for Drs. Sooter and Gannett

Predicting the Future of Predictive Modelling

by Tim Menzies

A discussion paper for AISE'12.

It is now well established that predictive models can be generated from the artifacts of software projects. So it is time to ask “what’s next?”.

 I suggest that predictive modelling tools can and should be refactored to address the near-term issue of decision systems and the long-term goal of social reasoning.

To download, right click and save to disk.

New TSE Experiment Results

Privacy and Utility results

pom2 & fun in games

pom2 graph: http://i.imgur.com/ffATu.png

Plans for fun games:
 - Prepare cog. tests: i.e. What dungeon parameters lead to highest user play time
 - Collect data: game dumps user data to server
 - - - Dungeon parameters used, total play time, explore ratios, speed of movement, items collected, etc
 - Analyze data: keys2?

Results - 27 Aug

Maze Game & Turing Test of AI

AiMazed2D Project (Java Jar download below):
https://sites.google.com/site/tanzastic/research/AiMazed2D.jar?attredirects=0&d=1

Tasks this week:
 1. Video record humans playing the game
 2. Video record AI playing the game
 3. Devise/research way to score results of formal turing test across gathered sample space from (1 & 2)

Tasks later down road:
 1. Improve score of turing test. (Study differences between humans and AI videos above)
 * Most prominently: humans have decision delays that must be imitated by the AI

Aptamer Predictions

Concentration Prediction Sample for Bromacil

Testing stability of FSS on NEMS dataset

Log_Aug_20

NSF Workshop: Planning Future Directions in Artificial Intelligence and Software Engineering (AISE'12)

NSF Workshop: Planning Future Directions in Artificial Intelligence and Software Engineering (AISE'12)

Tim Menzies, Rachel Harrison, Sol Greenspan

NSF is sponsoring a one-day workshop to consider how ideas and technologies from Artificial Intelligence (AI) can help achieve the goals of Software Engineering (SE). The purpose of the workshop is to gather researchers from both communities who have a common interest in leveraging AI research to advance SE. The converse -- improving SE for AI applications and systems -- is also in scope. The objective is to assemble a meeting of researchers from both communities to formulate a fruitful research agenda. After the workshop, the organizers will invite some attendees to co-author a report entitled Future Directions in Software Engineering and Artificial Intelligence Research.

Participation is by invitation only. Prospective participants should submit a research vision statement written from one or more of the following perspectives:

• Improving SE through AI -- including but not limited to knowledge acquisition / representation / reasoning, agents, machine learning, machine-human interaction, planning and search, natural language understanding, problem solving and decision-making, understanding and automation of human cognitive tasks, AI programming languages, reasoning about uncertainty, new logics, statistical reasoning, etc. 
• Applying AI to SE activities -- including but not limited to requirements, design, specification, traceability, program understanding, model-driven development, testing and quality assurance, domain-specific software engineering, adaptive systems, software evolution, etc. 
• SE for AI -- including but not limited to AI programming languages, program derivation techniques in AI domains, platforms and programmability, software architectures, rapid prototyping and scripting for AI techniques, software engineering infrastructure for reflective and self-sustaining systems, etc.

On the Value of User Preferences in Search-Based Software Engineering: A Case Study in Software Product Lines

On the Value of User Preferences in Search-Based Software Engineering: A Case Study in Software Product Lines

Abdel Salam Sayyad Tim Menzies Hany Ammar

Software design is a process of trading off competing objectives. If the user objective space is rich, then we use optimizers that can fully exploit that richness. For example, this study configures software product lines (expressed as feature maps) using various search-based software engineering methods. As we increase the number of optimization objectives, we find that methods in widespread use (e.g. NSGA-II, SPEA2) perform much worse than IBEA (Indicator-Based Evolutionary Algorithm). IBEA works best since it makes most use of user preference knowledge. Hence it does better on the standard measures (hypervolume and spread) but it also generates far more products with 0% violations of domain constraints. Our conclusion is that we need to change our methods for search-based software engineering- particularly when studying complex decision spaces.

Download

Better Cross Company Defect Prediction

Fayola Peters, Tim Menzies, Andrian Marcus Abstract— How can we find data for quality prediction? Early in the lifecycle, projects may lack the data needed to build such predictors. Prior work assumed that relevant training data was found nearest to the local project. But is this the best approach? This paper introduces the Peters filter that is based on the following conjecture. When local project data is scarce, there is more information in other projects than locally. Accordinging, this filter selects training data via the structure of the other projects. We tested the Peters filter on 21 small data set looking for training data in 35 larger data sets. In the majority case (67%), the Peters filter builds much better defect predictors that the current-state-of-the-art methods. Hence, we recommend the Peters filter for cross-company learning.


Download

Bromacil Cumulative Percentage by round

Atrazine Cumulative Percentage by round

Hmm, can you predict the cluster of the target?  Much simpler once the nearest neighbor heuristic was applied.

Erin Thurs 7-26

Worked example of Ordonez distance algorithm

Code snippet - shows code and marks the place where I have verified the algorithm

pseudoCode up to verified line

awk code where I'm hung up

must do: decide on a class the meets requirements, hard as there are very few open

Erin's To Dos

Ellington NN clustering, preliminary

Continue working on Binary Sparse NN implementation

  Think centroids need to be binary with stdDev instead of averages of the points.

  Nearly every instance is clustered, and the lack of StdDev cutoff is not identifying unknown instances

Double check methods to make sure they are working as I think they should

Start GRE studying - exam July 31

Schedule

Utility Results

Utility for 21 defect test data-set
and 8 defect train data-sets.

Raw and Summary Results

Raw Results

Summary Results

POM

POM Learner Results:

Software Project Performance Metrics: http://i.imgur.com/ERu9M.png

Learner Metrics: http://i.imgur.com/AJoq1.png

Cluster SA results

Results/Comparisons:
https://docs.google.com/document/d/1E0lwTCm-GDijJUjmfu_aA0EwuLCkm2B2rikJ2hoh-MM/edit

How to measure success/compare methods?
In the NSGA-II paper[1], there were two performance measures they used, neither were AUC.  Since these models were widely used, they used 500 known, evenly distributed, points on the Pareto to measure the average distance from each resultant point to the Pareto, which was the first metric.  The second metric was a measure of spread across the Pareto of the obtained solutions, calculated with a given algorithm.


REFERENCES:
[1] Kalyanmoy Deb, Associate Member, IEEE, Amrit Pratap, Sameer Agarwal, and T. Meyarivan,  A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002

FpFSS slides
Leverages Association Learning (FP Growth) and Clustering (EM) to create a predictive data model in an unclassified database where the number of rows and columns are similar. Model is then applied to a related time series database where cluster concentrations can be predicted for future time values.

Erin's To Dos

Local Cluster SA

Only SA for Constr (really bad):

[1] Baseline from NSGA-II for Constr:

SA on cluster for Constr(top: all points, bottom: only dominating):

Other runs for SA on cluster for Constr, only dominating:

Conclusion: Running SA with clusters was much MUCH better, but could use some improvement.  By limiting SA to within cluster we get points that aren't going to be on the pareto.

Up Next: DE



REFERENCES



[1] Kalyanmoy Deb, Associate Member, IEEE, Amrit Pratap, Sameer Agarwal, and T. Meyarivan,  A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II, IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002

POM

Todo List: https://docs.google.com/spreadsheet/ccc?key=0AolajDUgsGZ7dGF0Y2ppYk9XS0g5aTQ3bFRVbjRXSmc




POM: Portman Owens Menzies

What is it: A software project emulator model.  See how full projects which take 200 days or more complete in mere seconds in a model.  Can gather variety of statistics such as days to complete, money spent, and many more.  I've coded a version of it for use with a learner.

How it works: My POM model runs on Actory, which is a Finite State Machine of sorts, where each Team/Person in the development project is a different machine.  We also add a project manager, and an "assigner", who's job is to decide which task is best for the team/person.

Coded in: Python

Reason for Building POM: The transitions between machines in Actory have priorities.  The main goal of POM was to use a Learner (bore = best or the rest) to learn the best transition priorities in Actory.

Methodology for Learning: We run POM 1000 times to generate average statistics and then package them with the currently used (random) transition priorities.  This package gets sent to the learner, which spits out some data analysis on what the best transition priorities should be.  After learning the best transition priorities, we run POM again, 1000 times, and regenerate the statistics and compare them to see if any improvements were found.

Data Results: The five statistics used are as follows:
 - - - days = Days to Complete Project
 - - - s1 = Money per Day Spent
 - - - s2 = Money per LOC
 - - - s3 = Days per LOC
 - - - s4 = Average time spent IDLE for a team/person

Before learning:
 - - - days = 269
 - - - s1 = 1240
 - - - s2 = 10.25
 - - - s3 = 0.0083
 - - - s4 = 0.5004


After learning:

 - - - days = 268
 - - - s1 = 1242
 - - - s2 = 10.22
 - - - s3 = 0.0082
 - - - s4 = 0.4001

Brookes Law: Adding members to the project at a late phase in the game will only make it later.  We test this in POM by allowing team/persons to gain experience and become better coders the more they work on the project.  We test the effects and prove brookes law by running POM 35 times and gathering the number of days it takes, when team/persons can be added at different phases during the completion of the project.  The following chart depicts the results, and indicates a steady increase in the days when members can be added earlier in the development.

http://i.imgur.com/frqkH.png
Y Axis: Days
X Axis: (0 to 100%) Percent of the Project Completed (Teams/Persons can only be added to the project when it is this much complete)

Erin's updated to dos

Updated To Do

To-Do List:

• Summer Report 3: researching MOEA performance metrics, testing NIS active breeding pool updating, new performance metrics?
• Summer Report 4: researching nicheing techniques, testing new idea for nicheing technique against those in literature, new MOEA?
• Thesis: compiling summer research results into a thesis
• Paper? I'm pretty sure that my Non-dominated Insertion Sort will make MOEAs converge faster.  I think that the algorithm running times are worth publication on their own.  If it also accelerates convergence, I think the resulting algorithm could be called NSGA-III (or NISGA).
• Prepare for job hunt: After this, I'd like to prepare for getting a job.  I'd like to do some research that can relate to landing a data mining or game coding job.

Jared Update

**UPDATED**
Notes:
Dominance eastwest heuristic worked well
splitting while y decreasing was very prone to wacky results (some clusters of 10, some of 2)

next up:
reorganize and rethink code (very hard to SA on both models and real data as is)
get some/any pareto graph out for a model
DE & GA

Erin's update

To Dos
With paper details

Slope as Estimator of Cumulative Rule Percentages

These charts show the cumulative rule percentages for Atrazine and Bromacil.  There is a graph displaying all of the rules for both chemicals. The other graphs are an example of using the slope of the cumulative rule percentage to estimate the rule percentage in a later round of experimentation.  The 'A' rule set is used for both examples.

The example shows that the slope of the line in early rounds, 6 for Atrazine and 3 for Bromacil, provides a good estimate that could allow experimenters to jump forward in the aptamer discovery process by several rounds

Privacy Results

Enclave with 10 runs

Privacy with Public Data

To Dos

Vasil's To-Do list:

https://docs.google.com/document/d/1GXG14-n44l3we5wcfu_ViXWfQX6_-Q6bRaCabTA7ZWA

Jared To do

To do:

Easiest.

show perpendicular split in clustering graph (purely cosmetic)
Min and max on 1st pass
analyze non-numerical values
Dominance between eastwest heuristic
implement splitting while y is decreasing
SA on clusters
read in csv data files
get results on real data
get pareto frontier graphs
Code DE
Maybe try standard genetic algorithms
create baseline or benchmark to test against


Hardest

Jared Update

• Updated Models
• Plotting Models instead of random points
• Normalized data in table 0 to 1 for all dimensions

• Q's dealing with simulated annealing on clusters

update on recursive clustering

Whats different in the code:

• Cluster class, reorganized the code, now captures the points in each cluster
• changed for multidimension (hopefully)
• few more shortcuts in code
• clusters until root n (initial tests of "while y decreases" turned out bad)

Cluster:
[96, 5]
[88, 17]
[93, 24]
[63, 49]
[93, 52]
[97, 54]
Cluster: 
[71, 55]
[71, 57]
[93, 64]
[88, 68]
[92, 74]
Cluster:
[94, 2]
[83, 14]
[78, 14]
[62, 21]
[62, 34]
[59, 39]
Cluster:
[51, 34]
[51, 35]
[37, 28]
[30, 10]
[19, 26]
Cluster:
[18, 95]
[18, 85]
[32, 84]
[34, 64]
[41, 71]
[45, 55]
Cluster:
[61, 76]
[63, 75]
[70, 82]
[82, 88]
[82, 83]
Cluster:
[1, 20]
[2, 33]
[0, 37]
[2, 39]
[5, 41]
Cluster:
[19, 46]
[9, 49]
[7, 57]
[1, 61]
[1, 63]

Association Learning with FP-Tree/FP-Growth

FPGrowth algorithm introduction slides for learning on frequent patterns.
Another worked example.

Atrazine Target Rough Results

Rough tree on Atrazine Target (final selection round)
Created by using the FP-Tree prefix tree algorithm.  Not complete.

DNA Words, Atrazine Target Trends
Words that either increase or decrease during selection rounds.

Recursive Clustering Algorithm

Example 1

Example 2

Things to Note:

• Thickest blue line is first east-west, lines get thinner as the split recursively
• Implemented on 50 random points between (0, 0) and (100, 100)
• Set to 3 recursive splits (8 clusters of 6 or 7 points)

Things to Do:

• Ascii Tree of clusters
• Docs for program
• Implement w/ Models (should be very easy)
• Optimize for more than two dimensions
• Make decisions on most interesting clusters (genetic algorithm, differential evolution, or simulated annealing)
• Implement possible heuristics? 

Q's:

• To keep median point? As of right now it assigns to the higher upper half 
• Size of clusters to aim for? or number of times recursed?

Test Post

Jared Test Post