When all predictors seem uncorrelated with the response variable, then what's the next step to build predictive model? When the data set contains many predictors (and most of the predictors are categorical variable), and the correlation matrix shows that none of those predictors have high correlation with the response variables, then what should be the next step to go for building a predictive model? This is a real problem I am facing. The maximum correlation between a predictor and the response variable is 0.001. Note that correlation only measures the linear relationship between 2 random variables. This means, even if none of the predictors seems correlated with the response variable, this does not necessarily mean that those predictors are independent of the response variable. May be there are complex non-linear relationship, which is usually the case.
I've asked a professor, who suggested that first do PCA on the set of predictors. But I think the idea of PCA is just change a different coordinate system to express the same set of predictors. Then if the set of predictors seem uncorrelated with the response variable, then why after changing the coordinate system, the same set of predictors will start to be correlated with the response variable? Also, the result of PCA is a linear combination of the original set of predictors, then if the original set of predictors are uncorrelated with the response variable, then why it's linear combination will be correlated with the response variable? I couldn't understand this point intuitively. Can someone provide an example? 
Also, in my situation, most of the predictors are categorical variables, then I am not sure whether it make sense to do PCA, although you can always do PCA.
 A: It's possible that for any given predictor there is no significant difference in the response between predictor values, but that there is a difference between combinations of predictors.
Here's an example from a taste-test I conducted looking at the effects from two ingredients in a recipe for cookies, each with two levels: sugar (brown vs. white) and fat (butter vs. shortening). As it turned out, the combinations (brown sugar + shorting) and (white sugar + butter) both scored high on the taste test while (brown sugar + butter) and (white sugar + shortening) both scored low. As a result, there wasn't an overall effect for white vs brown sugar or for shortening vs butter.
The result is that if you considered a model with only first order terms like
$E[Y]=\alpha+\beta_1(fat)+\beta_2(sugar)$
neither predictor was significant. But including the interaction term
$E[Y]=\alpha+\beta_1(fat)+\beta_2(sugar)+\beta_3(fat*sugar)$
we found $\beta_3$ to be significant. I'd try adding interactions terms to you're model. PCA can help if you have many redundant predictors and need to reduce the dimensionality of the predictor space, but that doesn't sound like the main issue in your case.
