Modeling Ultra-high Dimensional Feature Selection as a Slow Intelligence System
Final Report
CS 2650 Project
Yingze Wang
()
This final reportdiscusses CS 2650 Project.The topic is modeling Ultra-high dimensional feature selection as a slow intelligence system. The report is organized as follows. In Section one, I will give a brief introduction about the problem definition and related work. In Section two, workflow diagrams are shown to indicate the modeling of system, which contain one main system and additional sub system. In Section three, the Petri Nets model build by ReNew and PIPE2 are shown. In Section four, the implementation of Petri Net for Time Controller is present.
1. Problem Definition
UltraHigh-dimensional variable selection is a hot topic in statistics and machine learning.The problem can be defined as modeling relationship between one response Y and associated featuresX1,...Xp, based on a sample of size n. It has wide application in different areas, for example gene selection or disease classification in bioinformatics in Fig 1.
Fig 1 gene selection
The recent algorithms like LASSO, forward regression, backward regression and etc, can deal with moderate scale data, but perform poorly even cannot handle with the ultrahigh dimensional data.In [1], the paper proposed an effective method to learn relationship between features and response in Ultrahigh dimension.This method is more accurate than other state-of-art works although it is not very fast. Motivated by [2], I will use the slow intelligence system proposed by [3] to model this method as well as introducing the new time controller and knowledge base.
Thus the project contains three main task. Firstly, I will model Ultra-high Dimensional Feature Selection as a Slow Intelligence System in mathematical way. Second, I will design the time controller and the Knowledge Base which make SIS approach different from other evolutionary approaches. A sophisticated Time Controller has two states (or module). In each different state, a different decision cycle can be invoked. Thirdly, I will use the Petri Net tools ReNew and PIPE2 to model the whole SIS system and Time Controller. Moreover I will use Xu Wen’s module to test the PetriNet.
2. Workflow Diagram
2.1 Main System
The main system contains five phases of slow intelligence system:
Enumeration:Enumerate number of |P| gene features X1,...Xp.
Eliminator: Compute Pearson correlation between each features Xj and response Y. Rj=Pearson(Y, Xj). Then rank Rj, eliminate the last |P|-|Ai| genes (|Ai|=constant). Select the subset Ai gene features with the largest values Rj.
Adaptation: For other features in subsetof features , adding one feature each time with to the regression model, compute the .
Concentrator: ranking , select the number of |Ai|-|Mi| features with smallest .
Propagator: add these features to Mi to form new Ai set of features. Then i=i+1.
Fig 2. Workflow diagram for Main system
In this diagram, the TC Main phase means main time controller which controls the termination of whole process. When main time controller set a threshold D, then it checks whether the total number of cycles are larger than threshold. If yes, then it stops the process and output the feature selection result. If the main time controller doesn’t start, then the process should check whether the current result is the same as the last cycle. If yes, the process will also stop.
2.2Sub Slow Intelligence System
The sub system concentrated on using the existing moderate scale feature selection algorithms to pick up the features from the smaller set Ai. It contains three phases of SIS and one Knowledge Base with a simple Sub Time Controller.
Enumeration: Inquire KB where stores the different moderate-scale algorithms, LASSO, Forward regression and Backward Regression and etc. Then enumerate these different algorithms and use them to compute Mi set of features respectively.
Concentrator: select the best algorithm’s result based on:
Eliminator: Eliminate the worse algorithm depending on its performance rate and update the KB.
Sub Time Controller: Panic Button to evoke the Eliminator.
Fig 3. Workflow diagram for Sub system
2.3Whole SIS System
The whole system workflow diagram is shown below:
Fig 4 workflow diagram for whole system
3Petri Net Model
3.1 Whole System
In order to show the modeling of this system, I use the ReNew tool to draw the Petri Net. ReNew is a very powerful software for modeling PetriNet because it can contain predicator. Also, the reference nets support method innovations using java language. I write some simple java code on the PetriNet to make it simulate the real system.
Fig 5. Petri Net for whole system
The gray sections indicate the sub time controller module and main time controller module. You can see from the net that “guard Mi = Mj”, then the process will output result and end. If “guard Mi !=Mj”, then the process will continue the next loop again. In ReNew, keyword “guard” is the predicator which can check the conditions.
3.2 Time controller design
There are two time controllers in the system. They cannot work synchronously. In other word, when the main time controller is working, the sub time controller cannot work at the same time. The Sub Time controller’s task is evoking the eliminator to eliminate some algorithms and update KB. Thus this can be modeled like a simple Panic Button. A more sophisticated Main Time Controller’s task is setting a threshold, and checking the loop condition. Thus we can represent these two controllers in one PetriNet. Motivated by mutual exclusive event in Operating System, a critical section is introduced in this Petrinet. When one controller occupies the critical section, the other one cannot access it but just wait. The sequence of these two controllers can be defined as different state of token markings in Petrinet.Petri Net modeled by PIPE2 is shown in Fig 6. In this figure, there are places of waiting, requesting, and having tokens, not having tokens and entering critical section for Sub and Main time controller respectively. These indicate the state of two mutual exclusive events.
Fig6. Petri Net for Time Controller
4. Implementation of Petri Net
In order to test the Petri Net for Time Controller, I use the Xu Wen’s software to implement this Petri Net. I write two dummy components for Sub Time Controller and Main Time Controller. Two experiments are running to test the Petri Net.
Case one:Initially, Sub time controller has the token, but Main one doesn’t have token, as Fig 6 marking state. Sub time controller request entering critical section first, then Main time controller request later. So Main one cannot enter critical section until sub one finishes job and free the critical section. The output of implementation is shown in Fig 7. And the sequence of Petrinet transition fired is shown in Fig 8.
Fig 7. Output of the implementation for case one
Fig 8. Trace of Petri Net simulation results for case one
Case two: Initially, Main time controller has the token, but Sub one doesn’t have token, as Fig 9 marking state. It is different from the marking state in Fig 6. Main time controller request entering critical section first, then Sub time controller request later. So Sub one cannot enter critical section until Main one finishes job and free the critical section. The output of implementation is shown in Fig 10. And the sequence of Petrinet transition fired is shown in Fig 11.
Fig 9. PetriNet for case two
Fig 10 Output of the implementation for case two
Fig 11. Trace of Petri Net simulation results for case two
5. Conclusion
This project use slow intelligence system structure to model Ultra-high dimensional feature selection algorithm. Petri Net model of whole system and time controller are built by ReNew and PIPE2. Also, time controller PetriNet is implemented by using Xu Wen’s simulation tool.
In the future, I will use some real data and syntheticdata to do the experiment and compare the results with some existingfeature selection method like LASSO, forward, backward regression, etc.Moreover, I will use some visualization tool to visualize the result andthe process of feature selection.
Appendix:
This is the checklist of all files submitted in the Final project_Wang.zip.
whole system.rnw: Petrinet model for whole system built in ReNew
Petrinet_TC_Caseone.html: Petrinet model for Time Controller for case one built in
PIPE2
Petrinet_TC_Casetwo.html: Petrinet model for Time Controller for case two built in
PIPE2
CreateTCMain.html: Create Msg20 for TCMain used in SIS server
CreateTCSub.html: Create Msg20 for TCSub used in SIS server
TCMain.java: java code for dummy main time controller
TCSub.java: java code for dummy sub time controller
freeMain.java: java code for main time controller free the critical section
freeSub.java: java code for sub time controller free the critical section
waitMain.java: java code for main time controller waiting the critical section
waitSub.java: java code for sub time controller waiting the critical section
manualMain.java: java code for main time controller requesting the critical section
manualSub.java: java code for sub time controller requesting the critical section
Reference:
[1] “Ultrahigh dimensional feature selection: beyond the linear model”,
Jianqing Fan, Richard Samworth and Yichao Wu
[2] “A General Framework for slow intelligence systems”, Shi-Kuo Chang
[3]”Modeling Human Intelligence as A Slow Intelligence System” , Tiansi Dong
[4] “Petri Net Theory and The Modeling of System” James L.Peterson.